邻接矩阵转连通性索引：二阶及高阶连通性索引实现求助

核心思路 #

首先预计算所有节点的度数（避免循环中重复求和），然后通过深度优先搜索（DFS）遍历所有符合长度要求的路径，累加对应项的贡献。该方案支持任意阶数的连通性索引计算，同时可选择是否允许路径中出现重复节点（环）。

优化后的一阶索引实现 #

先优化你已实现的一阶Randic索引，通过预计算度数+遍历上三角矩阵提升效率：

import numpy as np

def randic_index(A):
    deg = np.sum(A, axis=1)  # 预计算所有节点度数
    n = A.shape[0]
    total = 0.0
    # 只遍历上三角，避免重复计算i-j和j-i
    for i in range(n):
        for j in range(i+1, n):
            if A[i,j] != 0:
                total += 1 / np.sqrt(deg[i] * deg[j])
    return total

通用高阶连通性索引函数 #

支持任意阶数，兼容无向图去重处理：

def higher_order_connectivity(A, order, allow_cycles=False):
    deg = np.sum(A, axis=1)
    inv_sqrt_deg = 1 / np.sqrt(deg)  # 预计算度数平方根的倒数，提升效率
    n = A.shape[0]
    total = 0.0

    def dfs(current_node, path, depth):
        nonlocal total
        # 达到指定阶数时，计算当前路径的贡献
        if depth == order:
            contribution = np.prod([inv_sqrt_deg[node] for node in path])
            total += contribution
            return
        # 遍历当前节点的所有邻居
        for neighbor in range(n):
            if A[current_node, neighbor] != 0:
                # 不允许环时，跳过路径中已存在的节点
                if not allow_cycles and neighbor in path:
                    continue
                dfs(neighbor, path + [neighbor], depth + 1)

    # 从每个节点出发遍历所有路径
    for start in range(n):
        dfs(start, [start], 0)

    # 无向图中每个路径会被正向/反向各计算一次，因此除以2去重
    return total / 2

示例使用（基于你的邻接矩阵） #

# 构造示例邻接矩阵
A = np.array([
    [0.0, 1.0, 0.0, 0.0, 0.0, 0.0],
    [1.0, 0.0, 1.0, 0.0, 0.0, 0.0],
    [0.0, 1.0, 0.0, 1.0, 0.0, 0.0],
    [0.0, 0.0, 1.0, 0.0, 1.0, 0.0],
    [0.0, 0.0, 0.0, 1.0, 0.0, 1.0],
    [0.0, 0.0, 0.0, 0.0, 1.0, 0.0]
])

# 计算一阶连通性索引CF
cf = higher_order_connectivity(A, 1)
print(f"一阶连通性索引CF: {cf:.4f}")  # 输出约2.9142

# 计算二阶连通性索引CS
cs = higher_order_connectivity(A, 2)
print(f"二阶连通性索引CS: {cs:.4f}")  # 输出约1.7071

# 计算三阶连通性索引（示例）
ct = higher_order_connectivity(A, 3)
print(f"三阶连通性索引CT: {ct:.4f}")

关键说明 #

1. 阶数定义：order=1对应一阶邻居（边），order=2对应二阶邻居（长度为2的路径），以此类推。
2. 环控制：allow_cycles=False时，只计算无重复节点的简单路径，符合多数连通性索引的定义；若允许环，设置为True即可。
3. 效率优化：预计算度数和其平方根倒数，避免循环中重复计算；DFS遍历确保不遗漏任何符合条件的路径。

内容的提问来源于stack exchange，提问作者YZman