Randomly generate network with specified clustering coefficient

user_10615512 0
Viewed 347

In the past I have used igraph to generate small world networks with a specified rewiring probability p, which is especially easy because it's an argument in the sample_smallworld function. For instance:

myNetwork <- sample_smallworld(dim = 1, size = 10, nei = 2, p = 0.25)
plot(myNetwork, layout = layout_in_circle)

I'd now like to generate small world networks with a specified clustering coefficient. I'm new to igraph and this seems like a functionality that it would have, but after some searching I've only found ways to calculate the coefficient from pre-existing networks, rather than a way to use it as a parameter for generating the network itself.

What's the best way to generate networks with a specified clustering coefficient ?

igraph r
2 Answers

As far I understand, you cannot specify the clustering coefficient (or transitivity, as it is named in the igraph package) because it is conditional on the parameters you specify.

Why? sample_smallworld generates a graph according to the Watts-Strogatz Model, as explained in the documentation. Check out the maths of the model on Wikipedia. The Watts-Strogatz model has three parameters:

  1. Number of nodes (size parameter in the sample_smallworld method, N in the wikipedia article);
  2. Average number of links per node (nei parameter, K on wikipedia);
  3. Probability of connecting random pair of nodes, for each link in the graph, via "rewiring" (p parameter, beta on Wikipedia).

Have a look at Wikipedia (section "Clustering coefficient") to understand how the clustering coefficient can be computed from these parameters.

More empirically, if you play around with the parameters in your model, you can see how they affect the clustering coefficient with the transitivity command.

# clustering coefficient in your data:

myNetwork <- sample_smallworld(dim = 1, size = 10, nei = 2, p = 0.25)
transitivity(myNetwork)
[1] 0.3870968

# Varying average links/node:

for(i in 1:5) {
  set.seed(1) # use this to get the same results
  myNetwork <- sample_smallworld(dim = 1, size = 10, nei = i, p = 0.25)
  print(transitivity(myNetwork, type="global"))
}

[1] 0
[1] 0.2380952
[1] 0.6
[1] 0.8723404
[1] 1


# Varying rewiring probability:

for(i in c(0.05, 0.1, 0.2, 0.5, 1)) {
  set.seed(1)
  myNetwork <- sample_smallworld(dim = 1, size = 10, nei = 2, p = i)
  print(transitivity(myNetwork, type="global"))
}
[1] 0.483871
[1] 0.4615385
[1] 0.328125
[1] 0.3802817
[1] 0.4347826
user_104836920

If you are okay with a few conditions, then it is possible to get a sort of hacky approximation using sna::rguman(). The conditions are: (1) using global transitivity (maybe you could work with it and modify); (2) using undirected graphs; (3) using large size graphs if using small values of transitivity, or use larger values of transitivity for small size graphs. Also, give up the sample_smallworld() algorithm. If that's ok this might get you where you want to go:

library(sna)
library(igraph)

sample_cluster <- function(nv = 150, clustering_coef = 0.5, thres = 0.05) {
  g <- sna::rguman(1, nv, mut = clustering_coef, asym = 0, null = 1 - clustering_coef) %>% 
    graph_from_adjacency_matrix(mode = "undirected")

  while (!(transitivity(g) >= clustering_coef-thres & transitivity(g) <= clustering_coef+thres)) {
    g <- sna::rguman(1, nv, mut = clustering_coef, asym = 0, null = 1 - clustering_coef) %>% 
      graph_from_adjacency_matrix(mode = "undirected")
  }

  return(g)

} 


sample_cluster(15, clustering_coef = 0.2, thres = 0.001) %>% transitivity()
#> [1] 0.2

sample_cluster(200, clustering_coef = 0.01, thres = 0.001) %>% transitivity()
#> [1] 0.009009009

sample_cluster(200, clustering_coef = 0.2, thres = 0.001) %>% transitivity()
#> [1] 0.2007628

sample_cluster(20, clustering_coef = 0.7, thres = 0.001) %>% transitivity()
#> [1] 0.7007168

Created on 2020-03-31 by the reprex package (v0.3.0)

Not fancy, not sophisticated, but might do the trick!

user_44881050
Related