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:
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:

https://manu44.magtech.com.cn/Jwk_infotech_wk3/EN/10.11925/infotech.1003-3513.2015.04.08     OR     https://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] Shan Xiaohong,Wang Chunwen,Liu Xiaoyan,Han Shengxi,Yang Juan. Identifying Lead Users in Open Innovation Community from Knowledge-based Perspectives[J]. 数据分析与知识发现, 2021, 5(9): 85-96.
[2] Chen Wenjie,Wen Yi,Yang Ning. Fuzzy Overlapping Community Detection Algorithm Based on Node Vector Representation[J]. 数据分析与知识发现, 2021, 5(5): 41-50.
[3] Li Ming, Li Ying, Zhou Qing, Wang Jun. Analyzing Knowledge Demand and Supply of Community Question Answering with TF-PIDF[J]. 数据分析与知识发现, 2021, 5(2): 106-115.
[4] Shen Wang, Li Shiyu, Liu Jiayu, Li He. Optimizing Quality Evaluation for Answers of Q&A Community[J]. 数据分析与知识发现, 2021, 5(2): 83-93.
[5] Wang Song, Yang Yang, Liu Xinmin. Discovering Potentialities of User Ideas from Open Innovation Communities with Graph Attention Network[J]. 数据分析与知识发现, 2021, 5(11): 89-101.
[6] Cai Yongming,Liu Lu,Wang Kewei. Identifying Key Users and Topics from Online Learning Community[J]. 数据分析与知识发现, 2020, 4(6): 69-79.
[7] Tao Xing,Zhang Xiangxian,Guo Shunli,Zhang Liman. Automatic Summarization of User-Generated Content in Academic Q&A Community Based on Word2Vec and MMR[J]. 数据分析与知识发现, 2020, 4(4): 109-118.
[8] Li He,Liu Jiayu,Shen Wang,Liu Rui,Jin Shuaiqi. Recommending Knowledge for Online Health Community Users Based on Fuzzy Cognitive Map[J]. 数据分析与知识发现, 2020, 4(12): 55-67.
[9] Ding Heng,Li Yingxuan. Improving Online Q&A Service with Deep Learning[J]. 数据分析与知识发现, 2020, 4(10): 37-46.
[10] Yan Wen,Lijian Ma,Qingtian Zeng,Wenyan Guo. POI Recommendation Based on Geographic and Social Relationship Preferences[J]. 数据分析与知识发现, 2019, 3(8): 30-39.
[11] Liqing Qiu,Wei Jia,Xin Fan. Influence Maximization Algorithm Based on Overlapping Community[J]. 数据分析与知识发现, 2019, 3(7): 94-102.
[12] Ming Yi,Tingting Zhang. Ranking Answer Quality of Popular Q&A Community[J]. 数据分析与知识发现, 2019, 3(6): 12-20.
[13] 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.
[14] 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.
[15] 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.
  Copyright © 2016 Data Analysis and Knowledge Discovery   Tel/Fax:(010)82626611-6626,82624938   E-mail:jishu@mail.las.ac.cn