Efficient Influential Community Search over Dynamic Graphs

Influential community (IC) search has gained much attention with applications in many areas, such as event organization, recommendation systems, and biological analysis. The dynamic nature of graphs, with frequent insertions and deletions of vertices and edges, makes searching ICs over dynamic graphs computationally costly. To enable efficient IC search on large graphs, existing works often develop index-based approaches, which first compute all the ICs, a.k.a. IC decomposition, and then organize them into some index structures compactly. However, designed for static graphs, these index structures cannot be maintained efficiently for dynamic graphs, and little attention has been paid to the theoretical analysis of the index maintenance algorithms. To tackle the above issues, in this paper, we study the IC search problem on large dynamic graphs, and maintain the index structures efficiently by developing novel IC maintenance algorithms. We first theoretically show that all existing index maintenance algorithms, for the scenarios of both edge insertion and deletion, are relatively unbounded. We then propose a novel concept, called IC decomposition order (ICD-order), based on which we further develop novel efficient IC maintenance algorithms for the scenarios of edge insertions and deletions, respectively. These algorithms not only effectively reduce the scope of affected vertices for improving efficiency, but also offer more favorable time complexities. The comprehensive experiments on eight real datasets show that our algorithms are up to six and three orders of magnitude faster than state-of-the-art index maintenance algorithms under the edge insertion and deletion scenarios, respectively.