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

Summary: Introduces Local Sketch Modularity (LSM), a query-centric community quality measure computable without full-graph structure, aimed at overcoming free-rider effects in modularity-based search. Defines the NP-hard size-constrained community search problem LMSC and gives two efficient algorithms with strong empirical results on large networks. (summarized by gpt-5-mini on Apr 11 2026)

Paper ID: 7683
Venue: SIGMOD
Year: 2026
Pagerank: 5.0723324e-05
Overall Rank: 10,509 | 28.15%
DOI: 10.1145/3786666

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Dahee Kim (Ulsan National Institute of Science and Technology)
2. Taejoon Han (Ulsan National Institute of Science and Technology)
3. Kaiyu Feng (Beijing Institute of Science and Technology)
4. Junghoon Kim (Ulsan National Institute of Science and Technology)
5. Susik Yoon (Korea University)

BibTeX Citation

@inproceedings{kim_sigmod26,
        title = {{LMSC: Local Sketch Modularity Optimisation for Size-Constrained Community Search in Networks}},
        author = {Kim, Dahee and Han, Taejoon and Feng, Kaiyu and Kim, Junghoon and Yoon, Susik},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3786666},
        url = {https://dl.acm.org/doi/10.1145/3786666},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
277	Local Search of Communities in Large Graphs	2014	SIGMOD	0.00022528389
708	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014731991
811	Robust Local Community Detection: On Free Rider Effect and Its Elimination	2015	VLDB	0.00013840494
1,118	Approximate Closest Community Search in Networks	2016	VLDB	0.00012077425
1,244	Attribute-Driven Community Search	2017	VLDB	0.00011490151
1,337	Truss-based Community Search over Large Directed Graphs	2020	SIGMOD	0.00011098837
2,883	Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed	2022	VLDB	7.9767707e-05
3,411	Efficient Size-Bounded Community Search over Large Networks	2021	VLDB	7.4182404e-05
5,523	DMCS : Density Modularity based Community Search	2022	SIGMOD	6.1742075e-05
5,902	Neural Attributed Community Search at Billion Scale	2023	SIGMOD	6.0304168e-05
6,209	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD	5.9247273e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,168	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB
2	2,592	Community Detection in Social Networks: An In-depth Benchmarking Study with a Procedure-Oriented Framework	2015	VLDB
3	6,209	Densely Connected User Community and Location Cluster Search in Location-Based Social Networks	2020	SIGMOD
4	986	Influential Community Search in Large Networks	2015	VLDB
5	3,411	Efficient Size-Bounded Community Search over Large Networks	2021	VLDB
6	11,011	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB
7	10,407	Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements	2026	SIGMOD
8	277	Local Search of Communities in Large Graphs	2014	SIGMOD
9	6,436	On Density-based Local Community Search	2024	PODS
10	5,523	DMCS : Density Modularity based Community Search	2022	SIGMOD