|
|
A Community Detection Algorithm via Neighborhood Node Influence Based Label Propagation |
Liu Haoxia1, Peng Shanglian2 |
1 College of Literature and Journalism, Sichuan University, Chengdu 610064, China;
2 College of Computer Science and Technology, Chengdu University of Information Technology, Chengdu 610025, China |
|
|
Abstract [Objective] This paper aims to enhance quality and efficiency of community detection in recommandation system by controling propagation direction of labels. [Methods] A community detection algorithm via neighborhood node influence based label propagation is proposed to optimize label propagation paths and update nodes labels stably and effectively. [Results] The experimental analysis on artificial and real social network datasets verifies that updating and propagating labels based on neighborhood influlence can reduce labels updating space and time. [Limitations] The dataset used in this paper is not enough due to the restriction of the website, and the notion of neighborhood node influence needs to be generalized. [Conclusions] This study proposes a feasible solution to enhance community detection quality by reducing label propagation instability based on neighborhood influences.
|
Received: 26 September 2014
Published: 21 May 2015
|
|
[1] Danon L, Diaz-Guilera A, Duch J, et al. Comparing Community Structure Identification [J]. Journal of Statistical Mechanics: Theory and Experiment, 2005(9). doi: 10.1088/1742-5468/2005/09/P09008.
[2] Girvan M, Newman M E J. Community Structure in Social and Biological Networks [J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.
[3] Newman M E J. Modularity and Community Structure in Networks [J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577-8582.
[4] Newman M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices [J]. Physical Review E, 2006, 74(3). DOI: 10.1103/PhysRevE.74.036104.
[5] 陈盈晖, 杜海峰, 李树茁. 一种改进的模块性指标及其社群结构探测算法[J]. 西安电子科技大学学报, 2010, 37(2): 374-379. (Chen Yinghui, Du Haifeng, Li Shuzhuo. Modified Modularity and the Corresponding Community Structure Detecting Algorithm [J]. Journal of Xidian University, 2010, 37(2): 374-379.)
[6] 付立东, 高琳. 模块密度谱分的复杂网络社团发现方法[J]. 西安电子科技大学学报, 2010, 37(5): 916-920. (Fu Lidong, Gao Lin. Spectral Approach to Finding Communities in Networks Based on the Modularity Density [J]. Journal of Xidian University, 2010, 37(5): 916-920.)
[7] Good B H, de Montjoye Y A, Clauset A. The Performance of Modularity Maximization in Practical Contexts [J]. Physical Review E, 2010, 81(4). DOI: 10.1103/PhysRevE.81.046106.
[8] Wu F, Huberman B A. Finding Communities in Linear Time: A Physics Approach [J]. European Physical Journal B, 2004, 38(2): 331-338.
[9] Newman M E J. Fast Algorithm for Detecting Community Structure in Networks [J]. Physical Review E, 2004, 69(6). DOI: 10.1103/PhysRevE.69.066133.
[10] Raghavan U N, Albert R, Kumara S. Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks [J]. Physical Review E, 2007, 76(3). DOI: 10.1103/PhysRevE.76.036106.
[11] Barber M J, Clark J W. Detecting Network Communities by Propagating Labels Under Constraints [J]. Physical Review E, 2009, 80(2). DOI: 10.1103/PhysRevE.80.026129.
[12] Liu X, Murata T. Advanced Modularity-specialized Label Propagation Algorithm for Detecting Communities in Networks [J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389(7): 1493-1500.
[13] Leung I X Y, Hui P, Liò P. Towards Real-time Community Detection in Large Networks [J]. Physical Review E, 2009, 79. DOI: 10.1103/PhysRevE.79.066107.
[14] Newman M E J. The Structure and Function of Complex Networks [J]. SIAM Review, 2003, 45(2): 167-256.
[15] Schuetz P, Caflisch A. Efficient Modularity Optimization by Multistep Greedy Algorithm and Vertex Mover Refinement [J]. Physical Review E, 2008, 77. DOI: 10.1103/PhysRevE. 77.046112.
[16] 黄健斌, 钟翔, 孙鹤立, 等. 基于相似性模块度最大约束标记传播的网络社团发现算法[J]. 北京大学学报: 自然科学版, 2013, 49(3): 389-396. (Huang Jianbin, Zhong Xiang, Sun Heli, et al. A Network Community Detection Algorithm via Constrained Label Propagation with Maximization of Similarity-Based Modularity [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2013, 49(3): 389-396.)
[17] Tang L, Liu H. Community Detection and Mining in Social Media [M]. Morgan & Claypool Publishers, 2010.
[18] Orgnet.com [EB/OL]. [2014-10-25]. http://www.orgnet.com/. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|