Personalized Influential Community Search in Large Networks: A K-ECC-Based Model

Shi Meng, Hao Yang, Xijuan Liu, Zhenyue Chen, Jingwen Xuan, Yanping Wu and Gengxin Sun

Discrete Dynamics in Nature and Society, 2021, vol. 2021, 1-10

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.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/ddns/2021/5363946.pdf (application/pdf)
http://downloads.hindawi.com/journals/ddns/2021/5363946.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnddns:5363946

DOI: 10.1155/2021/5363946

Access Statistics for this article

More articles in Discrete Dynamics in Nature and Society from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().