Is Girvan Newman a Edros-Renyi model(?)
This article is part two 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
In our previous article, we were discussing how Girvan Newman had a new approach to building communities in a network. They proposed an idea that introduced the betweenness of nodes. From there, one could then remove central nodes to focus on the outermost nodes of a network.
However, how unique is a community in graph theory? While researching Girvan Newman, we came across a very interesting model for community detection called the Edros-Renyi Model (ER). Edros-Renyi summarised that any graphs and networks in the natural world can be modelled using some sort of random statistical probability. Edros-Renyi recognised this and developed an algorithm that would randomly generate a graph based on the likelihood of nodes being related [1].
So, how does Edros-Renyi work? By definition, an Erdos-Renyi Graph is formed of a vertex V of a random graph which connects a pair of nodes {i,j} with a probability. This probability is the independence of the nodes. Using a binomial distribution with a reducing number of nodes, you can then randomly determine edges between nodes, modelling a community [2].
Boost Graphing Library’s (BGL) in C++ already held the capability of producing a Erdos-Renyi graph, which takes in two main parameters: now many nodes you have, and what is the probability of independence between these nodes. Having a seeded start for this model, you can simply produce and model random communities using C++.
Figure 1.1: Modelling an Edros-Renyi graph using boost, C++.
In the final part of these series, we will be discussing how we used this model to explore the randomness of communities and compared it to the Girvan Newman algorithm.
References:
[1] Erdos Renyl Model (for generating Random Graphs).
https://www.geeksforgeeks.org/erdos-renyl-model-generating-random-graphs/ Nov 21st 2021
[2] https://pages.stat.wisc.edu/~karlrohe/netsci/ergraphs.html
Link to Part 1: https://medium.com/@katielrink/girvan-newman-changing-the-times-1c7eb3d4b109
Link to Part 3: Edros-Renyi model: Is it random chaos or a thriving way to model a community? | by Nicole Sood | Apr, 2022 | Medium
