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.
Advertisement
Answer
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: