Scalable Community Detection over Geo-Social Network
share
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 freedom to choose customized measurements for social cohesiveness (e.g., k-core or k-truss). For the spatial closeness constraint, we re-examine the hardness of the pairwise distance constraint problem that has been ambiguously regarded as exponentially hard in previous work, and develop a true polynomial exact algorithm together with effective pruning rules. To further improve the efficiency and make our framework scale to 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.
READ FULL TEXT