Increasing Accessibility of the Girvan-Newman Algorithm
Author: Elliot Boesch
What is the Girvan-Newman Algorithm?
This algorithm is a divisive hierarchal clustering algorithm proposed by Michelle Girvan & Mark Newman. When given a network of connected nodes, the algorithm will output the same network but with edges removed. By removing certain edges, the network will “transform” into a cluster of communities. To know which edges need to be removed from the network, a series of calculations are performed to find edge betweenness. This value represents the number shortest travel paths through an edge in a network. This algorithm, along with other community detection algorithms, can be extremely useful when implemented in social media platforms.
Increasing Accessibility
After implementing my own version of this algorithm, I wanted to be able to access the algorithm while away from my computer. That is, I wanted a way to interact with my program without running directly from my personal machine. To do this, SMS seemed like a great option. And since I wanted to be able to interact with the program at any time, running the algorithm on my machine constantly didn’t seem like the best option. Thankfully, I can rent a virtual machine.
SMS
To interact with my program using SMS, I need to use Twilio. Twilio is a great SMS API. This essentially allows me to run code that can generate and send messages to my phone. The number from Twilio that I can send messages from is: (970) 423–7617.
Virtual Machine
To run the program constantly, it needs to be not running on my personal machine. So a rented virtual machine will be perfect. I used a general purpose Droplet from DigitalOcean. This Droplet consists of 2 vCPUs, 4GB of Ram, and an 80GB Disk.
Both of these services were free of use because I utilized offers from these companies in the GitHub Student Developer Pack.
Outcome
With a rather ambitious goal, I was able to provide more accessibility than before to my Girvan-Newman algorithm. That being said, I was not able to accomplish my original plan.
What Works
Importing Twilio into the project was a breeze and I was communicating in no time. Currently, my setup allows for retrieval of community-divided networks. My program can send SMS messages and MMS images of the networks.
What Doesn’t Work… yet
Regarding the DigitalOcean Droplet, I was able to use Termius (SSH Client) to access the virtual machine. Since it was like a brand new computer, I needed to download everything. After many of Google searches, I finally was able to compile a simple C++ program on the virtual machine. Getting the Boost Graph Library to work on the virtual machine was the next issue. Ultimately, I was not able to run the my implementation of the Girvan-Newman algorithm on this virtual machine…yet. I plan on continuing my work on this extension project and I have faith in my capability to bring this functionality soon!
About the Author: I am a 4th year Computer Engineer major at SMU. I created my implementation of the Girvan-Newman algorithm for my Algorithms course here at SMU.
