Journal
VLDB JOURNAL
Volume 26, Issue 6, Pages 751-776Publisher
SPRINGER
DOI: 10.1007/s00778-017-0467-4
Keywords
Influential community; Core decomposition; Tree-shape data structure; Dynamic graph; I/O-efficient algorithm
Funding
- NSFC [61402292, U1301252]
- NSF-Shenzhen [JCYJ20150324-140036826, JCYJ20140418095735561]
- Shenzhen Kongque Program [827/000065]
- Research Grants Council of the Hong Kong SAR, China [14209314, 14221716]
- China 863 Grants [2015AA015305]
- [ARC DE140100999]
- [ARC DP160101513]
Ask authors/readers for more resources
Community search is a problem of finding densely connected subgraphs that satisfy the query conditions in a network, which has attracted much attention in recent years. However, all the previous studies on community search do not consider the influence of a community. In this paper, we introduce a novel community model called k-influential community based on the concept of k-core to capture the influence of a community. Based on this community model, we propose a linear time online search algorithm to find the top-r k-influential communities in a network. To further speed up the influential community search algorithm, we devise a linear space data structure which supports efficient search of the top-r k-influential communities in optimal time. We also propose an efficient algorithm to maintain the data structure when the network is frequently updated. Additionally, we propose a novel I/O-efficient algorithm to find the top-r k-influential communities in a disk-resident graph under the assumption of , where and n denote the size of the main memory and the number of nodes, respectively. Finally, we conduct extensive experiments on six real-world massive networks, and the results demonstrate the efficiency and effectiveness of the proposed methods.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available