如何使用给定Python代码计算图degeneracy（k-core）并适配自定义数据集

1. 数据集适配原k-core代码 #

你之前的邻接表生成方式不符合原代码要求，原代码的Graph类已经内置了邻接表维护逻辑，不需要手动生成，只需要遍历你的边数据集调用addEdge方法即可。注意要先对重复边去重（你的示例数据中同一条无向边会在两条记录中重复出现，比如A-F既出现在Node=A行也出现在Node=F行）：

import pandas as pd

# 读取示例数据，sep='\s+'适配多空格分隔格式
df = pd.read_csv("your_data_path.csv", sep='\s+')

# 去重无向边：将边转为排序后的元组去重，避免重复添加同一条边
unique_edges = list({tuple(sorted([row.Node, row.Target])) for _, row in df.iterrows()})

# 初始化原代码的Graph实例
g = Graph()
# 批量添加边
for u, v in unique_edges:
    g.addEdge(u, v)

# 测试调用，打印2-core结果
g.PrintKCores(2)

2. k-core可视化实现 #

我们可以扩展原Graph类，新增返回k-core节点和边的方法，配合networkx+matplotlib实现可视化：

2.1 扩展Graph类 #

在原Graph类中新增如下方法即可：

def getKCores(self, k):
    visit = set()
    degree = defaultdict(lambda: 0)
    for i in list(self.graph):
        degree[i] = len(self.graph[i])
    for i in list(self.graph):
        if i not in visit:
            self.DFSUtil(i, visit, degree, k)
    # 收集符合条件的节点
    core_nodes = [i for i in self.graph if degree[i]>=k]
    # 收集符合条件的边
    core_edges = []
    for u in core_nodes:
        for v in self.graph[u]:
            if v in core_nodes and (v, u) not in core_edges:
                core_edges.append((u, v))
    return core_nodes, core_edges

2.2 可视化代码 #

import networkx as nx
import matplotlib.pyplot as plt

def plot_kcore(core_nodes, core_edges):
    nx_g = nx.Graph()
    nx_g.add_nodes_from(core_nodes)
    nx_g.add_edges_from(core_edges)
    # 选固定种子的弹簧布局保证输出结果一致
    pos = nx.spring_layout(nx_g, seed=42)
    # 绘制节点
    nx.draw_networkx_nodes(nx_g, pos, node_size=700, node_color='lightblue')
    # 绘制边
    nx.draw_networkx_edges(nx_g, pos, edgelist=core_edges, width=2)
    # 绘制节点标签
    nx.draw_networkx_labels(nx_g, pos, font_size=12, font_weight='bold')
    plt.axis('off')
    plt.show()

# 示例：获取2-core并绘制
k = 2
nodes, edges = g.getKCores(k)
plot_kcore(nodes, edges)

3. 图degeneracy等级计算 #

图的degeneracy等级是最大的k值，使得该图存在非空k-core，计算方法如下：

def calc_degeneracy(g):
    # 先获取所有节点的最大度作为遍历上限
    max_degree = max(len(adj) for adj in g.graph.values()) if g.graph else 0
    for k in range(max_degree, 0, -1):
        nodes, _ = g.getKCores(k)
        if len(nodes) > 0:
            return k
    return 0

# 计算示例数据的degeneracy等级
print("图的degeneracy等级为：", calc_degeneracy(g))

你提供的示例数据最大非空k-core是2-core，对应degeneracy等级为2。

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