复杂网络局部社区挖掘的节点接近度算法

计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (17): 38-42.

复杂网络局部社区挖掘的节点接近度算法

方平1，3，4，李芝棠2，3，4，涂浩2，4，郭正彪3，4

1.海军航空工程学院青岛校区，山东青岛 266041
2.华中科技大学网络与计算中心，武汉 430074
3.华中科技大学计算机科学与技术学院，武汉 430074
4.华中科技大学下一代互联网接入系统国家工程实验室，武汉 430074

出版日期:2013-09-01 发布日期:2013-09-13

Closeness degree of node algorithm for mining local community from complex networks

FANG Ping1，3，4, LI Zhitang2，3，4, TU Hao2，4, GUO Zhengbiao3，4

1.Qingdao Branch, Naval Aeronautical and Astronautical University, Qingdao, Shandong 266041, China
2.Network Center, Huazhong University of Science and Technology, Wuhan 430074, China
3.College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
4.National Engineering Laboratory for Next Generation Internet Access System, Huazhong University of Science and Technology, Wuhan 430074, China

Online:2013-09-01 Published:2013-09-13

摘要/Abstract

摘要： 为了准确、快速地发现大规模复杂网络中的局部社区，提出了一种基于节点接近度的局部社区发现算法。该算法以最大度节点作为起始节点，利用节点接近度和局部社区Q值不断搜索其邻居节点，将接近度最大的节点加入初始社区形成新的初始社区；同时，该算法也可以应用于复杂网络全局社区结构的划分。对2个典型复杂网络进行了局部社区挖掘分析，实验结果表明，该算法能够有效识别隐藏在实验网络中的局部社区。针对稀疏网络，该算法的时间复杂度为O（nlog（n）），n为网络节点数。

关键词: 复杂网络, 局部社区发现, 节点接近度

Abstract: To make the local community detection faster and more accurate, this paper proposes an algorithm for detecting local community structures in complex networks based on closeness degree of node. The proposed method, which uses the maximal closeness degree of node and the local community’s Q value, starts from the maximum degree node of the network and detects the community it belongs to by searching the neighbor nodes. It is also applicable for global community structure detecting. The experiments on two typical complex networks show that the algorithm can effectively mine the intrinsic local community structure in networks. The time complexity of the algorithm is O（nlog（n）） on a sparse graph, where n is the number of nodes.

Key words: complex network, local community detection, closeness degree of node

方平1，3，4，李芝棠2，3，4，涂浩2，4，郭正彪3，4. 复杂网络局部社区挖掘的节点接近度算法[J]. 计算机工程与应用, 2013, 49(17): 38-42.

FANG Ping1，3，4, LI Zhitang2，3，4, TU Hao2，4, GUO Zhengbiao3，4. Closeness degree of node algorithm for mining local community from complex networks[J]. Computer Engineering and Applications, 2013, 49(17): 38-42.

[1]	马满福，郭晨彪，李勇，张钟颖，张强，王常青. 基于结构熵的注意力流网络异构性研究[J]. 计算机工程与应用, 2021, 57(23): 98-105.
[2]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[3]	李金海，何有世，张鹏. 融合情境语义推理及社会网络的团购推荐研究[J]. 计算机工程与应用, 2021, 57(18): 163-171.
[4]	王安，顾益军. 基于社区划分的节点重要性评估方法[J]. 计算机工程与应用, 2020, 56(8): 42-48.
[5]	陈杰，程胜，徐梦，史豪斌. 面向医疗辅助诊断的可视化多属性决策方法[J]. 计算机工程与应用, 2020, 56(8): 249-255.
[6]	赵亮，朱征宇. 融入K-核迭代因子的重叠社区发现算法[J]. 计算机工程与应用, 2020, 56(3): 61-67.
[7]	杜轻，辛守庭，雷新宇，于海涛. 基于脑网络和TSK模糊系统的癫痫脑电识别[J]. 计算机工程与应用, 2020, 56(2): 133-140.
[8]	易成岐，郭鑫，童楠楠，窦悦，陈东，王建冬. 基于启发式社团发现模型的创新态势研判算法[J]. 计算机工程与应用, 2020, 56(15): 74-79.
[9]	蔡菲，张鑫，牟晓慧，陈杰，蔡珣. 深度非负矩阵分解的链路预测方法研究[J]. 计算机工程与应用, 2020, 56(15): 153-161.
[10]	张昕，郭阳. 复杂网络中的一种介度熵抗毁性度量方法[J]. 计算机工程与应用, 2020, 56(12): 105-111.
[11]	盛津芳，刘家广，王斌. 基于Katz自动编码器的城市路网链路预测模型[J]. 计算机工程与应用, 2019, 55(8): 116-123.
[12]	姚蓉1，杨雄1，杨鹏飞1，阴桂梅1，2，李海芳1. 精分EEG脑网络同步稳定性研究[J]. 计算机工程与应用, 2019, 55(5): 60-64.
[13]	陈紫扬，张月霞. 结合二层节点度和聚类系数的链路预测算法[J]. 计算机工程与应用, 2019, 55(23): 40-44.
[14]	张昕，严沛，郭阳，王慧慧. 基于k-shell的复杂网络最短路径近似算法[J]. 计算机工程与应用, 2019, 55(14): 54-60.
[15]	朱晓霞，胡小雪. 基于改进k-shell算法的节点影响力的识别[J]. 计算机工程与应用, 2019, 55(1): 35-41.