Variance and covariance of distributions on graphs

DOI10.1137/20M1361328MaRDI QIDQ5075836zbMATH OpenOpenAlexFDO

Authors Karel Devriendt, Samuel Martin-Gutierrez, Renaud Lambiotte

Publication date 12 May 2022

Published in SIAM Review (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• GitHub
• KONECT

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)