如何优化k-plex检测代码以提升大型图的运行速度？

你的两段k-plex检测代码在小图上表现正常，但在jazz、karate这类中型图中性能瓶颈明显，核心原因是频繁创建子图、重复计算邻居关系、冗余遍历以及低效的集合判断。以下是针对性的优化方案：

1. 核心判断函数的性能优化 #

优化isKPlex：避免子图创建，直接用集合运算计算度数 #

原函数每次创建子图再遍历邻居，开销极大。改为直接利用原图预存的邻居集合，通过交集运算快速得到子图内的节点度数：

def isKPlex(G, node_set, k):
    n = len(node_set)
    # 预存所有节点的邻居集合（仅第一次调用时生成）
    if not hasattr(G, 'neighbor_sets'):
        G.neighbor_sets = {u: set(G.neighbors(u)) for u in G.nodes()}
    for u in node_set:
        # 子图中u的度数 = 原图邻居与当前节点集合的交集大小
        sub_degree = len(G.neighbor_sets[u] & node_set)
        if sub_degree < (n - k):
            return False
    return True

优化isMaximalKPlex：缩小待检查节点范围 #

原函数遍历原图所有节点，实际上只有当前k-plex集合的邻居节点才有可能加入后仍满足k-plex条件，大幅减少遍历数量：

def isMaximalKPlex(G, node_set, k):
    if not isKPlex(G, node_set, k):
        return False
    # 只收集当前集合的邻居中不在集合内的节点
    candidate_nodes = set()
    for u in node_set:
        candidate_nodes.update(G.neighbor_sets[u])
    candidate_nodes -= node_set
    # 检查每个候选节点加入后是否仍为k-plex
    for v in candidate_nodes:
        if isKPlex(G, node_set | {v}, k):
            return False
    return True

2. 数据结构与枚举逻辑优化 #

用set存储结果集合，快速去重 #

原代码用list存储listOfMaximals，判断P in listOfMaximals是O(n)复杂度，改为用set存储frozenset，判断速度提升至O(1)：

def listEnum(G, k):
    full_node_set = set(G.nodes())
    if isKPlex(G, full_node_set, k):
        return [full_node_set]
    else:
        C = full_node_set
        listOfMaximals = set()  # 用set存frozenset，快速去重
        excluded = []
        for c in C:
            buildMaximal(G, k, {c}, C - {c}, listOfMaximals, excluded)
            neighbors = G.neighbor_sets[c]
            buildMaximal(G, k, neighbors | {c}, C - (neighbors | {c}), listOfMaximals, excluded)
        print("Excluded size = " + str(len(excluded)))
        # 转换回list[set]格式
        return [set(s) for s in listOfMaximals]

def buildMaximal(G, k, P, C, listOfMaximals, excluded):
    frozenset_P = frozenset(P)
    if frozenset_P in listOfMaximals:
        return
    if isMaximalKPlex(G, P, k):
        listOfMaximals.add(frozenset_P)
        return
    if C:
        # 遍历C的副本，避免修改原集合导致的迭代错误
        for c in list(C):
            new_P = P | {c}
            if isKPlex(G, new_P, k):
                buildMaximal(G, k, new_P, C - {c}, listOfMaximals, excluded)
            else:
                if frozenset_P not in listOfMaximals:
                    excluded.append(P)

预计算邻居集合，避免重复生成 #

在读取图之后立即预计算所有节点的邻居集合，后续所有函数复用该数据：

G = readGraph('test.txt')
# 预计算每个节点的邻居集合，全局复用
G.neighbor_sets = {u: set(G.neighbors(u)) for u in G.nodes()}
nx.draw_spring(G, with_labels=True)
plt.show()

3. 剪枝与递归优化 #

提前剪枝不可能成为k-plex的分支 #

利用k-plex的性质：当集合大小n <= 2k-1时，连通的集合必然是k-plex（因为每个节点只需要与至少n-k个节点相邻，而n-k <= k-1，连通集合满足该条件）。在递归函数中加入剪枝逻辑：

def listKPlexRecursive(G, k, candidate_set, listOfMaximals, memo=None):
    if memo is None:
        memo = set()
    key = (frozenset(candidate_set), k)
    if key in memo:
        return
    n_candidate = len(candidate_set)
    # 剪枝：小连通集合直接判断是否为极大k-plex
    if n_candidate <= 2*k -1:
        subgraph = G.subgraph(candidate_set)
        if nx.is_connected(subgraph) and isMaximalKPlex(G, candidate_set, k):
            frozenset_cand = frozenset(candidate_set)
            if frozenset_cand not in listOfMaximals:
                listOfMaximals.append(candidate_set)
        memo.add(key)
        return
    # 原逻辑
    if isMaximalKPlex(G, candidate_set, k):
        frozenset_cand = frozenset(candidate_set)
        if frozenset_cand not in listOfMaximals:
            listOfMaximals.append(candidate_set)
        memo.add(key)
        return
    else:
        if not isKPlex(G, candidate_set, k) and nx.is_connected(G.subgraph(candidate_set)):
            for vertex in candidate_set:
                next_set = candidate_set - {vertex}
                listKPlexRecursive(G, k, next_set, listOfMaximals, memo)
            memo.add(key)

4. 辅助函数的效率提升 #

用NetworkX内置函数优化图读取 #

原readGraph函数手动遍历行读取，改用NetworkX内置的read_edgelist，效率更高，同时补充单节点行的处理：

def readGraph(f):
    # 用内置函数读取边列表，比手动实现更高效
    G = nx.read_edgelist(f, create_using=nx.Graph(), nodetype=str)
    # 补充处理单节点行（read_edgelist不会自动添加孤立节点）
    with open(f, 'r') as fobj:
        for line in fobj:
            vertices = line.strip().split()
            if len(vertices) == 1:
                G.add_node(vertices[0])
    return G

优化后的效果 #

这些优化主要从减少子图创建、避免重复计算、缩小遍历范围、快速去重四个维度入手，能将中型图（如karate，34节点）的运行速度提升数倍至数十倍，对于更大的图也能显著降低时间开销。

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