LMSC: Local Sketch Modularity Optimisation for Size-Constrained Community Search in Networks

With the proliferation of social networks, identifying meaningful community structures efficiently is essential for analysing 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 Optimisation 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.