An efficient probabilistic approach to network community mining

Yang Bo*, Jiming Liu

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

5 Citations (Scopus)


A network community refers to a group of vertices within which the links are dense but between which they are sparse. A network community mining problem (NCMP) is the problem to find all such communities from a given network. A wide variety of applications can be formalized as NCMPs such as complex network analysis, Web pages clustering as well as image segmentation. How to solve a NCMP efficiently and accurately remains an open challenge. Distinct from other works, the paper addresses the problem from a probabilistic perspective and presents an efficient algorithm that can linearly scale to the size of networks based on a proposed Markov random walk model. The proposed algorithm is strictly tested against several benchmark networks including a semantic social network. The experimental results show its good performance with respect to both speed and accuracy.

Original languageEnglish
Title of host publicationRough Sets and Knowledge Technology - Second International Conference, RSKT 2007, Proceedings
Number of pages9
Publication statusPublished - 2007
Event2nd International Conference on Rough Sets and Knowledge Technology, RSKT 2007 - Toronto, Canada
Duration: 14 May 200716 May 2007

Publication series

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


Conference2nd International Conference on Rough Sets and Knowledge Technology, RSKT 2007

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Community
  • Markov chain
  • Semantic web
  • Social networks


Dive into the research topics of 'An efficient probabilistic approach to network community mining'. Together they form a unique fingerprint.

Cite this