Community Discovery on Dynamic Graphs with Edge-Local Differential Privacy

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.