Variance and covariance of distributions on graphs

DOI10.1137/20M1361328zbMATH Open1489.05152arXiv2008.09155OpenAlexW3080801325MaRDI QIDQ5075836FDOQ5075836

Authors: Karel Devriendt, Samuel Martin-Gutierrez, Renaud Lambiotte 

Publication date: 12 May 2022

Published in: SIAM Review (Search for Journal in Brave)

Abstract: We develop a theory to measure the variance and covariance of probability distributions defined on the nodes of a graph, which takes into account the distance between nodes. Our approach generalizes the usual (co)variance to the setting of weighted graphs and retains many of its intuitive and desired properties. Interestingly, we find that a number of famous concepts in graph theory and network science can be reinterpreted in this setting as variances and covariances of particular distributions. As a particular application, we define the maximum variance problem on graphs with respect to the effective resistance distance, and characterize the solutions to this problem both numerically and theoretically. We show how the maximum variance distribution is concentrated on the boundary of the graph, and illustrate this in the case of random geometric graphs. Our theoretical results are supported by a number of experiments on a network of mathematical concepts, where we use the variance and covariance as analytical tools to study the (co-)occurrence of concepts in scientific papers with respect to the (network) relations between these concepts.

Full work available at URL: https://arxiv.org/abs/2008.09155

Recommendations

• Isotropic covariance functions on graphs and their edges
• Covariance and correlation measures on a graph in a generalized bag-of-paths formalism
• Variable neighborhood search for extremal graphs. 12. A note on the variance of bounded degrees in graphs.
• Graphs with large variance.
• Centrality measure in graphs

zbMATH Keywords

network analysisgeometric networkeffective resistanceWikipedia networkdiversity measurevariance and covariancebibliographic network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial probability (60C05) Distance in graphs (05C12) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Title not available (Why is that?)
• Random Geometric Graphs
• On the resistance matrix of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphs and matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite metric spaces of strictly negative type
• On a quadratic programming problem involving distances in trees
• Average distance in weighted graphs
• Minimizing Effective Resistance of a Graph
• Effective graph resistance
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Networks
• Effective resistance is more than distance: Laplacians, simplices and the Schur complement
• Generalization of a fundamental matrix
• \(k\)-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases
• Hitting and commute times in large random neighborhood graphs
• Kemeny's constant and the effective graph resistance
• Entropy and diversity. The axiomatic approach
• On solving a non-convex quadratic programming problem involving resistance distances in graphs

Cited In (3)

• Isotropic covariance functions on graphs and their edges
• Covariance and correlation measures on a graph in a generalized bag-of-paths formalism
• \(k\)-variance: a clustered notion of variance

Uses Software

• KONECT
• GitHub

This page was built for publication: Variance and covariance of distributions on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075836)