We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Finding influential communities in massive networks.
- Authors
Li, Rong-Hua; Qin, Lu; Yu, Jeffrey; Mao, Rui
- Abstract
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 $${{\mathcal {U}}}=O(n)$$ , where $${{\mathcal {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.
- Subjects
SEARCH algorithms; COMMUNITIES; DATA analysis
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2017, Vol 26, Issue 6, p751
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-017-0467-4