Paper
PERCeIDs: PERiodic CommunIty Detection
Published Nov 1, 2019 · Lin Zhang, A. Gorovits, Petko Bogdanov
2019 IEEE International Conference on Data Mining (ICDM)
9
Citations
0
Influential Citations
Abstract
Many complex networked systems, both natural and human-made, exhibit periodic behavior driven by underlying seasonal processes: election cycles and regular sporting events in social networks, cell cycle phases in gene networks, and load variation in infrastructure networks due to weather or daylight patterns. The "natural" periodicity may vary across network communities. At the same time this periodic community behavior is central to (i) understating the overall system dynamics and (ii) for detection of the communities themselves. The predominant approach to dynamic community detection first detects communities and then as a second step quantify seasonality in their activity. How to jointly detect communities and their inherent periodicity, while also accounting for non-periodic one-off events? We propose PERCeIDs, a framework for periodic overlapping community detection from temporal interaction data. We model observed pairwise interaction activity as a mixture of periodic and outlier (non-periodic) components. We explicitly enforce periodic structure within our model by learning a succinct Ramanujan basis dictionary for community behaviors. By explicitly modeling periodicity, PERCeIDs outperforms baselines on both detecting highly overlapping communities with up to 2-fold improvement in NMI compared to state-of-the-art baselines, while offering an interpretable temporal structure for discovered communities in the dataset. Implementation of our method can be found at http://www.cs.albany.edu/~petko/lab/code.html.
PERCeIDs effectively detects periodic communities in complex networked systems, outperforming state-of-the-art methods and offering interpretable temporal structures for discovered communities.
Full text analysis coming soon...