On the clustering property of the random intersection graphs
Xin Yao, Jinwen Chen, Changshui Zhang, Yanda Li · RENATE · 2008
A random intersection graph \mtl{\mcal{G}_{V,W,p}} is induced from a random bipartite graph \mtl{\mcal{G}^{*}_{V,W,p}} with vertices classes \mtl{V}, \mtl{W} and the edges incident between \mtl{v \in V} and \mtl{w \in W} with probability \mtl{p}. Two vertices in \mtl{V} are considered to be connected with each other if both of them connect with some common vertices in \mtl{W}. The clustering properties of the random intersection graph are investigated completely in this article. Suppose that the vertices number be \mtl{N = \mabs{V}} and \mtl{M=\mabs{W}} and \mtl{M = N^{\alpha},\ p=N^{-\beta}}, where \mtl{\alpha > 0,\, \beta > 0}, we derive the exact expressions of the clustering coefficient \mtl{C_{v}} of vertex \mtl{v} in \mtl{\mcal{G}_{V,W,p}}. The results show that if \mtl{\alpha 2\beta}, 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 \mtl{\riG} being high clustering graph.