The Density of a network is defined as the fraction of edges present over all possible edges. i.e., For undirected graphs \[\eta = \frac{2|E|}{|V|(|V|-1)}.\] For directed graphs \[\eta = \frac{|E|}{|V|(|V|-1)}.\] Here \(|V|\) is the number of vertexes, and \(|E|\) is the number of edges in the graph.
The density of a complete graph is 1, verify this by looking at the graph and computing its density.
import networkx as nx
import matplotlib.pyplot as plt
g = nx.complete_graph(5)
nx.draw(g) # also do plt.show() if you need it
nx.density(g)Now generate an (undirected) cycle graph, and convert it to a directed ring.
# generate and examine the undirected cycle graph
g = nx.cycle_graph(10)
nx.draw(g)
# convert it to a numpy matrix
import numpy as np
m = nx.to_numpy_matrix(g)
mu = np.triu(nx.to_numpy_matrix(g))
gd = nx.DiGraph(mu)
nx.draw(gd)
# try an alternative layout
nx.draw_circular(gd)Question: What is the density of this 10-node directed ring?
Recall the lecture slides about small-world experiment in message forwarding. One well-known class of graphs that will lead to such small-world behavior is Watts-Strogatz graphs. A very brief description of the underlying models is at its networkx reference page, a longer description can be found on wikipedia. Generate such a graph:
# generate Watts-Strogatz graphs with parameters (n, k, p)
ws = nx.watts_strogatz_graph(25, 5, 0.25)
# look at the network
nx.draw_circular(ws)Question: Can you see that a graph structure like this will lead to small world phenomenon? Why?
Question: What would a Watts-Strogatz graph become when p approaches 0? when p approaches 1?
Question: What is the density of a Watts-Strogatz graph (n, k, p), with n=50, k=5, p=0.1? n=50, k=5, p=0.5? or \(n=\infty\), \(k=\frac{n}{100}\), \(p=0.01\)?
Additional material: This page contains some R code that can reproduce the degree distribution plot in the original Watts-Strogatz (1998) paper.
Extra excercises: