Personalized top-n influential community search over large social networks

Jian Xu*, Xiaoyi FU, Liming Tu, Ming Luo, Ming Xu, Ning Zheng

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-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 may add new edges to existing networks. To conduct personalized top-n influential community search efficiently in such networks, we first introduce a search space refinement method. We then present pruning based and heuristic based search approaches. The proposed algorithms more than double the efficiency of the search performance for basic solutions. The effectiveness and efficiency of our algorithms have been verified using four real datasets.

Original languageEnglish
Title of host publicationWeb and Big Data - Second International Joint Conference, APWeb-WAIM 2018, Proceedings
EditorsJianliang Xu, Yoshiharu Ishikawa, Yi Cai
PublisherSpringer Verlag
Pages105-120
Number of pages16
ISBN (Print)9783319968896
DOIs
Publication statusPublished - 2018
Event2nd Asia Pacific Web and Web-Age Information Management Joint Conference on Web and Big Data, APWeb-WAIM 2018 - Macau, China
Duration: 23 Jul 201825 Jul 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10987 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd Asia Pacific Web and Web-Age Information Management Joint Conference on Web and Big Data, APWeb-WAIM 2018
Country/TerritoryChina
CityMacau
Period23/07/1825/07/18

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Community search
  • Heuristic 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