Please wait a minute...
Advanced Search
现代图书情报技术  2015, Vol. 31 Issue (4): 58-64     https://doi.org/10.11925/infotech.1003-3513.2015.04.08
  研究论文 本期目录 | 过刊浏览 | 高级检索 |
一种基于邻近节点影响强度标签传播社区发现方法
刘郝霞1, 彭商濂2
1 四川大学文学与新闻学院 成都 610064;
2 成都信息工程学院计算机学院 成都 610025
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
全文: PDF (595 KB)   HTML  
输出: BibTeX | EndNote (RIS)      
摘要 

[目的]通过对标签传播方式的控制, 提高社区发现的质量和效率, 提升社区发现在推荐系统中的能力。[方法]提出一种高效的基于临近节点影响力强度的标签传播社区发现算法, 利用临近节点间的影响强度优化标签的传播路径。[结果]在真实数据集和人工数据集上的实验结果表明, 利用邻近节点间的相互影响强度进行标签的传播和更新, 本文的算法社区发现准确率比经典LPA算法提高2-5倍, 比MLPA算法提高约10%。[局限]实验数据的规模有待加强, 临近节点影响强度的概念模型的推广还需要完善。[结论]为提高社区发现的质量, 减少标签传播的不稳定性提供一种可行方案。

服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
刘郝霞
彭商濂
关键词 社区发现社交网络社区标签传播    
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
收稿日期: 2014-09-26      出版日期: 2015-05-21
:  TP311  
基金资助:

本文系国家自然科学基金重点项目“数据密集型计算环境下的数据管理方法与技术”(项目编号:61033007)、四川省教育厅项目“分布式复杂事件检测关键技术研究”(项目编号:13ZB0080)和四川大学985工程“文化遗产与文化互动创新基地”项目的研究成果之一。

通讯作者: 彭商濂,ORCID:0000-0002-1822-5772,E-mail:pengshanglian@126.com     E-mail: pengshanglian@126.com
作者简介: 作者贡献声明: 刘郝霞:提出研究思路,设计研究方案,分析数据,论文撰写及最终版本修订;彭商濂:提出研究思路,采集、清洗和分析数据,进行实验验证。
引用本文:   
刘郝霞, 彭商濂. 一种基于邻近节点影响强度标签传播社区发现方法[J]. 现代图书情报技术, 2015, 31(4): 58-64.
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.
链接本文:  
https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.1003-3513.2015.04.08      或      https://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/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] 单晓红,王春稳,刘晓燕,韩晟熙,杨娟. 开放式创新社区领先用户识别——知识基础观视角*[J]. 数据分析与知识发现, 2021, 5(9): 85-96.
[2] 王晰巍,贾若男,韦雅楠,张柳. 多维度社交网络舆情用户群体聚类分析方法研究*[J]. 数据分析与知识发现, 2021, 5(6): 25-35.
[3] 马莹雪,赵吉昌. 自然灾害期间微博平台的舆情特征及演变*——以台风和暴雨数据为例[J]. 数据分析与知识发现, 2021, 5(6): 66-79.
[4] 陈文杰,文奕,杨宁. 基于节点向量表示的模糊重叠社区划分算法*[J]. 数据分析与知识发现, 2021, 5(5): 41-50.
[5] 李明, 李莹, 周庆, 王君. 基于TF-PIDF的网络问答社区中的知识供需研究 *[J]. 数据分析与知识发现, 2021, 5(2): 106-115.
[6] 沈旺, 李世钰, 刘嘉宇, 李贺. 问答社区回答质量评价体系优化方法研究 *[J]. 数据分析与知识发现, 2021, 5(2): 83-93.
[7] 王松, 杨洋, 刘新民. 基于图注意力网络的开放式创新社区用户创意潜在价值发现研究*[J]. 数据分析与知识发现, 2021, 5(11): 89-101.
[8] 蔡永明,刘璐,王科唯. 网络虚拟学习社区重要用户与核心主题联合分析*[J]. 数据分析与知识发现, 2020, 4(6): 69-79.
[9] 陶兴,张向先,郭顺利,张莉曼. 学术问答社区用户生成内容的W2V-MMR自动摘要方法研究*[J]. 数据分析与知识发现, 2020, 4(4): 109-118.
[10] 李文政,顾益军,闫红丽. 基于网络贝叶斯信息准则算法的社区数量预测研究*[J]. 数据分析与知识发现, 2020, 4(4): 72-82.
[11] 李贺,刘嘉宇,沈旺,刘锐,金帅岐. 基于模糊认知图的在线健康社区知识推荐研究*[J]. 数据分析与知识发现, 2020, 4(12): 55-67.
[12] 温彦,马立健,曾庆田,郭文艳. 基于地理信息偏好修正和社交关系偏好隐式分析的POI推荐 *[J]. 数据分析与知识发现, 2019, 3(8): 30-39.
[13] 仇丽青,贾玮,范鑫. 基于重叠社区的影响力最大化算法 *[J]. 数据分析与知识发现, 2019, 3(7): 94-102.
[14] 易明,张婷婷. 大众性问答社区答案质量排序方法研究*[J]. 数据分析与知识发现, 2019, 3(6): 12-20.
[15] 石静,厉臣璐,钱宇星,周利琴,张斌. 国内外健康问答社区用户信息需求对比研究*——基于主题和时间视角的实证分析[J]. 数据分析与知识发现, 2019, 3(5): 1-10.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 2015 《数据分析与知识发现》编辑部
地址:北京市海淀区中关村北四环西路33号 邮编:100190
电话/传真:(010)82626611-6626,82624938
E-mail:jishu@mail.las.ac.cn