Finding influential communities in massive networks
- Publication Type:
- Journal Article
- Citation:
- VLDB Journal, 2017, 26 (6), pp. 751 - 776
- Issue Date:
- 2017-12-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 10.1007%2Fs00778-017-0467-4.pdf | Published Version | 1.89 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 2017, Springer-Verlag Berlin Heidelberg. 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-rk-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-rk-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-rk-influential communities in a disk-resident graph under the assumption of U= O(n) , where U 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.
Please use this identifier to cite or link to this item: