Python使用NetworkX计算图节点graphlet度的实现方案咨询

Graphlet度的核心统计逻辑是：对指定大小k，统计每个节点作为成员参与的所有连通k节点诱导子图（即k阶graphlet）的数量，不需要区分graphlet类型时直接累加总数即可，需要做更细粒度的图特征分析时可以按graphlet拓扑类型分别计数得到Graphlet度向量（GDV）。

基础实现（适配k≤3、节点数百级以内的场景） #

这个版本逻辑无黑箱、依赖只有NetworkX本身，开箱即用：

• 先固定你要统计的graphlet节点规模k，日常用的最多的是k=3、k=4两个规格，k≥5时计算量会指数级上升，非必要不要选太大的k值
• 枚举所有k个节点的组合，提取对应的诱导子图，过滤掉不连通的子图，剩下的就是合法的k阶graphlet
• 遍历每个合法graphlet包含的节点，给对应节点的计数值加1，最后补全没有参与任何graphlet的节点计数为0即可

import networkx as nx
from itertools import combinations
from collections import defaultdict

def count_graphlet_degree(G, k=3):
    """
    计算无向图中每个节点的k阶graphlet度
    参数:
        G: NetworkX无向图对象
        k: 单个graphlet包含的节点数，默认统计3阶graphlet
    返回:
        字典，键为节点ID，值为对应节点的k阶graphlet总计数
    """
    node_gd = defaultdict(int)
    # 遍历所有k节点组合
    for node_combo in combinations(G.nodes(), k):
        subgraph = G.subgraph(node_combo)
        # 仅保留连通的诱导子图
        if nx.is_connected(subgraph):
            for node in node_combo:
                node_gd[node] += 1
    # 补全孤立节点/未参与任何graphlet的节点计数
    for node in G.nodes():
        node_gd.setdefault(node, 0)
    return dict(node_gd)

# 调用示例
if __name__ == "__main__":
    # 拿NetworkX自带的空手道俱乐部测试图跑样例
    test_G = nx.karate_club_graph()
    gd_3 = count_graphlet_degree(test_G, k=3)
    print(f"节点0的3阶graphlet度为: {gd_3[0]}")

优化方案（适配k=4/5、节点数千级的场景） #

基础版全量枚举的组合数随节点数上涨太快，千节点以上场景可以做几个剪枝优化，不需要换框架：

• 邻域剪枝：任何包含节点v的k阶graphlet，所有节点必然在v的k-1跳邻域内，不需要遍历全局节点组合，只需要针对每个节点，在它的邻域范围内枚举剩余k-1个节点即可，能砍掉99%以上的无效遍历
• 预计算复用：k=3的场景不用全量枚举，直接调用NetworkX自带的nx.triangles()拿到三角形计数，再结合每个节点的度算楔形数量，两者相加就是3阶graphlet度，速度比全量枚举快10倍以上
• 大图采样：节点数万以上的大图不要做精确计数，改用随机采样策略：每次随机选一个根节点，在它的邻域内随机抽k-1个节点判断对应诱导子图是否连通，重复足够多次后按采样率折算计数，误差可控的前提下速度能提升几个数量级

如果需要统计区分拓扑类型的Graphlet度向量，只需要在拿到连通诱导子图后，计算子图的边数、度序列等拓扑特征，匹配对应graphlet的类型编号，再给对应节点的对应类型计数位累加即可，不需要额外引入重型图计算库。

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