Exploring Erdos-Renyi Random Graphs

G(n,p) graphs properties

Fernando J. Pérez García

Introduction

What is a Random Graph


A random graph is a model network in which some specific set of parameters take fixed values, but the network is random in other respects. One of the simplest examples of a random graph is the G(n,p) network, studied by Erdos-Renyi during the 1960's. This graphs are generated with 2 parameters: n the total number of vertices in the graph, p the probability of edges between vertices.
In this networks the number of edges is not fixed but there are some values of p that suppose some important changes in the network:

  • if \(p = \frac{1}{n^2}\), the network has some links
  • if \(p = \frac{1}{n^\frac{3}{2}}\), the network has a component with at least three links
  • if \(p = \frac{1}{n}\), the network has a cycle
  • if \(p = \frac{log(n)}{n}\), the network is connected (there are no isolated nodes)

Exploring Random Graphs shiny app, helps you test this characteristics of the Erdos-Renyi G(n,p) random graphs.

Graph Samples, for n = 70 nodes and different values of p

plot of chunk unnamed-chunk-1

R Code

aGraph <- function(n, p, title){
    g <- erdos.renyi.game(n, p)

    if (max(degree(g)) > 0)
        dclust = cut(degree(g),9,label=F)
    else
        dclust = 1

    V(g)$color = brewer.pal(9,"Blues")[dclust]

    plot.igraph(g, edge.arrow.size=0, edge.curved=FALSE,
            layout = layout.fruchterman.reingold(g, niter=10000),
            vertex.label=NA, vertex.color=V(g)$color,
            vertex.size=6, main=paste(title,"\n","Probability: ",p))
}

library(igraph)
par(mfrow=c(2,2))
aGraph(70, 0.0004, "Some links")
aGraph(70, 0.004, "At least three links")
aGraph(70, 0.025, "A cycle")
aGraph(70, 0.08, "Connected")

Shiny App


Exploring Random Graphs

Left panel alows you to select:

  • Parameter n (number of nodes)
  • Parameter p (probability of generating a link)
  • Network parameter by which nodes are coloured

Main Panel has three tabs:

  • Tab1, shows a hint text with some interesting probablity values for the given value of n, and a plot with the resulting network
  • Tab2, contains an histogram of nodes degree distribution
  • Tab3, includes the application help

Exploring Random Graphs

Random Graphs G(n,p) Question

Keeping the same value of p, as n gets larger, what happens with the average degree in the network?

  1. Average degree increases
  2. Average degree decreases

As n gets larger, there are more nodes in the network, therefore more nodes applying for generating a new link.