Detection of community overlap according to belief propagation and conflict
AbstractMost 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Bibliographic InfoArticle provided by Elsevier in its journal Physica A: Statistical Mechanics and its Applications.
Volume (Year): 392 (2013)
Issue (Month): 4 ()
Contact details of provider:
Web page: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/
Overlapping community; Community detection; Belief propagation; Belief conflict;
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Shen, Huawei & Cheng, Xueqi & Cai, Kai & Hu, Mao-Bin, 2009. "Detect overlapping and hierarchical community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(8), pages 1706-1712.
- A. Tabrizi, Shayan & Shakery, Azadeh & Asadpour, Masoud & Abbasi, Maziar & Tavallaie, Mohammad Ali, 2013. "Personalized PageRank Clustering: A graph clustering algorithm based on random walks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(22), pages 5772-5785.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei).
If references are entirely missing, you can add them using this form.