摩根娱乐货物运输站
 
 
新闻中心
分类

新闻中心

复杂网络拓扑结构与静态特征
编辑:佚名 时间:2024-07-29
style: bullet | number | inline (default: bullet)
min_depth: number (default: 2)
max_depth: number (default: 6)
title: string (default: undefined)
allow_inconsistent_headings: boolean (default: false)
delimiter: string (default: |)
varied_style: boolean (default: false)
  • 节点间的距离
  • 节点间的效率
  • 节点距离的平均值
  • 距离与邻接矩阵的关系
  • 集聚系数clustering coefficient 假设节点$v_i$与$k_i$ 个节点直接相连,那么对于无向网络来说,这$k_i$ 个节点间可能存在最大边数为$k_i(k_i-1)/2$ ,而实际存在的边数为$M_i$ ,由此我们定义 C_i=2M_i/[k_i(k_i-1)]
  • 网络集聚系数 对于有向网络来说集聚系数为如上的$1/2$ ,然后将集聚系数平均我们可以得到网络平均集聚系数 C=\\frac{1}{N}\\sum_{i=1}^{N}C_i  节点的集聚系数还可以定义为 C_i=\\frac{ N_{i\\Delta}}{N_{i\\wedge}}=\\frac{ 2N_{i\\Delta}}{k_i(k_i-1)}=\\frac{ a_{ii}^{(3)}}{a_{ii}^{(2)}(a_{ii}^{(2)}-1)}
  • 每个节点的度,即为邻接矩阵的平方的主对角线元素k_i=a_{ii}^{(2)}
  • 网络平均度 \\left \\langle k \\right \\rangle=\\frac{1}{N}\\sum_{N}^{i=1}k_i=\\frac{tr(A^2)}{N}
  • 度分布 $P(k)$为网络中度为$k$的节点在整个网络中的占比 规则网络——Delta分布 完全随机网路——Poisson分布 均匀网络——幂律分布、指数分布
  • 无标度网络Scale-free network 具有幂指数形式的度分布:$P(k)\\propto k^{-\\gamma}$ 无标度指一个概率分布函数$F(x)$ 对于任意给定常数$a$ 存在常数$b$ 使得$F(x)$满足 F(ax)=bF(x) $F(a)=bF(1)$可以得到$b=f(a)/f(1)$ 代回入公式中我们有$f(ax)=f(a)f(x)/f(1)$ 接着我们对$a$进行求导,再令$a=1$ ,我们有 x{\\frac{df(ax)}{d(ax)}}={\\frac{f'(1)}{f(1)}}f(x) 微分方程的解为lnf(x)={\\frac{f(1)}{f'(1)}lnx+lnf(x)} 两边取指数,可以得到如下定理 定理2.1 满足$F(ax)=bF(x)$无标度条件的概率分布函数形式是如下的幂律分布函数: F(x)=F(1)x^{-\\gamma}, \\gamma=-F(1)/F'(1)
  • 累积度分布(cumulative degree distribution function)

实际网络的统计特征: 拓扑类型(有向、无向)、节点总数$N$、总边数$M$、平均度$\\left \\langle k \\right \\rangle$ 、平均距离$L$、集聚系数$C$、如果符合幂律还可以加入幂指数$\\gamma$

  • 联合度分布 从无向网络中随机选一条边,该边两个节点为$k_1,k_2$的概率,即 P(k_1,k2)=M(k_1,k_2)/M 平均度与度分布的关系 \\left \\langle k \\right \\rangle=\\sum_{k=0}^{k_{max}}kP(k) 运用联合度分布推导度分布求解公式: P(k)=(\\left \\langle k \\right \\rangle/k)\\sum_{k_2}\\frac{P(k,k_2)}{2-\\delta_{kk_2}}
  • 基于最近邻平均度值的度-度相关性 对节点$v_i$最近邻平均度值定义 k_{nn,i}=\\frac{\\sum_ja_{ij}k_j}{k_i} 则所有度值为$k$ 的节点的最近邻平均值$k_{nn}(k)$ 定义为 k_{nn}(k)=\\frac{(\\sum_{i|k_i=k}{k_{nn,i}})}{NP(k)} 若该值随着$k$的增加而增加为同配网络,否则异配
  • 基于Pearson相关系数的度-度相关性 pearson相关系数:协方差与其标准差的乘积比

通过任意一条边找到两个点,进而得到两个度值,这样遍历所有的边就可以得到两个序列,分析两个数的相关性即可。

r=\\frac{M^{-1}\\sum_{所有e_{ij}}k_ik_j-[M^{-1}\\sum_{所有e_{ij}}(k_i+k_j)]^2}{M^-1\\sum_{所有e_{ij}}\\frac{1}{2}(k_i^2+k_j^2)-[\\sum_{所有e_{ij}}(k_i+k_j)]^2}

  1. 集聚系数分布 从网络中任选一节点,其集聚系数值为$C$的概率 P(C)=[\\sum_i\\delta(C_i-C)]/N 其中$\\delta(x)$ 为冲击函数
  2. 聚-度相关性 局部集聚系数和全局集聚系数都可以刻画网络节点的集聚程度
  3. 局部集聚系数 C=[\\sum_{k=0}^{k_{max}}k(k-1)P(k)C(k)]/[\\left \\langle k^2 \\right \\rangle-\\left \\langle k \\right \\rangle] 一阶原点矩对应期望 二阶原点矩对应方差
  1. 介数
  2. 结点介数 B_i=\\sum_{所有j,l,j≠i≠l}[N_{jl}(i)/N_{jl}] 分子表示两个节点间的最短路径经过节点$v_i$
  3. 边介数 B_{ij}=\\sum_{所有l,m;l≠m (l,m)≠(i,j)}[N_{lm}(e_{ij})/N_{lm})] 分子表示两个节点间的最短路径经过边$e_{ij}$
  4. 介数分布和介-度相关性 节点的介数可能满足幂律分布
  5. 核度 节点核度的最大值叫做网络的核度

中心性反应了网络中各节点的相对重要性 1. 度中心性 - 节点的度中心性 $v_i$和度的中心性$C_D(v_i)$ 就是其度$k_i$ 除以最大可能最大的度$N-1$ C_D(v_i)=\\frac{k_i}{N-1} 网络$G$ 的度中心性$C_D$定义为 C_D=\\frac{1}{H}\\sum_{i=1}^N[C_D(v_{max})-C_D(v_i)] 当网络为星形网络时,$H=(N-1)[1-1/(N-1)]=N-2$ 这样的我们可以得到上式为 - 网络中心性 C_D=\\frac{1}{N-2}\\sum_{i=1}^N[C_D(v_{max})-C_D(v_i)] 2. 介数中心性 - 节点的介数中心性 最多可能的节点对数$(N-1)(N-2)/2$ ,设节点$v_i$的介数为$B_i$ ,则介数中心性$C_B(v_i)$ 可以定义为 C_B(v_i)=2B_i/[(N-2)(N-1)] 当网络为星形网络时,$H=(N-1)$ 这样一来我们可以得到,网络的介数如下 - 网络的介数中心性

C_B=\\frac{1}{N-1}\\sum^{N}_{i=1}[C_B(v_{max})-C_B(v_i))] 3. 接近度中心性 - 节点的接近度中心性 接近度表示某个节点$v_i$到其他所有节点最短路径之和的倒数乘以其他节点个数,节点接近度越大,表明节点越居于网络的中心。 C_c(v_i)=(N-1)/[\\sum_{j=1,j≠i}^{N}d_{ij}] - 网络的接近度中心性 当网络为星形网络时$H=[(N-1)(N-2)/(2N-3)]$ C_C=\\frac{2N-3}{(N-1)(N-2)}\\sum_{i=1}^N[C_C(v_{max}-C_c(v_i))]

4. 特征向量中心性 考虑相邻矩阵的特征值

  • 网络密度 网络$G$中实际拥有的连线数与最多可能存在的连接总数之比来表示,即 d(G)=\\frac{2M}{N(N-1)}

在无向网络的基础上对方向进行进一步的确定

公式推导: 假设网络的总弧数为$M$,容易证明 P_v(k_{in},k_{out})=\\left\\{\\begin{matrix}M\\cdot P_f(k_{in},k_{out})/(N\\cdot k_{out}),k_{out}\\ge 1 \\\\     M\\cdot P_f(k_{in},0)/(N\\cdot k_{in}),k_{out}=1\\   \\end{matrix}\\right.

  1. 点权 节点$v_i$ 的点权$S_i$定义为与它关联的边权之和 S_i=\\sum_{j\\in N_i}\\omega_{ij}

对于无向网络,还可以引入邻接矩阵的元素

S_i=\\sum_{j=1}^Na_{ij}\\omega_{ij}=\\sum_{j=1}^Na_{ji}\\omega_{ji} 2. 单位权 其定义为,节点点权$S_i$ 除以其节点的度$k_i$ U_i=S_i/k_i 3. 权重分布的差异性 节点的权重分布差异性$Y_i$ 表示与节点$v_i$ 相连的边权分布的离散程度,定义为 Y_i=\\sum_{j \\in N_j}(\\omega_{ij}/S_i)^2 对于无向网络,可以用邻接矩阵表示为 Y_i=\\sum_{j=1}^{N}(a_{ij}\\omega_{ij}/S_i)^2=\\sum_{j=1}^{N}(a_{ji}\\omega_{ji}/S_i)^2

  • 最短路径问题
  • $Dijkstra$ 算法
  • $Bellman-Ford$ 算法
  • $Floyd-Warshall$ 算法

节点的重要程度 I_i=k_i/\\sum^N_{i=1}k_i 定义网络结构熵 E=-\\sum^N_{i=1}I_i\\cdot lnI_i

当网络为星形网络,网络的结构熵最小$E_{min}$

为了消除节点数目$N$对$E$的影响,可以对网络结构熵进行归一化,定义  \\hat{E}=\\frac{E-E_{min}}{E_{max}-E_{min}}=\\frac{-2\\sum^N_{i=1}I_i\\cdot lnI_i-ln4(N-1)}{2lnN-ln4(N-1)} $\\hat{E}$ 在$0-1$之间 网络的结构熵是由度分布确定的,而网络结构熵可以更加精确简洁地度量复杂网络的非同质性。

如何理解归一化? ) 大话讲解:归一化、信息熵、交叉熵

  • 特征谱 简单无向网络$G$的邻接矩阵$A$,令对角矩阵$D$的对角元素分别是各节点的度,我们称矩阵$L=D-A$ 为网络G的$Laplacian$ 矩阵。
  • 冲击函数 狄拉克δ函数

调和矩阵 - 维基

  • zipf定理
  • 度秩函数 不统计各个节点度值得频率分布,取而代之得是关注网络节点得度与其排序之间的关系。


分享到:
上一条凯里
摩根娱乐货物运输站

分享到:

400-123-4567
Copyright © 2012-2018 摩根娱乐货物运输站 版权所有 非商用版本
 

平台注册入口