Tracking network dynamics: a survey using graph distances
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 2089760 (Why is no real title available?)
- A survey of statistical network models
- Comparison of graphs by their number of spanning trees
- Graph Wavelets for Multiscale Community Mining
- Graph kernels
- Graph similarity scoring and matching
- Spectral classes of regular, random, and empirical graphs
- Spectral plot properties: towards a qualitative classification of networks
- Spectral recognition of graphs
- The resistance perturbation distance: a metric for the analysis of dynamic networks
- The spectrum of the graph Laplacian as a tool for analyzing structure and evolution of networks
- Transformations of a graph increasing its Laplacian polynomial and number of spanning trees
- Vertex-frequency analysis on graphs
- Wavelets on graphs via spectral graph theory
Cited in
(19)- Model-based clustering of multiple networks with a hierarchical algorithm
- Generalized correlation dimension and heterogeneity of network spaces
- A measure of dissimilarity between diffusive processes on networks
- Nonlinear correlation analysis of time series based on complex network similarity
- The many faces of graph dynamics
- On network similarities and their applications
- Improved methods to compare distance metrics in networks using uniform random spanning trees (DIMECOST)
- Bayesian classification, anomaly detection, and survival analysis using network inputs with application to the microbiome
- Modeling Network Populations via Graph Distances
- Differentiate data by higher-order structures
- Graph-Adaptive Semi-Supervised Tracking of Dynamic Processes Over Switching Network Modes
- Network comparison and the within-ensemble graph distance
- Distance Queries in Large-Scale Fully Dynamic Complex Networks
- Tracking Dynamic Point Processes on Networks
- Network distances for weighted digraphs
- Tracking a Markov-Modulated Stationary Degree Distribution of a Dynamic Random Graph
- Applying correlation dimension to the analysis of the evolution of network structure
- Hurst analysis of dynamic networks
- Communication network dynamics in a large organizational hierarchy
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)
