Optimal timescale for community detection in growing networks
arXiv:1809.04943 · doi:10.1088/1367-2630/ab413f
Abstract
Time-stamped data are increasingly available for many social, economic, and information systems that can be represented as networks growing with time. The World Wide Web, social contact networks, and citation networks of scientific papers and online news articles, for example, are of this kind. Static methods can be inadequate for the analysis of growing networks as they miss essential information on the system's dynamics. At the same time, time-aware methods require the choice of an observation timescale, yet we lack principled ways to determine it. We focus on the popular community detection problem which aims to partition a network's nodes into meaningful groups. We use a multi-layer quality function to show, on both synthetic and real datasets, that the observation timescale that leads to optimal communities is tightly related to the system's intrinsic aging timescale that can be inferred from the time-stamped network data. The use of temporal information leads to drastically different conclusions on the community structure of real information networks, which challenges the current understanding of the large-scale organization of growing networks. Our findings indicate that before attempting to assess structural patterns of evolving networks, it is vital to uncover the timescales of the dynamical processes that generated them.
14 pages, 8 figures + Supplementary Material
References in corpus (13)
- Fast unfolding of communities in large networks
- Benchmark graphs for testing community detection algorithms
- Community detection in networks: A user guide
- Consensus clustering in complex networks
- Bots increase exposure to negative and inflammatory content in online social systems
- The physics of brain network structure, function, and control
- Size reduction of complex networks preserving modularity
- Nestedness in complex networks: Observation, emergence, and implications
- Ranking in evolving complex networks
- Large-scale structure of time evolving citation networks
- Effects of time window size and placement on the structure of aggregated networks
- Growing complex network of citations of scientific papers -- measurements and modeling
- Randomizing growing networks with a time-respecting null model