Degeneracy given a graph

Question

An exercise requires to determine the degenerative level of a graph. To do that, I have found useful the following code (source: https://www.geeksforgeeks.org/find-k-cores-graph/) which represents an undirected graph using adjacency list representation

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()

An example of data that I am using for building a graph is

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

I have tried to calculate the adjacency list as follows:

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

but this format does not suit the code above. I would like to see how I can use my data with the code mentioned at the top, in order to visually representating the k-core found. Feel free to use a different dataset, bigger than mine, in case you need.

Answer 1

You can compute and visualize k-cores in a few lines with networkx.

First, load your dataset (I saved the data in a file called 'graph.txt') in a pandas dataframe with df=pd.read_fwf('graph.txt'). You can then create a networkx graph from this dataframe with G=nx.from_pandas_edgelist(df, 'Node', 'Target'). To calculate the k-cores of your graph you can use nx.k_core(G). Without any k arguments, it will return the main core of your graph. You can then draw your main core with nx.draw. Overall the code looks like that:

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()

And the output of this code gives: