Hierarchical community detection with applications to real-world network analysis

Bo Yang*, Jin Di, Jiming LIU, Dayou Liu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

36 Citations (Scopus)

Abstract

Community structure is ubiquitous in real-world networks and community detection is of fundamental importance in many applications. Although considerable efforts have been made to address the task, the objective of seeking a good trade-off between effectiveness and efficiency, especially in the case of large-scale networks, remains challenging. This paper explores the nature of community structure from a probabilistic perspective and introduces a novel community detection algorithm named as PMC, which stands for probabilistically mining communities, to meet the challenging objective. In PMC, community detection is modeled as a constrained quadratic optimization problem that can be efficiently solved by a random walk based heuristic. The performance of PMC has been rigorously validated through comparisons with six representative methods against both synthetic and real-world networks with different scales. Moreover, two applications of analyzing real-world networks by means of PMC have been demonstrated.

Original languageEnglish
Pages (from-to)20-38
Number of pages19
JournalData and Knowledge Engineering
Volume83
DOIs
Publication statusPublished - Jan 2013

Scopus Subject Areas

  • Information Systems and Management

User-Defined Keywords

  • Community detection
  • Graph mining
  • Link analysis
  • Social network analysis

Fingerprint

Dive into the research topics of 'Hierarchical community detection with applications to real-world network analysis'. Together they form a unique fingerprint.

Cite this