Tracking network dynamics: a survey using graph distances

DOI10.1214/18-AOAS1176zbMATH Open1405.62171arXiv1801.07351OpenAlexW2884041582WikidataQ129462701 ScholiaQ129462701MaRDI QIDQ1624818FDOQ1624818

Authors: Claire Donnat, Susan Holmes 

Publication date: 16 November 2018

Published in: The Annals of Applied Statistics (Search for Journal in Brave)

Abstract: From longitudinal biomedical studies to social networks, graphs have emerged as a powerful framework for describing evolving interactions between agents in complex systems. In such studies, after pre-processing, the data can be represented by a set of graphs, each representing a system's state at different points in time. The analysis of the system's dynamics depends on the selection of the appropriate analytical tools. After characterizing similarities between states, a critical step lies in the choice of a distance between graphs capable of reflecting such similarities. While the literature offers a number of distances that one could a priori choose from, their properties have been little investigated and no guidelines regarding the choice of such a distance have yet been provided. In particular, most graph distances consider that the nodes are exchangeable and do not take into account node identities. Accounting for the alignment of the graphs enables us to enhance these distances' sensitivity to perturbations in the network and detect important changes in graph dynamics. Thus the selection of an adequate metric is a decisive --yet delicate--practical matter. In the spirit of Goldenberg, Zheng and Fienberg's seminal 2009 review, the purpose of this article is to provide an overview of commonly-used graph distances and an explicit characterization of the structural changes that they are best able to capture. We use as a guiding thread to our discussion the application of these distances to the analysis of both a longitudinal microbiome dataset and a brain fMRI study. We show examples of using permutation tests to detect the effect of covariates on the graphs' variability. Synthetic examples provide intuition as to the qualities and drawbacks of the different distances. Above all, we provide some guidance for choosing one distance over another in certain types of applications.

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

Recommendations

• The many faces of graph dynamics
• The resistance perturbation distance: a metric for the analysis of dynamic networks
• Network comparison and the within-ensemble graph distance
• A graph-theoretic approach to enterprise network dynamics.
• Spectral distances on graphs

zbMATH Keywords

waveletsmicrobiometemporal networksgraph distanceslongitudinal analysisgraph signal processing

Mathematics Subject Classification ID

Applications of statistics to biology and medical sciences; meta analysis (62P10) Applications of graph theory (05C90) Research exposition (monographs, survey articles) pertaining to statistics (62-02) Distance in graphs (05C12)

Cites Work

• Graph Wavelets for Multiscale Community Mining
• A survey of statistical network models
• Wavelets on graphs via spectral graph theory
• Graph kernels
• Comparison of graphs by their number of spanning trees
• Transformations of a graph increasing its Laplacian polynomial and number of spanning trees
• Graph similarity scoring and matching
• Spectral plot properties: towards a qualitative classification of networks
• The spectrum of the graph Laplacian as a tool for analyzing structure and evolution of networks
• Title not available (Why is that?)
• Vertex-frequency analysis on graphs
• Spectral classes of regular, random, and empirical graphs
• The resistance perturbation distance: a metric for the analysis of dynamic networks
• Spectral recognition of graphs

Cited In (19)

• Hurst analysis of dynamic networks
• Graph-Adaptive Semi-Supervised Tracking of Dynamic Processes Over Switching Network Modes
• Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph
• Network distances for weighted digraphs
• Modeling Network Populations via Graph Distances
• Applying correlation dimension to the analysis of the evolution of network structure
• The many faces of graph dynamics
• Tracking Dynamic Point Processes on Networks
• A measure of dissimilarity between diffusive processes on networks
• Nonlinear correlation analysis of time series based on complex network similarity
• On network similarities and their applications
• Model-based clustering of multiple networks with a hierarchical algorithm
• Improved methods to compare distance metrics in networks using uniform random spanning trees (DIMECOST)
• Network comparison and the within-ensemble graph distance
• Bayesian classification, anomaly detection, and survival analysis using network inputs with application to the microbiome
• Communication network dynamics in a large organizational hierarchy
• Distance Queries in Large-Scale Fully Dynamic Complex Networks
• Differentiate data by higher-order structures
• Generalized correlation dimension and heterogeneity of network spaces

This page was built for publication: Tracking network dynamics: a survey using graph distances

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