Source-linked AI summary
Small-world behavior in time-varying graphs
J. Tang, S. Scellato, M. Musolesi, C. Mascolo, V. Latora
TL;DR
Static graph measures miss the time order, duration, and correlations of fluctuating links. The paper introduces temporal paths, distances, and link-persistence measures, showing temporal small-world behavior in modeled and real networks.
Problem
Standard static graph measures do not fully capture dynamic correlations in networks whose links fluctuate over time.
Method
The paper represents systems as ordered sequences of graphs and defines temporal distances, paths, and temporal-correlation measures to analyze their connectivity.
Results
Real brain and social traces show high temporal clustering alongside characteristic temporal path lengths comparable to shuffled sequences, while social clustering exceeds shuffled values by more than twofold.
Takeaways & Limitations
Small-world behavior in time-varying systems consists of highly correlated links combined with small temporal distances or high temporal efficiency.
Abstract
from arXiv · showhide
Connections in complex networks are inherently fluctuating over time and exhibit more dimensionality than analysis based on standard static graph measures can capture. Here, we introduce the concepts of temporal paths and distance in time-varying graphs. We define as temporal small world a time-varying graph in which the links are highly clustered in time, yet the nodes are at small average temporal distances. We explore the small-world behavior in synthetic time-varying networks of mobile agents, and in real social and biological time-varying systems.