Abstract 

With the proliferation of social networks, identifying meaningful community structures efficiently is essential for analyzing complex interactions. This paper introduces Local Sketch Modularity (LSM), a novel modularity that measures community quality without relying on the entire structural information of the network, enabling a more targeted and practical approach to find the query-centric community. We validate the efficacy of the proposed modularity LSM through theoretical analyses, showing robustness against the free-rider effect. We further formulate the Local Modularity Optimization for Size-Constrained Community Search (LMSC) problem, which leverages LSM to identify the query-centric community without requiring knowledge of the entire graph. We prove that LMSC is NP-hard and propose two efficient and effective algorithms. Extensive experiments on real-world networks demonstrate both the effectiveness and efficiency of the proposed method, confirming its applicability for large-scale network analysis.

A research team led by Professor JungHoon Kim from the Department of Computer Science and Engineering at UNIST has introduced an innovative network analysis algorithm capable of identifying relevant communities around a target node without requiring access to the entire network. This advancement has the potential to enhance targeted marketing, improve fraud detection, and generate new insights in biological network research.

Traditional community detection tools often struggle with large-scale data or are limited by privacy restrictions that prevent access to full network information. They tend to include unrelated nodes or overlook tightly connected groups around a specific target. The new method addresses these challenges by focusing solely on the neighborhood of a designated node, expanding the community incrementally while adhering to a predefined size.

Starting from the target node—such as a potential customer, a suspicious account, or a biological molecule—the algorithm examines neighboring candidates and assesses whether adding each one improves the overall coherence of the group. It balances internal connectivity with external separation, preventing the community from becoming excessively large. To capture subtle relationships, it also considers small, tightly linked subgroups that might otherwise be missed.

Testing on real-world networks shows this approach significantly outperforms existing methods, with F1 scores up to 1.39 times higher and ARI scores up to 5.95 times higher. These results demonstrate more accurate detection of relevant communities while reducing false positives.

“In many real-world situations, obtaining full network data isn't feasible, and the target community size is often fixed,” said Professor Kim. “Our method quickly identifies meaningful groups around a specific node, making it applicable to areas like customer segmentation, fraud prevention, and biological research.”

Supported by the National Research Foundation of Korea (NRF), the study was led by first author Dahee Kim. Their work has been accepted for presentation at the ACM Special Interest Group on Management of Data (SIGMOD) 2026, scheduled to take place in Bengaluru, India, from May 31 to June 5, 2026. As one of the most respected conferences in data management, SIGMOD offers a platform for pioneering research in the field.

Journal Reference

Dahee Kim, Taejoon Han, Kaiyu Feng, et al., "LMSC: Local Sketch Modularity Optimization for Size-Constrained Community Search in Networks,"'26 SIGMOD, (2026).