Tutorial 3: Network centralities

From the lecture

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$:

• degree centrality - $$\frac{\deg(v)}{n-1}$$
• eccentricity - $$\epsilon(v) = \max_{u \in V(G)} \{d(u,v)\}$$
• closeness centrality - $$C_C(v) = \frac{n}{\sum_{u \in V(G)}d(u,v)}$$
• betweenness centrality - for

$\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').$$

Counting centralities

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

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 labels.

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

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.degree_centrality.html

Eccentricity

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

Closeness centrality

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

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.closeness_centrality.html

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

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 path length

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,

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.generic.average_shortest_path_length.html

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.

def global_bc(G):
    bc = nx.betweenness_centrality(G, normalized=False)
    total_bc = 0
    for node in bc:
        # formula uses betweenness counting paths in oriented way, 
        # nx.betweenness_centrality uses unoriented paths -> we multiply by 2
        total_bc += 2*bc[node]
    return total_bc / len(G.nodes())

print(global_bc(p8))
print(global_bc(house))
print(global_bc(star))
print(global_bc(nx.heawood_graph()))

14.0
1.6
6.222222222222222
13.999999999999998

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.

import math

def check_gbc_vs_avg_path(G):
    gbc = global_bc(G)
    avg_len = nx.average_shortest_path_length(G)
    n = len(G)
    right_side = (n-1)*(avg_len - 1)
    print(right_side)
    print(gbc)
    return math.isclose(gbc, right_side)

print(check_gbc_vs_avg_path(star))

6.222222222222221
6.222222222222222
True

Spanning tree

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)

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_tree.html

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.

def gbc_graph_vs_spanning_tree(G):
    gbc = global_bc(G)
    spanning_tree = nx.minimum_spanning_tree(G)
    gbc_spanning_tree = global_bc(spanning_tree)
    n = len(G)
    m = len(G.edges())
    error_term = 2*(m-n+1)/n
    print("GBC(spanning-tree):{: 0.2f}, 2(m-n+1)/n:{: 0.2f}".format(gbc_spanning_tree, error_term))
    print("GBC(G): {: 0.2f}".format(gbc))
    return gbc <= gbc_spanning_tree - error_term

complete_graph = nx.complete_graph(8)
gbc_graph_vs_spanning_tree(star)

GBC(spanning-tree): 6.22, 2(m-n+1)/n: 0.00
GBC(G):  6.22

True

Task 4: Verify the bound on the change of global betweenness after adding a new vertex connected to two leafs of a star.

def gbc_after_adding_vertex(G, u, v):
    n = len(G)
    gbc_orig = global_bc(G)
    # check that the distance between u and v is at most 2
    assert(G.has_edge(u, v)) or (v in nx.descendants_at_distance(G, u, 2))
    G.add_node('w')
    G.add_edge(u, 'w')
    G.add_edge(v, 'w')
    gbc_new = global_bc(G)
    left = (1/(n+1))*(n*gbc_orig + n - 2)
    right = gbc_new
    print(left)
    print(right)
    return left <= right

u = list(star.nodes())[1]
v = list(star.nodes())[2]
gbc_after_adding_vertex(star, u, v)

8.0
8.0

True

Small world

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.

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.smallworld.sigma.html

nx.sigma(nx.watts_strogatz_graph(12, 4, 0))

2.3374741200828155

nx.sigma(nx.watts_strogatz_graph(30, 4, 0))

3.1330459770114936

For the following task it will be useful to visualize numbers in a graph. For simple bar graph we can use for example function bar from matplotlib.pyplot: https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.bar.html

football = nx.read_pajek('football.paj')
undir_football = nx.Graph(football)
print(nx.sigma(undir_football))

Task 5: Fix $n=15$, $k=4$. Find how the small-world coefficient changes with growing $p$.

import matplotlib.pyplot as plt
import numpy as np

# Generate sample graphs
def gen_ws_graphs(n, k, p, how_many):
    ws_graphs = []
    for i in range(0, how_many):
        ws_graphs.append(nx.newman_watts_strogatz_graph(n, k, p))
    return ws_graphs

# Generate list of probabilities
p_array = np.arange(0, 1, 0.1)
p_list = list(p_array)

sigmas = []
for p in p_list:
    ws_graphs = gen_ws_graphs(15, 4, p, 5)
    sigma = 0
    for g in ws_graphs:
        sigma += nx.sigma(g)
    sigmas.append(sigma/10)
    print(p, sigma/10)

plt.plot(p_list, sigmas)
plt.title("Small world of Watts-Strogatz, n=15, k=4")
plt.xlabel("Probability of rewiring")
plt.ylabel("Small world coefficient")

0.0 1.160401864366254
0.1 0.8925145766320345
0.2 0.7363828185141074
0.30000000000000004 0.6373981754134506
0.4 0.6659926713110631
0.5 0.6077130967281535
0.6000000000000001 0.5203344513232522
0.7000000000000001 0.5486086547553952
0.8 0.5295457301793357
0.9 0.5246143926467987

Text(0, 0.5, 'Small world coefficient')

Note that for $n=15$ and $k=4$ the distances are already short, so rewiring decreases small-world coefficient, by not making paths much shorter while destroying clustering.