|
|
最近在看实验室师兄留下来的《网络科学导论》，顺便写点笔记
一 复杂网络的连通性
经验和实践研究表明，无向的复杂网络通常是不连通的，但是在网络往往会存在一个特别大的连通片，被称为巨片（Giant Component）例如在网络科学中常用的一个数据：Facebook2011年5月7.21亿活跃用户所构成的网络中，最大的一个连通片包含了99.91%的用户，第二大连通片只包含了不到3000个节点。
对于有向的复杂网络，通常既不是强连通也不是弱连通。许多邮箱网络中往往会包含一个大型的弱连通片，称为弱连通巨片（Giant Weakly Connected Component, GWCG）这一弱连通巨片一般可以划分为4个部分，构成一个类似于蝴蝶结的结构：
- 强连通核（SCC）：网络中心的强连通分量
- 入部：能够抵达SCC，但是无法由SCC抵达
- 出部：能够由SCC抵达，但是无法抵达SCC
- 卷须（Tendrils）：既无法抵达SCC，也无法由SCC抵达的节点。如果一个卷须连通了入部和出部，则被称为Tube。
二 网络的度与稀疏性
度是刻画单个节点属性的最简单的概念。在网络科学中，网络的平均度数通常记为 \langle k\rangle 。在度数的基础上，定义包含 N 个节点的网络的密度为实际边数 M 与理论最大边数的比，即： \\\rho=\frac M{\frac12N(N-1)} 对于有向网络，只需去掉分母中的系数1/2。显然，网络的密度与平均度数之间存在如下关系： \langle k\rangle=(N-1)\rho\approx N\rho
在分析网络模型时，当 N\to\infty 时，如果网络密度趋向于某个非零常数，可以认为网络是稠密的；如果密度趋向于0，或者平均度数趋于某个常数，那么该网络是稀疏的。对实际网络的研究表明，大部分实际网络的演化介于稀疏网络和稠密的全耦合网络之间，服从稠密化幂律（Densification Power Law），即： \\M(t)\sim N^\alpha(t),1<\alpha<2
三 平均路径长度与直径
网络中两个节点 i,j 之间的最短路径（测地路径）上边的数目被定义两个节点之间的距离 d_{ij} 网络的平均路径长度 L 定义为任意两个节点之间距离的平均值，即 \\L\frac1{\frac12N(N-1)}\sum_{i\ge j}d_{ij} 也被称为网络的特征路径长度。大型实际网络往往是不连通的，这会导致网络平均路径长度的发散，对此存在两种解决方案：一种是将网络平均路径长度定义为存在连通路径的节点对之间距离的均值；另一种是把平均路径长度定义为网络中两点间距离的调和平均： \\L=\frac1{GE},\quad GE=\frac1{\frac12N(N-1)}\sum_{i\ge j}\frac1{d_{ij}}
假设两个节点间距离越短，信息传播的效率越高，则GE反映了网络中信息传播的效率，因而GE也被称为网络的全局效率（Global efficiency）。
在实际网络中，存在广泛的小世界现象，即网络的节点数很大，但是平均路径长度却很小，例如Facebook的平均路径长度为4.74。
网络中任意两点距离的最大值称为网络的直径，通常记为 D ，即 \\D=\max_{i,j}d_{ij} 考虑到实际网络的连通性，通常只考虑存在有限距离的节点对。在距离的基础上，记网络中距离不超过 d 的节点对占全部节点对的比例为 g(d) 。一般地，如果整数 D 满足 \\g(D-1)<0.9,g(D)\ge0.9 则称 D 为网络的有效直径（Effective Diameter）。为了方便研究，可以通过线性插值的方法将 g(d) 的定义域扩展为正实数，即对于任意 d\le r<d+1 有 \\g(r)=g(d)+(g(d+1)-g(d))(r-d) 实际网络中，随着时间的推移，其直径和有效直径都呈现缩小的趋势，称为直径收缩现象（Shrinking Diameters）。
四 聚类系数
假设网络中节点 i 度数为 k_i ，其1阶邻域节点之间边的数量为 E_i ，则该节点的聚类系数（Clustering Coefficient）定义为 \\C_i=\frac{2E_i}{k_i(k_i-1)}\tag{4.1} 对于孤立点以及度数为1的节点，其聚类系数定义为0。聚类系数可以理解为一个节点与其邻域中任意两个节点构成一个三角形的概率。一个网络的聚类系数定义为其所有节点聚类系数的平均值，即 \\C=\frac1N\sum_{i=1}^NC_i基于网络之中三角形的数量可以给出另一种定义方式 \\C_i=\frac{\sum_{i\ne j,i\ne k,j\ne k}a_{ij}a_{ik}a_{jk}}{\sum_{i\ne j,i\ne k,j\ne k}a_{ij}a_{ik}}\tag{4.2} 两种定义方式并不完全等价，但是在实际研究中通常关心的是网络聚类系数的相对大小，因而并不会带来本质区别。
在加权网络中，节点 i 的聚类系数表示为 \\C_i=\frac1{k_i(k_i-1)}\sum_{j,k}\omega_{ijk}a_{ij}a_{ik}a_{jk}其中，系数 \omega_{ijk} 的取值存在若干限制：
- 如果节点 i,j,k 不构成三角形， \omega_{ijk} 的取值不受限制，因为这种情况下 a_{ij}a_{ik}a_{jk}=0
- 在无权网络的情况下，该公式必须退化公式(4.1)
- 最终结果 C_i\in[0,1] ，所以 \omega_{ijk}\in[0,1] ，因此有权网络中节点的聚类系数必然不大于对应无权网络相应节点的聚类系数。
在上述限制条件下，存在2种不同的 \omega 定义：
- \omega_{ijk}=\frac1{\langle w_i\rangle}\frac{w_{ij}+w_{ik}}2 ，即归一化后边 (i,j),(i,k) 权值的平均值
- 归一化后三角形三条边权值的几何平均，即 \omega_{ijk}=(\hat w_{ij}\hat w_{ik}\hat w_{jk})^{1/3} ，其中 \hat w_{ij}=\frac{w_{ij}}{\max_{k,l}w_{kl}}
此外，还存在一种基于公式(4.2)的定义方式： \\C_i=\frac{\sum_{i,k}\hat w_{ij}\hat w_{ik}\hat w_{jk}}{\sum_{j\ne k}\hat w_{ij}\hat w_{ik}}
在三种定义方式中，第一种定义 C_i^{(1)}=1 的充要条件是节点 i 与任意两个相邻节点构成三角形。该条件同时也是后两种聚类系数为1的必要条件。 C_i^{(2)}=1 还要求所有三角形的边权值相等； C_i^{(3)}=1 要求三角形中边 (j,k) 的权值最大。
五 度分布
在网络中，度为 k 的节点占总节点数的比例记为 p_k 。从概率统计的角度， p_k 可以视为网络中一个随机节点的度为 k 的概率，即度分布 P(k) 。对于有向网络，则有出度分布 P(k^{out}) 和入度分布 P(k^{in}) 。
如果一个网络的度分布曲线近似于正态分布，其形状在远离峰值 \langle k\rangle 处呈现指数下降，这类网络被称为匀质网络（Homogeneous Network）然而，大部分实际网络的度分布服从幂律分布，即 P(k)\sim k^{-\gamma} 。这意味着网络是无标度的。
无标度性质是指对于任意常数 a ，存在常数 b 使得概率分布函数 f(x) 满足 \\f(ax)=bf(x) 幂律分布是唯一满足无标度条件的该率分布函数。 |
|
发表于 2022-11-30 11:14:26