关键节点识别是网络科学中的一个重要研究领域，旨在从复杂的网络结构中找出那些在信息传播、影响力扩散等方面具有重要作用的节点。这一过程通常基于一系列的中心性指标来衡量节点的重要性，包括但不限于度数中心性、介数中心性、接近中心性、特征向量中心性等。通过识别这些关键节点，不仅可以帮助我们理解网络的基本结构和功能，还能为各种实际应用提供指导，如优化社会网络中的信息传播途径、提升技术网络的鲁棒性和安全性、改善医疗网络中的疾病防控策略等。因此，关键节点识别不仅是理论研究的重要组成部分，也是诸多实际问题解决的关键所在。随着网络科学的发展，这一领域的研究方法和技术也在不断创新，为更精准、高效的网络分析提供了坚实的基础，下面介绍重要节点识别比较经典的指标。

1.度中心性

度中心性（Degree Centrality）是一种衡量复杂网络中节点重要性的基本指标。它是指一个节点在无向图中直接相连的边的数量，或者在一个有向图中，它可以被拆分为出度（从该节点出发的边的数量）和入度（指向该节点的边的数量）。度中心性越高，表示该节点与其他节点的直接连接越多，这意味着它在网络中占据更为中心的位置。

计算代码：

# 计算每个节点的度中心性
degree_centrality = nx.degree_centrality(G)

度中心性虽然简单有效，但它也有局限性，比如它无法捕捉到节点在网络中的相对位置以及节点间的关系复杂度。因此，在很多情况下，研究者还会结合其他中心性指标一起使用，以获得更全面的网络结构理解。

2.介数中心性

介数中心性（Betweenness Centrality）是一种衡量网络中节点重要性的指标，它反映了某个节点在网络中的中介作用。具体来说，介数中心性衡量的是一个节点在所有节点对之间最短路径上的出现次数。具有高介数中心性的节点意味着它们在网络中起到重要的“桥梁”作用，是信息、资源或其他形式流动的关键路径。

介数中心性的定义是由Freeman在1977年提出的。对于一个无向图中的节点 v，其介数中心性 CB​(v) 可以定义为：

其中，σst​ 表示所有从节点 s 到节点 t 的最短路径数量，而 σst​(v) 是这些路径中包含节点 v 的路径数量。

生成代码：

# 计算每个节点的介数中心性
betweenness_centrality = nx.betweenness_centrality(G)

介数中心性在研究网络结构和功能时非常有用，在所有中心性指标中对于节点重要性识别度是最高的，可以帮助我们识别出那些在网络中起着关键连接作用的节点。但是介数中心性的计算通常是一个较为耗时的过程，特别是对于大型网络。这是因为需要遍历所有节点对之间的最短路径，并统计每个节点在这过程中出现的次数。

3.接近中心性

接近中心性（Closeness Centrality）是衡量网络中节点重要性的一种指标，它强调的是节点在网络中的可达性，即一个节点到达网络中其他所有节点的平均距离。接近中心性高的节点意味着它能够快速地与其他节点通信或交互，因此在网络中具有较高的地位。

接近中心性的定义基于节点间的最短路径长度。对于无向图中的节点 v，其接近中心性 CC​(v) 可以定义为：

其中 n 是网络中总的节点数，d(u,v) 表示从节点 u 到节点 v 的最短路径长度（即距离）。对于有向图，接近中心性也可以通过类似的方式定义，只是需要考虑到方向性。

生成代码：

# 计算每个节点的接近中心性
closeness_centrality = nx.closeness_centrality(G)

高接近中心性的节点往往在网络结构中占据重要的地位，能够更快速地影响到整个网络系统，从而在某些应用场景下显得极为关键。然而，这种方法也有其局限性，比如在计算上较为复杂，尤其是在处理大型网络时，寻找所有节点间的最短路径是一个计算密集型的任务。此外，接近中心性对网络的整体结构敏感，当网络包含多个不连通的组件时，这种方法的效果会受到影响，而且它没有考虑到信息实际流动过程中可能存在的多重路径选择问题，因此在某些情况下可能不能完全反映节点的实际影响力。

4.特征向量中心性

特征向量中心性（Eigenvcentrality）是另一种用于评估网络中节点重要性的方式。与简单的度中心性（Degree Centrality）相比，特征向量中心性不仅考虑了节点的直接邻居数量，还考虑了通过邻居连接的间接影响。这意味着一个节点的重要性不仅取决于它直接连接了多少个其他节点，还取决于这些邻居本身的中心性。

在一个网络中，如果一个节点连接了许多高中心性的节点，那么这个节点本身也会被认为是非常重要的。特征向量中心性正是通过这种方式来量化节点在整体网络中的相对重要性。具体来说，特征向量中心性是通过求解网络邻接矩阵的主特征向量来获得的，即找到一个向量，其中每个节点的得分是其所有邻居得分的加权总和，并且这个向量是邻接矩阵的最大特征值对应的特征向量。

特征向量中心性（Eigenvector Centrality）可以通过数学公式来表示。假设有一个无向图 G=(V,E)，其中 V 是节点集合，E 是边的集合。定义一个节点 v 的特征向量中心性 xv​ 可以用以下形式表示：

Ax=λx

这里 A 是图的邻接矩阵，其中 Aij​ 表示从节点 i 到节点 j 的连接情况；如果节点 i 和节点 j 之间有边，则 Aij​=1，否则 Aij​=0（这个知识点一般在《数据结构》课程中会学到）。向量 x 包含每个节点的中心性得分，而 λ 是最大的特征值。

生成代码：

# 计算特征向量中心性
eigenvector_centrality = nx.eigenvector_centrality(G)

5.信息熵

信息熵是信息论中的一个基本概念，它由克劳德·香农（Claude Shannon）在1948年首次提出，用来量化信息的不确定性或信息源的平均信息含量。在信息论中，熵通常被定义为消息出现的概率分布的期望值，它反映了不确定性的程度。

信息熵的数学定义基于概率论，通常对于一个离散随机变量 X 具有概率分布p(x)，其信息熵 H(X) 定义为：

信息熵在复杂领域已经有了广泛的应用，不同研究者将信息熵中的概率分布结合复杂网络中的某些信息相结合，如介数中心性。同样可以作为复杂网络鲁棒性衡量的一个标准。

生成代码：

import math

def entropy(probabilities):
    """
    计算给定概率分布的信息熵。
    
    参数:
        probabilities (list): 随机变量各个状态的概率分布列表。
        
    返回:
        float: 信息熵。
    """
    # 确保概率和为1
    if not math.isclose(sum(probabilities), 1.0):
        raise ValueError("The sum of probabilities must be 1.")
    
    # 计算信息熵
    ent = 0.0
    for p in probabilities:
        if p > 0:
            ent -= p * math.log2(p)
    
    return ent

# 示例：计算一个公平硬币投掷的信息熵
probabilities = [0.5, 0.5]  # 假设这是一个公平硬币投掷的概率分布
h = entropy(probabilities)
print(f"The entropy is: {h:.4f} bits")

6.结构洞

结构洞（Structural Holes）是社会网络分析中的一个概念，由社会学家罗纳德·博特（Ron Burt）提出。结构洞指的是在一个网络中，两个节点之间没有直接联系的情况，即这两者间存在一个“空隙”或者“洞”。这个概念主要用于描述网络中节点之间的间接连接，并且强调了这些“洞”的存在对于网络中信息流、资源分配以及权力分配的影响。

在社会网络中，如果一个节点位于其他两个节点之间的唯一路径上，那么这个节点就被认为占据了结构洞。占据结构洞的节点具有中介作用，可以控制信息或资源的流向。这些节点可以利用自己处于结构洞的位置来获取信息优势，从而在社会或经济活动中获得利益。

结构洞（Structural Holes）的概念虽然不像中心性度量那样直接通过单一的数学公式来表达，但它可以通过一系列指标来度量。其中，一个常用的相关度量是“约束度”（Constraint），它帮助我们理解一个节点在其网络中的结构洞的程度。约束度高的节点意味着其邻居之间也相互连接，形成了一个紧密的小团体；相反，约束度低的节点意味着其邻居之间缺乏直接联系，表明该节点可能位于结构洞中。

罗纳德·博特提出的约束度公式可以用来量化一个节点与其邻居之间的紧密程度。对于节点 i，其约束度 Ci​ 可以表示为：

aij​ 是邻接矩阵中的元素，上面已经讲过了，就不赘述了。djk​ 表示节点 j 和 k 之间的最短路径长度，同理。pi​ 是节点 i 的邻居数量（度数）。

需要注意的是，结构洞的概念更多是关于网络结构的描述和分析，而不是像中心性度量那样可以直接用一个简单的公式来表达。在实际分析中，研究者可能会使用多种方法和技术来识别和量化结构洞的存在及其影响。

生成代码：

def calculate_constraint(G):
    """
    计算给定图中所有节点的约束度。

    参数:
        G (networkx.Graph): 一个无向图。

    返回:
        dict: 每个节点的约束度。
    """
    constraint_dict = nx.constraint(G)
    return constraint_dict

7.k-shell值（k-core分解）

K-shell分解是一种用于分析复杂网络结构的技术，它可以帮助揭示网络的层次结构。这种方法最初是在凝聚态物理的研究中发展起来的，后来被引入到社会网络和其他复杂网络的研究中。K-shell 分解的核心思想是通过迭代地去除网络中度数（邻居节点的数量）最小的节点，直到无法再去除任何节点为止。这个过程会不断重复，直到网络中不再有节点可以去除。在每次去除节点之后，都会重新计算剩余节点的度数，并继续移除最低度数的节点。图片来源（吴亚丽,任远光,董昂,等.基于邻域 K-shell 分布的关键节点识别方法[J].计算机工程与应 用,2024,60(02):87-95.）。

在图中，先找到度值为1的节点，分别有节点9、10、12、13、14、15，移除这些节点后，发现节点11的度值也为1，可以看出，最后被分配度值为1的节点有9，10，11，12，13，14，15。同理分配度值为2的节点有5，6，7，8。分配度值为3的节点有1，2，3，4。分配k-shell越大的节点被认为是越重要的节点，也就越处于网络的核心地带。k-shell方法的提出对于复杂网络重要节点识别有着不容忽视的推进作用，对复杂系统的保护有着一定的指导意义。

生成代码：

def k_shell_decomposition(G):
    """
    执行K-shell分解并返回每个节点所在的K-shell。

    参数:
        G (networkx.Graph): 输入图。

    返回:
        shells (dict): 键是节点，值是该节点所在的K-shell编号。
    """
    # 复制图以避免修改原始图
    graph_copy = G.copy()
    shells = {}
    
    # 当图中还有节点时继续循环
    while graph_copy:
        # 获取当前图中度数最小的度数
        min_degree = min(dict(graph_copy.degree()).values())
        
        # 找到所有度数等于最小度数的节点
        nodes_to_remove = [n for n, d in graph_copy.degree() if d == min_degree]
        
        # 移除这些节点并记录它们所在的K-shell编号
        for node in nodes_to_remove:
            shells[node] = min_degree
            graph_copy.remove_node(node)
    
    return shells

整理不易，谢谢各位的点赞，比心！！！