其它节点的重要性相对比较低.PPT

应用以上的标准来验证节点重要性评估指标，可以发掘不同指标的差异，探寻到每种评估指标设计者的不同出发点，以便更好的寻找合适的指标来对复杂网络节点的重要性进行评价。 由于每个节点都有其特殊之处，每个节点的重要性差异是通过对网络的一些基本信息统计分析，挖掘节点所处环境的特征，然后放大这些节点的显著性，从而量化节点的重要性。已有的指标包括：度数，介数，接近度，特征向量，网络直径等都属于社会网络分析提出的指标，这类研究方法对指标的研究并不破坏网络的整体性，且是从网络的某些结构特性出发研究，所以得出的各种指标都有一定的局限性。 这种研究方法假设节点被删除，然后计算网络性能的下降，进而来评估该节点的重要性。 这种基于节点删除的思想来评估重要性的方法的缺点是计算复杂度较高，随着网络规模的增大计算复杂度成几何级增长。 网页的重要性发掘就是互联网搜索引擎的一项十分重要的功能，搜索引擎对于关键词的检索结果就是许多依据重要性排序后的网页，随着近二十年来互联网搜索技术的迅猛发展，计算机学家提出的一些算法考虑的更加全面。 * 节点的介数是指网络中所有节点对的最短路径中经过该节点的数量比例。介数的缺点是计算复杂度非常高，时间复杂度为O(N3). 紧密度是网络中节点到其他所有节点距离之和的倒数。紧密度指标的提出是基于这样的考虑：网络中较短的距离传输时耗费较低，因此位于网络中心的节点所发出的信息能在较短的时间内传遍整个网络，显然这些中心节点对于网络的影响力较大，因此它们的重要性程度较高，但是由于紧密度根据节点所处位置的中心化程度确定重要性，比较依赖网络的拓扑结构，因此对于集中式的网络例如星形网络紧密度比较适合，但是对于ER随机网络，正则图并不太适合[9]。 特征向量指标针对这一实际情况，把网络中某个节点的重要性程度看成邻居节点重要性的一个线性叠加。特征向量指标是网络的邻接矩阵对应的最大特征值的特征向量，每一维即为对应节点的重要性指标。 * 对于任意一个节点，如果将它的n条边看作n条数据流，那么复杂网络可以看成一个复杂的通信系统模型（如图3.1所示为信息通信模型），因此可以运用信息论的观点来评估节点的重要性，在这种基于互信息的评估方法中，每个节点所包含的信息代表了节点的重要程度，计算出这些节点的信息并进行比较，就可以得到节点之间的相对重要性。 * * * 从表3.2可以看出，本文提出的基于互信息的评估算法得出的最重要节点是v14，而其它的几种方法得出的结果是v3或v14。从图3.2中可见v3、v14两个节点局部的拓扑结构很相似，它们都是网络中度数最大的节点，不同方法得出不同结果的原因是因为不同方法关注的角度不同。 另外在度数，介数，生成树指标中， v7、v8、v9、v10、v11 这五个节点的重要性相同，而在本文提出的方法中，节点v8、v9、v10相对于v7、v11更为重要。观察可以发现：移除v7节点后，v12节点的负载加重；而移除v9节点可能同时造成v6节点和v12节点的拥塞，对网络造成的潜在破坏更大。以上分析表明，从本文提出的互信息方法求出的结果中，可以明确地分辨出这些差别。 图3.4是根据各种指标挖掘出的APRA网络头五个重要节点（用黑色标记），其中同一指标中值相等的节点只取一个。可见虽然各种方法出发点不一样，关注的角度不同，但是得出的重要节点是类似的。 * 长期以来，对网络模型的认识最初是从规则网络模型开始，之后ER随机图理论取得巨大的成功，成为很长一段时间内研究复杂网络的主要模型，直到十几年前小世界模型和无标度模型两大模型的提出，才开辟了复杂网络研究的新纪元 * * BA模型通过度数来做优先选择，这一假设过于简单，实际上在真实的网络中，节点都倾向于连接“口碑”好的节点。比如：在科研合作网中，学者们都喜欢引用被他人引用较多的文献。这些口碑好的节点通常就是网络的重要节点。另外，BA模型按照结点的度数来预测网络中新增的连接，对于较新的节点，获得新的连接时间较少，因此连接数少。但是真实系统中一个节点的连接和增长并不仅仅是依赖节点进入网络的先后，比如，一夜成名的明星相对一些进入娱乐圈更早的明星人气更旺。所以要考虑节点的被认可程度对新增连接的影响。 * * 这种模型的度分布遵循幂律分布，模拟结果与理论分析一致，证明理论推导的度分布是正确的。 * 聚类系数是复杂网络的一个重要统计特性，标志着网络的聚集程度，图4.6是对本章提出的pagerank无标度网络模型和BA模型计算聚类系数的结果，网络大小分别从200个节点开始，间隔200个节点，逐渐增加至2000个节点。图中横坐标是网络节点数目，纵坐标是聚类系数。可见基于pagerank的无标度模型的聚类系数小于BA模型，这是因为在做优先选择时，pagerank所代表的节点重要程度影响