一种基于邻近节点影响强度标签传播社区发现方法

doi:10.11925/infotech.1003-3513.2015.04.08

摘要
参考文献
相关文章
Metrics

全文: 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 words： Community detection Social networks Community Label propagation

收稿日期: 2014-09-26

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, DOI：10.11925/infotech.1003-3513.2015.04.08.

链接本文:

http://manu44.magtech.com.cn/Jwk_infotech_wk3/CN/10.11925/infotech.1003-3513.2015.04.08

[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]. 数据分析与知识发现, 2019, 3(7): 94-102.
[2]	易明,张婷婷. 大众性问答社区答案质量排序方法研究^*[J]. 数据分析与知识发现, 2019, 3(6): 12-20.
[3]	石静,厉臣璐,钱宇星,周利琴,张斌. *国内外健康问答社区用户信息需求对比研究^——基于主题和时间视角的实证分析**[J]. 数据分析与知识发现, 2019, 3(5): 1-10.
[4]	吴小兰,章成志. *学术社交媒体视角下学科知识流动规律研究^——以科学网为例**[J]. 数据分析与知识发现, 2019, 3(4): 107-116.
[5]	陆泉,朱安琪,张霁月,陈静. *中文网络健康社区中的用户信息需求挖掘研究^——以求医网肿瘤板块数据为例**[J]. 数据分析与知识发现, 2019, 3(4): 22-32.
[6]	彭昱欣,邓朝华,吴江. 基于社会资本与动机理论的在线健康社区医学专业用户知识共享行为分析^*[J]. 数据分析与知识发现, 2019, 3(4): 63-70.
[7]	吴菊华,王煜,黎明,蔡少云. 基于加权知识网络的在线健康社区用户知识发现^*[J]. 数据分析与知识发现, 2019, 3(2): 108-117.
[8]	伍杰华,沈静,周蓓. 基于迁移成分分析的多层社交网络链接分类^*[J]. 数据分析与知识发现, 2018, 2(9): 88-99.
[9]	钱晓东,李敏. 基于复杂网络重叠社区的电子商务用户复合类型识别^*[J]. 数据分析与知识发现, 2018, 2(6): 79-91.
[10]	郭博,赵隽瑞,孙宇. 社会化问答社区用户行为统计特性及其动力学分析: 以知乎网为例[J]. 数据分析与知识发现, 2018, 2(4): 48-58.
[11]	王飞飞,张生太. 移动社交网络微信用户信息发布行为统计特征分析^*[J]. 数据分析与知识发现, 2018, 2(4): 99-109.
[12]	张凌,罗曼曼,朱礼军. 基于社交网络的信息扩散分析研究^*[J]. 数据分析与知识发现, 2018, 2(2): 46-57.
[13]	李贺,祝琳琳,闫敏,刘金承,洪闯. 开放式创新社区用户信息有用性识别研究^*[J]. 数据分析与知识发现, 2018, 2(12): 12-22.
[14]	程秀峰,张心怡,王宁. 基于CART决策树的网络问答社区新兴话题识别研究^*[J]. 数据分析与知识发现, 2018, 2(12): 52-59.
[15]	李纲,王晓,郭洋. 基于成员合作共现的微信群内部关系研究^*[J]. 数据分析与知识发现, 2018, 2(11): 54-63.

Viewed

Full text

Abstract

Cited

Shared

Discussed