Personalized top-n influential community search over large social networks

Jian Xu, Xiaoyi FU*, Yiming Wu, Ming Luo, Ming Xu, Ning Zheng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

User-centered analysis is one of the aims of online community search. In this paper, we study personalized top-n influential community search that has a practical application. Given an evolving social network, where every edge has a propagation probability, we propose a maximal pk-Clique community model, that uses a new cohesive criterion. The criterion requires that the propagation probability of each edge or each maximal influence path between two vertices that is considered as an edge, is greater than p. The maximal clique problem is an NP-hard problem, and the introduction of this cohesive criterion makes things worse, as it mights add new edges to existing networks. To conduct personalized top-n influential community search efficiently in such networks, we first introduce a pruning based method. We then present search space refinement and heuristic based search approaches. To diversify the search result in one pass, we also propose a diversify algorithm which is based on a novel tree-like index. The proposed algorithms achieve more than double the efficiency of the the search performance for basic solutions. The effectiveness and efficiency of our algorithms have been demonstrated using four real datasets.

Original languageEnglish
Pages (from-to)2153-2184
Number of pages32
JournalWorld Wide Web
Volume23
Issue number3
DOIs
Publication statusPublished - 1 May 2020

Scopus Subject Areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

User-Defined Keywords

  • Community search
  • Diversified search
  • Online
  • Pruning

Fingerprint

Dive into the research topics of 'Personalized top-n influential community search over large social networks'. Together they form a unique fingerprint.

Cite this