Personalized Influential Community Search in Large Networks: A K-ECC-Based Model. (29th November 2021)

• Record Type: Journal Article
• Authors: Meng, Shi; Yang, Hao; Liu, Xijuan; Chen, Zhenyue; Xuan, Jingwen; Wu, Yanping
• Other Names: Sun Gengxin Academic Editor.
• Is Part Of: Discrete dynamics in nature and society. Volume 2021(2021)
• Publication Date: 2021-11-29
• Subjects: System analysis -- Periodicals; Dynamics -- Periodicals; Chaotic behavior in systems -- Periodicals; Differentiable dynamical systems -- Periodicals; 003.05
• DOI: 10.1155/2021/5363946
• Languages: English
• ISSNs: 1026-0226

Abstract

Abstract : Graphs have been widely used to model the complex relationships among entities. Community search is a fundamental problem in graph analysis. It aims to identify cohesive subgraphs or communities that contain the given query vertices. In social networks, a user is usually associated with a weight denoting its influence. Recently, some research is conducted to detect influential communities. However, there is a lack of research that can support personalized requirement. In this study, we propose a novel problem, named personalized influential k -ECC (PIKE) search, which leverages the k -ECC model to measure the cohesiveness of subgraphs and tries to find the influential community for a set of query vertices. To solve the problem, a baseline method is first proposed. To scale for large networks, a dichotomy-based algorithm is developed. To further speed up the computation and meet the online requirement, we develop an index-based algorithm. Finally, extensive experiments are conducted on 6 real-world social networks to evaluate the performance of proposed techniques. Compared with the baseline method, the index-based approach can achieve up to 7 orders of magnitude speedup.