This project that we took on was quite a journey. We (Eileen Garcia, Sofia Murillo, and Oliver Zhu) walked into this without knowing anything about graphs and networks beyond what we learned in class. And, as many of you already know, learning from lecture slides vs actually applying your knowledge are TWO very different experiences. Not only that, but we also had to learn an entirely new library, Boost, which is quite the learning curve.

Our Initial vs Final Approach to this Project:

When we first started this project, we did a lot of research regarding the Girvan-Newman Algorithm and its various implementations and modifications. We learned the base-level concepts and immediately jumped into coding — a big mistake. By the end of the project, we were deeply researching the equations and each individual component that makes up the Girvan-Newman Algorithm in order to accurately reflect their role — and to make up for the fact that we did not truly understand their role to begin with.

What was the most important thing we learned?

We learned many technical skills and important concepts while creating this project. Even a few life lessons. The Girvan-Newman Algorithm, as mentioned in Part 1, is “a hierarchical method used to detect communities in complex systems” [1]. Networks… Graphs… Boost… Modularity…everything felt overwhelming to learn at the moment. It is a lot to take in. However, out of all the things we learned, the most important thing we took away from this was the importance of truly understanding the base concepts before jumping to code. Specific concepts like modularity took us days to code, and it was simply because we did not understand the underlying concepts behind modularity enough to do it.

What would we change?

If we could go back in time and change something about the way we approached this project, it would be to slow down and actually take time to understand the mathematical concepts behind the Girvan-Newman Algorithm. If we had done so, we could have dedicated more time to the modification portion of the project. In particular, there was one modification we were very excited to implement, but could not do due to the time constraints of this project. This modification, in particular, utilized an extremal optimization of the modularity. In order to do so, the creators of this modification took the following approach:

“1) Initially, we split the nodes of the whole graph into two random partitions having the same number of nodes in each one. This splitting creates an initial community division, where communities are understood as connected components in each partition.

2) At each time step, the system self-organizes by moving the node with the lower fitness extremal from one partition to the other. In principle, each movement implies the recalculation of the fitness of many nodes because the righthand side of Eq. 3 involves the pseudoglobal magnitude ari.

3) The process is repeated until an “optimal state” with a maximum value of Q is reached. After that, we delete all the links between both partitions and proceed recursively with every resultant connected component. The process finishes when the modularity Q cannot be improved.”

By doing so, they were able to drastically improve the modularity initially produced by the base implementation of the Girvan-Newman Algorithm and their heuristic approach to the Girvan-Newman Algorithm was the combination of everything we have learned up to this point in CS3353.

Our own performance analysis:

Although we were able to implement the Girvan-Newman Algorithm and its modification, were we actually successful in our endeavors? In order to evaluate our success, we will compare our modularity from the base implementation on the US Football Network Dataset (Q (modularity)= 0.65597) to the published modularity [3] (Q = 0.4397). We calculated our error to be approximately 33%. In summary, we definitely have room for improvement in our implementation, but, taking our milestones and the learning curves into consideration, we performed quite well.

Lastly, the dream for the Ultimate Girvan-Newman Algorithm is far from over. We hope you stay tuned for our results on that implementation.

Sources:

[1] https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm

[2] https://journals-aps-org.proxy.libraries.smu.edu/pre/abstract/10.1103/PhysRevE.72.027104 (MLA Citation: Duch, Jordi, and Alex Arenas. “Community Detection in Complex Networks Using Extremal Optimization.” Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics, vol. 72, no. 2 Pt 2, 2005, pp. 027104–027104, https://doi.org/10.1103/PhysRevE.72.027104.)

[3] https://ieeexplore.ieee.org/abstract/document/6859714 (MLA Citation: L. Despalatović, T. Vojković and D. Vukic̆ević, “Community structure in networks: Girvan-Newman algorithm improvement,” 2014 37th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2014, pp. 997–1002, doi: 10.1109/MIPRO.2014.6859714.)

Personal Performance Analysis (GMZ Series Part 3) was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Sarah Dessen, in her novel Just Listen, states that “Music is the great uniter. An incredible force. Something that people who differ on everything and anything else can have in common.” And while music unites those with shared love of a certain singer or band, it can also unite those of separate fan-bases when two artists collaborate to make a song together. As someone who only listened to Christian rap until the age of 16 (surely the pinnacle of music), music collaborations were my lanterns shining light on the wondrous expanse of the world of music. I discovered the Japanese-pop band Kero Kero Bonito, who make a song with the hyperpop band 100 gecs, who made a song with rock band Fall Out Boy, who made a song with the rapper Kanye West, who made a song with the R&B singer Anderson Paak, who made a song with singer-songwriter Ed Sheeran, who made a song with the pop-star Taylor Swift, who… you get the idea. Music collaborations are surprising, with artists often crossing genres and generational gaps to give us our greatest hits, so my partner Zaid Benyacoub and I set out to analyze and visualize the human communities formed from those collaborations.

To accomplish this, we used the help of the Girvin Newman algorithm. The Girvin Newman algorithm takes a graph and slowly chips away at its edges, removing ones with the most “betweenness,” which means most vertices have to cross its path to get around. We had previously implemented this on standard graph files, so the challenge would now be how to translate music in a graph.

The solution: a website called Soundiiz. With a subscription, Soundiiz allows you to export entire playlists into CSV files like the one shown below.

The specific file shown above is one exported from the playlist I titled “Ed Sheeran: Degrees of Separation.” It contains the discography of all 22 artists featured on his album №6 Collaborations Project and contains 2,463 songs and over 150 hours of music. Ed Sheeran is a prominent collaborator with artists in almost every genre, resulting in the majority of artists being tied to Ed Sheeran through 2 or 3 degrees of song separation.

Once the playlist is in CSV form, it’s simple to parse, with columns being delimited by semicolons and artists being delimited by commas. And once parsed, the conversion to graph was straightforward using the boost library , creating a hash map to keep track of vertex values and already-visited vertices.

std::vector<std::vector<std::string>> allSongs = readCSV(in);

std::unordered_map<std::string, pair<int, vector<int>>> map; 
/* the string key stores the artist's name, the int in the pair is the index, and the int vector is all the vertices already visited */

int currIndex = 0;
for (auto song: allSongs){ //Loop through all songs
    for (auto artist: song){ //Loop through all artists on a song
        if (map.find(artist) == map.end()){
            map[artist].first = currIndex; //Store an artist's index
            currIndex++;
        }
    }
    for (int i = 0; i < song.size(); i++){  //Create edges
        for (int j = i; j < song.size(); j++){
            if (i != j) {
                int edge1 = map[song.at(i)].first;
                int edge2 = map[song.at(j)].first;

                if (find(map[song.at(i)].second.begin(),  map[song.at(i)].second.end(),edge2) == map[song.at(i)].second.end()){

                    boost::add_edge(edge1, edge2, mg); 
                    mg[edge1].name = song.at(i);
                    mg[edge2].name = song.at(j);
                    map[song.at(i)].second.push_back(edge2);
                    map[song.at(j)].second.push_back(edge1);
                }
            }
        }
    }
}

Once in a graph object, the graph was run through the Girvin Newman algorithm to create communities. The result is shown below in yEd:

As seen, the songwriting of one Ed Sheeran blossomed into over 20 distinct, sizeable communities and a plethora of smaller communities. The ways in which the communities developed were fascinating, with a multitude of niches being representing. There was a community high-energies rappers, including the likes of Lil Uzi, Sheck Wes, JACKBOYS, Yung Kayo, and Yak Gotti; a community of artists from the groovier side of hip-hop, including Bruno Mars, Thundercat, Damian Marley, Anderson Paak, and Boosty Collins; a community of pop-stars; a community of folk singers; also, communities of artists seemingly dissimilar until learning those artists are frequent collaborators. In total, the graph contained 828 different vertices (artists) connected by 704 edges.

These surprising culminations, communities of genres very distant from the pop, folk-pop, singer-songwriter influences of Ed Sheeran, are a testament not only to the man’s willingness to collab with those outside his bubble, but also to the great wonders of music. When connected, you could take a trip from one artist’s node to the other side of the word in a second. And once made into communities, you could see circles of bright, like-minded, minds creating musical masterpieces and collectively propelling their styles of music forward.

Detection of Communities Among Musical Artists Part 2 was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.

A network can be represented by a graph with vertices (nodes) that are linked to each other by edges.

Two vertices are adjacent vertices if they are connected to each other.

An edge and its endpoint are said to be incident. When we talk about the degree of a vertex, we mean the number of edges incident to that vertex, so the degree of a vertex is the number of edges that have that vertex as its endpoint. When considering loops in degrees of vertices (an edge that connects a vertex to itself), you count the loop twice.

A graph is regular if all of the vertices have the same degree.

What is the Girvan-Newman Algorithm?

Named after Michelle Girvan and Mark Newman, it is a hierarchical method used to detect communities in networks[1].

The Girvan Newman Algorithm essentially takes these networks from above and breaks them down into communities. Why do we care about this? There are lots of things we can do by breaking down networks into communities, for example, by identifying critical groups across a network social networks can deliver on their promise of providing content based on a person’s interests [1].

According to Jana Coronicová Hurajová, a leading researcher in this field, the algorithm “is based on the successive deletion of edges which have the maximum edge betweenness centrality which is the quantity measuring the frequency of appearance of an edge on geodesic paths in a graph.”[2]

The Girvan Newman essentially finds edges with this “maximum edge betweenness” (which are basically the edges joining communities) and it deletes them. By eliminating these edges, we can see individual, centralized communities come to the light. It’s like if you are unknotting your earbuds and you look for the part of the wire that is most common throughout the entire knot. You can find the other individual knots and handle them accordingly by removing the larger knots first. This is basically what the Girvan Newman Algorithm does.

The Algorithm also makes use of modularity, which is a measure of how well-defined communities are in a graph. Generally, and depending on the formula used to calculate modularity, its value can range from [-1, 1]. A graph with well-defined communities will have a value between 0.3 and 0.7. Modularity is also used to determine the performance of the algorithm when compared to the “real” communities formed by the graph.

How did we implement the algorithm?

To implement the Girvan Newman Algorithm, we closely followed NetworkX’s documentation about the Girvan Newman algorithm. [3] The specific pseudocode is:

REPEAT

LET n BE number of edges in the graph

FOR i=0 to n-1

LET B[i] BE betweenness centrality of edge i

IF B[i] > max_B THEN

max_B = B[i]

max_B_edge = i

ENDIF

ENDFOR

remove edge i from graph

UNTIL number of edges in graph is 0

Note that for our implementation itself, we used the Boost Library[4].

Sources:

[1] https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm.

[2] http://ceur-ws.org/Vol-1649/200.pdf

[3] https://networkx.guide/algorithms/community-detection/girvan-newman/

[4] https://www.boost.org/

Base Implementation of the Girvan-Newman Algorithm (GMZ Series Part 1) was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Zachary Suzuki is a sophomore pursuing a Bachelor of Science in Computer Science with a specialization in Data Engineering, and a minor in music for piano. His life goal is to figure out a way to sum n numbers in log(n) time

Datasets

The program uses files formatted using graphml, which is a way to organize vertices, edges, and their respective properties. It is formatted with properties defined on the top of file, nodes listed below with distinctive keys, and edges defined underneath.

An example of a small Graphml file with 2 nodes and 1 edge is shown below:

<?xml version=”1.0" encoding=”UTF-8"?>
<graphml xmlns=”http://graphml.graphdrawing.org/xmlns"
  xmlns:xsi=”http://www.w3.org/2001/XMLSchema-instance"
  xsi:schemaLocation=”http://graphml.graphdrawing.org/xmlns
  http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
  <key id=”d0" for=”node” attr.name=”community” attr.type=”int”/>
    <graph id=”G” edgedefault=”undirected”>
      <node id=”n0">
        <data key=”d0">1</data>
      </node>
      <node id=”n1">
        <data key=”d0">1</data>
      </node>
      <edge source=”n0" target=”n1"/>
    </graph>
</graphml>

Note that the graphs used are undirected, unweighted graphs.

Randomly generated .graphml graphs were generated using the NetworkX python library with the random_partition_graph function. The final testing dataset was converted from gml to graphml using the same library.

The process in which the algorithm determines the separate partitions is with the help of edge betweeness centrality, which is the frequency each node is used in all the shortest paths for each pair of nodes. Once a new partition is created, resulting in more unconnected clusters, a modularity is calculated, which measures the degree to which the partition is densely connected and can be separated into communities. We want a cluster that interacts more with itself than other communities.

The modularity is calculated for the graph every time a new component is formed and is saved if larger than the current max. In general, a modularity between 0.3–0.7 is considered a good division of communities.[

Edge Betweeness

Here is an example of how edges are removed in the algorithm. For each pair of nodes, the shortest path is calculated using Breadth First Search and path reconstruction.

1–2
1–3
1–3–4
1–3–5
…
5–6

When following through these paths, the frequency is tracked to find the highest used path. This highest path is then removed from the graph and the number of total components is calculated. Since the number of components increased, the edge betweeness loop ends and the modularity is calculated and compared with the current max. This process repeats until there are no more edges remaining, where the partition with the highest modularity is picked and is printed in the report.

Testing

This implementation was tested using the Football Conference 2000 dataset provided by Girvan and Newman, which is a network containing American football games between colleges in 2000. Each node printed is accompanied by a value to indicate the correct conference they belong to (formatted as nodeID-conference). Here is the resulting clustering as reported by the algorithm:

Community Report
community #0: [0–7, 4–7, 9–7, 11–10, 16–7, 23–7, 24–10, 28–11, 41–7, 50–10, 69–10, 90–5, 93–7, 104–7]
community #1: [1–0, 25–0, 33–0, 37–0, 45–0, 89–0, 103–0, 105–0, 109–0]
community #2: [2–2, 6–2, 13–2, 15–2, 32–2, 39–2, 47–2, 60–2, 64–2, 100–2, 106–2]
community #3: [3–3, 5–3, 10–3, 40–3, 52–3, 72–3, 74–3, 81–3, 84–3, 98–3, 102–3, 107–3]
community #4: [7–8, 8–8, 21–8, 22–8, 51–8, 68–8, 77–8, 78–8, 108–8, 111–8]
community #5: [12–6, 14–6, 18–6, 26–6, 31–6, 34–6, 38–6, 42–5, 43–6, 54–6, 61–6, 71–6, 85–6, 99–6]
community #6: [17–9, 20–9, 27–9, 56–9, 62–9, 65–9, 70–9, 76–9, 87–9, 95–9, 96–9, 113–9]
community #7: [19–1, 29–1, 30–1, 35–1, 55–1, 79–1, 80–5, 82–5, 94–1, 101–1]
community #8: [36–5, 58–11, 59–10, 63–10, 97–10]
community #9: [44–4, 48–4, 57–4, 66–4, 75–4, 86–4, 91–4, 92–4, 112–4]
community #10: [46–11, 49–11, 53–11, 67–11, 73–11, 83–11, 88–11, 110–4, 114–11]
Modularity: 0.595356

For the most part, the algorithm was able to correctly cluster the teams with their respective groups. However, some flaws are shown, mainly due to the presence of independent teams which don’t belong in a formal conference. The algorithm also calculated a modularity score that is relatively high. Nevertheless, this output provides a good starting point with many opportunities for optimization.

For our extension, we decided to implement an agglomerative algorithm and compare it to the Girvan-Newman algorithm. The metrics we used for comparison were final modularity, and the time it took to reach the partitions. The algorithm we decided to use was the Louvain algorithm.

Here is the pseudocode[1]:

Essentially, what Louvain does is move nodes into different communities, where each node starts in its own community, until there is no discernable increase in modularity.

To test, we used the football.graphml file, and six randomly generated graphs with 4 communities and a total of 32 nodes each. One thing to note here is that in the Louvain algorithm, a community-joining optimization was implemented. The way that community optimization works is instead of moving individual nodes, it calculates the resulting modularity of joining two communities together, and tests this for every combination of communities. The modularity and timing comparisons with this optimization are shown below:

Without this optimization, modularity tends to be less consistent, with less communities being joined together. Those graphs are shown below:

Here is an example of the difference in communities with and without the community optimization on the football.graphml file:

Community Report (without community optimization)
community #0: [0–7, 4–7, 9–7, 16–7, 23–7, 41–7, 93–7, 104–7]
community #1: [1–0, 25–0, 33–0, 37–0, 45–0, 89–0, 103–0, 105–0, 109–0]
community #2: [2–2, 6–2, 13–2, 15–2, 32–2, 39–2, 47–2, 60–2, 64–2, 100–2, 106–2]
community #3: [3–3, 5–3, 10–3, 40–3, 52–3, 72–3, 74–3, 81–3, 84–3, 98–3, 102–3, 107–3]
community #4: [7–8, 8–8, 21–8, 22–8, 51–8, 68–8, 77–8, 78–8, 108–8, 111–8]
community #5: [11–10, 24–10, 28–11, 50–10, 69–10, 90–5]
community #6: [12–6, 18–6, 26–6, 34–6, 36–5, 42–5, 43–6, 61–6]
community #7: [14–6, 31–6, 38–6, 54–6, 71–6, 85–6, 99–6]
community #8: [17–9, 20–9, 27–9, 56–9, 62–9, 65–9, 70–9, 76–9, 87–9, 95–9, 96–9, 113–9]
community #9: [19–1, 29–1, 30–1, 35–1, 55–1, 79–1, 80–5, 82–5, 94–1, 101–1]
community #10: [44–4, 48–4, 57–4, 66–4, 75–4, 86–4, 91–4, 92–4, 112–4]
community #11: [46–11, 49–11, 53–11, 67–11, 73–11, 83–11, 88–11, 110–4, 114–11]
community #12: [58–11, 59–10, 63–10, 97–10]

Community Report (with community optimization)
community #0: [0–7, 4–7, 9–7, 11–10, 16–7, 23–7, 24–10, 28–11, 41–7, 50–10, 69–10, 90–5, 93–7, 104–7]
community #1: [1–0, 25–0, 33–0, 37–0, 45–0, 89–0, 103–0, 105–0, 109–0]
community #2: [2–2, 6–2, 13–2, 15–2, 32–2, 39–2, 47–2, 60–2, 64–2, 100–2, 106–2]
community #3: [3–3, 5–3, 10–3, 40–3, 52–3, 72–3, 74–3, 81–3, 84–3, 98–3, 102–3, 107–3]
community #4: [7–8, 8–8, 21–8, 22–8, 51–8, 68–8, 77–8, 78–8, 108–8, 111–8]
community #5: [12–6, 14–6, 18–6, 26–6, 31–6, 34–6, 36–5, 38–6, 42–5, 43–6, 54–6, 61–6, 71–6, 85–6, 99–6]
community #6: [17–9, 20–9, 27–9, 56–9, 58–11, 59–10, 62–9, 63–10, 65–9, 70–9, 76–9, 87–9, 95–9, 96–9, 97–10, 113–9]
community #7: [19–1, 29–1, 30–1, 35–1, 55–1, 79–1, 80–5, 82–5, 94–1, 101–1]
community #8: [44–4, 48–4, 57–4, 66–4, 75–4, 86–4, 91–4, 92–4, 112–4]
community #9: [46–11, 49–11, 53–11, 67–11, 73–11, 83–11, 88–11, 110–4, 114–11]

In conclusion, using the Louvain algorithm, we can decrease the time by around 68.7%, while still achieving a similar modularity.

Works Cited

[1] Pseudocode of the Louvain Method taken from Aynaud & Guillaume (2010) | Download Scientific Diagram (researchgate.net)

Qualitative Comparison of Community Detection Algorithms (arxiv.org)

https://link.aps.org/doi/10.1103/PhysRevE.69.026113

https://doi.org/10.1073/pnas.122653799

Comparing Divisive and Agglomerative Community Detection Algorithms was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Reintroduction to Girvan Newman Algorithm

As mentioned in part 1 of this 3-part series, the Girvan-Newman Algorithm, named after Michelle Girvan and Mark Newman, is a hierarchical method used to detect communities in networks[1].

Modifications — Multi Edge Removal

Our initial idea for the extension portion of our project was to find a variety of modifications and improvements to the Girvan-Newman Algorithm and essentially implement all of them. Following these implementations, we were going to compare the individual performance of each modification and, finally, implement all of them into the “Ultimate Girvan-Newman Algorithm.” However, after much research, we found that many of these modifications do not work on undirected, unweighted graphs (which we were using). So, we had to do away with the idea.

Regardless, we decided to implement the one modification that DID work with our implementation, which was the ability for multi-edge removal. Essentially, instead of removing one edge at a time, we can remove multiple edges at a time which reduces the number of operations but retains the same computational complexity. So, it is still unable to apply the algorithm to networks with a lot of nodes[2].

Our results?

For one, the time it took to run the base implementation versus running the extension portion could be discerned. In terms of its performance, which is measured by the final modularity, the modularity decreased from 0.65597 from the base implementation to 0.611.

Notes

Although we weren't able to implement it, we found a certain modification interesting. This modification is worth noting.

• Trust-Based Girvan Newman Algorithm: This modification was highly intriguing because it reconstructs the Girvan-Newman Algorithm so it isn’t based on the betweenness centrality, but, rather, it is based on trust. This modification did not work with our algorithm because its implementation works better with weighted, directed graphs, which was not what we were using for our implementation[3].

The trust between nodes u and v is determined using the “direct trust” between nodes (u,v) and the “indirect trust between nodes (u, v).

The pseudocode for this algorithm is as follows:

As you’ll notice, this algorithm requires a weighted graph so we didn’t implement this one. We thought it was still worth noting though!

Sources:

[1] https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm.

[2] L. Despalatović, T. Vojković, and D. Vukic̆ević, “Community structure in networks: Girvan-Newman algorithm improvement,” 2014 37th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), 2014, pp. 997–1002, doi: 10.1109/MIPRO.2014.6859714.

[3] https://link.springer.com/content/pdf/10.1007/s12652-021-03508-y.pdf

About Eileen:

Eileen is a sophomore at Southern Methodist University. She is pursuing a B.S. in Computer Science with a specialization in Cyber Security. In her free time, Eileen enjoys catching up on sleep and practicing self-care.

Modifications to the Base Implementation of the Girvan-Newman Algorithm (GMZ Series Part 2) was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Paige McFarlain is a Sophomore at Southern Methodist University, pursuing a Bachelor of Science in Computer Science and a minor in Business.

I was recently tasked with implementing the Girvan Newman algorithm for community detection relying primarily upon C++’s Boost Graph Library and during my countless hours of desperate googling, I realized I was asking a question that no one cared enough to answer. No one was going out of their way to implement Girvan Newman in C++ because it had already been done in a shinier, newer language: Python.

What is the Girvan-Newman algorithm?

The Girvan-Newman algorithm is a community detection algorithm developed by Michelle Girvan and Mark Newman. The primary functionality of the algorithm is centered around finding edges that are most common in between communities and removing said edges from the network. This algorithm relies heavily on the concept of edge betweenness, a measurement of how likely a given edge is to be found between the shortest paths from one point in the network to another. The measurement of edge betweenness is not authoritatively decided upon but in my implementation of the Girvan-Newman algorithm, I decided to go with a more basic heuristic. To calculate edge betweenness, my algorithm uses Breadth-First Search to identify the nodes used in the shortest paths from any given node on the map to another. With this data, it then identifies which edge is most commonly used in these shortest paths by traversing the shortest paths and counting each edge that is used. The edge that is featured the most is hereby removed in accordance with the Girvan-Newman algorithm and the process repeats.

Another important concept to the Girvan-Newman algorithm is that of modularity. If one follows the Girvan-Newman algorithm through to its entirety, they will be left with a disconnected cluster of nodes. To decide when to pause the algorithm to ensure the ideal clustering of communities, one must calculate a modularity value. The best equation for this number is also somewhat contested so I decided to implement my own (albeit limited) heuristic for this value. I believe that an ideal stopping point for the Girvan-Newman algorithm is when it begins to stabilize. The Girvan-Newman algorithm focuses on removing edges that may be deemed outliers in a given community. Take this simple graph below for example.

Edges (A, B) and (E, F) have only 1 shortest path passing through them. Whereas edge (C, D) has 9, more than double any of the other edges. This makes (C, D) an outlier. Thus, following the Girvan-Newman algorithm, this edge is removed resulting in the graph below.

As you can see, each of the edges have identical edge betweenness. This is what I would consider a “stable” graph. To determine the stability of a graph, I keep track of the minimum and maximum edge betweenness values. When the minimum edge betweenness divided by the maximum edge betweenness equals 1, the graph is 100% stable and the algorithm can exit.

Of course, not every situation is quite so simple. For most graphs, there is no equilibrium for them to reach. For others, the equilibrium lies only in impossibly small communities. So through trial and error, and comparisons against pre-existing community data [1], I determined that the ideal stability lies around 70%.

So clearly, I made quite a few changes to the average heuristic followed in a Girvan-Newman implementation. After these changes, I was curious to see how my implementation performed against Python’s NetworkX Girvan-Newman algorithm.

While the Python implementation consisted of 30 lines of code including code to output a graph visualization, my C++ implementation spanned 3 files with about 300 lines of code altogether, not including the Python file needed to convert GML to GraphML.

Python, however, performed consistently faster and more accurate than my algorithm. This is not even a disappointing realization, however, considering the power of technology that can perform such quick and accurate calculations with minimal effort.

References:

[1] http://www-personal.umich.edu/~mejn/netdata/

Comparing the Performance of Community Detection Algorithms in Python’s NetworkX and C++’s Boost… was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.

By Ian Webster

Links to other parts: Part 1, Part 2

Multi-Edge Removal

We settled on implementing a multi-edge removal feature in our Girvan Newman algorithm for our project's improvement. This feature speeds up the process of separating communities in the graph by removing multiple edges with equal betweenness values at a time, rather than removing them one at a time like the original algorithm does.

Further adding to this feature, we implemented a range of edge removal to see how this would affect the graph and the performance of the algorithm. The range is any positive whole integer and defines how far away from the maximum betweenness value the algorithm will delete. For instance, if the highest betweenness is 80, and the range is 5, the algorithm will remove all edges with a betweenness greater than or equal to 75. Our intent is that this will speed up the process for the larger datasets by removing larger chunks of edges than the default range of zero would.

Pros:

Compared to single edge removal, multi-edge removal cuts the processing time in half. This is more and more valuable the larger the graph or dataset is.

Below are the calculated times it took for our algorithm to separate the communities of the football graph with single-edge-removal and multi-edge-removal with both the default range of 0 and a range of 3.

Cons:

Unfortunately after recording the runtimes between the different ranges, we found that the differences in times are either non-existent or too small to be deemed effective.

Multi also has a chance to remove integral edges, which will isolate an individual vertex/node to its own community that should not exist. This risk increases as the range increases and as the size of the graph decreases.

Links to other parts: Part 1, Part 2

References

[1] The Boost Graph Library — 1.78.0

[2] Girvan-Newman algorithm | NetworkX Guide

[3]https://www.researchgate.net/publication/271472127_Community_structure_in_networks_Girvan-Newman_algorithm_improvement

[4] smu-cs-3353/22s-pa03-girvan-newman-ian_maxwell: 22s-pa03-girvan-newman-ian_maxwell created by GitHub Classroom

Writer Bio

I am a Sophomore at SMU majoring in Computer Science and Creative Computations. I have a deep interest in procedural generations and algorithms and a passion for game design and development.

Girvan Newman Part 3 — Two Multi-Edge Removal was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Links to other parts: Part 1, Part 3

By Maxwell Calvert

Spring 2022

Resources Used

For our implementation of the Girvan Newman community detection algorithm, we coded it in C++ using the Boost Graph Library. The Boost Graph Library (BGL) is a C++ library that includes a wide range of functionality and implementations for graph data structures and algorithms. The graphs being read and handled by the BGL are in .graphml format, which contains all of the vertex and edge information for the graph.

Our implementation

Our betweenness algorithm uses a map to track each edge present within a graph and its associated betweenness value.

std::map<Edge, int> betweenness_map;
auto bet_property_map = boost::make_assoc_property_map(betweenness_map);

Utilizing boost visitors, a list of shortest paths is generated for each vertex in a graph. For each edge present in this list, we simply increment the value for the corresponding edge in our map container. This is then done for every vertex in the graph such that each edge can now be associated with its overall betweenness. E.g.:

for(vertex i in Graph){
    breadth_first_search(visitor(record_predecessors));
    for(vertex j in Graph){
        Edge e = edge present in predecessors[j];
        map[e]++;
    }
}

We then followed the basic Girvan-Newman algorithm and deleted the edge(s) with highest betweenness (note that we separately implemented both single and multiple edge deletion). Because we knew in advance the number of communities in our testing datasets, we could utilize boost’s connected_components function to determine when to stop our algorithm. Once this detected the proper amount of communities, we could stop deleting edges and thereby be left with a graph separated into disconnected clusters.

Efficiency Comparison

An attempt was also made to compare our betweenness algorithm with Brandes’ Betweenness Centrality provided in the boost library. In comparing runtimes of the entire algorithm when the betweenness algorithms were swapped out, we discovered our own betweenness algorithm completing significantly faster than when using brandes_betweenness_centrality (to the tune of ~0.2 second runs for ours versus ~6 second runs on the same graphs for Brandes). The extreme disparity here led us to believe that there was some misunderstanding on our part of how boost’s algorithm works or perhaps some greater level of functionality added to boost’s that is not present in our own algorithm that might cause such a disparity. Ultimately, we decided the comparison was not helpful in measuring the efficiency of our own betweenness algorithm.

References

[1] The Boost Graph Library — 1.78.0

[2] Girvan-Newman algorithm | NetworkX Guide

[3]https://www.researchgate.net/publication/271472127_Community_structure_in_networks_Girvan-Newman_algorithm_improvement

[4] smu-cs-3353/22s-pa03-girvan-newman-ian_maxwell: 22s-pa03-girvan-newman-ian_maxwell created by GitHub Classroom

Writer Bio

Maxwell Calvert is an SMU graduate with degrees in Computer Science and Data Science. He is passionate about programming, growing personal skills, music, and gaming.

Girvan-Newman Part 2 — Our Method was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.

By Austin Werth

Links to other parts: Part 2, Part 3

The Girvan Newman Algorithm

The Girvan Newman algorithm is a community detection algorithm that aims to detect and separate communities based on the connections between each node in a graph (or some other series of items with connections). This is done by iteratively removing edges between communities until each community is separated or “detected”. However, the process used to properly remove edges only between communities uses the main idea of what is known as edge betweenness centrality.

Edge betweenness centrality is a measure of centrality between two nodes based on the shortest path between the nodes. In other words, if the betweenness centrality of every edge in a graph was to be calculated for every pair of nodes, then one would find that the edges connecting two communities together would have the greatest betweenness centrality. This is true because the shortest paths between nodes of two separate communities would almost always be required to traverse that one (or multiple) edge(s) that bridges the two communities together. By knowing this, it can be assumed that the edges with the greatest betweenness centrality would also be the edges that connect multiple communities together. Therefore, if all the edges with a very high between centrality were removed from a graph, it would effectively separate all of the nodes into their respective “communities”. However, when does the algorithm know when to stop removing edges in order to accurately separate the communities in the graph? The answer, modularity.

Modularity is a measure of the strength of division of a graph/network into groups or communities. In other words, it serves as an indicator for the algorithm on whether it should continue to remove edges to separate the communities or if no more edges need to be removed since the communities are now separated. Modularity can be implemented in many different ways using an equation such as

or by checking the number of separated communities every time an edge is removed. Modularity is a very important aspect of the community detection algorithm since it ensures that the communities will be accurately separated. For instance, if the modularity value is off it could either not remove enough edges, defeating the entire point of the algorithm, or remove too many edges, isolating individual and small groups of nodes that are supposed to belong to a larger community.

The Girvan Newman algorithm community detection has several complex parts that can be implemented in a variety of ways, with some bad and some good. These possible implementation differences are some of the main reasons why there are nearly endless posts, coding libraries, etc. relating to the Girvan Newman algorithm as well as why it is still widely used today. The next part of this article will explore one possible implementation of the Girvan Newman algorithm using the Boost Graph Library for C++.

Link to other parts: Part 2, Part 3

References

[1] The Boost Graph Library — 1.78.0

[2] Girvan-Newman algorithm | NetworkX Guide

[3] https://www.researchgate.net/publication/271472127_Community_structure_in_networks_Girvan-Newman_algorithm_improvement

[4] smu-cs-3353/22s-pa03-girvan-newman-ian_maxwell: 22s-pa03-girvan-newman-ian_maxwell created by GitHub Classroom

Writer Bio

Austin Werth is a Sophomore at SMU majoring in Computer Science. He is passionate about algorithm analysis, software development, and app development.

Girvan Newman Part 1 — Description and Components was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Her desired track is Cybersecurity. Her future plan is to become a game designer.

Introduction

If we visualize our social network like a graph, where each node on the graph represents a person, and each edge on the graph represents a form of connection between two people (be it friendship or any kind of relationship)
then we can see, clearly, that some nodes are more closely related to each other than to other nodes.

We call those clustering nodes communities. So, how can we identify individual community in this massive interconnected network?

Community detection is one of the most practiced and revised algorithms for detecting patterns in graph . By rewriting properties of edges in a complex graph, we can analyze the .

For project 3, we were asked to find the possible communities in a network by implementing the Girvan-Newman algorithm in an unweighted, undirected graph.

According to Girvan and Newman, the basic steps of the GN Algorithm are:

1. Calculate the betweenness for all edges in the network.

2. Remove the edge with the highest betweenness.

3. Recalculate betweennesses for all edges affected by the removal.

4. Repeat from step 2 until no edges remain.

It is said that the worst case computation time is O(m^2 * n). However, if we recalculate only the edges, or rather, only the communities that are affected by the removal, the computation time could potentially increase.

Let’s consider this case, where some edges had already been removed, and the graph has been split into multiple communities:

The algorithm will most likely choose to break down the biggest, most clustered community, BL, on the bottom left, and then recalculate the edge betweenness.

But we want it to calculate only the related edges — which are all edges that exist within BL. We don’t want the algorithm to calculate other edges as they will remain unchanged.

Here comes a question: on the first run, the algorithm was intended to go through all edges in the graph.

1. Calculate the betweenness for all edges in the network.

So how can we modify the algorithm that we only calculate the edges in the same community?

Implementation

1. Pass the paired vertices (source,target) of the removed edge E as parameters into our breadth-first-search function
2. Update the only the communities that have the passed vertices. If the removed edge causing one community to break down, calculate them separately.

Pseudocode:

void BFSCont(const Graph& g,Vertex source, Vertex target){
int groupIndexS = component[source];
updateGroup(g, groupIndexS);

int groupIndexT = component[target];
updateGroup(g, groupIndexT);

return findMaxCentralityEdge(g);

}

void updateGroup(Graph g,Vertex groupIndex){
Community = findCommunity(groupIndex);
for(Edge i : Community){
updateBetweenness(i);
}
}

Performance

I tested the original(notByGroup) and the improved(byGroup) algorithm on different vertex and edge sizes.

The Number of Vertices vs Computation Time (ms)

The Number of Edges vs Computation Time (ms)

Conclusion

It is clear from the output graph that the computation time is less for the improved algorithm, albeit not by much. I expect the computation time will be significantly better with more edges and vertices, as it will cost more time to iterating through every affected and unaffected community every time an edge is removed.

References

Girvan, M., & Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12), 7821–7826.

Newman, M. E. (2006). Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23), 8577–8582.

Attempt to Update Only Affected Communities In Girvan-Newman Algorithm Using Boost Graph Library was originally published in smucs on Medium, where people are continuing the conversation by highlighting and responding to this story.