Detection of community overlap according to belief propagation and conflict

Xianghua Fu, Liandong Liu and Chao Wang

Physica A: Statistical Mechanics and its Applications, 2013, vol. 392, issue 4, 941-952

Abstract: Most existing methods for detection of community overlap cannot balance efficiency and accuracy for large and densely overlapping networks. To quickly identify overlapping communities for such networks, we propose a new method that uses belief propagation and conflict (PCB) to occupy communities. We first identify triangles with maximal clustering coefficients as seed nodes and sow a new type of belief to the seed nodes. Then the beliefs explore their territory by occupying nodes with high assent ability. The beliefs propagate their strength along the graph to consolidate their territory, and conflict with each other when they encounter the same node simultaneously. Finally, the node membership is judged from the belief vectors. The PCB time complexity is nearly linear and its space complexity is linear. The algorithm was tested in extensive experiments on three real-world social networks and three computer-generated artificial graphs. The experimental results show that PCB is very fast and highly reliable. Tests on real and artificial networks give excellent results compared with three newly proposed overlapping community detection algorithms.

Keywords: Overlapping community; Community detection; Belief propagation; Belief conflict (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437112008783
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

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:eee:phsmap:v:392:y:2013:i:4:p:941-952

DOI: 10.1016/j.physa.2012.09.023

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().