基于多层次灰色关联分析的复杂网络节点排序模型

摘要/Abstract

摘要：

复杂网络节点重要性是研究复杂网络特性的重要方面之一,被广泛应用于数据挖掘、Web 搜索、社会网络分析等众多研究领域。在选取评估节点重要性指标时,考虑到普通聚类系数仅能衡量网络节点聚类的疏密度,不能衡量聚类的规模,提出了修正的聚类系数;同时，选取了Erdos数和介数两个指标来综合衡量网络节点重要性,建立多层次灰色关联分析模型,确定出各个节点与理想节点的关联度,实现对复杂网络节点的排序。模型不仅考虑到度、路径距离对节点排序的影响,而且也考虑到每个节点聚类程度对节点排序的影响。通过与实际网络和其他方法的排序结果对比,模型能够准确找到复杂网络的核心节点,并且排序结果真实反映了节点依次的重要程度。

关键词: 复杂网络, 节点重要性排序, 多层次灰色关联分析, 修正的聚类系数, Erdos数, 介数

Abstract:

Nodes importance ranking in complex network is one of the most important aspects of studying the properties of complex network. It has been widely used in data mining, web search, analysis of social network and so on. When selecting the node importance evaluation index, considering that the average clustering coefficient can only measure a network node clustering density, and not measure the clustering size, the amended clustering coefficient is proposed. Meanwhile, the other two indexes, the Erdos number and the betweenness,are selected to evaluate node importance in networks. A multilevel gray relational analysis model is established to identify the correlation degree between node and the optimal node,and to sort nodes of complex networks. The model considers the node sorting influence factors involving not only the degree of nodes and the path distance but also the degree of node clustering.Compared with the real network and other methods of sorting results,the model can accurately find the core nodes of the complex network,and the sorted results truly reflect the important degree of nodes.

Key words: complex network;nodes importance ranking;multilevel gray relational analysis;amended clustering coefficient;Erdos number;betweenness

曹卫东,刘红霞. 基于多层次灰色关联分析的复杂网络节点排序模型[J]. J4, 2014, 36(06): 1165-1171.

CAO Weidong,LIU Hongxia. Nodes importance ranking model of complex
network based on multi-level gray relational analysis [J]. J4, 2014, 36(06): 1165-1171.

参考文献

［1］Watts D J,Strogatz S H. Collective dynamics of smallworld networks［J］. Nature,1998,393:440442.
［2］Guo Lei, Xu Xiaoming. Complex network［M］.Shanghai: Shanghai Science and Technology Education Press,2006.(in Chinese)
［3］Wang Xiaofan,Li Xiang,Chen Guanrong.Complex network theory and its application［M］.Beijing:Tsinghua University Press,2006.(in Chinese)
［4］Chen J,Sun L F. Evaluation of node importance in complex networks［J］.Journal of Southwest Jiaotong University,2009,44(3):426429.(in Chinese)
［5］Tan Y J, Wu J, Deng H Z. Evaluation method for node importance based on node contraction in complex networks［J］. Systems Engineering —Theory & Practice,2006,11(11):7983.(in Chinese)
［6］Liu Y,Gu X P. Node importance assessment based skeletonnetwork reconfiguration［J］. Proceedings of the CSEE,2007,27（10）：2026.(in Chinese)
［7］Wu J,Tan Y J,Deng H Z, et al. Evaluating node importance considering cxascading failure in complex loadnetworks［J］. Journal of Chinese Computer Systems, 2007,28(4):627630.(in Chinese)
［8］He J J,Li R F. Modified nodes ranking method using random walk model［J］.Computer Engineering and Applications,2011,47（12）：8789.(in Chinese)
［9］West D B.Introduction to graph theory［M］.Upper Saddle River：Prentice Hall,2001.
［10］Washio T,Motoda H.State of the art of graphbased data mining［J］.SIGKDD,2003,5（1）：5968.
［11］Freeman L C. A set of measures of centrality based upon betweenness［J］. Socicometry,1977,40(1):3541.
［12］Chen Y,Hu A Q,Hu J, et al. Evaluation method for link importance in communication networks［J］. High Technology Letters, 2004(1):573575.(in Chinese)
［13］Page L,Brin S,Motwani R,et al.The PageRank citation ranking：Bringing order to the WEB［Z］.1998.
［14］Zhu Tian. Research on the node role of social network and population evolution［D］.Beijing:Beijing University of Posts and Telecommunications,2011.
［15］Zhou Bin. Community structure mining and applied research of complex networks［D］.Nanning:Guangxi Normal University,2010.
［16］Cai Hua.Research on social mining algorithm［D］.Jilin:Jilin University,2008.［17］Scott J. Social network Analysis［M］.Liu Jun Translated.Chongqing:Chongqing University Press,2007.
［18］Juxe L, Kevin J L, Anirban D, er al. statistical ProPerties of cornmunity structure in large soeial and information network［C］∥Proc of the 17th Intemational Conference on World Wide Web,2008:695704.
［19］Jiang Qiyuan,Xie Jinxing,Ye Jun.Mathematical model［M］.third ed.Beijing: Higher Education Press, 2003.
［20］Deng Julong.Gray system ［M］. Beijing: National Defense Industry Press, 1985.
［21］Deng Julong.Grey prediction and grey decision［M］. Wuhan:Huazhong University of Science and Technology Publishing House,2005.
［22］Liu Sifeng,Guo Tianbang,Dang Yaoguo,et al.Grey system theory and its application ［M］. Beijing: Science Press,1999.

附中文参考文献：
［2］郭雷,许晓鸣. 复杂网络［M］. 上海:上海科技教育出版社,2006.
［3］汪小帆,李翔,陈关荣. 复杂网络理论及其应用［M］.北京：清华大学出版社,2006.
［4］陈静,孙林夫.复杂网络中节点重要度评估［J］,西南交通大学学报,2009,44（3）:426429.
［5］谭跃进,吴俊,邓宏钟. 复杂网络中节点重要度评估的节点收缩方法［J］.系统工程理论与实践,2006,11(11):7983.
［6］刘艳,顾雪平.基于节点重要度评价的骨架网络重构［J］.中国电机工程学报,2007,27（10）：2026.
［7］吴俊,谭跃进,邓宏钟,等.考虑级联失效的复杂负载网络节点重要度评估［J］.小型微型计算机系统,2007,28(4):627630.
［8］何建军,李仁发. 改进的随机游走模型节点排序方法［J］.计算机工程与应用,2011,47（12）：8789.
［12］陈勇,胡爱群,胡俊等.通信网络中最重要节点确定方法［J］.高技术通讯,2004,1:573575.
［14］朱天,社会网络中节点角色以及群体演化研究［D］.北京:北京邮电大学,2011.
［15］周斌,复杂网络的社团结构挖掘及应用研究［D］.南宁:广西师范大学,2010.
［16］才华,社会挖掘算法研究［D］.吉林:吉林大学,2008.
［17］Scott J．社会网络分析法［M］．刘军，译．重庆：重庆大学出版社，2007.
［19］姜启源、谢金星、叶俊,数学模型［M］.第三版.北京：高等教育出版社,2003.
［20］邓聚龙.灰色系统［M］.北京：国防工业出版社,1985.
［21］邓聚龙.灰预测与灰决策［M］. 武汉：华中科技大学出版社,2005.
［22］刘思蜂，郭天榜，党耀国,等.灰色系统理论及其应用［M］.北京：科学出版社,1999.

[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,2,吴晓军1,2,吴霞1. 基于节点依赖度和相似社团融合的社团结构发现算法[J]. 计算机工程与科学, 2017, 39(07): 1273-1280.
[14]	张其林1，董政呈2，赵永标1 . 一种具有核心-边缘结构的无标度网络演化模型[J]. 计算机工程与科学, 2017, 39(03): 500-504.
[15]	曾振华1，毕贵红2，张寿明1，蔡子龙2. 语言竞争社会仿真模型与计算实验[J]. 计算机工程与科学, 2016, 38(12): 2514-2528.