基于改进的标签传播算法的网络聚类方法

doi:10.13229/j.cnki.jdxbgxb20171019

摘要/Abstract

摘要： 采用传统标签传播算法实现网络聚类时,由于标签初始分配过程随机、节点选择过程随机、且标签更新顺序随机的原因,影响聚类结果。为此,提出一种新的基于改进标签传播算法的网络聚类方法,即用图对网络进行描述,并为网络聚类提供基础。改进标签传播算法过程如下:求出网络中任意两节点拥有最大公共邻居的平均阶数,把相似性最高的节点和邻居节点看作初始核心社团,为其分配初始标签;引入基于随机游走的相似度矩阵,令节点选择和自身相似度最高的节点拥有的标签;通过H指数对标签算法更新顺序进行改进;依据改进后结果,按照标签传播算法网络聚类过程实现聚类。实验结果表明,本文所提的网络聚类方法具有更高的准确性和稳定性。

关键词: 计算机应用, 节点, 标签, 传播算法, 网络聚类, 相似度

Abstract: Using traditional label propagation algorithm in network clustering, the initial allocation of taps, the node selection and updating order of the labels are all random processes, which affect the clustering results. To overcome this problem, a new method of network clustering based on improved label propagation algorithm is proposed, in which the graph is used to describe the network and provide the basis for the network clustering. The process of the improved label propagation algorithm includes the following steps. First, the average malpractice in the network order of any two nodes with the largest common neighbor number is obtained. Second, the most similar node and neighbor node are taken as the initial core community and its initial label is assigned. Third, the random walk similarity matrix is introduced based on the node selection and the label of the node with the highest similarity. Fourth, by using the H index on the label algorithm, the update order is improved. Finally, according to the improved result, the clustering process is realized according to the clustering process of the label propagation algorithm network. Experimental results show that the proposed network clustering method has higher accuracy and stability.

Key words: computer application, node, label, propagation algorithm, network clustering, similarity

中图分类号:

TP301

桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.

GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.

参考文献

[1] 孙生才, 范菁, 陈明木,等. 基于H指数的改进标签传播算法研究[J]. 云南民族大学学报:自然科学版, 2017, 26(4):317-321.
Sun Sheng-cai, Fan Jing, Chen Ming-mu, et al.Research on improved label propagation algorithm based on H-index[J]. Journal of Yunnan Minzu University(Natural Science Edition), 2017, 26(4):317-321.
[2] 郝晓丽, 张靖. 基于改进自适应聚类算法的RBF神经网络分类器设计与实现[J]. 计算机科学, 2014, 41(6):260-263.
Hao Xiao-li, Zhang Jing.Design and implementation of RBF neural network classifier based on improved adaptive clustering algorithm[J]. Computer Science, 2014, 41(6):260-263.
[3] 陈羽中, 方明月, 郭文忠. 面向微博热点话题发现的多标签传播聚类方法研究[J]. 模式识别与人工智能, 2015, 28(1):1-10.
Chen Yu-zhong, Fang Ming-yue, Guo Wen-zhong.Research on multi-label propagation clustering method for micro-blog hot topic discovery[J]. Pattern Recognition and Artificial Intelligence, 2015, 28(1):1-10.
[4] 张健沛, 邓琨, 杨静,等. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6):1113-1118.
Zhang Jian-pei, Deng Kun, Yang Jing, et al.Community identification method based on link label propagation in complex networks[J]. Electronic Journal, 2015, 43(6):1113-1118.
[5] 孙沁瑶, 谢涛, 于重重,等. 图像标签传播标注算法的研究[J]. 计算机仿真, 2016, 33(8):229-233.
Sun Qin-yao, Xie Tao, Yu Chong-chong, et al.Research on image label propagation annotation algorithm[J]. Computer Simulation, 2016, 33(8):229-233.
[6] 张康, 顾幸生. 基于近邻传播的改进组搜索优化聚类算法[J]. 系统仿真学报, 2015, 27(9):2066-2074.
Zhang Kang, Gu Xing-sheng.Improved group search optimization clustering algorithm based on neighborhood propagation[J]. System Simulation Journal, 2015, 27(9):2066-2074.
[7] 夏磊, 张乐君, 国林,等. 节点相似度标签传播在社会网络中的应用研究[J]. 计算机工程与应用, 2014, 50(14):103-109.
Xia Lei, Zhang Le-jun, Guo Lin, et al.Application of node similarity label propagation in social network[J]. Computer Engineering and Application, 2014, 50(14):103-109.
[8] 王旭仁, 李娜, 何发镁,等. 基于改进聚类算法的网络舆情分析系统研究[J]. 情报学报, 2014, 33(5):530-537.
Wang Xu-ren, Li Na, He Fa-mei, et al.Research on network public opinion analysis system based on improved clustering algorithm[J]. Journal of Information, 2014, 33(5):530-537.
[9] 汪西莉, 蔺洪帅. 最小代价路径标签传播算法[J]. 计算机学报, 2016, 39(7):1407-1418.
Wang Xi-li, Lin Hong-shuai.Minimum cost path label propagation algorithm[J]. Journal of Computer Science, 2016, 39(7):1407-1418.
[10] 喻金平, 郑杰, 梅宏标. 基于改进人工蜂群算法的K均值聚类算法[J]. 计算机应用, 2014, 34(4):1065-1069.
Yu Jin-ping, Zheng Jie, Mei Hong-biao.K mean clustering algorithm based on improved artificial bee colony algorithm[J]. Computer Application, 2014, 34(4):1065-1069.
[11] 唐丹, 张正军, 王俐莉. 基于改进的近邻传播聚类算法的Gap统计研究[J]. 计算机技术与发展, 2017, 27(1):182-185.
Tang Dan, Zhang Zheng-jun, Wang Li-li.Gap statistical research based on improved near neighbor propagation clustering algorithm[J]. Computer Technology and Development, 2017, 27(1):182-185.
[12] 陈季梦, 陈佳俊, 刘杰,等. 基于结构相似度的大规模社交网络聚类算法[J]. 电子与信息学报, 2015, 37(2):449-454.
Chen Ji-meng, Chen Jia-jun, Liu Jie, et al.Clustering algorithm for large scale social networks based on structural similarity[J]. Journal of Electronics and Information, 2015, 37(2):449-454.
[13] 王永,万潇逸,陶娅芝,等.基于K-medoids项目聚类的协同过滤推荐算法[J]. 重庆邮电大学学报:自然科学版,2017,29(4):521-526.
Wang Yong,Wan Xiao-yi,Tao Ya-zhi,et al.Collaborative filtering recommendation algorithm based on K-medoids item clustering[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2017,29(4):521-526.
[14] 杨玉梅. 基于信息熵改进的 K-means 动态聚类算法[J].重庆邮电大学学报:自然科学版,2016,28(2):254-259.
Yang Yu-mei.Improved K-means dynamic clustering algorithm based on information entropy[J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2016,28(2):254-259.

相关文章 15

[1]	刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2]	王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3]	金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5]	刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6]	周彦果,张海林,陈瑞瑞,周韬. 协作网络中采用双层博弈的资源分配方案[J]. 吉林大学学报(工学版), 2018, 48(6): 1879-1886.
[7]	欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[8]	刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[9]	刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10]	车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11]	王旭, 欧阳继红, 陈桂芬. 基于垂直维序列动态时间规整方法的图相似度度量[J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[12]	赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[13]	黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[14]	傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[15]	曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed