Edros-Renyi model: Is it random chaos or a thriving way to model a community?

This article is the conclusion of a three-part series following a project completed by three undergraduate students from Southern Methodist University.

Nicole Sood — Computer Science

Maggie Asare — Computer Engineer and Business Studies

Katie Rink — Computer Science

In our previous articles, we began by discussing how Girvan Newman had a new approach to building communities in a network. From there, we then introduced to our readers the Edros-Reyni model which in summery can model a community network using probability and statistics. As an exploration of this idea of ‘betweenness’ introduced by Girvan Newman, we decided to see how varying the probability can change the perception of communities in a graph.

In addition to our C++ implementation, we also decided to implement Edros-Reyni using Python. The logic and execution of the program followed that of the C++ implementation, however it allowed us to easily visualise the graph. For each test, we modelled using 60 nodes and adjusted the probability of independence between the nodes.

With this in mind, we wanted to explore the following:

1. What happens if there is no relationship between the nodes?

2. What happens if there is guaranteed to be a relationship between the nodes?

3. Can we produce a graph that reflects the Girvan Newman algorithm?

What happens if there is no relationship between the nodes?

Figure 1: An Edros-Reyni model for a network with nodes that are completely independent of each other.
(Probability of independence = 0.001)

As we can see in Figure 1, if the chance of independence is high, we end up with a graph with 60 completely isolated nodes. There are no edges between the nodes, and there does not seem to be any sort of logical connection between any of the points.

What happens if there is a high chance the nodes are related?

Figure 2: An Edros-Reyni model for a network with nodes that are completely dependent of each other.
Probability of independence (1)

In Figure 2, we can see that if nodes are highly interconnected if the nodes are dependent on each other. Like a completely unrelated graph, we see this clear circle effect of the graph, however this time there are multiple edges between each node.

Can we produce a graph that reflects the Girvan Newman algorithm?

Figure 3: An Edros-Reyni model for a network attempting to model Girvan-Newman.
Probability of independence (0.075)

In Figure 3, we have explored and managed to produce an Edros-Reyni graph which highly reflects the traits of a Girvan-Newman graph. Due to the random nature of this algorithm, it is extremely difficult to produce an output with completely isolated communities.

However, you can still see the following traits for a Girvan-Newman graph:

- A hierarchical ordering or the nodes,

- Some grouping based on community,

- Moderate ‘edginess’ and betweenness of nodes

Figure Four: An image showing the impact different probabilities of independence has on an Edros-Reyni Model

Overall we found it was possible to model a Girvan Newman graph using the Erdos-Reyni model, and for the best results you want to use an independence between roughly 0.065 and 0.085 for the best results.

Thank you for following along on our three part series. If you missed a part please check out the following:

Part One:https://medium.com/@katielrink/girvan-newman-changing-the-times-1c7eb3d4b109

Part Two: https://medium.com/@robotics.mags/is-girvan-newman-a-edros-renyi-model-8c6d378d4e39