给定图形的退化

Question

练习需要确定图形的退化级别。为此，我发现以下代码（来源：https://www.geeksforgeeks.org/find-k-cores-graph/）很有用，它使用邻接表表示

表示无向图

from collections import defaultdict

class Graph:
 
    def __init__(self):
 
        self.graph = defaultdict(list)
 
    # function to add an edge to undirected graph
    def addEdge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)
 
    def DFSUtil(self, v, visited, vDegree, k):
 
        visited.add(v)
 
        for i in self.graph[v]:
 
            # vDegree of v is less than k, then vDegree of
            # adjacent must be reduced
            if vDegree[v] < k:
                vDegree[i] = vDegree[i] - 1
 
            # If adjacent is not processed, process it
            if i not in visited:

                self.DFSUtil(i, visited, vDegree, k)
 
    def PrintKCores(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)

        for i in list(self.graph):
 
            if degree[i] >= k:
                print(str("\n [ ") + str(i) + str(" ]"), end=" ")
 
                for j in self.graph[i]:
                    if degree[j] >= k:
                        print("-> " + str(j), end=" ")
 
                print()

我用来构建图表的数据示例是

Node Target Label
A      F      1
A      B      1
A      N      1
B      A      0
B      F      0 
C      F      1
A      V      1
D      S      0
D      E      0
F      A      1
F      B      1
F      G      1
G      E      0
E      W      0

我尝试计算邻接表如下：

df['adjacency_list'] = df.apply(lambda s: df[(df['Node'] == s.Target)].index.tolist(), axis=1)

但是这种格式不适合上面的代码。我想看看如何将我的数据与顶部提到的代码一起使用，以便直观地表示找到的 k-core。随意使用不同的数据集，比我的大，以备不时之需。

Answer 1

您可以使用 networkx 在几行中计算和可视化 k 核。

首先，将您的数据集（我将数据保存在一个名为 'graph.txt' 的文件中）加载到 pandas 数据帧中 df=pd.read_fwf('graph.txt')。然后，您可以使用 G=nx.from_pandas_edgelist(df, 'Node', 'Target') 从该数据帧创建一个 networkx 图。要计算图表的 k 核，您可以使用 nx.k_core(G)。没有任何 k 参数，它将 return 成为图表的主要核心。然后你可以用 nx.draw 画出你的主要核心。总体而言，代码如下所示：

import matplotlib.pyplot as plt
import numpy as np
import networkx as nx
import pandas as pd

df=pd.read_fwf('graph.txt')
G=nx.from_pandas_edgelist(df, 'Node', 'Target')
kcore=nx.k_core(G)

plt.subplot(121)
plt.title('Full graph')
nx.draw(G,with_labels=True)


plt.subplot(122)
plt.title('Main core')
nx.draw(kcore,with_labels=True)

plt.show()

此代码的输出为：

给定图形的退化

Degeneracy given a graph

python

visualization

networkx

pandas