Reliability-Driven Local Community Search in Dynamic Networks
Yifu Tang, Jianxin Li, Nur Al Hasan Haldar, Ziyu Guan, Jiajie Xu, Chengfei Liu
Abstract
Community search over large dynamic graph has become an important research problem in modern complex networks, such as the online social network, collaboration network and biological networks. Network data in the time-varied environment has motivated several recent studies to identify the evolution of the communities. However, these studies mostly match communities of different snapshot or utilize the aggregation of the disjoint structural information and ignores the cohesion continuity. To fill this research gap, in this work, we propose a novel <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(\theta ,k)$</tex-math></inline-formula> -core reliable community (CRC) and define the reliable community search problem which jointly considers member engagement, connection strength and cohesion continuity of the community in the dynamic network. We propose an online search algorithm based on eligible edge filtering and we further construct the Weighted Core Forest-Index (WCF-index) and develop efficient index-based querying algorithm with strong pruning properties. We also propose top- <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$l$</tex-math></inline-formula> reliable community search problem that couples query based distance to reduce the free rider effect in local community search and support flexible multiple query vertices. Extensive experiments are conducted to show the efficiency and effectiveness of the proposed algorithms.