1. Efficient Influential Community Search in Large Uncertain Graphs
- Author
-
Luo Wensheng, Kenli Li, Keqin Li, Xu Zhou, and Yunjun Gao
- Subjects
Property (philosophy) ,Operator (computer programming) ,Theoretical computer science ,Computational Theory and Mathematics ,Computer science ,Community search ,Probabilistic logic ,Interval (graph theory) ,Space (commercial competition) ,Graph ,Biological network ,Computer Science Applications ,Information Systems - Abstract
Influential community search aims to find cohesive subgraphs (communities) with considerable influence. It is a fundamental graph management operator that can play a crucial role in biological network analysis, activity organization, and other real-life applications. Existing research on influential community search is mainly focused on deterministic graphs with the assumption that influences between entities are certain. This assumption is invalid in many cases because it ignores the uncertainty which is an inherent property of influence. Against this backdrop, in this paper, we introduce an uncertain influential community model, namely (k,)-influential community, based on which the influential community search problem over uncertain graphs is formulated. Furthermore, we propose an online approach by integrating a peeling-pruning strategy that can progressively refine the given uncertain graph to find the (k,)-influential communities. To further improve the search performance, two novel indexes, ICU-Index and FICU-Index, are developed to organize the (k,)-influential communities at different probabilistic intervals. The indexes decompose the probabilistic interval into multiple subintervals and based on this, the (k,)-influential communities are divided into different groups in turn. Compared with ICU-Index, FICU-Index requires considerably less space with the introduction of two optimization strategies.
- Published
- 2023
- Full Text
- View/download PDF