Does anyone know how to compute node degree distribution in a graph ? I am talking about a large graph for example California road network and imagine we have some data such as number of nodes and number of edges and now we want to visualize data by histogram for distribution of nodes degrees.Is there any specific formula ?the link is included : https://snap.stanford.edu/data/roadNet-CA.html
5
-
$\begingroup$ If all you know is the number of vertices and the number of edges, then essentially all you know about the degree distribution is its expectation. $\endgroup$– Yuval FilmusCommented Nov 7, 2019 at 21:20
-
$\begingroup$ Thank you for your reply and we have some other information such as Nodes in largest WCC so you mean we should skip wcc and only focus on node and edges for visualizing ? $\endgroup$– graphicart86Commented Nov 7, 2019 at 22:06
-
1$\begingroup$ The link allows you to download the actual network. Given the network, it's easy to compute the degree distribution. $\endgroup$– Yuval FilmusCommented Nov 7, 2019 at 22:07
-
$\begingroup$ yes , thank you so much it was my mistake , so now I should use coding for that ? I mean python codes ? could you please help me more? $\endgroup$– graphicart86Commented Nov 7, 2019 at 22:11
-
1$\begingroup$ Coding is off-topic here. $\endgroup$– Yuval FilmusCommented Nov 7, 2019 at 22:12
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
To compute the node degree distribution, compute the degree of each node in the graph; then compute the distribution of these numbers (e.g., display a histogram of them). Each of those tasks is a straightforward coding exercise.
$\begingroup$
$\endgroup$
I know the question was asked long ago. Just responding to this so that others might get the help.
You can easily plot and visualize the degree distribution using the NetworkX library. It is a python based library for doing graph analysis. Here is a sample code that you can use to visualize the degree distribution of California road network. Hope you will find it useful.
# import libraries
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import collections as collec
%matplotlib inline
# reading roadNet-CA graph.
G_road = nx.read_edgelist("/data/roadNet-CA.el", nodetype=int, comments='#', create_using=nx.DiGraph)
# Calculate out degrees of roadNet-CA graph
out_degrees = G_road.out_degree() # dictionary node:degree
out_values = sorted([d for n, d in out_degrees])
out_set = set(out_values)
# building the histogram
out_hist = []
for x in out_set:
cnt = out_values.count(x)
for i in range(cnt):
out_hist.append(cnt)
# log-log ploting the out-degree distribution
plt.figure(figsize=(12, 8))
plt.grid(True)
plt.loglog(out_values, out_hist, 'bv-') # out-degree
plt.xlabel('Out Degree')
plt.ylabel('Number of nodes')
plt.title('Out-degree distribution (Log-Log) of RoadNet graph')
plt.show()
```
