2022/05/01 by Karel Devriendt, Samuel Martin-Gutierrez, Samuel Martín-Gutíerrez +1 · 25 citations
Computer Science · Mathematics · Physics and Astronomy · #Applied mathematics #Combinatorics #Complex Network Analysis Techniques #Computer science #Covariance #Data mining #Discrete mathematics #Graph #Graph theory #Graph theory and applications #Mathematics #Measure (data warehouse) #Random graph #Statistics #Topological and Geometric Data Analysis #Variance (accounting)
paper · doi:10.1137/20m1361328
published in SIAM Review 64(2), 343-359 (Society for Industrial and Applied Mathematics)
openalex publication_date 2022/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 we 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.