Please wait a minute...
New Technology of Library and Information Service  2015, Vol. 31 Issue (4): 58-64    DOI: 10.11925/infotech.1003-3513.2015.04.08
Current Issue | Archive | Adv Search |
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
Download: PDF(595 KB)   HTML  
Export: BibTeX | EndNote (RIS)      
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.

Key wordsCommunity detection      Social networks      Community      Label propagation     
Received: 26 September 2014      Published: 21 May 2015
:  TP311  

Cite this article:

Liu Haoxia, Peng Shanglian. A Community Detection Algorithm via Neighborhood Node Influence Based Label Propagation. New Technology of Library and Information Service, 2015, 31(4): 58-64.

URL:

http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.1003-3513.2015.04.08     OR     http://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/Y2015/V31/I4/58

[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/.

[1] Liqing Qiu,Wei Jia,Xin Fan. Influence Maximization Algorithm Based on Overlapping Community[J]. 数据分析与知识发现, 2019, 3(7): 94-102.
[2] Ming Yi,Tingting Zhang. Ranking Answer Quality of Popular Q&A Community[J]. 数据分析与知识发现, 2019, 3(6): 12-20.
[3] Xiaolan Wu,Chengzhi Zhang. Analysis of Knowledge Flow Based on Academic Social Networks:
A Case Study of ScienceNet.cn
[J]. 数据分析与知识发现, 2019, 3(4): 107-116.
[4] Quan Lu,Anqi Zhu,Jiyue Zhang,Jing Chen. Research on User Information Requirement in Chinese Network Health Community: Taking Tumor-forum Data of Qiuyi as an Example[J]. 数据分析与知识发现, 2019, 3(4): 22-32.
[5] Xiwei Wang,Duo Wang,Qingxiao Zheng,Ya’nan Wei. Information Interaction Between User and Enterprise in Online Brand Community: A Study of Virtual Reality Industry[J]. 数据分析与知识发现, 2019, 3(3): 83-94.
[6] He Li,Linlin Zhu,Min Yan,Jincheng Liu,Chuang Hong. Identifying Useful Information from Open Innovation Community[J]. 数据分析与知识发现, 2018, 2(12): 12-22.
[7] Xiufeng Cheng,Xinyi Zhang,Ning Wang. Identifying Trending Topics in Q&A Community with CART Decision Tree[J]. 数据分析与知识发现, 2018, 2(12): 52-59.
[8] Yunwei Chen,Ruihong Zhang. Comparing on Community Detection Algorithms for Information Mining[J]. 数据分析与知识发现, 2018, 2(10): 84-94.
[9] Xiaohua Shi,Hongtao Lu. Detecting Community in Scientific Collaboration Network with Bayesian Symmetric NMF[J]. 数据分析与知识发现, 2017, 1(9): 49-56.
[10] Yaxian Qing,Rui Li,Huayi Wu. Analyzing Academic Community Based on Co-author Network[J]. 数据分析与知识发现, 2017, 1(4): 20-29.
[11] Xinwei Yuan,Shaohua Yang,Chaochao Wang,Zhanhe Du. Identifying Lead Players of User Innovation Communities Based on Feature Extraction and Random Forest Classification[J]. 数据分析与知识发现, 2017, 1(11): 62-74.
[12] Guo Chen,Lu Xiao. Linking Knowledge Elements from Online Community[J]. 数据分析与知识发现, 2017, 1(11): 75-83.
[13] Niu Liang. New Research and Application with Co-topics Network[J]. 现代图书情报技术, 2016, 32(7-8): 137-146.
[14] Wu Xiaolan,Zhang Chengzhi. Analyzing Food Community with Recipes and Weibo User Reviews[J]. 现代图书情报技术, 2016, 32(6): 54-62.
[15] Sun He,Li Shuqin,Lv Xueqiang,Liu Kehui. Retrieving Geographic Information for Micro-blog’s City Complaints[J]. 现代图书情报技术, 2016, 32(3): 58-66.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626,82624938   E-mail:jishu@mail.las.ac.cn