基于节点多属性相似性聚类的社团划分算法

doi:10.19678/j.issn.1000-3428.0055070

计算机工程 ›› 2020, Vol. 46 ›› Issue (7): 84-90,97. doi: 10.19678/j.issn.1000-3428.0055070

基于节点多属性相似性聚类的社团划分算法

邱少明¹, 於涛¹, 杜秀丽¹, 陈波²

1. 大连大学通信与网络重点实验室, 辽宁大连 116622;
2. 岭南师范学院信息工程学院, 广东湛江 524048

收稿日期:2019-05-30 修回日期:2019-07-23 发布日期:2019-08-09
作者简介:邱少明(1977-),男,副教授,主研方向为智能故障诊断、复杂网络;於涛,硕士研究生;杜秀丽、陈波,教授、博士。
基金资助:
装备发展部预研基金（6140002010101，6140001030111）。

Community Division Algorithm Based on Similarity Clustering of Node Multiple Attribute

QIU Shaoming¹, YU Tao¹, DU Xiuli¹, CHEN Bo²

1. Key Laboratory of Communication and Network, Dalian University, Dalian, Liaoning 116622, China;
2. School of Information Engineering, Lingnan Normal University, Zhanjiang, Guangdong 524048, China

Received:2019-05-30 Revised:2019-07-23 Published:2019-08-09

摘要/Abstract

摘要： 针对当前社团划分算法存在划分方式单一和划分结果准确度低等问题，提出一种基于节点多属性相似性聚类的社团划分算法SM-CD。根据社会网络特性定义网络节点的结构属性与自身属性，通过调整两类属性在网络中所占的权重计算网络节点之间的相似度矩阵，并将网络节点按照相似度和模块度指标划分为不同的社团。在Zachary和Football真实网络数据集上的实验结果表明，SM-CD算法相比Newman、GN等算法具有更高的社团划分准确率。

关键词: 复杂网络, 社团划分, 节点属性, 相似度矩阵, 聚类

Abstract: Existing community division algorithms lack diversity in the division method,and division results are not accurate.To address the problem,this paper proposes a community division algorithm,SM-CD,on the basis of similarity clustering of multiple attributes of nodes.The algorithm uses social network features to define the structure attributes of nodes and the attributes of oneself.By adjusting the weight of two kinds of attributes in network,the similarity matrix of network nodes is calculated.Then the nodes are divided into different communities according to similarity and modularity.Experimental results on the real network data from Zachary and Football show that SM-CD has a higher accuracy rate in community division than Newman,GN and other algorithms.

Key words: complex network, community division, node attribute, similarity matrix, clustering

中图分类号:

TP393

邱少明, 於涛, 杜秀丽, 陈波. 基于节点多属性相似性聚类的社团划分算法[J]. 计算机工程, 2020, 46(7): 84-90,97.

QIU Shaoming, YU Tao, DU Xiuli, CHEN Bo. Community Division Algorithm Based on Similarity Clustering of Node Multiple Attribute[J]. Computer Engineering, 2020, 46(7): 84-90,97.

https://www.ecice06.com/CN/Y2020/V46/I7/84

参考文献

[1] LI Peng,HE Tingting,HU Xiaohua.A novel protein complex identification algorithm based on Connected Affinity Clique Extension(CACE)[J].IEEE Transactions on Nanobioscience,2014,13(2):89-96.
[2] ANDREAS A,LOUKIANOS S,MARTIN-LOPEZ D,et al.Detection of interictal discharges with convolutional neural networks using discrete ordered multichannel intracranial EEG[J].IEEE Transactions on Neural Systems and Rehabilitation Engineering,2013,25(12):2285-2294.
[3] JENNIFER G,HARISH C,ADAM W,et al.Node dominance:revealing community and core-periphery structure in social networks[J].IEEE Transactions on Signal and Information Processing over Networks,2016,2(2):186-199.
[4] WANG Xiaofan,LIU Yabing.Overview of algorithms for detecting community structure in complex networks[J].Journal of University of Electronic Science and Technology of China,2009,38(5):537-543.(in Chinese) 汪小帆,刘亚并.复杂网络中的社团结构算法综述[J].电子科技大学学报,2009,38(5):537-543.
[5] NEWMAN M E J.Analysis of weighted networks[J].Physical Review E,2004,70(5):53-131.
[6] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics Theory and Experiment,2015,30(2):155-168.
[7] KERNIGHAN B W,LIN S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,1970,49(2):291-307.
[8] CAPOCCI A,SERVEDIO V D P,CALDARELLI G,et al.Detecting communities in large networks[J].Computer Science,2004,3243:181-187.
[9] BORGATTI S P.Centrality and network flow[J].Social Networks,2005,27(1):55-71.
[10] LUO Wenjian,ZHANG Daofu,JIANG Hao,et al.Local community detection with the dynamic membership function[J].IEEE Transactions on Fuzzy Systems,2018,26(5):3136-3150.
[11] KRIEGEL H P,KRÖGER P,SANDER J,et al.Density-based clustering[J].Data Mining and Knowledge Discovery,2011,1(3):231-240.
[12] LEICHT E A,HOLME P,NEWMAN M E J.Vertex similarity in network[J].Physical Review E,2006,73(2):26-45.
[13] TAN Yuejin,WU Jun,DENG Hongzhong.Evaluation method for node importance based on node contraction in complex networks[J].Systems Engineering—Theory & Practice,2016,26(11):79-83.(in Chinese) 谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J].系统工程理论与实践,2016,26(11):79-83.
[14] CHEN Lingjiao,ZHANG Zike,LIU Jinhu,et al.A vertex similarity index for better personalized recommendation[J].Physica A:Statistical Mechanics and Its Applications,2017,466:607-615.
[15] LUO Mingwei,YAO Hongliang,LI Junzhao,et al.A hierarchical division algorithm for community based on node dissimilarity[J].Computer Engineering,2014,40(1):275-279.(in Chinese)罗明伟,姚宏亮,李俊照,等.一种基于节点相异度的社团层次划分算法[J].计算机工程,2014,40(1):275-279.
[16] 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.
[17] 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):36-76.
[18] WEI Qingjie,LI Jingteng,WANG Yu.Detection algorithm for microblogging networks community based on user closeness[J].Computer Applications and Software,2016,33(9):254-258.(in Chinese)韦庆杰,李京腾,汪雨.基于用户紧密度的微博网络社区发现算法[J].计算机应用与软件,2016,33(9):254-258.
[19] ZHANG Meng,LI Lingjuan.Community division algorithm based on improved Jaccard similarity coefficient matrix[J].Journal of Nanjing University of Posts and Telecommunica-tions(Natural Science),2018,38(6):96-102.(in Chinese)张猛,李玲娟.基于改进的Jaccard相似系数矩阵的社团划分算法[J].南京邮电大学学报(自然科学版),2018,38(6):96-102.
[20] ZHAO Wentao,ZHAO Haohao,MENG Lingjun.Local community detection algorithm based on node cohesive clustering coefficient[J].Computer Applications and Software,2016,33(12):270-274.(in Chinese)赵文涛,赵好好,孟令军.基于节点内聚系数的局部社团发现算法[J].计算机应用与软件,2016,33(12):270-274.
[21] CHEN Dongming,WANG Yunkai,HUANG Xinyu,et al.Community detection algorithm for complex networks based on group density[J].Journal of Northeastern University(Natural Science),2019,40(2):186-191.(in Chinese)陈东明,王云开,黄新宇,等.基于社团密合度的复杂网络社团发现算法[J].东北大学学报(自然科学版),2019,40(2):186-191.

选择文件类型/文献管理软件名称

选择包含的内容

基于节点多属性相似性聚类的社团划分算法

Community Division Algorithm Based on Similarity Clustering of Node Multiple Attribute

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	徐明亮, 李芳媛, 马浩然, 何飞. 大规模神经记录的峰电位聚类算法(特邀)[J]. 计算机工程, 2024, 50(6): 1-34.
[2]	胡傲然, 陈晓红. 基于多样性与一致性的单步多视图聚类[J]. 计算机工程, 2024, 50(5): 51-61.
[3]	马越, 温蜜. 基于多尺度LDTW和TCN的空间负荷预测方法[J]. 计算机工程, 2024, 50(3): 106-113.
[4]	宋华伟, 李升起, 万方杰, 卫玉萍. 非独立同分布场景下的联邦学习优化方法[J]. 计算机工程, 2024, 50(3): 166-172.
[5]	王丽娟, 邢津萍, 尹明, 郝志峰, 蔡瑞初, 温雯. 基于一致性图的权重自适应多视角谱聚类算法[J]. 计算机工程, 2024, 50(2): 122-131.
[6]	刘思慧, 高全学, 宋伟, 谢德燕. 基于加权张量低秩约束的多视图谱聚类[J]. 计算机工程, 2024, 50(1): 129-137.
[7]	郑美光, 杨泳. 基于互信息软聚类的个性化联邦学习算法[J]. 计算机工程, 2023, 49(8): 20-28.
[8]	李泽水, 冀俊忠, 杨翠翠. 基于边权重信息深度网络嵌入的PPIN功能模块检测[J]. 计算机工程, 2023, 49(8): 69-76.
[9]	江雨燕, 陶承凤, 李平. 数据增强和自适应自步学习的深度子空间聚类算法[J]. 计算机工程, 2023, 49(8): 96-103, 110.
[10]	邱天晨, 郑小盈, 祝永新, 封松林. 面向非独立同分布数据的联邦学习架构[J]. 计算机工程, 2023, 49(7): 110-117.
[11]	位雅, 张正军, 何凯琳, 唐莉. 基于相对密度的密度峰值聚类算法[J]. 计算机工程, 2023, 49(6): 53-61.
[12]	戴浩磊, 黄永慧, 周郭许. 基于超图正则化非负张量链分解的聚类分析[J]. 计算机工程, 2023, 49(6): 81-89.
[13]	高小方, 原玉梁, 温静, 白雪飞. 面向相交多流形聚类的标签传播算法[J]. 计算机工程, 2023, 49(6): 90-98.
[14]	李晓腾, 张盼盼, 勾智楠, 高凯. 基于多任务学习的多模态命名实体识别方法[J]. 计算机工程, 2023, 49(4): 114-119.
[15]	白首圳, 陈美娟. 面向工业互联网的区块链分层分片研究[J]. 计算机工程, 2023, 49(3): 58-66,79.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于节点多属性相似性聚类的社团划分算法

Community Division Algorithm Based on Similarity Clustering of Node Multiple Attribute

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价