Centrality measures are used to appraise the "importance" of the elements of the network. The problem is that "importance"
During this seminar we will consider two node centrality measures: degree centrality and closeness centrality
In fact you have already met the degree centrality in this course.
Given adjacency matrix $A$ of the unweighted and undirected graph $G = (V,E)$ degree centrality of the node $v_i$ is computed as: $$ C_D(i) = \sum_j A_{ji} $$ In order to compare nodes across graphs this measure can be normalized by a factor $\frac{1}{N-1}$
The most correspondent to the word "central". Closeness centrality is used to identify nodes that can reach other nodes quickly. $$ C_C(i) = \left[ \sum_{j,\ j\neq i} d(v_i, v_j) \right]^{-1}\text{,} $$ where $d(v_i, v_j)$ is a length of the shortest path between $v_i$ and $v_j$. Again, to be normalized it is multiplied by $(N-1)$.
Centralities allow us to
import numpy as np
import matplotlib.pyplot as plt
plt.xkcd()
import networkx as nx
%matplotlib inline
Let's load Zachary's Karate Club network. This is quite small example so we can both calculate centralities and map them of the picture of the graph
G = nx.karate_club_graph()
pos = nx.spring_layout(G) # Fix node positions on all pictures
# Original network
nx.draw_networkx(G, pos)
# Degree centrality
dc = nx.degree_centrality(G)
plt.figure(1, figsize=(10,7))
coord = nx.spring_layout(G)
nx.draw(G,
pos,
nodelist=dc.keys(),
node_size = [d*7000 for d in dc.values()],
node_color=dc.values(),
font_size=8,
cmap=plt.cm.Reds,
)
# Closeness centrality
cl = nx.closeness_centrality(G)
plt.figure(1, figsize=(10,7))
coord = nx.spring_layout(G)
nx.draw(G,
pos,
nodelist=cl.keys(),
node_size = [d*3000 for d in cl.values()],
node_color=cl.values(),
font_size=8,
cmap=plt.cm.Reds,
)
# Plot degree-closeness
xdata = dc.values()
ydata = cl.values()
plt.figure(1, figsize=(7,7))
plt.plot(xdata,ydata, '+')
plt.xlabel('Degree Centrality')
plt.ylabel('Closeness Centrality')
<matplotlib.text.Text at 0xc468710>
# Not Clear. Lets add node ids:
fig = plt.figure(1, figsize=(14,7))
ax1 = fig.add_subplot(121)
ax2 = fig.add_subplot(122)
for v in xrange(len(dc)):
ax1.text(x = xdata[v], y = ydata[v], s=str(v))
ax1.set_xlim(0, 0.6)
ax1.set_ylim(0.25, 0.6)
ax1.set_xlabel('Degree Centrality')
ax1.set_ylabel('Closeness Centrality')
ax2 = nx.draw_networkx(G, pos)