Community Discovery on Dynamic Graphs with Edge-Local Differential Privacy
Sudipta Paul
Fatemeh Sadjadi
Vicenç Torra
Department of Computing Science, Umeå University
90187 Umeå, Sweden
Julián Salas
Faculty of Computer Science, Multimedia and Telecommunications
Universitat Oberta de Catalunya
Rambla del Poblenou, 156
Barcelona, 08018, Spain
Abstract
Interactions among different elements of complex networks are organized in a structured manner. The collective behavior of the elements of these networks is organized according to community structure. Several methods have been defined to automatically detect these substructures in the field known as community discovery. Most of the methods have been applied to static or aggregated data. Recently the identification of evolving communities has gained more attention. Studying the relations among individuals yields insights on how communities form and evolve, but there are some limits that should be enforced to respect individuals’ privacy while sharing and collecting their data. Privacy-protection techniques have been commonly applied to static data, while there are few methods that work on dynamic data. Recently, there have been some approaches to protect dynamic graphs with local edge-differential privacy that have been tested for community discovery applications. However, the evolution of the communities over time has not been evaluated on the privacy-protected data. We test the utility considering community discovery and evolution in time-varying networks for such local-edge-ε-differential privacy methods. We show empirically how these algorithms can provide privacy while preserving the community life cycles, for their privacy-aware study.
Keywords: edge local differential privacy; dynamic graphs; community discovery
Cite this publication as:
S. Paul, F. Sadjadi, V. Torra and J. Salas, “Community Discovery on Dynamic Graphs with Edge-Local Differential Privacy,” Complex Systems, 34(2), 2025 pp. 203–215.
https://doi.org/10.25088/ComplexSystems.34.2.203
