首页 > 其他分享 >【复杂网络经典案例】无向和有向网络中心距离、效率及Delta中心性

【复杂网络经典案例】无向和有向网络中心距离、效率及Delta中心性

时间：2024-07-07 19:31:44浏览次数：13  
标签：weight 网络 nx 无向 Delta print nodes 节点

文章目录

概要

复杂网络理论涉及多种重要概念，包括无向和有向网络中的距离、效率和Delta中心性。这些概念有助于我们理解网络结构及其功能特性。

1.节点间的距离（Distance）

在网络科学中，更多的是关注两个节点 i i i和节点 j j j之间的最短路径，最短路径通常被称为他们之间的距离 d i j d_{ij} dij​。

  • 在无向网络中，距离通常指两个节点之间的最短路径长度，即连接这两个节点所需的最少边数。

  • 在有向网络中，距离可以分为两种：单向距离（从一个节点到另一个节点的最短路径长度）和双向距离（考虑两个节点之间所有可能的路径长度的平均值）。

  • 网络直径：网络直径 D D D为所有距离 d i j d_{ij} dij​中的最大值： D = m a x 1 ≤ i , j ≤ N d i j D=max_{1\leq i,j\leq N}d_{ij} D=max1≤i,j≤N​dij​

  • 网络平均距离： < d > <d> <d>指网络中所有节点对之间最短路径长度的平均值，它能够反映整个网络的紧密程度和信息传递的效率。计算公式为:
    ⟨ d ⟩ = 1 N 2 ∑ j = 1 N ∑ i = 1 N d i j \langle d\rangle=\frac1{N^2}\sum_{j=1}^N\sum_{i=1}^Nd_{ij} ⟨d⟩=N21​j=1∑N​i=1∑N​dij​注意:这个公式只测量出现在同一个网络连通分支中的节点对。我们可以使用广度优先搜索算法计算一个大网络的平均路径长度。
    无向图： 对于无向图来说 d i j d_{ij} dij​ = d j i d_{ji} dji​且 d i i d_{ii} dii​ = 0，上面公式可以进行化简为: ⟨ d ⟩ = 2 N ( N − 1 ) ∑ i = 1 N ∑ j = i + 1 N d i j = 2 W ( G ) N ( N − 1 ) \langle d\rangle=\frac2{N(N-1)}\sum_{i=1}^N\sum_{j=i+1}^Nd_{ij}=\frac{2W(G)}{N(N-1)} ⟨d⟩=N(N−1)2​i=1∑N​j=i+1∑N​dij​=N(N−1)2W(G)​
    有向图： 对于有向图来说 d i j d_{ij} dij​ 不等于 d j i d_{ji} dji​且 d i i d_{ii} dii​ = 0，上面公式可以进行化简为： ⟨ d ⟩ = 1 N ( N − 1 ) ∑ i = 1 N ∑ j = 1 , j ≠ i N d i j = W ( G ) N ( N − 1 ) \langle d\rangle=\frac1{N(N-1)}\sum_{i=1}^N\sum_{j=1,j\neq i}^Nd_{ij}=\frac{W(G)}{N(N-1)} ⟨d⟩=N(N−1)1​i=1∑N​j=1,j=i∑N​dij​=N(N−1)W(G)​
    案例：
    Alt
    如图所示，节点1和节点4的距离最远，因此网络直径为 d m a x d_{max} dmax​ = 3；平均路径为1.6，计算过程入下：
    ( l 1 → 2 + l 1 → 3 + l 1 → 4 + + l 1 → 5 + l 2 → 3 + l 2 → 4 + + l 2 → 5 + l 3 → 4 + l 3 → 5 + + l 4 → 5 ) / 10 = 1.6 \begin{aligned} &\begin{aligned}(l_{1\to2}+l_{1\to3}+l_{1\to4}+\end{aligned} \\ &\begin{aligned}&+l_{1\to5}+l_{2\to3}+l_{2\to4}+\end{aligned} \\ &+l_{2\to5}+l_{3\to4}+l_{3\to5}+ \\ &\begin{aligned}&+ l_{4\to5}) /10=1.6\end{aligned} \end{aligned} ​(l1→2​+l1→3​+l1→4​+​​+l1→5​+l2→3​+l2→4​+​+l2→5​+l3→4​+l3→5​+​+l4→5​)/10=1.6​​

2.节点间的效率

定义:节点 v i v_{i} vi​和 v j v_{j} vj​之间距离的倒数称为效率，记为 ε i j ε_{ij} εij​。

  • 网络的效率是指网络中节点间信息传递的快捷程度或有效性,当节点 v i v_{i} vi​和 v j v_{j} vj​之间没有路径相通的时候， d i j = ∞ d_{ij}=\infty dij​=∞，而 ε i j ε_{ij} εij​ = 0，因此效率更适合度量非全连通网络。
  • 在无向网络中，全局效率衡量了网络中任意一对节点间通信的便捷性，通常是倒数平均距离的形式。全局效率： E = 1 N ( N − 1 ) ∑ i ≠ j ε i j E=\frac1{N(N-1)}\sum_{i\neq j}\varepsilon_{ij} E=N(N−1)1​i=j∑​εij​
  • 在有向网络中，效率可以分为全局和局部效率，分别考虑了单向和双向通信的情况。节点的局部效率是由该节点的邻居所诱导的子图的平均全局效率。平均局部效率是每个节点的局部效率的平均值：
    $ E l o c = 1 N ∑ i ∈ G E ( G i ) E_{\mathrm{loc}}=\frac1N\sum_{i\in\mathbf{G}}E\left(\mathbf{G}_i\right) Eloc​=N1​∑i∈G​E(Gi​)
    提示: 对于无向网络，networkx库中提供了可以直接调用的库函数。然而，对于有向网络，现阶段还需自己编写函数来计算。

3.Delta中心性

Delta中心性思想:一个节点的重要性与网络对节点(节点组)从网络中停用的反应能力有关。

  1. Delta中心性衡量了网络中节点对网络结构的重要性贡献，特别是在网络拓扑结构中的关键位置。
  2. 在无向网络中，Delta中心性可以理解为节点对网络直径的贡献度量，即通过该节点可以增加多少网络直径的长度。
  3. 在有向网络中，Delta中心性的定义略有不同，可以基于节点对路径长度的平均增加量。
  4. 如果一个节点通过较短的路径与其他节点连接，那么它的Delta中心性就会相对较高，反之则较低。定义如下：
    Δ ( i ) = ∑ j ≠ i 1 d i j \Delta(i) = \sum_{j \neq i} \frac{1}{d_{ij}} Δ(i)=j=i∑​dij​1​
    Delta中心性不同于其他常见的中心性指标（如度中心性、介数中心性），它更侧重于节点在网络中的影响力和控制力，特别是在信息传播和影响传递方面的作用。
# 从外部读取数据来构建网络
df = pd.read_excel("example_network.xlsx")
G = nx.from_pandas_edgelist(df, 'source', 'target',create_using = nx.Graph())
# 绘制网络图
pos = nx.kamada_kawai_layout(G)
nx.draw(G, pos, node_color='red', edge_color='blue', with_labels=True)

在这里插入图片描述

# 计算信息中心性
CI = {}
EG0 = global_efficiency_undirected_graph(G, False)
for i in G.nodes():
    Gi = G.copy()
    edges_i = nx.edges(G, i)
    Gi.remove_edges_from(edges_i)
#     print(Gi.nodes())
    EGi = global_efficiency_undirected_graph(Gi, False)
    CI[i] = (EG0 - EGi)/EG0

# 降序排序
sorted_CI = dict(sorted(CI.items(), key=lambda x: x[1], reverse=True))
print(sorted_CI)

4.仿真实现（Jupyter Notebook）

  • 导入包
import networkx as nx
import pandas as pd
  • 类型一：无向网络
# 创建网络
G = nx.Graph()
G.add_nodes_from(list(range(1, 6)))
edges = [(1, 2), (1, 3), (2, 3), (2, 5), (2, 6), (3, 5), (4, 5)]
G.add_edges_from(edges)
# 绘制网络图
pos = nx.kamada_kawai_layout(G)
nx.draw(G, pos, node_color='red', edge_color='blue', with_labels=True)

在这里插入图片描述

# 计算距离和效率
nodes = list(G.nodes())
for i in range(len(nodes)-1):
    for j in range(i+1,len(nodes)):
        u, v = nodes[i], nodes[j]
        if nx.has_path(G, u, v):
            duv = nx.shortest_path_length(G, u, v)
            print("节点{}和{}之间的距离为{}".format(u, v, duv))
            print("节点{}和{}之间的效率为{}".format(u, v, 1/duv))
        else:
            print("节点{}和{}之间没有路径，距离为无穷大".format(u, v))
            print("节点{}和{}之间的效率为{}".format(u, v, 0))

# 全局效率
print(nx.global_efficiency(G)) #0.9
# 局部效率
print(nx.local_efficiency(G)) #0.833333333333333334

# 以一个不连通的网络为例
GER = nx.gnm_random_graph(10, 10)
print(nx.is_connected(GER))
# print(nx.average_shortest_path_length(GER))
print(nx.global_efficiency(GER))
nodes = list(GER.nodes())
for i in range(len(nodes)-1):
    for j in range(i+1,len(nodes)):
        u, v = nodes[i], nodes[j]
        if nx.has_path(GER, u, v):
            duv = nx.shortest_path_length(GER, u, v)
            print("节点{}和{}之间的距离为{}".format(u, v, duv))
            print("节点{}和{}之间的效率为{}".format(u, v, 1/duv))
        else:
            print("节点{}和{}之间没有路径，距离为无穷大".format(u, v))
            print("节点{}和{}之间的效率为{}".format(u, v, 0))
  • 类型二：无向加权网络
# 创建网络
G = nx.Graph()
G.add_nodes_from(list(range(1, 6)))
edges = [(1, 2, 3), (1, 3, 7), (1, 4, 10), (2, 3, 2), (2, 4, 2), (2, 5, 9), (3, 5, 4), (4, 5, 1)]
G.add_weighted_edges_from(edges)
# 设置连边的粗细等于权重
edgewidth = [G.get_edge_data(*e)['weight'] for e in G.edges()]
# 将连边的标签设置为权重值
edge_labels = {e: G.get_edge_data(*e)['weight'] for e in G.edges()}

# 绘制网络图
pos = nx.kamada_kawai_layout(G, weight='weight')
nx.draw(G, pos, node_color='red', edge_color='blue', width=edgewidth, with_labels=True)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, label_pos=0.5, font_color="black")
# 计算节点之间的效率
nodes = list(G.nodes())
for i in range(len(nodes)-1):
    for j in range(i+1,len(nodes)):
        u, v = nodes[i], nodes[j]
        if nx.has_path(G, u, v):
            duv = nx.shortest_path_length(G, u, v, weight='weight')
            print("节点{}和{}之间的距离为{}".format(u, v, duv))
            print("节点{}和{}之间的效率为{}".format(u, v, 1/duv))
        else:
            print("节点{}和{}之间没有路径，距离为无穷大".format(u, v))
            print("节点{}和{}之间的效率为{}".format(u, v, 0))

在这里插入图片描述

  • 类型三：有向无权网络
# 创建网络
G = nx.DiGraph()
G.add_nodes_from(list(range(1, 6)))
edges = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (2, 5), (3, 5), (4, 5)]
G.add_edges_from(edges)
# 绘制网络图
pos = nx.spring_layout(G)
nx.draw(G, pos, node_color='red', edge_color='blue', with_labels=True)

在这里插入图片描述

for u in G.nodes():
    for v in G.nodes():
        if u!=v:
            if nx.has_path(G, u, v):
                duv = nx.shortest_path_length(G, u, v)
                print("节点{}和{}之间的距离为{}".format(u, v, duv))
                print("节点{}和{}之间的效率为{}".format(u, v, 1/duv))
            else:
                print("节点{}和{}之间没有路径，距离为无穷大".format(u, v))
                print("节点{}和{}之间的效率为{}".format(u, v, 0))
  • 类型四：有向加权网络
# 创建网络
G = nx.DiGraph()
G.add_nodes_from(list(range(1, 6)))
edges = [(1, 2, 5), (1, 3, 7), (1, 4, 10), (2, 3, 2), (2, 4, 2), (2, 5, 9), (3, 5, 4), (4, 5, 1)]
G.add_weighted_edges_from(edges)
# 设置连边的粗细等于权重
edgewidth = [G.get_edge_data(*e)['weight']/5 for e in G.edges()]
# 将连边的标签设置为权重值
edge_labels = {e: G.get_edge_data(*e)['weight'] for e in G.edges()}

# 绘制网络图
pos = nx.kamada_kawai_layout(G, weight='weight')
nx.draw(G, pos, node_color='red', edge_color='blue', width=edgewidth, with_labels=True)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, label_pos=0.5, font_color="black")

在这里插入图片描述

for u in G.nodes():
    for v in G.nodes():
        if u!=v:
            if nx.has_path(G, u, v):
                duv = nx.shortest_path_length(G, u, v, weight='weight')
                print("节点{}和{}之间的距离为{}".format(u, v, duv))
                print("节点{}和{}之间的效率为{}".format(u, v, 1/duv))
            else:
                print("节点{}和{}之间没有路径，距离为无穷大".format(u, v))
                print("节点{}和{}之间的效率为{}".format(u, v, 0))

提示：networkx中目前没有计算加权网络和有向网络全局效率的函数

# 计算无向(无权、加权)网络的全局效率
def global_efficiency_undirected_graph(G, weight):
    nodes = list(G.nodes())
    n = len(nodes)
    s = 0
    for i in range(n-1):
        for j in range(i+1,n):
            if nx.has_path(G, nodes[i], nodes[j]) and i!=j:
                # 若为无权网络
                if not weight:
                    s += 1/nx.shortest_path_length(G, nodes[i], nodes[j])
                # 若为加权网络
                else:
                    s += 1/nx.shortest_path_length(G, nodes[i], nodes[j], weight='weight')

    av_eff = 2*s/(n*(n-1))
    return av_eff


# 计算有向(无权、加权)网络的全局效率
def global_efficiency_directed_graph(G, weight):
    nodes = list(G.nodes())
    n = len(nodes)
    s = 0
    for i in range(n):
        for j in range(n):
            if nx.has_path(G, nodes[i], nodes[j]) and i!=j:
                # 若为无权网络
                if not weight:
                    s += 1/nx.shortest_path_length(G, nodes[i], nodes[j])
                # 若为加权网络
                else:
                    s += 1/nx.shortest_path_length(G, nodes[i], nodes[j], weight='weight')

    av_eff = s/(n*(n-1))
    return av_eff

# 无权无向
df1 = pd.read_excel("undirected_graph.xlsx")
G1 = nx.from_pandas_edgelist(df1, 'source', 'target', create_using = nx.Graph())

# 加权无向
df2 = pd.read_excel("undirected_graph.xlsx")
G2 = nx.from_pandas_edgelist(df2, 'source', 'target', 'weight', create_using = nx.Graph())

# 无权有向
df3 = pd.read_excel("directed_graph.xlsx")
G3 = nx.from_pandas_edgelist(df3, 'source', 'target', create_using = nx.DiGraph())

# 加权有向
df4 = pd.read_excel("directed_graph.xlsx")
G4 = nx.from_pandas_edgelist(df4, 'source', 'target', 'weight', create_using = nx.DiGraph())

eff1 = global_efficiency_undirected_graph(G1, False)
print(eff1)

eff2 = global_efficiency_undirected_graph(G2, True)
print(eff2)

eff3 = global_efficiency_directed_graph(G3, False)
print(eff3)

eff4 = global_efficiency_directed_graph(G4, True)
print(eff4)

5.小结

复杂网络中，中心距离和效率是评估节点间信息传递速度和效率的重要指标。中心距离反映了网络结构的紧密程度，而效率则表征了信息传播的高效程度。另一方面，Delta中心性则衡量了节点对整个网络信息传播和控制的影响力，是网络功能与结构分析的关键工具。

通过分析这些指标，可以深入理解复杂网络在信息传递和控制方面的特性，为网络优化与设计提供理论支持。

标签：weight,网络,nx,无向,Delta,print,nodes,节点
From： https://blog.csdn.net/weixin_43584285/article/details/140250111

相关文章

  • 网络数据传输中的封装与解封装详解
    注：机翻，未校对。Thegoalofnetworksistotransmitdatafromonehosttoanother.网络的目标是将数据从一个主机传输到另一个主机。Encapsulation封装Toachievethisgoal,eachlayeraddsitsownheadertothedata.Aheadercontainsinformationspecific......
  • RedHat7.4—配置常规网络
    配置主机名把主机名修改为hyborn方法一、使用nmtui修改主机名需要管理员权限运行su-root输入root密码后进入管理员模式运行nmtui通过上下左右选择菜单栏回车选择，进入设置系统名即可设置确定后退出      运行hostnamectlstatus命令查看主机名，查看到的主机名，即......
  • 网络通信系统的voronoi图显示与能耗分析matlab仿真
    1.程序功能描述       两层基站（BS）组成整个通讯网络，第1层为Macro基站记为，第2层为Micro基站记为，均服从泊松分布，相互独立，在坐标为10×10km的面积内、按照泊松分布随机生成若干个点（随机抛洒两遍nodes，两层叠加起来）。然后画成voronoi图：也就是在相邻两个点（同种......
  • 基于负相关误差函数的4集成BP神经网络matlab建模与仿真
    1.算法运行效果图预览(完整程序运行后无水印)   2.算法运行软件版本MATLAB2022a 3.部分核心程序while(Index<=Max_iteration)Indexjj=1;error2=zeros(Len,KER);while(jj<=Len)fork=1:No;d(k)=T(jj);end......
  • 图神经网络版本的Kolmogorov Arnold（KAN）代码实现和效果对比
    MLP是多层感知器（MultilayerPerceptron）的缩写，它是一种前馈人工神经网络。MLP由至少三层节点组成：一个输入层、一个或多个隐藏层以及一个输出层。每一层的节点都与下一层的每个节点相连，并且每个连接都有一个权重。MLP通过这些权重和节点的激活函数来学习输入数据的模式。Kolmogorov......
  • Pytorch 实践手写数字识别深度学习网络 LeNet-5
    Pytorch实践手写数字识别深度学习网络LeNet-5文章目录Pytorch实践手写数字识别深度学习网络LeNet-5认识LeNet-5认识数据集处理数据集下载数据集读取数据定义Dataset的继承类把数据进行载入载入`dataloader`编写网络编写训练与测试代码实践结果展示完整代码训......
  • 网络安全基础
    概述基本概念网络安全通信的基本属性机密性。只有发送方与预定接收方能理解报文内容。消息完整性。发送方与接收方希望确保消息未被篡改，发生篡改一定会被检测到。可访问性与可用性。可访问性与可用性是网络信息可被授权实体访问并按需求使用的特性。身份认证。发送......
  • Java面试之并发与网络通信常见面试题
    并发编程部分1.什么是进程和线程？进程：操作系统分配资源的最小单位，各个进程之间占据独立的寻址空间，运行也是独立运行，进程间通信需要一些机制。线程：程序执行的基本单位，一个进程可以开启多个线程，他们的很多空间（如堆空间）是公用的。线程执行开销小，但是不够安全。2.线程有几......
  • 计算机网络面试常见题目（一）
    计算机网络面试中常见的问题涉及多个层面，包括网络协议、网络体系结构、网络安全、数据传输等。以下是一些常见题目的详解：1.OSI七层模型是什么？每层的功能是什么？OSI七层模型是国际标准化组织（ISO）制定的一个用于计算机或通信系统间互联的标准体系，它从上到下分别是：应用层：为应用......
  • Linux网络命令大全，收藏不迷路！
    Linux系统在网络管理中占据重要地位。无论是服务器管理、网络诊断还是安全维护，Linux网络命令都能提供强大的支持。网络配置命令ifconfigifconfig（interfaceconfiguration）是用于配置网络接口的命令。尽管被新的ip命令所取代，但它仍然在很多系统中使用。查看网络接口配置：......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99