Algorithms for generating large-scale clustered random graphs

Abstract

Abstract Real-world networks are often compared to random graphs to assess whether their topological structure could be a result of random processes. However, a simple random graph in large scale often lacks social structure beyond the dyadic level. As a result we need to generate clustered random graph to compare the local structure at higher network levels. In this paper a generalized version of Gleeson's algorithm G(V S , V T , E S , E T , S, T) is advanced to generate a clustered random graph in large-scale which persists the number of vertices | V |, the number of edges | E |, and the global clustering coefficient C Δ as in the real network and it works successfully for nine large-scale networks. Our new algorithm also has advantages in randomness evaluation and computation efficiency when compared with the existing algorithms.