Algorithms For Dummies

 Exploring the World of Graphs

When modeling real-world data, such as the tweets about a particular topic, the 

nodes also tend to cluster. You might think of this tendency as a kind of  trending — 

what people feel is important now. The fancy math term for this tendency is  

clustering, and measuring this tendency helps you understand which group of 

nodes is most important in a graph. Here is the code you use to measure clustering 

for the example graph:

nx.clustering(AGraph)

{1: 0.16666666666666666, 2: 1.0, 3: 0.3333333333333333,

 4: 0.0, 5: 0.0, 6: 0.0}

The output shows that the nodes are most likely to cluster around node 2 even 

though node 1 has the highest degree. That’s because both nodes 1 and 3 have high 

degrees and node 2 is between them.

Clustering graphs helps aid understanding data. The technique helps show that 

there are nodes in the graph that are better connected and nodes that risk isola-

tion. When you understand how elements connect in a graph, you can determine 

how to strengthen its structure or, on the contrary, destroy it. During the Cold 

war, military scientists from both the United States and the Soviet bloc studied 

graph clustering to better understand how to disrupt the other side’s supply chain 

in case of a conflict.