图论（四）：图的中心性——度中心性介数中心性紧密中心性

图的中心性：描述节点在图中有多“中心”

度中心性

以节点的度数度量中心性 用nx.degree_centrality(G)计算

---

介数中心性

量化节点在图中承担“桥梁”程度。计算 节点v 出现在其他任意两个节点对 (s,t) 之间的最短路径的次数（下式V 是无向图节点集合。(s,t) 是无向图中任意一对节点）

用 nx.betweenness_centrality(G , normalized = False) 计算。参数 normalized = False 表示不归一化。默认是 True ，计算归一化介数中心性

---

紧密中心性：

紧密中心性 具体定义如下，其中，d(a, v) 是节点 a 和 v 最短距离，k – 1 代表节点 a 可达节点的数量；也就是说 k 为包含节点自身可达节点数量。

上式取倒数是节点 a 和可达节点之间平均最短距离，说明平均最短距离越大，中心性越小（倒数），即越远离中心。

用nx.closeness_centrality(G)计算。对于有向图，可以分别计算入度紧密中心性、出度紧密中心性。

---

特征向量中心性：

基于邻接矩阵、特征值分解等线性代数工具（下节）用nx.eigenvector_centrality(G)计算

---

邻接矩阵：用于表示图的矩阵 无向图的邻接矩阵对称，行和列的数量等于图中的节点数量矩阵的元素表示节点之间是否存在边——对于无权无向图，两节点之间存在边，元素值为1；反之为0提供了一种紧凑的方式来表示图中的连接关系，某些算法易于处理这种格式利用 NetworkX 的工具to_numpy_matrix()或 adjacency_matrix()方法将无向图转化为邻接矩阵 undirected_G = nx.Graph() # 创建无向图的实例 undirected_G.add_nodes_from(['a', 'b', 'c', 'd']) # 添加多个顶点 undirected_G.add_edges_from([('a','b'), ('b','c'), ('b','d'), ('c','d'), ('c','a')]) # 增加一组边 # adjacency_matrix = nx.to_numpy_matrix(undirected_G) adjacency_matrix = nx.adjacency_matrix(undirected_G).todense() #2种方法。将图转化为邻接矩阵

#用热图可视化矩阵 plt.figure(figsize = (14,9)) sns.heatmap(adjacency_matrix,cmap = 'RdYlBu_r', square = True, xticklabels = [], yticklabels = []) plt.savefig('A邻接矩阵.svg')

也可利用nx.Graph(adjacency_matrix, nodetype=int)的方法将邻接矩阵转化为图。对于有权无向图，其邻接矩阵的每个元素直接换成边的权重值有向图的邻接矩阵 A 一般不是对称矩阵，这种不对称也显示了其方向性 成对（欧式）距离矩阵、亲近度矩阵、协方差矩阵、相关性系数矩阵等等都可以看做是 邻接矩阵 成对欧式距离矩阵、亲近度矩阵、相关系数矩阵都可叫 成对度量矩阵！（后续博客....） 邻接矩阵算是 与图直接相关的矩阵，其他与图也相关的矩阵有： 关联矩阵、度矩阵、拉普拉斯矩阵、转移矩阵等。

---

分割社群：紧密连接的节点集合

Girvan-Newman用于社区检测的算法实现，它基于边介数中心性的概念。是一种分裂算法，它通过逐步移除图中边介数最高的边来揭示网络中的社区结构。

NetworkX还提供了其他社区检测算法：

Louvain方法（通过community.greedy_modularity_communities）标签传播算法（通过community.label_propagation_communities）等

---

Girvan-Newman算法

特点：

基于边的移除：算法通过移除网络中起“桥接”作用的关键边来逐渐揭露社区结构。模块度优化：和Louvain方法一样，Girvan-Newman算法也关注于优化模块度指标，但它通过不同的策略来达到这一目标。计算复杂度高：算法的时间复杂度较高，尤其是在大规模网络中，这限制了它的实用性。层次结构：算法产生一个社区的层次结构，从整体网络到最精细的单节点社区。

实现过程：

初始化：开始时，整个网络被视为一个单一的大社区。计算边介数：对于网络中的每一条边，计算其介数（即网络中所有最短路径经过该边的比例）。介数高的边通常连接不同的社区。移除最高介数的边：找到介数最高的边并移除，这通常会分离出一些子社区。重新计算介数：在更新后的网络中重新计算所有边的介数。重复过程：重复步骤3和4，直到不再有边可以移除或满足停止条件（如模块度不再显著增加）。分析层次结构：算法结束时，可以得到一个层次结构的社区划分，从顶层的整个网络到底层的单个节点社区

---

标签传播算法 (LPA)————随机性、动态变化图、快速检测

特点：

简单快速：LPA是一种基于局部邻域信息的迭代算法，不需要任何参数设置，因此非常容易实现和快速执行。非确定性：每次运行可能会得到不同的结果，因为它依赖于初始化标签的随机性。动态适应性：适用于动态网络，能够快速适应网络结构的变化。

实现过程：

初始化：为网络中的每个节点随机分配一个唯一的标签。迭代传播：在每个迭代步骤中，每个节点更新自己的标签为邻居节点中出现次数最多的标签。收敛检查：当没有节点改变标签时，算法收敛，输出社区划分结果。

---

Louvain方法——较高的模块度优化

特点：

优化目标明确：通过最大化模块度（Modularity）来优化社区结构。层次结构：采用两阶段策略，首先在局部层面优化社区，然后在全局层面重组社区。高效性：通过多层次的优化策略，能够在大规模网络上高效运行。

实现过程：

初始化：每个节点视为独立的社区。局部优化：在每一层中，遍历网络中的每个节点，尝试将其移动到相邻的社区中，计算模块度的改变，选择模块度增加最大的移动。重构网络：将上一步中形成的社区视为超节点，重新构建网络。重复步骤2和3，直到模块度不再提高。

---

Infomap算法——适合网络规模非常大，且需要考虑信息流的角度

特点：

信息理论基础：基于最小化社区内和社区间的信息流编码长度。适合检测重叠社区：虽然原始算法不直接支持重叠社区，但有改进版本可以处理这种情况。可扩展性：适用于大规模网络，通过层次聚类减少计算复杂度。

实现过程：

构建概率转移矩阵：基于网络中的边权重，计算节点之间的转移概率。层次聚类：使用树状图（Dendrogram）表示节点之间的关系，通过信息理论原则分割树状图，形成社区。最小化码率：寻找最优的社区划分，使得信息流编码的总长度最短。

---

若需要快速得到结果且网络是动态变化的，LPA可能是首选；如果追求较高的模块度优化，Louvain方法更为合适；而如果网络规模非常大，且需要考虑信息流的角度，Infomap算法则可能更为适用。Girvan-Newman高计算成本，通常不适用于非常大的网络。

---

communities = girvan_newman(G) #用于社区检测的算法，它基于边的“边介数”来迭代地移除图中的边，直到将图分割成多个社区。 #这个过程通常通过计算图中所有边的边介数开始，然后移除边介数最高的边， #并重复这个过程，直到满足某个停止条件（比如达到预定的社区数量，或者边的边介数低于某个阈值）。 node_groups = [] for com in next(communities): node_groups.append(list(com)) # 根据社区划分设置节点颜色 color_map = [] for node in G: if node in node_groups[0]: color_map.append('green') else: color_map.append('red') plt.figure(figsize = (14,9)) nx.draw_networkx(G, pos = nx.circular_layout(G), node_color=color_map, node_size = 400, with_labels=True) plt.savefig('社区划分，circular_layout.svg')