R/graphs_erdos.R

In tjtnew/graphr: Random Graph Generation

#' Adjacency matrix version of undirected Erdos-Renyi random graph
#'
#' \code{erdos_matrix} creates an adjacency matrix representation of an
#' undirected Erdos-Renyi random graph.
#'
#' This functon generates an undirected random graph of size \code{N}, each node
#' having average degree \code{avk}.  Self and repeated edges are not permitted
#' so if \code{avk > (N - 1)} a fully connected network will always be returned.
#'
#' @param N Number of vertices / nodes in the network.
#' @param avk desired average degree of the network
#' @return adjacency matrix representation of the resultant network
#' @examples
#' gr <- erdos_matrix(1000,10)
#' @export
erdos_matrix <- function(N, avk) {
  network <- matrix(0L, nrow = N, ncol = N)
  p <- avk / (N - 1)
  for (i in 1:(N - 1)) {
    for (j in (i + 1):N) {
      if (stats::runif(1) < p){
        network[i, j] <- 1L
        network[j, i] <- 1L
      }
    }
  }
  return(network)
}



#' Adjacency list version of undirected Erdos-Renyi random graph
#'
#' \code{erdos_list} creates an adjacency list representation of an
#' undirected Erdos-Renyi random graph.
#'
#' This functon generates an undirected random graph of size \code{N}, each node
#' having average degree \code{avk}.  Self and repeated edges are not permitted
#' so if \code{avk > (N - 1)} a fully connected network will always be returned.
#'
#' @param N Number of vertices / nodes in the network.
#' @param avk desired average degree of the network
#' @return adjacency list representation of the resultant network
#' @examples
#' gr <- erdos_list(1000,10)
#' @export
erdos_list <- function(N, avk) {
  network <- vector("list", N)
  # initialise list for better behaviour and compatibility with c++ code
  for (i in 1:N) {
    network[[i]] <- integer()
  }

  neighbours <- rep(0, N)
  p <- avk / (N - 1)
  for (i in 1:(N - 1)) {
    for (j in (i + 1):N) {
      if (stats::runif(1) < p){
        neighbours[i] <- neighbours[i] + 1
        neighbours[j] <- neighbours[j] + 1
        network[[i]][neighbours[i]] <- j
        network[[j]][neighbours[j]] <- i
      }
    }
  }
  return(network)
}