Girvan Newman Changing the Times
This article is part one of a three-part series following a project completed by three undergraduate college students from Southern Methodist University.
Nicole Sood — Computer Science
Maggie Asare — Computer Engineer and Business Studies
Katie Rink — Computer Science
Networks form some of the most powerful systems on our planet, from the internet to social media. It is used on the daily, and as a result we have built up a community structure using the ideas of graph theory.
Many of these systems use a series of nodes and vertices to create a link between a natural world [1]. It allows us to visually identify communities. Traditionally to detect a community, you would use a form of hierarchical clustering, which would use a weighted graph. You would then add nodes to a network biased on which edges were the strongest [2]. This traditional way of building up a community network, however, was an inefficient and long-winded tactic.
In attempt to try and solve this, Girvan Newman proposed a new way to approach to try and improve traditional methods. The proposed using the idea of betweenness to identify the community’s that are most central and remove them. This so you can focus on the outer edges and can separate them out [2].
The algorithm they proposed was simple:
1. Calculate betweenness of all edges in the network
2. Remove the edge with highest betweenness
3. Recalculate betweenness for all edges affected by the removal
4. Repeat steps 2 & 3 until no edges remain.
As a team, we implemented the Girvan Newman algorithm with our own custom way to calculate betweenness. In order to do this, we by brute force determined all of the centrality values for each edge. Utilizing a Dijkstras algorithm, the shortest path to all nodes from each individual node was determined, while tracking the number of times each edges is traversed. Then, by determining which edge was visited the most, we now know which edge has the highest centrality. This edge is removed, and then the process is repeated until there are not remaining edges.
boost::list_edge<unsigned long, Edge_Properties> GirvanNewmanAlgorithm::calculateBetweeness(Graph& g){
std::vector<edge_list_type> edgeLists;
auto mainEdges = g.m_edges;
for(auto vertex : g.m_vertices)
edgeLists.push_back(Dijkstras(g, vertex.m_property.id));
for(auto &edges : edgeLists){
auto edgeIter = edges.begin();
for(auto &d : mainEdges){
d.get_property().time_visited += edgeIter->m_property.time_visited;
edgeIter++;
}
}
auto max = *mainEdges.begin();
for(auto &c : mainEdges){
if(c.m_property.time_visited > max.m_property.time_visited)
max = c;
}
return max;
}[1] Strogatz, S. Exploring complex networks. Nature 410, 268–276 (2001). https://doi.org/10.1038/35065725
[2] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, Jun. 2002, doi: 10.1073/pnas.122653799.
