Paper Info
Title
Tracking Network Dynamics: a review of distances and similarity metrics.
Abstract
From longitudinal biomedical studies to social networks, graphs have emerged as a powerful framework for describing evolving interactions between agents in complex systems. such studies, the data typically consists of a set of graphs representing a systemu0027s state at different points in time or space. The analysis of the systemu0027s dynamics depends on the selection of the appropriate tools. particular, after specifying properties characterizing similarities between states, a critical step lies in the choice of a distance 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. However, these distancesu0027 sensitivity to perturbations in the networku0027s structure and their ability to identify important changes are crucial to the analysis, making the selection of an adequate metric a decisive -- yet delicate -- practical matter. In the spirit of Goldenberg, Zheng and Fienbergu0027s 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. To see how this translates in real-life situations, we use as a guiding thread to our discussion the application of these distances to the analysis a longitudinal microbiome study -- as well as on synthetic examples. Having unveiled some of traditional distancesu0027 shortcomings, we also suggest alternative similarity metrics and highlight their relative advantages in specific analysis scenarios. Above all, we provide some guidance for choosing one distance over another in certain types of applications. Finally, we show an application of these different distances to a network created from worldwide recipes.
Year
Venue
Field
2018
arXiv: Applications
Econometrics,Complex system,Graph,Network dynamics,Social network,A priori and a posteriori,Theoretical computer science,Thread (computing),Mathematics
DocType
Volume
Citations 
Journal
abs/1801.07351
2
PageRank 
References 
Authors
0.51
0
2
Name
Order
Citations
PageRank
Claire Donnat131.22
Susan Holmes221126.51