基于节点依赖度和相似社团融合的社团结构发现算法

计算机工程与科学

基于节点依赖度和相似社团融合的社团结构发现算法

聂祥林1,2,张玉梅1,2,吴晓军1,2,吴霞1

(1.陕西师范大学现代教学技术教育部重点实验室,陕西西安 710072)
2.陕西师范大学计算机科学学院,陕西西安 710062)

收稿日期:2015-11-23 修回日期:2016-03-04 出版日期:2017-07-25 发布日期:2017-07-25
基金资助:
国家自然科学基金(11172342,11372167,11502133);陕西省重点科技创新团队项目(2014KTC-18);西安市科技计划项目(CXY1437(1));榆林市科技计划(2014cxy-09,sf13-43,2012 cxy3-6)

A community detection algorithm based on node

dependence and similar community fusion

NIE Xiang-lin1,2,ZHANG Yu-mei1,2,WU Xiao-jun1,2,WU Xia1

(1.Key Laboratory of Modern Teaching Technology of Ministry of Education,Shaanxi Normal University,Xi’an 710072;
2.School of Computer Science,Shaanxi Normal University,Xi’an 710062,China)

Received:2015-11-23 Revised:2016-03-04 Online:2017-07-25 Published:2017-07-25

摘要/Abstract

摘要：

社团结构作为复杂网络的拓扑特性之一具有重要的理论和实践意义。提出一种基于节点依赖度和相似社团融合的社团结构发现算法，首先根据依赖度和相似度的定义将整个网络划分成若干个平均集聚系数较大的局部网络，构成网络的基础骨架社团；然后根据连接度的定义不断将社团边缘的节点和小社团吸收到相应的骨架网络中去，直到所有节点都得到准确的社团划分。算法在Zachary空手道俱乐部网络和海豚社会网络中进行了社团划分实验，并与GN算法和Newman快速算法进行了比较，结果表明该算法可以有效地划分社团边缘的模糊节点，社团划分结果具有较高的准确度。

关键词: 复杂网络, 社团发现, 依赖度, 相似社团

Abstract:

As one of the topological properties of complex networks, the community structure has important theoretical and practical significance. We propose a community detection algorithm based on node dependence and the fusion of similar communities. The algorithm firstly divides the whole network into several local networks with large average clustering coefficients, thus constructing a skeleton of the complex networks. Then according to the definition of connectivity, the algorithm continuously absorbs the edge nodes of the community and small communities into the backbone network until all the nodes are accurately allocated to the community. This algorithm is applied to Zachary Karate Club network and the dolphin social network, and compared with the Girvan-Newman algorithm (GN) and Newman fast algorithm (NFA). The results show that our algorithm can effectively classify fuzzy edge nodes and the result of the community division has high accuracy.

Key words: complex networks, community detection, dependence degree, similar community

聂祥林1,2,张玉梅1,2,吴晓军1,2,吴霞1. 基于节点依赖度和相似社团融合的社团结构发现算法[J]. 计算机工程与科学.

NIE Xiang-lin1,2,ZHANG Yu-mei1,2,WU Xiao-jun1,2,WU Xia1.

A community detection algorithm based on node

dependence and similar community fusion

[J]. Computer Engineering & Science.

[1]	皇甫斐斐, 杨阳, 邓晓懿, . 基于节点影响力的理性节点标签传播算法[J]. 计算机工程与科学, 2022, 44(04): 713-722.
[2]	燕云鸿, 钱晓东. 区块链环境下电商消费者网络多子群混合增长模型构建及特性研究[J]. 计算机工程与科学, 2021, 43(12): 2157-2168.
[3]	张丽, 马静. 融合词语统计特征和语义信息的文本分类方法研究[J]. 计算机工程与科学, 2021, 43(07): 1308-1315.
[4]	张士进, 张胜, 田纪彪, 吴志强, 戴维凯. 基于深度编码器的复杂网络社区发现算法 #br# [J]. 计算机工程与科学, 2020, 42(09): 1640-1648.
[5]	潘曙灿, 许青林. 融合特征向量中心性与标签熵的标签传播算法[J]. 计算机工程与科学, 2020, 42(08): 1489-1499.
[6]	徐曼1,2,3，鲁富荣1,2,3，马国帅1,2,3，钱宇华1,2,3. 基于信息传播影响因素的边重要性度量方法[J]. 计算机工程与科学, 2020, 42(01): 55-63.
[7]	杨迪，刘琰，陈静，张伟丽. 基于模体的目标区域网络拓扑划分方法[J]. 计算机工程与科学, 2019, 41(03): 466-478.
[8]	李慧，杨青泉，王慧慧. 一种基于局部扩展优化的重叠社区发现算法[J]. 计算机工程与科学, 2018, 40(12): 2258-2264.
[9]	付丹龙1，朱淑华1，原智峰2，梁倬骞1,2，邓原2. 基于不同子网络级联机制的相依网络鲁棒性研究[J]. 计算机工程与科学, 2018, 40(03): 439-444.
[10]	吕铃，彭雅丽，曾欣怡,杨雨鑫，黄明和. 公共自行车复杂网络可达性指标潜力评价模型[J]. 计算机工程与科学, 2018, 40(01): 175-183.
[11]	董建亮，赵文涛，李方,黄心昊. 一种基于标签传播算法的关键链路探测方法[J]. 计算机工程与科学, 2017, 39(11): 2022-2027.
[12]	伍杰华1,2,沈静1,周蓓1. 改进朴素贝叶斯模型的复杂网络关系预测[J]. 计算机工程与科学, 2017, 39(10): 1825-1831.
[13]	张其林1，董政呈2，赵永标1 . 一种具有核心-边缘结构的无标度网络演化模型[J]. 计算机工程与科学, 2017, 39(03): 500-504.
[14]	曾振华1，毕贵红2，张寿明1，蔡子龙2. 语言竞争社会仿真模型与计算实验[J]. 计算机工程与科学, 2016, 38(12): 2514-2528.
[15]	张红，王小军. 软件体系结构脆性分析与验证[J]. 计算机工程与科学, 2016, 38(11): 2254-2260.