IJCsatellite IJCsatellite/PRL


Phys. Rev. Lett. 94, 160202 (2005)

Clique Percolation in Random Networks

Imre Der?nyi,1 Gergely Palla,2 and Tam?s Vicsek1,2
1Department of Biological Physics, E?tv?s University, P?zm?ny P. stny. 1A, H-1117 Budapest, Hungary
2Biological Physics Research Group of HAS, P?zm?ny P. stny. 1A, H-1117 Budapest, Hungary

(Received 10 November 2004; published 29 April 2005)

The notion of k-clique percolation in random graphs is introduced, where k is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erds-R?nyi graph of N vertices we obtain that the percolation transition of k-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold pc(k)=[(k-1)N]-1/(k-1). At the transition point the scaling of the giant component with N is highly nontrivial and depends on k. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks. ?2005 The American Physical Society

URL: http://link.aps.org/abstract/PRL/v94/e160202
PACS: 02.10.Ox, 05.70.Fh, 64.60.-i, 89.75.Hc

© Copyright 2013 Kei Tokita, Powered by Pukiwiki.  Last-modified: Sun, 23 Jun 2013 13:50:21 JST (2340d)   リロード   新規 編集 凍結 差分 添付 複製 改名   トップ 一覧 検索 最終更新 バックアップ   ヘルプ   最終更新のRSS