Finding local influential communities in large weighted networks

Recently, influential community discovery in large weighted networks has attracted extensive attention by capturing both the importance and cohesiveness of communities, and has been widely applied in the analysis of collaborative networks, social networks, biological networks, etc. Most existing work models the influence of a community by the minimum vertex weight. Moreover, the weight of a vertex is assumed to be invariant in the whole network. Yet, the influence (weight) of a vertex usually differs depending on which community it belongs to, and therefore such an assumption is impractical. In this paper, we propose a novel community model called local k-influential community (k-LIC for short), inspired by the concept of k-core. Specifically, the weight of a vertex in a k-LIC is determined by the weights of its incident edges in the local subgraph, and thus is more flexible. Further, we formulate the top-r k-LIC mining problem. Unfortunately, due to the loss of the vertex weight invariance property, mining the k-LIC with the highest influence becomes NP-hard. To find top-r k-LICs, (1) we devise an exact depth-first search method with several elegant pruning rules to enumerate the exact top-r k-LICs; (2) to further speed up the top-r k-LIC mining process, we propose an efficient greedy method to find the approximate subgraphs based on different heuristic strategies. Comprehensive experimental results on several real-world large networks demonstrate the effectiveness and efficiency of the proposed model and approaches. The source code of this project is publicly available at https://github.com/ThIsnullPtR/LIC.git.