Algorithms For Dummies

 Exploring the World of Graphs

Node 1 is indeed in the center of the graph with the most connections. The node 1 

degree ensures that it’s the most important based on the number of connections. 

When working with directed graphs, you can also use the 

in_degree_centrality()

 

and 

out_degree_centrality()

 functions to determine degree centrality based on 

connection type rather than just the number of connections.

When working with traffic analysis, you might need to determine which locations 

are central based on their distance to other nodes. Even though a shopping center 

in the suburbs may have all sorts of connections to it, the fact that it is in the 

suburbs may reduce its impact on traffic. Yet, a supermarket in the center of the 

city with few connections might have a great impact on traffic because it’s close 

to so many other nodes. To see how this works, add another node, 7, that is dis-

connected to the graph. The centrality of that node is infinite because no other 

node can reach it. The following code shows how to calculate the closeness cen-

trality for the various nodes in the example graph:

AGraph.add_node(7)

nx.closeness_centrality(AGraph)

{1: 0.6944444444444445,

 2: 0.5208333333333334,

 3: 0.5952380952380952,

 4: 0.462962962962963,

 5: 0.5208333333333334,

 6: 0.4166666666666667,

 7: 0.0}

The output shows the centrality of each node in the graph based on its closeness 

to every other node. Notice that node 7 has a value of 0, which means that it’s an 

infinite distance to every other node. On the other hand, node 1 has a high value 

because it’s close to every node to which it has a connection. By calculating the 

closeness centrality, you can determine which nodes are the most important based 

on their location.

Another form of distance centrality is betweenness. Say that you’re running a 

company that transfers goods throughout the city. You’d like to know which nodes 

have  the  greatest  effect  on  these  transfers.  Perhaps  you  can  route  some  traffic 

around this node to make your operation more specific. When calculating between-

ness centrality, you determine the node that has the highest number of short 

paths coming to it. Here’s the code used to perform this calculation (with the 

disconnected node 7 still in place):

nx.betweenness_centrality(AGraph)

{1: 0.36666666666666664,

---

CHAPTER 8