2021/10/28 by Yanhao Yang, Yang, Yanhao, Meng Wang +5 · 1 citation
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #Network Security and Intrusion Detection #Peer-to-Peer Network Technologies #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2110.14972
openalex publication_date 2021/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Community is a universal structure in various complex networks, and community detection is a fundamental task for network analysis. With the rapid growth of network scale, networks are massive, changing rapidly and could naturally be modeled as graph streams. Due to the limited memory and access constraint in graph streams, existing non-streaming community detection methods are no longer applicable. This raises an emerging need for online approaches. In this work, we consider the problem of uncovering the local community containing a few query nodes in graph streams, termed streaming local community detection. This is a new problem raised recently that is more challenging for community detection and only a few works address this online setting. Correspondingly, we design an online single-pass streaming local community detection approach. Inspired by the "local" property of communities, our method samples the local structure around the query nodes in graph streams, and extracts the target community on the sampled subgraph using our proposed metric called the approximate conductance. Comprehensive experiments show that our method remarkably outperforms the streaming baseline on both effectiveness and efficiency, and even achieves similar accuracy comparing to the state-of-the-art non-streaming local community detection methods that use static and complete graphs.