Network characteristics can be local, describing single vertices, e.g. degree and clustering, or they can be global, describing the whole network, e.g. average path length, average clustering coefficient.
Centralities are functions evaluating the importance of a single vertex $v$:
$\sigma_{x,y}$ number of shortest paths between $x$ and $y$ and for
$\sigma_{x,y}(v)$ number of shortest paths between $x$ and $y$ passing through $v$ is
$$C_B(v) = \sum_{\substack{x,y \in V(G) \setminus v\\x \neq y}} \frac{\sigma_{x,y}(v)}{\sigma_{x,y}}$$Global betweenness centrality $$\bar{C}_B(G) = \frac{1}{n} \sum_{v \in V(G)} C_B(v)$$
Average shortest path length $$L(G) = \frac{1}{n(n-1)} \sum_{\substack{u,v \in V(G)\\ u \neq v}} d(u,v)$$
Theorem Let $G$ be unoriented graph of size $|V(G)| = n$, $L(G)$ its average path length and $\overline{C}_B(G)$ its global betweeness centrality. Then it holds that $\overline{C}_B(G) = (n - 1) (L(G) - 1)$.
Lemma Let $G$ be a graph of size $n$ and let $G'$ be a graph obtained from $G$ by adding an edge between random vertices $u,v$ in distance $d = d(u,v) > 1$. Then it holds that $$\overline{C}_B(G') \leq \overline{C}_B(G) - \frac{2(d - 1)}{n}.$$
Corollary Let $G=(V,E)$ be a graph, $G'=(V,E')$ its subgraph on all vertices and $r = | E \setminus E'|$. Then $$\overline{C}_B(G) \leq \overline{C}_B(G') - \frac{2r}{n}.$$
Corollary Let $G=(V,E)$ be a graph with $|V|=n$ and $|E|=m$, and let $T$ be its spanning tree. Then $$\overline{C}_B(G) \leq \overline{C}_B(T) - \frac{2(m - n + 1)}{n}.$$
A vertex is called a leaf if $\deg(v) = 1$ and a k-neighbourhood of a vertex is defined as $$\Gamma_k(v) = \{v\in V : d(u,v) = k\}.$$
Theorem Let $G$ be a graph of size $n$, $w \in V$ a vertex with eccentricity $\epsilon(w)$ and let $G'$ be a graph obtained from $G$ by adding a vertex $u$ which is connected to $G$ by the edge $\{u,w\}$. Then $$\overline{C}_B(G') = \frac{n}{n - 1}\overline{C}_B(G) + \frac{2}{n - 1}\sum_{k=1}^{\epsilon(w)} k|\Gamma_k(w)|.$$
Theorem Let $G$ be a graph of size $n$ and let $G'$ be a graph obtained from $G$ by adding a new vertex $w$ and edges connecting it with vertices $u$ and $v$ in distance $1 \leq d(u,v) \leq 2$. Then $$\frac{1}{n+1} \left[n\overline{C}_B(G) + n - 2\right] \leq \overline{C}_B(G').$$
During this tutorial we will compute centralities. We will start with some simple graphs.
import networkx as nx
p8 = nx.path_graph(8)
star = nx.star_graph(8)
house = nx.house_graph()
Degree centrality can be computed using function degree_centrality with network as a parameter. This function returns a dictionary of vertices with values corresponding to degree centrality. In the first example we also showcase working with attributes.
for node in p8.nodes():
p8.nodes[node]["label"] = 'vertex{}'.format(node)
dc_p8 = nx.degree_centrality(p8)
for node in dc_p8:
print('vertex:{}, degree centrality: {: 0.2f}'.format(p8.nodes[node]["label"], dc_p8[node]))
nx.draw(p8)
vertex:vertex0, degree centrality: 0.14 vertex:vertex1, degree centrality: 0.29 vertex:vertex2, degree centrality: 0.29 vertex:vertex3, degree centrality: 0.29 vertex:vertex4, degree centrality: 0.29 vertex:vertex5, degree centrality: 0.29 vertex:vertex6, degree centrality: 0.29 vertex:vertex7, degree centrality: 0.14
dc_house = nx.degree_centrality(house)
for node in dc_house:
print('vertex:{}, degree centrality: {: 0.2f}'.format(node, dc_house[node]))
nx.draw(house)
vertex:0, degree centrality: 0.50 vertex:1, degree centrality: 0.50 vertex:2, degree centrality: 0.75 vertex:3, degree centrality: 0.75 vertex:4, degree centrality: 0.50
dc_star = nx.degree_centrality(star)
for node in dc_star:
print('vertex:{}, degree centrality: {: 0.2f}'.format(node, dc_star[node]))
nx.draw(star)
vertex:0, degree centrality: 1.00 vertex:1, degree centrality: 0.12 vertex:2, degree centrality: 0.12 vertex:3, degree centrality: 0.12 vertex:4, degree centrality: 0.12 vertex:5, degree centrality: 0.12 vertex:6, degree centrality: 0.12 vertex:7, degree centrality: 0.12 vertex:8, degree centrality: 0.12
Eccentricity of vertex $v$ is the maximum of distances from $v$ to other vertices in $G$.
ecc_p8 = nx.eccentricity(p8)
for node in ecc_p8:
print('vertex:{}, eccentricity: {: 0.2f}'.format(node, ecc_p8[node]))
nx.draw(p8)
vertex:0, eccentricity: 7.00 vertex:1, eccentricity: 6.00 vertex:2, eccentricity: 5.00 vertex:3, eccentricity: 4.00 vertex:4, eccentricity: 4.00 vertex:5, eccentricity: 5.00 vertex:6, eccentricity: 6.00 vertex:7, eccentricity: 7.00
ecc_house = nx.eccentricity(house)
for node in ecc_house:
print('vertex:{}, eccentricity: {: 0.2f}'.format(node, ecc_house[node]))
nx.draw(house)
vertex:0, eccentricity: 2.00 vertex:1, eccentricity: 2.00 vertex:2, eccentricity: 2.00 vertex:3, eccentricity: 2.00 vertex:4, eccentricity: 2.00
ecc_star = nx.eccentricity(star)
for node in ecc_star:
print('vertex:{}, eccentricity: {: 0.2f}'.format(node, ecc_star[node]))
nx.draw(star)
vertex:0, eccentricity: 1.00 vertex:1, eccentricity: 2.00 vertex:2, eccentricity: 2.00 vertex:3, eccentricity: 2.00 vertex:4, eccentricity: 2.00 vertex:5, eccentricity: 2.00 vertex:6, eccentricity: 2.00 vertex:7, eccentricity: 2.00 vertex:8, eccentricity: 2.00
cc_p8 = nx.closeness_centrality(p8)
for node in cc_p8:
print('vertex:{}, closeness centrality: {: 0.2f}'.format(node, cc_p8[node]))
nx.draw(p8)
vertex:0, closeness centrality: 0.25 vertex:1, closeness centrality: 0.32 vertex:2, closeness centrality: 0.39 vertex:3, closeness centrality: 0.44 vertex:4, closeness centrality: 0.44 vertex:5, closeness centrality: 0.39 vertex:6, closeness centrality: 0.32 vertex:7, closeness centrality: 0.25
cc_house = nx.closeness_centrality(house)
for node in cc_house:
print('vertex:{}, closeness centrality: {: 0.2f}'.format(node, cc_house[node]))
nx.draw(house)
vertex:0, closeness centrality: 0.67 vertex:1, closeness centrality: 0.67 vertex:2, closeness centrality: 0.80 vertex:3, closeness centrality: 0.80 vertex:4, closeness centrality: 0.67
cc_star = nx.closeness_centrality(star)
for node in cc_star:
print('vertex:{}, closeness centrality: {: 0.2f}'.format(node, cc_star[node]))
nx.draw(star)
vertex:0, closeness centrality: 1.00 vertex:1, closeness centrality: 0.53 vertex:2, closeness centrality: 0.53 vertex:3, closeness centrality: 0.53 vertex:4, closeness centrality: 0.53 vertex:5, closeness centrality: 0.53 vertex:6, closeness centrality: 0.53 vertex:7, closeness centrality: 0.53 vertex:8, closeness centrality: 0.53
Betweenness centrality can be computed using NetworkX as follows.
cb_p8 = nx.betweenness_centrality(p8, normalized=False)
print(cb_p8)
for node in cb_p8:
print('vertex:{}, betweeness: {: 0.2f}'.format(node, cb_p8[node]))
{0: 0.0, 1: 6.0, 2: 10.0, 3: 12.0, 4: 12.0, 5: 10.0, 6: 6.0, 7: 0.0} vertex:0, betweeness: 0.00 vertex:1, betweeness: 6.00 vertex:2, betweeness: 10.00 vertex:3, betweeness: 12.00 vertex:4, betweeness: 12.00 vertex:5, betweeness: 10.00 vertex:6, betweeness: 6.00 vertex:7, betweeness: 0.00
Parameter normalized=False
tells us, that we want betweenness in real sizes, not after division by ${n-1 \choose 2}$, which normalizes the values into range $\langle 0, 1 \rangle$.
Note that this function computes betweenness for unoriented graphs. To obtain values compatible with values from the lecture, we have to multiply these values by two (or divide the values from the lecture).
More information about implementation of this function is in the documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.betweenness_centrality.html#networkx.algorithms.centrality.betweenness_centrality
bc_house = nx.betweenness_centrality(house, normalized=False)
for node in bc_house:
print('vertex:{}, betweenness centrality: {: 0.2f}'.format(node, bc_house[node]))
nx.draw(house)
vertex:0, betweenness centrality: 0.50 vertex:1, betweenness centrality: 0.50 vertex:2, betweenness centrality: 1.50 vertex:3, betweenness centrality: 1.50 vertex:4, betweenness centrality: 0.00
bc_star = nx.betweenness_centrality(star, normalized=False)
for node in bc_star:
print('vertex:{}, betweenness centrality: {: 0.2f}'.format(node, bc_star[node]))
nx.draw(star)
vertex:0, betweenness centrality: 28.00 vertex:1, betweenness centrality: 0.00 vertex:2, betweenness centrality: 0.00 vertex:3, betweenness centrality: 0.00 vertex:4, betweenness centrality: 0.00 vertex:5, betweenness centrality: 0.00 vertex:6, betweenness centrality: 0.00 vertex:7, betweenness centrality: 0.00 vertex:8, betweenness centrality: 0.00
Average shortest path length can be also easily computed using NetworkX. The algorithm for counting the lengths of paths in weighted graphs is Dijkstra's algorithm by default, other options are algorithms of Bellman-Ford and Floyd-Warshall. See the documentation for details,
p8_avg_length = nx.average_shortest_path_length(p8)
print('Path on 8 vertices: {: 0.2f}'.format(p8_avg_length))
house_avg_length = nx.average_shortest_path_length(house)
print('House: {: 0.2f}'.format(house_avg_length))
star_avg_length = nx.average_shortest_path_length(star)
print('Star: {: 0.2f}'.format(star_avg_length))
Path on 8 vertices: 3.00 House: 1.40 Star: 1.78
Task 1: Write a function which counts the global betweenness centrality of a given graph $G$. Which of our three graphs do you expect to have largest and lowest average betweenness? First guess and then run the computation.
Task 2: Use the function from previous task to write a function verifying the relation between global betweenness and average path length. Use such function on several graphs.
Spanning tree of a graph $G$ on $n$ vertices is a subgraph of $G$, which is a tree covering all vertices of $G$. In NetworkX there are many methods for spanning trees, see the documentation for trees, section about spanning trees:
https://networkx.org/documentation/stable/reference/algorithms/tree.html
spanning_tree = nx.minimum_spanning_tree(house)
nx.draw(spanning_tree)
Task 3: Verify the bound relating global betweenness of $G$ and its spanning tree by implementing a function enumerating the betweenness and the "error term". Try to find graphs for which it is more tight and graphs where the difference is large.
Task 4: Verify the bound on the change of global betweenness after adding a new vertex connected to two leafs of a star.
In NetworkX we can generate a Watts-Strogatz model by function watts_strogatz_graph(n, k, p)
, where $n$ stands for number of vertices, $k$ denotes how many closest vertices is any vertex neighbouring and $p$ is the probability of rewiring an edge. See the docs for more information:
https://networkx.org/documentation/stable/reference/generated/networkx.generators.random_graphs.watts_strogatz_graph.html
ring_lattice = nx.watts_strogatz_graph(12, 4, 0)
nx.draw(ring_lattice)
ws = nx.watts_strogatz_graph(12, 4, 0.3)
nx.draw_circular(ws)
There are several coefficients and indexes used to evaluate how much small-world is a graph.
Let $C$ be the average clustering coefficient of $G$, $L$ be average shortest path length of $G$, $C_R$ be average clustering coefficient of a reference random model for $G$ and $L_R$ be the average shortest path length of a reference random model. Then the small-world coefficient of a graph $G$ is defined as $$\sigma(G) = \frac{\frac{C}{C_R}}{\frac{L}{L_R}}.$$ Usually, graphs with $\sigma(G) > 1$ are considered to be small-worlds.
nx.sigma(nx.watts_strogatz_graph(12, 4, 0))
nx.sigma(nx.watts_strogatz_graph(30, 4, 0))
Task 5: Fix $n=15$, $k=4$. Find how the small-world coefficient changes with growing $p$.