基于平衡系数的加权网络改进k核算法

王 棹,张曦煌

(江南大学 物联网工程学院,江苏 无锡 214000)

0 概述

复杂网络节点重要性研究是复杂网络理论中十分重要的部分,对不同网络的研究已经发展出很多新的理论[1-3]。这些相关理论已应用到社交网络[4]、传播网络[5]、计算机网络[6]等各种网络的分析中,并取得了科学的可靠的结果。由于复杂网络中的节点数目十分巨大,一个网络中有成百上千个甚至数十万个网络节点,如何高效准确地识别出其中的重要节点变得十分困难,这些关键的节点处于网络中十分重要的位置,对整个网络的抗毁性[7-8]有至关重要的作用。

目前,在复杂网络理论中节点重要性的评价方法主要有节点度[9]、网络介数[10]、接近中心和PankRank[11]。节点度只反映了节点在网络局部的重要性。介数和接近中心算法从网络全局角度出发,对节点在网络中所处的位置给出了较为准确的节点重要性评价,但是由于它们都需要计算所有节点到其他网络节点的最短路径[12],因此算法复杂度非常高。文献[13]提出了基于节点重要度贡献的节点重要性算法,给出了基于m阶邻居节点重要度贡献的复杂网络节点重要度计算方法,该算法取得了较好的实验结果,但不适用于加权网络。文献[14]在文献[12]的基础上提出了适用于加权网络的节点重要度改进算法,但由于算法复杂度高,因此不适合用来分析大型网络。PankRank算法是由谷歌公司提出的基于随机游走的网页重要性排序算法,该算法主要应用在互联网领域,且不适合用来分析加权网络。……