能力与权力:大规模复杂网络重要节点识别的二重异质指标及算法  

Capability and authority:A dual-heterogeneous index and algorithm for important nodes identification in large scale complex networks

作　　者：齐林[1,2] 张健 黎晓奇[3] 王宗水 QI Lin;ZHANG Jian;LI Xiaoqi;WANG Zongshui(School of Economics and Management,Beijing Information S＆T University,Beijing 100192,China;Beijing Key Laboratory of Big Data Decision-making for Green Development,Beijing 109192,China;National Academy of Innovation Strategy,China Association for Science and Technology,Beijing 100863,China;School of Economics and Management,University of Chinese Academy of Sciences,Beijing 100190,China)

机构地区：[1]北京信息科技大学经济管理学院,北京100192 [2]绿色发展大数据决策北京市重点实验室,北京100192 [3]中国科协创新战略研究院,北京100863 [4]中国科学院大学经济与管理学院,北京100190

出　　处：《系统工程理论与实践》2018年第7期1842-1852,共11页Systems Engineering-Theory & Practice

基　　金：北京市社会科学基金研究基地项目(15JDJGC042);北京市教委科研计划项目(KM201711232016)~~

摘　　要：为快速识别大规模复杂网络中的重要节点，本研究将人类社会普遍存在的两类不平等映射为节点在网络中的能力与权力的二重异质性，设计了评价复杂网络节点重要度的DH指标，构造了用于DH指标快速分布式计算的并行随机距离渐进（parallel random distance approach，简称PRDA）算法．通过网络最大连通率、网络均衡熵、算法有效性和算法效率的评价实验验证DH指标及PRDA算法的有效性，得出结论如下：DH指标在识别重要节点时能适应不同拓扑特征的复杂网络，识别性能优于或同于时间复杂度更高的介数；PRDA估计算法在最短路径获得概率P=1—10^-1.5。的水平上得到的节点效率估计值^ηi与真实值ηi的Pearson相关系数在0．975以上，且在大规模网络上进行节点效率估计结果更可靠；在Apache Spark并行内存计算环境中应用时间复杂度为O（n^2／l）的PRDA算法求解DH指标耗时远小于介数求解耗时，这表明算法的时间特性也适于大规模网络．In order to identify important nodes in large-scale complex networks rapidly, this study maps the two types of universal inequality in human society as the dual-heterogeneities of the nodes＇ capability and authority in the networks and designs the DH index to evaluate the importance of nodes. Moreover, a parallel random distance approach （PRDA） algorithm is constructed for distributed calculation of DH index. The validity of DH index and PRDA algorithm is verified by the experiments of network maximum connectivity, network equilibrium entropy, algorithm validity and algorithm efficiency. The conclusions are as follows： The DH indicator adapts different topological complex networks during important nodes identification and shows the same or better performance than betweenness centrality which has a much higher time complexity. The Pearson correlation coefficient of the estimate node efficiency and the true value obtained from the PRDA algorithm at the shortest path acquisition probability p = 1-10^-15 is above 0.975 and the estimations are more reliable when dealing with large-scale networks. In the Apache Spark parallel computing environment, the solution of the DH index applying the PRDA algorithm with the time complexity of O （n^2/l） is much less time consuming than betweenness centrality which indicates that the time consuming characteristic of the algorithm is also suitable for large-scale networks.

关 键 词：复杂网络 节点重要度 分布式计算 节点效率 

分 类 号：N945[自然科学总论—系统科学]