File(s) under permanent embargo
Maximum co-located community search in large scale social networks
journal contribution
posted on 2018-06-01, 00:00 authored by Lu Chen, Chengfei Liu, Rui Zhou, Jianxin LiJianxin Li, Xiaochun Yang, Bin WangThe problem of k-truss search has been well defined and investigated to find the highly correlated user groups in social networks. But there is no previous study to consider the constraint of users' spatial information in k-truss search, denoted as co-located community search in this paper. The co-located community can serve many real applications. To search the maximum co-located communities efficiently, we first develop an efficient exact algorithm with several pruning techniques. After that, we further develop an approximation algorithm with adjustable accuracy guarantees and explore more effective pruning rules, which can reduce the computational cost significantly. To accelerate the real-time efficiency, we also devise a novel quadtree based index to support the efficient retrieval of users in a region and optimise the search regions with regards to the given query region. Finally, we verify the performance of our proposed algorithms and index using five real datasets.
History
Journal
Proceedings of the VLDB EndowmentVolume
11Issue
10Pagination
1233 - 1246Publisher
VLDB EndowmentLocation
New York, N.Y.Publisher DOI
ISSN
2150-8097Language
engPublication classification
C1 Refereed article in a scholarly journalCopyright notice
2018, VLDB EndowmentUsage metrics
Categories
Keywords
k-truss searchsocial networksspatial informationco-located community searchScience & TechnologyTechnologyComputer Science, Information SystemsComputer Science, Theory & MethodsComputer ScienceEFFICIENTDECOMPOSITIONCOMPUTATIONCORE2018 A*Information SystemsLibrary and Information StudiesComputation Theory and Mathematics
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC