基于节点相似性的并行启发式网络拓扑结构发现算法  

Parallel heuristic network topology discovery algorithm based on node similarity

作　　者：董振亮 陈志宾[3] 张华[4] 何文海[2] 孙丽丽[2] DONG Zhenliang;CHEN Zhibin;ZHANG Hua;HE Wenhai;SUN Lili(Department of Computer Science,North China Electric Power University,Baoding 071003,Hebei,China;Information Management Department,Hebei Education and Examination Institute,Shijiazhuang 050091,Hebei,China;Institute of Applied Mathematics,Hebei Academy of Sciences,Shijiazhuang 050081,Hebei,China;Public Course Department,Shijiazhuang Medical College,Shijiazhuang 050000,Hebei,China)

机构地区：[1]华北电力大学计算机系,河北保定071003 [2]河北省教育考试院信息管理部,河北石家庄050091 [3]河北省科学院应用数学研究所,河北石家庄050081 [4]石家庄医学高等专科学校公共课部,河北石家庄050000

出　　处：《沈阳工业大学学报》2023年第6期692-696,共5页Journal of Shenyang University of Technology

基　　金：河北省科技厅自然科学研究项目(14210116D,18210316D);河北省教育厅人文社会科学研究项目(KSZX201801)。

摘　　要：针对网络社区发现算法的低精确度与高复杂度问题,在节点相似性的基础上提出了一种适用于复杂网络的社区发现算法。利用邻接矩阵和经典决策规则,制定具有较高可靠性和准确性的相似性判定准则,实现网络拓扑中相邻节点之间关系的量化与计算。通过引入具有较少冲突的哈希表,提出具有并行运算结构的启发式社区发现算法,完成对复杂网络拓扑结构的高质量检测。仿真测试结果表明,与经典的Jaccard准则发现算法相比,基于节点相似性的发现算法具有更高的发现精确度及时间效率。Aiming at the low accuracy and high complexity of network community discovery algorithm,a community discovery algorithm based on node similarity and suitable for complex networks was proposed.Using the adjacency matrix and quadratic decision rules,the similarity judgment criteria with high reliability and accuracy were formulated to realize the quantification and calculation of the relationship among adjacent nodes in the network topology.By introducing a hash table with fewer conflicts,a heuristic community discovery algorithm with parallel operation structure was proposed to complete the high-quality detection of complex network topology.The simulation results show that the discovery algorithm based on node similarity has higher discovery accuracy and time efficiency than the classical Jaccard criterion discovery algorithm.

关 键 词：复杂网络 拓扑结构 Jaccard准则 动态网络 社区发现 节点相似性 邻接矩阵 二次决策准则 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]