This script demonstrates the betweenness clustering algorithm developed by Girvan and Newman on a network of top political bloggers. Mouse over the nodes to see the blog names. An edge is present if the two blogs reciprocally cited one another in the months preceding the 2004 presidential election. Use the left mouse button to pan around, and drag while holding the right mouse button to zoom in and out.
The way the algorithm works is that it repeatedly removed the edge with the highest betweenness. Roughly speaking, betweenness corresponds to the number of shortest paths between nodes that go through that edge. By removing the highest betweenness edges, those that lie between communities, the algorithm reveals the community structure. You can sit there clicking the 'remove edge' button to remove the edges one at a time, or to find the next breaking point of the network, click on the 'next breakup' button. Once you are finished discovering the communities, you can add the edges back to see what you have removed.
This algorithm is not exceptionally fast, and won't always maximize modulairty, but it is intuitive and makes for a good demonstration of community structure. To read more about it:
M. Girvan and M. E. J. Newman, "Community structure in social and biological networks", PNAS, 99(12), 7821-7826, 2002.
You may need to refresh to get the applet to pop up (and make sure
you have pop up blockers disabled).