全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

基于节点层级与标签传播增益的重叠社区发现*

DOI: 10.16451/j.cnki.issn1003-6059.201504001, PP. 289-298

Keywords: 重叠社区发现,多标签传播,节点层级,传播增益,中心度

Full-Text   Cite this paper   Add to My Lib

Abstract:

多标签传播算法具有接近线性的时间复杂度,但用于重叠社区发现时存在精度低、稳定性差的问题.文中基于重叠节点更可能出现在社区边缘的思想,提出基于节点层级与标签传播增益的重叠社区发现算法.该算法首先利用改进的基于节点中心度与社区分布约束的单标签传播方法发现非重叠社区,并在标签传播过程中利用局部信息同步计算节点中心度.然后根据节点中心度定义节点层级函数,标记节点在所属社区中的层级.最后基于节点间的标签传播增益,利用新的多标签更新规则,获得重叠社区结构.实验表明该算法能有效提高精度和稳定性.

References

[1]  Xie J R, Kelley S, Szymanski B K. Overlapping Community Detection in Networks: The State-of-the-Art and Comparative Study. ACM Computing Surveys, 2013, 45(4): 1-35
[2]  Palla G, Derényi I, Farkas I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature, 2005, 435: 814-818
[3]  Zhu M, Meng F R, Zhou Y. Density-Based Link Clustering Algorithm for Overlapping Community Detection. Journal of Computer Research and Development, 2013, 50(12): 2520-2530 (in Chinese)(朱 牧,孟凡荣,周 勇.基于链接密度聚类的重叠社区发现算法.计算机研究与发展, 2013, 50(12): 2520-2530)
[4]  Zhang Z H, Miao D Q, Qian J. Detecting Overlapping Communities with Heuristic Expansion Method Based on Rough Neighborhood. Chinese Journal of Computers, 2013, 36(10): 2078-2086 (in Chinese)(张泽华,苗夺谦,钱 进.邻域粗糙化的启发式重叠社区扩张方法.计算机学报, 2013, 36(10): 2078-2086)
[5]  Wang W J, Liu D, Liu X, et al. Fuzzy Overlapping Community Detection Based on Local Random Walk and Multidimensional Scaling. Physica A: Statistical Mechanics and Its Applications, 2013, 392(24): 6578-6586
[6]  Gregory S. Finding Overlapping Communities in Networks by Label Propagation. New Journal of Physics, 2010. DOI: 10.1088/1367-2630/12/10/103018
[7]  Raghavan U N, Albert R, Kumara S. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0709.2938.pdf
[8]  Xie J R, Szymanski B K, Liu X M. SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process // Proc of the 11thInternational Conference on Data Mining. Vancouver, Canada, 2011: 344-349
[9]  Dai Q G, Guo M Z, Liu Y, et al. MLPA: Detecting Overlapping Communities by Multi-label Propagation Approach // Proc of theCongress on Evolutionary Computation. Cancun, Mexico, 2013: 681-688
[10]  Page L, Brin S, Motwani R, et al. The PageRank Citation Ranking: Bringing Order to the Web[EB/OL]. [2014-04-20]. http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf
[11]  Barber M J, Clark J W. Detecting Network Communities by Propagating Labels under Constraints. Physcial Review E[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0903.3138.pdf
[12]  Liu X, Murata T. Advanced Modularity-Specialized Label Propagation Algorithm for Detecting Communities in Networks[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0910.1154.pdf
[13]  ubelj L, Bajec M. Unfolding Network Communities by Combining Defensive and Offensive Label Propagation // Proc of the ECML PKDD Workshop on the Analysis of Complex Networks. Barcelona, Spain, 2010: 87-104
[14]  Lancichinetti A, Fortunato S, Radicchi F. Benchmark Graphs for Testing Community Detection Algorithms[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0805.4770v4.pdf
[15]  Danon L, Diaz-Guilera A, Duch J, et al. Comparing Community Structure Identification[EB/OL]. [2014-04-20]. http://deim.urv.cat/~alexandre.arenas/publicacions/pdf/jstat05.pdf
[16]  Nicosia V, Mangioni G, Carchiolo V, et al. Extending the Definition of Modularity to Directed Graphs with Overlapping Communities[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0801.1647.pdf

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133