In [2]:
import networkx as nx
G = nx.gnp_random_graph(50, 0.2)
nx.draw(G)
Model $G(n,p)$ has different degree distribution than real graphs. In the case $G(n,p)$ the degree distribution behaves Poisson distribution, whereas real networks often have the scale-free property. For this reason there are several other network models, which try to fix this issue.
It has given degree sequence $k_1, k_2, \ldots, k_n$, where $k_i = \deg(v_i)$, so $m = \frac{1}{2}\sum_i k_i$. Configuration model is analogy of $G(n,m)$ with given degree sequence.
Generating random network in configuration model:
A graph has power-law degree distribution, if its degree distribution is in the form $p_k = C k^{-\alpha}$. Usually we consider $2 \leq \alpha \leq 3$.
Analogy of $G(n,p)$. We set weights $w_i$ corresponding to mean degree.
Probability $p_{i,j}$ of an edge between $v_i$ and $v_j$ is given by $$p_{ij}=\begin{cases} \frac{w_iw_j}{2m} & \text{ for } i\neq j\\ \frac{w_i^2}{2m} & \text{ for } i = j \end{cases}$$
We define $m = \frac{1}{2}\sum_i w_i$. Mean number of edges is $$ \sum_{i < j} p_{ij} + \sum_i p_{ii} = \sum_{i < j} \frac{w_iw_j}{2m} + \sum_i \frac{w_i^2}{2m} = \sum_{ij} \frac{w_iw_j}{4m} = m $$ and similarly the mean degree of a vertex $v_i$ is $$\langle k_i \rangle = 2p_{ii} + \sum_{j\neq i} p_{ij} = \frac{w_i^2}{2m} + \sum_{j\neq i} \frac{w_iw_j}{2m} = \sum_{j} \frac{w_iw_j}{2m} = w_i.$$
Random graphs $G(n,p)$ and $G(n,m)$ can be generated by NetworkX as follows:
import networkx as nx
G = nx.gnp_random_graph(50, 0.2)
nx.draw(G)
import networkx as nx
G = nx.gnm_random_graph(10, 15)
nx.draw(G)
More types of random graphs and details to their implementation can be found in the documentation: https://networkx.org/documentation/stable/reference/generators.html#module-networkx.generators.random_graphs
Task 1: Randomly generate set of 100 graphs on $n$ vertices with probability of an edge $p$ for given $n$ and $p$. Compare average values for the set of graphs with theoretical values for $G(n,p)$ from the lecture for the following parameters
import networkx as nx
import collections
import matplotlib.pyplot as plt
import math
def generate_random_graphs(k, n, p):
# k ... number of random graphs generated
# n ... number of vertices
# p ... probability of an edge
random_graphs = []
for i in range(k):
random_graphs.append(nx.gnp_random_graph(n,p))
return random_graphs
def average_degree(graph):
deg_sum = 0
for i in graph.nodes():
deg_sum += graph.degree[i]
return deg_sum/len(graph.nodes())
def average_degree_of_collection(random_graphs):
sum_avg_deg = 0
for g in random_graphs:
sum_avg_deg += average_degree(g)
return sum_avg_deg/len(random_graphs)
def average_degree_of_gnp(n,p):
return p * (n-1)
def degree_distribution(graph):
degree_sequence = sorted([graph.degree[i] for i in graph.nodes()], reverse=True)
return collections.Counter(degree_sequence).items()
def average_degree_distribution(random_graphs):
deg_distr_col = {}
n = len(random_graphs[0].nodes())
for g in random_graphs:
for deg, count in degree_distribution(g):
if deg in deg_distr_col:
deg_distr_col[deg] += count
else:
deg_distr_col[deg] = count
for deg, count in deg_distr_col.items():
deg_distr_col[deg] = count/len(random_graphs)
return deg_distr_col
def degree_distribution_of_gnp(n,p):
random_deg_distr = {}
for i in range(1, n+1):
random_deg_distr[i] = n * math.comb(n-1, i)*pow(p, i)*pow((1-p), n-1-i)
return random_deg_distr
def draw_deg_dist_from_dict(dictionary):
degree, count = zip(*dictionary.items())
plt.bar(degree, count)
plt.title("Degree distribution of vertices")
plt.ylabel("Frequency")
plt.xlabel("Degree")
plt.draw()
return
n = 50
p = 0.2
collection = generate_random_graphs(100,n,p)
print("Average degree in random graph: {}".format(average_degree_of_gnp(n, p)))
print("Average degree on generated instances: {}".format(
average_degree_of_collection(collection)))
draw_deg_dist_from_dict(average_degree_distribution(collection))
draw_deg_dist_from_dict(degree_distribution_of_gnp(n,p))
Average degree in random graph: 9.8 Average degree on generated instances: 9.929200000000002
Task 2: Generate reasonably large random graph $G(n,p)$ and find around which value of $p$
import math
import matplotlib.pyplot as plt
import networkx as nx
def draw_largest_comp(n,p):
layout = nx.spring_layout
G = nx.binomial_graph(n, p)
pos = layout(G)
plt.title("p = {}".format(p))
nx.draw(G, pos, node_size=15)
Gcc = sorted(nx.connected_components(G), key=len, reverse=True)
G0 = G.subgraph(Gcc[0])
nx.draw_networkx_edges(G0, pos, edge_color="r", width=1.0)
print("Largest component size:{}".format(len(G0.nodes())))
plt.show()
return
draw_largest_comp(100, 0.02)
Largest component size:87
Task 3: Write a function which for given degree distribution returns randomly generated network using the configuration model.
Task 4: Write a function which for given weights of vertices returns randomly generated network using the Chung-Lu model.