02 复杂网络分析中的基本概念
2.1.复杂网络的表达方式2.2.度、平均度、度分布2.3.路径、距离与介数2.4.集聚系数2.5.网络稀疏性与联通性2.6.度相关性2.7.富人俱乐部2.8.有向网络2.9.加权网络2.1复杂网络的表达方式
哥尼斯堡七桥问题
1736年 欧拉定理
网络的可视化表达 图表达如果图具有两个以上的奇数度的节点，则没有路径;如果图是连通的且没有奇数度节点，则它至少有一条路径。
节点，顶点之间的相互作用，表达成连边或者是边，如此，网络变成了一个系统。该系统是由节点与节点之间相互作用抽象出来的连边所构成的
2. 集合表达
VVV 点集 {\{{1,2,3,4,5,61,2,3,4,5,61,2,3,4,5,6}\}}
EEE 边集 {\{{eee111,,,eee222,eee333,,,eee444,,,eee555,}\}}
网络G=(V,E)G=(V,E)G=(V,E),由点集V(G)V(G)V(G)和边集E(G)E(G)E(G)组成一个图，可分为无向、有向和加权网络
令e∈E(G)e∈E(G)e∈E(G),每条边eeeiii有V(G)V(G)V(G)中的一对点(u,v)(u,v)(u,v)与之对应；如果任意(u,v)(u,v)(u,v)与(v,u)(v,u)(v,u)对应同一条边，则称无向网络，否则成为有向网络；如果任意∣e|e∣eiii∣|∣=1=1=1,则称无权网络，否则称为加权网络。
3. 链接矩阵
{001000001000110100001011000100000100}(A)\begin{Bmatrix} 0 & 0 & 1 & 0 & 0 &0 \\ 0 & 0 & 1 & 0 & 0 &0 \\ 1 & 1 & 0 & 1 & 0 &0 \\ 0 & 0 & 1 & 0 & 1 &1 \\ 0 & 0 & 0 & 1 & 0 &0 \\ 0 & 0 & 0 & 1 & 0 &0 \\ \end{Bmatrix} \tag{A} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧001000001000110100001011000100000100⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫(A)
两个节点之间有边存在所对应的位置取值为1 无边则放0
在链接矩阵基础上，构造Laplace矩阵L=K−AL=K-AL=K−A;AAA为网络链接矩阵，KKK为对角矩阵，对角线上的元素对应的网络中各个节点的度。
链接矩阵及其对应的拉普拉斯矩阵的特征值和特征谱分析可以提供帮助。
什么是网络拓扑
网络是一个由多个节点组成的集合，节点之间有一定的连接。
拓扑指的是节点之间相互联系的模式
2.2度、平均度、度分布
度 节点的度：与节点直接相连的连边数k1=1 k2=3 k3=2 k4=2 *2节点的度最高*通常，节点的度值是一个离散型随机变量，在计算中主要涉及以下统计量 均值方差标准差n阶矩x的分布 平均度k=1N∑i=0Nkik=\frac 1N\sum_{i=0}^Nk_ik=N1∑i=0Nki
k=2LNk=\frac {2L}Nk=N2L
NNN:图中节点数LLL:图中连边数 度分布 将网络中节点的度值从小到大排列，统计值为k的节点，占整个网络节点数的比例P(k)P(k)P(k),即P(k)−Nk/NP(k)-N_k/NP(k)−Nk/N NkN_kNk 度为k的节点数目NNN 网络中的节点总数 连续性变量表述：节点的度的概率密度函数归一化条件
∑0∞\sum_0^\infin∑0∞pk=1p_k=1pk=1
∫m∞\int_m^\infin∫m∞p(k)dk=1p(k)dk=1p(k)dk=1mmm是网络所有节点的度值中的最小值,一般从1开始取。 正则网络的度分布 全连接网络：n-1Δ\DeltaΔ最近邻居连接网络：Δ\DeltaΔ星型网络：中心点（特殊点）：n-1；其他点（边缘点）：1
2.3路径、距离与介数
路径 一条路径是指一个节点序列，其中每一对相邻的节点之间都有一条连边。一条从节点i0i_0i0到ini_nin的长度为n的路径P经过n+1个节点和n条连边。最短路径 两个节点之间的最短路径是指连接这两个节点的变数最少的路径。两个节点之间的最短路径上的边数目，即两个节点之间的最短距离。 两点之间路径的条数NNNijijij两点间路径的条数。 如果节点iii和jjj之间存在一条连边，则AAAijijij=1=1=1,反之，AAAijijij=0=0=0如果节点iii和jjj之间存在一条长度为2的连边，则AAAikikikAAAkjkjkj=1=1=1,反之，AAAikikikAAAkjkjkj=0=0=0……长度为n，如果节点iii和jjj间存在一条长度为n的路径，则AAAikikik…A…A…Aljljlj=1=1=1，否则，AAAikikik…A…A…Aljljlj=0=0=0。在节点ij之间长度为n的路径数量：
NNNijijij(n)(n)(n)=[An][A^n][An]ijijij网络直径与平均距离 直径dddmaxmaxmax:网络中任意两点间的最短距离的最大值。平均路径长度（平均最短距离）⟨d⟩\langle d \rangle⟨d⟩ 连通图 ⟨d⟩\langle d \rangle⟨d⟩≡12L∑i,j+1≡\frac1{2L}\sum_{i,j+1}≡2L1∑i,j+1dddijijij无向图 ⟨d⟩\langle d \rangle⟨d⟩≡1L∑i,j+1≡\frac1L\sum_{i,j+1}≡L1∑i,j+1dddijijij
将网络中任意一堆节点之间的最短距离求出来后进行求和，然后再除以这个网络当中节点对的数目。
直径 3；平均距离9/5
实例 全连接网络：平均距离为1最近邻居网络：平均距离为N/8星型网络：平均距离为2−2-2−2(N−1)N(N−1)\frac{2(N-1)}{N(N-1)}N(N−1)2(N−1) 介数 任意一堆节点间的最短路径所经过的次数 点介数边介数 介数反映了响应的节点或边在整个网络中的作用和影响力，是一个全局几何量。
2.4集聚系数
节点集聚系数的定义1 节点iii的kik_iki个邻居节点之间实际存在的变数EiE_iEi和总的可能边数之比。Ci=C_i=Ci=2eiki(ki−1)\frac{2e_i}{k_i(k_i-1)}ki(ki−1)2ei
eie_iei指i点邻居之间存在连边的个数；
kik_iki指i点的度值；Ci=C_i=Ci=包含节点i的三角形数目以节点i为中心的连通三元组数目\frac{包含节点i的三角形数目}{以节点i为中心的连通三元组数目}以节点i为中心的连通三元组数目包含节点i的三角形数目 网络集聚系数定义
网络中所有节点的集聚系数的平均值 ⟨C⟩\langle C \rangle⟨C⟩=1N∑i=1N=\frac1N\sum_{i=1}^N=N1∑i=1NCiC_iCi
网络的传递性T=网络中三角形数目网络中连通三元组的数目/3T=\frac{网络中三角形数目}{网络中连通三元组的数目/3}T=网络中连通三元组的数目/3网络中三角形数目
T∈[0,1]T∈[0,1]T∈[0,1]
如果T=1，则任意两个节点有连接。
如果T=0，则无三角形连接。
2.5网络稀疏性与连通性
完全连接网络
定义：如果一个网络中任意两个节点之间都有连边存在，则称之为完全连接网络，平均度为N-1
可能拥有的最大连边数：
LLLmaxmaxmax=CN2C_N^2CN2ma
网络稀疏性
定义：网络稀疏程度定义为网络中实际存在的边数与最大可能的边数之比。
LLL/LmaxLmaxLmax
L:网络中实际存在的边数
利用比值衡量稀疏程度，很多网络是稀疏网络
无向网络的联通
联通（无向）图：网络中任意两个节点之间都至少存在一条路径最大连通集团：含有节点数最多的连通子图对于不连通网络的邻接矩阵，所有的非零元素都存在于沿着矩阵对角线排列的一些方块中，其余部分元素均为零。
+（一般会选择最大连通集团进行性质分析
2.6度相关性
众多的社会关系网络，呈现出正向匹配特性；信息网络和神经网络则呈现出负向匹配特性；而常用的ER模型和BA模型则没有任何倾向性。2网络中两个节点度值之间的关系 同配：度大节点 倾向于连接 度大节点（对角线）异配：度大节点 倾向于连接 度小节点（两轴）中性：节点间的连接与它们自身的度值无关 衡量网络的度度相关性 可视化描述3 eeejkjkjk:网络中随机选取的一条边的两个端点的度分别为jjj和kkk的概率qkq_kqk：网络中随机选取的一条边的断电的度为k的概率。如果网络不具有度相关性：eeejkjkjk=qj=q_j=qjqkq_kqk计算eeejkjkjk，并对其进行可视化，观察分布，判断网络度度相关性。 度相关函数4 平均邻居度kkknnnnnn(k)(k)(k):度为k的节点的邻居节点的平均度。kkknnnnnn(k)=akμ(k)=ak^\mu(k)=akμμ>0\mu>0μ>0:同配μ=0\mu=0μ=0:中性μ<0\mu<0μ<0:异配 相关系数
如果网络是度相关的，eeejkjkjk!=qjqk!=q_jq_k!=qjqk,可以考虑-的差值大小来刻画网络同配或异配的程度。
正值，同配；0，中性；负值，异配。 为了比较不同规模网络的同配或异配程度，通过归一化处理得到归一化的相关系数。 皮尔逊相关系数
取出网络中所有连边，计算每条连边两端节点的度值，并将其按从小到大排序，得到度小序列和度大序列，最后计算它们的皮尔逊相关系数。
2.7富人俱乐部
研究Internet的AS拓扑过程中发现，虽然AS拓扑具有异配特性，但高度节点之间仍然具有很高的连接概率，这个现象成为富人俱乐部现象。引入夫人俱乐部系数来对富人俱乐部现象进行量化描述。5
富人俱乐部系数：$\phi(k)=222E<sub><sub><sub>>k</sub></sub></sub>/N<sub>N<sub>N<sub>>k</sub>(N<sub></sub>(N<sub></sub>(N<sub>>k</sub></sub></sub>-1)$ EEE>k>k>k:网络中度值大于k的节点之间的连边数。NNN>k>k>k:网络中度值大于k的节点数。 标准化后的富人俱乐部系数6 总平均入度=总平均出度 路径、最短距离 在有向网络中，路径只能沿着箭头的方向。因此，在有向网络中，从A到B的最短距离可能不等于从B到A的最短距离。有向网络的集聚系数7有向网络的连通 将有向网络中的所有有向边替换为无向边，替换后的无向网络是一个连通图，则称该有向网络是一个弱连通图。 强定义：有向网络中必须任何两个节点之间都存在路径，强连通图。度相关8 实例食物网：一条有向边由节点A指向节点B，表示物种B以物种A为食物。四种模式下的度度相关性。 （out，in）（in，out）（out，out）（in，in） 有向网络的模体9 有向网络和随机网络模体，随机网络的生成方式10,随机交叉换边，并且保证每个节点的入度和出度不变。 可以利用有向网络对实体系统进行抽象，再通过与随机化有向网络进行对比可以挑选出系统当中所存在的个数居多的模体模式。而模体模式可以揭示系统所具有的一些特征 节点之间对应的多条连边=>链接矩阵所对应位置上元素的数值表达。依旧可以利用无权网络的公式计算边数、平均度，链接矩阵也同时保持着对称的特征。权重 权重（点、边）加权网络中加权的赋予 加权方式： a)利用网络中已有的物理量进行权重的抽象：因特网——带宽；电路网——电阻 b)相互作用的抽象：科学家合作网——合著文章数；演员合作网——合作次数；中药网；菜肴网 双顶点网络的抽象 顶点——事件 构成双顶点网 广义合作网投影到单顶点网关于权重的定义11 相似权（Similarity Weight）：概念与距离相反，边权越大，顶点之间越亲近（0为无连接）如合作次数相异权(Dissimilarity Weight):概念与距离相同，边权越大，顶点间距离越远（∞为无连接）如里程数 节点距离计算 相异权 ddd131313=w=w=w121212+w+w+w232323相似权 ddd131313=1/w==1/w==1/w=1/w1/w1/w121212+1/w+1/w+1/w232323 加权网络集聚系数 加权网集聚系数的定义满足以下4个条件12: 在[0,1]之间权重为0则无边连接权重为1时回归无权网定义与三角形每条边上的权重相关 文献给出了加权网络集聚系数的公式 Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of “small world” networks. Nature, 393, 440-442. ↩︎ Newman, M. E J . Assortative Mixing in Networks[J]. Physical Review Letters, 2002, 89(20):208701. ↩︎ Maslov, S. Specificity and Stability in Topology of Protein Networks[J]. Science, 2002, 296(5569):910-913. ↩︎ Pastor-Satorras, Romualdo, Vázquez, Alexei, Vespignani, Alessandro. Dynamical and Correlation Properties of the Internet[J]. Physical Review Letters, 87(25):258701. ↩︎ Zhou S, Mondragon RJ. The rich-club phenomenon in the Internet topology. IEEE Communications Letters, .8(3):180- 182. ↩︎ Colizza, V.，Flammini, A.，Serrano, M. A., & Vespignani, A. . (). Detecting rich-club ordering in complex networks. Nature Physics, 2(3), 110-115. ↩︎ Fagiolo, Giorgio. Clustering in Complex Directed Networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, , 76(2):026107. ↩︎ Jacob G. Foster, David V. Foster, Peter Grassberger,等. Edge direction and the structure of networks[J]. Proceedings of the National Academy of Sciences of the United States of America, . ↩︎ Milo R , Shen-Orr S , Itzkovitz S , et al. Network Motifs: Simple Building Blocks of Complex Networks[J]. Science, 298. ↩︎ Maslov, S. Specificity and Stability in Topology of Protein Networks. Science, 2002, 296(5569):910-913. ↩︎ FAN, YING, LI, MENGHUI, CHEN, JIAWEI,等. NETWORK OF ECONOPHYSICISTS: A WEIGHTED NETWORK TO INVESTIGATE THE DEVELOPMENT OF ECONOPHYSICS[J]. International Journal of Modern Physics B, 18(17n19):2505-2511. ↩︎ Petter Holme, Sung Min Park, Beom Jun Kim,等. Korean university life in a network perspective: Dynamics of a large affiliation network[J]. Physica A Statistical Mechanics & Its Applications, 373(none):821-830. ↩︎2.8有向网络
有向网络：在网络的连边上面存在方向。方向体现在链接矩阵中为非对称性；对角线为0AAAijijij≠A≠A=AjijijiAAAiiiiii=0=0=0 度的进一步划分 节点iii的出度 从节点i指向其他节点的边数目节点iii的入度 从其他节点指向节点i的边数目节点的度（总度） 节点的入度和出度的加和源 一个节点的入度kkkininin=0=0=0汇 一个节点的出度kkkoutoutout=0=0=0 平均度 平均入度平均出度总平均度2.9加权网络
多条边网络参考文献
