2019/06/13 by Xiuwen Zheng, Qiyu Liu, Zheng, Xiuwen +3
Computer Science · Physics and Astronomy · Social Sciences · #Complex Network Analysis Techniques #Databases (cs.DB) #FOS: Computer and information sciences #Human Mobility and Location-Based Analysis #Mobile Crowdsensing and Crowdsourcing #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1906.05505
openalex publication_date 2019/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a community finding problem called Co-located Community Detection (CCD) over geo-social networks, which retrieves communities that satisfy both high structural tightness and spatial closeness constraints. To provide a solution that benefits from existing studies on community detection, we decouple the spatial constraint from graph structural constraint and propose a uniform CCD framework which gives users the freedom to choose customized measurements for social cohesiveness (e.g., k-core or k-truss). For the spatial closeness constraint, we apply the bounded radius spatial constraint and develop an exact algorithm together with effective pruning rules. To further improve the efficiency and make our framework scale to a very large scale of data, we propose a near-linear time approximation algorithm with a constant approximation ratio (√(2)). We conduct extensive experiments on both synthetic and real-world datasets to demonstrate the efficiency and effectiveness of our algorithms.