Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks

Abstract

Temporal Networks, and more specifically, Markovian Temporal Networks, present a unique challenge regarding the community discovery task. The inherent dynamism of these systems requires an intricate understanding of memory effects and structural heterogeneity, which are often key drivers of network evolution. In this study, we address these aspects by introducing an innovative approach to community detection, centered around a novel modularity function. We focus on demonstrating the improvements our new approach brings to a fundamental aspect of community detection: the detectability threshold problem. We show that by associating memory directly with nodes' memberships and considering it in the expression of the modularity, the detectability threshold can be lowered with respect to cases where memory is not considered, thereby enhancing the quality of the communities discovered. To validate our approach, we carry out extensive numerical simulations, assessing the effectiveness of our method in a controlled setting. Furthermore, we apply our method to real-world data to underscore its practicality and robustness. This application not only demonstrates the method's effectiveness but also reveals its capacity to indirectly tackle additional challenges, such as determining the optimal time window for aggregating data in dynamic graphs. This illustrates the method's versatility in addressing complex aspects of temporal network analysis.

References in corpus (27)

• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Quantifying social group evolution
• High-resolution measurements of face-to-face contact patterns in a primary school
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• The statistical mechanics of networks
• Community Discovery in Dynamic Networks: a Survey
• Robust Detection of Dynamic Community Structure in Networks
• Spectral methods for network community detection and graph partitioning
• Phase transition in the detection of modules in sparse networks
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Graph spectra and the detectability of community structure in networks
• Maximum likelihood: extracting unbiased information from complex networks
• Localization of weakly disordered flat band states
• Effects of time window size and placement on the structure of aggregated networks
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Unbiased sampling of network ensembles
• (Un)detectable cluster structure in sparse networks
• Distance dependent competitive interactions in a frustrated network of mobile agents
• The Temporal Rich Club Phenomenon
• Fluctuating ecological networks: a synthesis of maximum-entropy approaches for pattern detection and process inference
• Finite size analysis of the detectability limit of the stochastic block model
• Characterization of interactions' persistence in time-varying networks