Incremental Influential Community Detection in Large Networks

The concept of network communities has been studied thoroughly in the network science literature since it has many important applications in diverse fields. Recently, the community concept has been combined with the concept of influence. The aim of this combination is to allow for the detection of communities that have also a high degree of influence. To achieve this, there is a need to guarantee that communities are good with respect to their structure and also influential with respect to attribute values of the nodes participating in the community. In the literature, there are two main directions to attack the problem: i) the online approach, which computes influential communities in increasing influence value order, and ii) the index-based approach, which pre-computes influential communities and stores appropriate information in a tree-based index structure. Based on these two directions, we propose a new technique with the following properties: i) there is no need to process the graph each time a new query arrives, and ii) there is no need to waste computational resources to maintain parts of the index that users are not interested in. This is achieved by starting without any index in memory. Then, using online algorithms, as new queries arrive, we incrementally build parts of the index that help answering similar future queries. Extensive experimental results, on real world graphs, demonstrate the efficiency of our method against existing approaches in most realistic cases.