Influential community search in large networks

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, which can capture the influence of a community. Based on the new 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 index structure which supports efficient search of the top- r k -influential communities in optimal time. We also propose an efficient algorithm to maintain the index when the network is frequently updated. We conduct extensive experiments on 7 real-world large networks, and the results demonstrate the efficiency and effectiveness of the proposed methods.