Distributed Community Detection in Historical Graphs

Abstract 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 extend two existing algorithms by incorporating the temporal information and evaluate their performance on both near-real-world and synthetic datasets. To the best of our knowledge, handling temporal graphs with valid intervals in community detection has not been previously explored in the literature.