Abstract
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.
Original language | English (US) |
---|---|
Title of host publication | 34th International Conference on Scientific and Statistical Database Management |
Publisher | ACM |
ISBN (Print) | 9781450396677 |
DOIs | |
State | Published - Aug 23 2022 |
Bibliographical note
KAUST Repository Item: Exported on 2022-09-26Acknowledgements: This work was supported financially by King Abdullah University of Science and Technology (KAUST), Saudi Arabia. In particular, Klearchos Kosmanos (the first author) was a Research Intern in KAUST during the period June 2020 - August 2020 working in the topic of Incremental Influential Community Search.