### Recommended Links

Like this piece? Share it with your friends:

In Network Analysis the identification of important nodes is a common task. We have various

centrality measures
that we can use and in this post we will focus on the Betweenness
Centrality. We will see how this measure is computed and how to use the
library networkx in order to create a visualization of the network where
the nodes with the highest betweenness are highlighted.
The betweenness focuses on the number of visits through the shortests
paths. If a walker moves from one node to another node via the shortests
path, then the nodes with a large number of visits have a higher
centrality. The betweenness centrality is defined as

where

*s(s,t)* is total number of shortest paths from node

*s* to node

*t* and

*sv(s,t)* is the number of those paths that pass through

*v*.

Let's see how to compute the betweenness with networkx. As first step we
have to load a sample network (yes, it's the same of this

post):

# read the graph (gml format)
G = nx.read_gml('lesmiserables.gml',relabel=True)

Now we have a representation G of our network and we can use the
function betweenness_centrality() to compute the centrality of each
node. This function returns a list of tuples, one for each node, and
each tuple contains the label of the node and the centrality value. We
can use this information in order to trim the original network and keep
only the most important nodes:

def most_important(G):
""" returns a copy of G with
the most important nodes
according to the pagerank """
ranking = nx.betweenness_centrality(G).items()
print ranking
r = [x[1] for x in ranking]
m = sum(r)/len(r) # mean centrality
t = m*3 # threshold, we keep only the nodes with 3 times the mean
Gt = G.copy()
for k, v in ranking:
if v < t:
Gt.remove_node(k)
return Gt
Gt = most_important(G) # trimming

And we can use the original network and the trimmed one to visualize the network as follows:

from pylab import show
# create the layout
pos = nx.spring_layout(G)
# draw the nodes and the edges (all)
nx.draw_networkx_nodes(G,pos,node_color='b',alpha=0.2,node_size=8)
nx.draw_networkx_edges(G,pos,alpha=0.1)
# draw the most important nodes with a different style
nx.draw_networkx_nodes(Gt,pos,node_color='r',alpha=0.4,node_size=254)
# also the labels this time
nx.draw_networkx_labels(Gt,pos,font_size=12,font_color='b')
show()

The graph should be like this one:

This graph is pretty interesting, indeed it highlights the nodes which
are very influential on the way the information spreads over the
network. In the sample network we used each node represents a character
and the connection between two characters represent the coappearance in
the same chapter of the book 'Les miserable'. Looking at the graph we
can easily say what are the most important characters according to the
Betweenness Centrality. We can also observe some interesting situations
like the ones of Valjean and Myriel. They are to connected to groups of
characters who don't have a direct connection with the main ones.