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.
arXiv comment14 pages, 8 figures + Supplementary Material
References in corpus (37)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Benchmark graphs for testing community detection algorithms
- Temporal Networks
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Community detection in networks: A user guide
- Solving the apparent diversity-accuracy dilemma of recommender systems
- Consensus clustering in complex networks
- Modern temporal network theory: A colloquium
- Clustering and Community Detection in Directed Networks: A Survey
- The fundamental advantages of temporal networks
- Bots increase exposure to negative and inflammatory content in online social systems
- The ground truth about metadata and community detection in networks
- Evolution of reference networks with aging
- The physics of brain network structure, function, and control
- Memory in network flows and its effects on spreading dynamics and community detection
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Size reduction of complex networks preserving modularity
- Fundamental structures of dynamic social networks
- Causality-Driven Slow-Down and Speed-Up of Diffusion in Non-Markovian Temporal Networks
- Nestedness in complex networks: Observation, emergence, and implications
- Representing higher-order dependencies in networks
- Ranking in evolving complex networks
- Attention decay in science
- Community Structure of the Physical Review Citation Network
- Temporal effects in the growth of networks
- Large-scale structure of time evolving citation networks
- Effects of time window size and placement on the structure of aggregated networks
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Benchmark model to assess community structure in evolving networks
- Temporal network structures controlling disease spreading
- Growing complex network of citations of scientific papers -- measurements and modeling
- Detection of timescales in evolving complex systems
- Statistical validation of high-dimensional models of growing networks
- Randomizing growing networks with a time-respecting null model