Distributed community detection in historical graphs

Community detection is a fundamental task in network analysis that has been extensively studied over the past 25 years, primarily within the context of static networks. It involves dividing a network into groups of nodes that are more densely connected internally than with the rest of the network. In recent years, the challenge has grown more complex with the emergence of historical graphs, a form of static network where each node and edge is associated with a specific time interval of validity. Unlike traditional graphs, historical graphs integrate a temporal dimension, enabling the study of how relationships evolve over time. In this work, we introduce distributed algorithms designed to detect communities within a specified query time interval in historical graphs. Given a user-defined time window, the proposed methods identify communities by evaluating the contribution of each node and edge during that specific period. This contribution is quantified either by means of aggregating the temporal information through weights, as usually happens in the literature when handling temporal graphs, or by handling the time intervals using set operations–intersection in our case. We propose two distributed algorithms that incorporate temporal information, and we evaluate their performance on both real-world and synthetic datasets. To the best of our knowledge, community detection in historical graphs represented through explicit validity intervals has not previously been addressed in the literature, neither in centralized nor in distributed settings.