2016/05/03 by Nathan D. Monnig, Monnig, Nathan D, François G. Meyer +1 · 1 citation
Physics and Astronomy · Psychology · #Complex Network Analysis Techniques #Mental Health Research Topics #Opinion Dynamics and Social Influence
paper · pdf · doi:10.48550/arxiv.1605.01091
To quantify the fundamental evolution of time-varying networks, and detect\nabnormal behavior, one needs a notion of temporal difference that captures\nsignificant organizational changes between two successive instants. In this\nwork, we propose a family of distances that can be tuned to quantify structural\nchanges occurring on a graph at different scales: from the local scale formed\nby the neighbors of each vertex, to the largest scale that quantifies the\nconnections between clusters, or communities. Our approach results in the\ndefinition of a true distance, and not merely a notion of similarity. We\npropose fast (linear in the number of edges) randomized algorithms that can\nquickly compute an approximation to the graph metric. The third contribution\ninvolves a fast algorithm to increase the robustness of a network by optimally\ndecreasing the Kirchhoff index. Finally, we conduct several experiments on\nsynthetic graphs and real networks, and we demonstrate that we can detect\nconfigurational changes that are directly related to the hidden variables\ngoverning the evolution of dynamic networks.\n