WIAS Preprint No. 1369, (2008)

On the clustering property of the random intersection graphs


  • Yao, Xin
  • Chen, Jinwen
  • Zhang, Changshui
  • Li, Yanda

2010 Mathematics Subject Classification

  • 05C80 05C75 05C40


  • random intersection graphs, clustering coefficient, phase transition




A random intersection graph mtlmcalG_V,W,p is induced from a random bipartite graph mtlmcalG^*_V,W,p with vertices classes mtlV, mtlW and the edges incident between mtlv in V and mtlw in W with probability mtlp. Two vertices in mtlV are considered to be connected with each other if both of them connect with some common vertices in mtlW. The clustering properties of the random intersection graph are investigated completely in this article. Suppose that the vertices number be mtlN = mabsV and mtlM=mabsW and mtlM = N^alpha, p=N^-beta, where mtlalpha > 0,, beta > 0, we derive the exact expressions of the clustering coefficient mtlC_v of vertex mtlv in mtlmcalG_V,W,p. The results show that if mtlalpha < 2beta and mtlalpha neq beta, mtlC_v decreases with the increasing of the graph size; if mtlalpha = beta or mtlalpha geq 2beta, the graph has the constant clustering coefficients, in addition, if mtlalpha > 2beta, the graph connecChangshui Zhangts almost completely. Therefore, we illustrate the phase transition for the clustering property in the random intersection graphs and give the condition that mtlriG being high clustering graph.

Download Documents