网络测度总结

.复杂网络简介结构决定功能是系统科学的基本观点，如果我们将系统内部的各个元素作为节点，元素之间的关系视为连接，那么系统就构成了一个网络。例如神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络，计算机网络可以看作是计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络，类似的还有电力网络、社会关系网络、交通网络等等.强调系统的结构并从结构角度分析系统的功能正是复杂网络的研究思路，所不同的是这些抽象出来的真实网络的拓扑结构性质不同于以前研究的网络，且节点众多/故称其为复杂网络。复杂网络的研究可以简单概括为三方面密切相关却又依次深入的内容，通过实证方法度量网络的统计性质，构建相应的网络模型来理解这些统计性质何以如此，在已知网络结构特征及其形成规则的基础上，预测网络系统的行为。二.复杂网络的统计性质用网络的观点描述客观世界起源于德国数学家Eular解决哥尼斯堡七桥问题。复杂网络研究的不同之处在于首先从统计角度考察网络中大规模节点及其连接之间的性质，这些性质的不同意味着不同的网络内部结构，而网络内部结构的不同导致系统功能有所差异。所以对这些统计性质的描述和理解是我们进行复杂网络相关研究的第一步。一般来说，按照是否考虑节点中的相互作用的方向性，可以把网络分为无向网络和有向网络；按照是否考虑节点间的作用强度可以分为无权网络和加权网络。本文介绍的由脑电信号构造的复杂网络的基本概念主要是针对无向无权网路的。节点的度和度分布一个节点的度就是与相连的边的条数，用邻接矩阵来表示即为k二乞a..iijjeN对于有向网络。节点的度还细分为入读和出度，节点的总度为入读和出度之和。在网络中，刻画一个节点的特征的最简单同时也是最重要的概念就是度，一个节点.的度k.定义为与它连接的边数目。在网络中，节点的度越大，表明它在网络中的重要性越高，反之亦然。数学上，网络节点的度分布可以用一个分布函数P(kP(k)来描述：P()=度等于k的节点数―节点总数―(V正整数k)设节点总数为N，边总数为W，则由于每个节点的度最少为l、最多为N-1，易知度分布存在下列关系七1P(k)二1k=1对于在全局耦合的网络中，所有节点都和其他节点连接，每个节点所连接的边数都相等，因此节点的度分布比较简单，就是一个Delta函数。随机网络和小世界网络的度分布满足泊松分布。而在无标度复杂网络如神经网络、组织代谢、好莱坞、蛋白质调控网络、万维网，P(k)是一个幕函数，即存在丫>0及CN>0，使得:P(k)=CNk-丫式中Y称为度分布指数(degreeexponent)平均路径长度

网络研究中，一般定义两节点间的距离为连接两者的最短路径的边的数目，网络的直径为任意两点间的最大距离，网络的平均路径长度L则是所有节点对之间距离的平均值，它描述了网络中节点间的分离程度，即网络有多小.L二-工dN(N-1) j1,jeN,1丰j其中dj表示节点1和之间的距离。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长度比想象的小得多，称之为小世界效应，这一提法来源于著名iBilgrm'小世界'试验，试验要求参与者把一封信传给他们熟悉的人之一，使这封信最终传到指定的人/籍此来探明熟人网络中路径长度的分布，结果表明平均传过人数仅为六/这一试验也正是流行的“六度分离”概念的起源。聚类系数聚类系数C用来描述网络中节点的聚集情况，即网络有多紧密，比如在社会网络中/你朋友的朋友可能也是你的朋友或者你的两个朋友可能彼此也是朋友，其计算方法为：假设节点i与其他k(i)个节点相连，这与k(i)个节点之间最多可能存在k(i)(k(i)-1),''2条边，而它们之间实际存在E(i)条边，则节点i的聚类系数为2E(i)

k(i)(k(i)-1)2E(i)

k(i)(k(i)-1)整个网络的聚类系数C(i)C=-t^i n显然对于完全连接的规则网络有C=1，而完全孤立的“网络”(即全部是孤立的节点，没有任何连接)聚类系数C=0。研究发现对于具有n个节点的完全随机网络的聚类系数C〜O(-)；真实世界的网络具有小世界特性，O(-)<C<1。nn介数介数是网络里衡量节点中心性的一个指标量。介数分为边介数和节点介数。节点的介数为网络中所有的最短路径中经过该节点的数量比例；边的介数含义类似。介数反映了相应的节点或者边在整个网络中的作用和影响力，具有很强的现实意义。例如，在社会关系网络或技术网络中，介数的分布特征反映了不同人员、资源和技术在相应生产关系中的地位，这对于在网络中发现和保护关键资源和技术具有重要意义。亍n.(i)如:节点的介数定义为B=乙」j,kevjk其中njk表示节点j和k之间的最短路径的个数，nj()表示节点j和k之间的最短路径经过节点i的个数。在拓扑意义下，节点j和k之间的最短路径就是节点j和k之间经过的边数

最少的路径；当网络为一个加权网络时，节点j和k之间的最短路径就是j和k之间经过边权之和最小的路径。边的介数定义类似。网络效率网络效率是对网络信息传递速率的度量，即表征了网络的传输能力。全局效率Egloba定义为每对节点间最短路径的倒数的平均值：global1global1N(N-1)工丄L.i丰jeGj子图Gi的局部效率定义为:i-圖=ng.(ng-i)EjGiGi i丰keGijk其中，Gi为节点i的子图，即与节点i直接相连的所有节点构成的图，不包括节点i。因此,E.-local可以描述为当节点i消除后，其子图交换信息的能力。网络密度网络密度S的公式描述为S二1右.N(N-1)「'i=1其中心为节点i的度数。正负匹配度(assortativecoefficient)很多网络中包含不只一种类型的节点，节点间有边相连的概率常常依赖于节点的类型。例如在食物网络中，顶点可以分为三种类型——植物、食草动物和食肉动物。显然，在植物和食草动物间，食草动物和食肉动物间以及食肉动物内部，都有很多边相连；但是在食草动物间，植物与食肉动物间却几乎没有边相连oNewman提出了一种用关联系数来定量描述混合弄湿的量化方法，及正负匹配度。用ez.表示连接第i类节点与第j类节点的边数占网络所有边数的ij比例，记为a=丫eb=Ye如果网络是无向的，ei?.=e a=b。于是网络政府i ij j ij ij ji i iji匹配度定义为工e..一工ab.A= 匕 ii~1-乙ab.ii对于完全随机网，A=0；对于完全同类图(只有同类节点才相连)，A=1o当节点没有明显可以分类的标准时，一种最简单的考虑是根据节点的度进行分类——这就引出了度度相关性的概念。如果说度大的节点倾向于和度大的相连，度小的节点倾向于和度小的相连，我们就说这种网络是度度正相关的，或者简称正相关；反之，如果度大的节点倾向于和度小的节点相连，我们就说这个网络是负相关的。Pastor-Satorras等人给出了度度相关性的一个直观的刻画，他们在对Internet的研究中计算了一个顶点的邻接顶点的平均度,它是该顶点度数k的函数。当网络正相关时，它给出了一条随k递减的曲线；反之，则随k递减。Newman指出只需要计算网络顶点度的Pearson系数r即可定量衡量网络相关性:

M-i工jk.-[M-i工-(ji+k.)]2r= - L—M-1工2(j.2+k.—)-[M-1工—(j.+k.)]—.— .—其中j和k表示第i条边的两个节点的度。M表示总边数。当r>0时网络是正相关的，当r<0时网络是负相关的，r=0时网络无相关性。模块度群落结构：真实世界网络研究发现，无论是社会网络还是其他类型的网络都表现出一种群落结构。群落结构指网络由很多群落组成，群落内部连边密集，群落之间连边很少。在引文网络中，群落代表特定的研究领域；在万维网中，群落反应网络的主题分类；在神经网络中，群落可能代表功能单元，如此等等。传统的识别网络群落结构的方法是聚类分析。Newman在2004年提出了模块度的定义用来评价群落结构的分类质量，其定义为测量网络分离性的一个度量是它的模块性，通过在许多实际网络中的观察得来。模块化指数定义为Q=工&厂a2)i其中a.= e..指与群落i中的节点相连的边数占整个网络总变数的比例，e.i指两个节点都j在群落.中的边数所占的比例，一般的，Q取0.3到0.7之间的数。Q值越大，网络中的群落结构越明显。传递性(Transitivity)网络传递性定义为E 2t.T— /E牡k-1)zeN其中，t.其中，t.为围绕.周围的三角形数量,t.—工a..aa，i ijihjhj,hwN说明：传递性不被定义为个