Number of cliques in random scale-free network ensembles

被引：15

作者：

Bianconi, Ginestra ^{[1
]}

Marsili, Matteo ^{[1
]}

机构：

[1] Abdus Salaam Int Ctr Theoret Phys, Condensed Matter Sect, I-34014 Trieste, Italy

来源：

PHYSICA D-NONLINEAR PHENOMENA | 2006年 / 224卷 / 1-2期

关键词：

complex networks;

D O I：

10.1016/j.physd.2006.09.013

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper we calculate the average number of cliques in random scale-free networks in the limit of large network size N >> 1. We consider first the hidden variable ensemble and subsequently the Molloy Reed ensemble. In both cases we find that cliques, i.e. fully connected subgraphs, appear also when the average degree is finite. This is in contrast to what happens in Erdos and Renyi graphs in which diverging average degree is required to observe cliques of size c > 3. Moreover we show that in random scale-free networks the clique number, i.e. the size of the largest clique present in the network, diverges with the system size. (c) 2006 Elsevier B.V All rights reserved.

引用

页码：1 / 6

页数：6

共 21 条

[1] Statistical mechanics of complex networks [J].

Albert, R ;

Barabási, AL .

REVIEWS OF MODERN PHYSICS, 2002, 74 (01) :47-97

[2] Loops of any size and Hamilton cycles in random scale-free networks [J].

Bianconi, G ;

Marsili, M .

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2005, :75-88

[3] Emergence of large cliques in random scale-free networks [J].

Bianconi, G ;

Marsili, M .

EUROPHYSICS LETTERS, 2006, 74 (04) :740-746

[4] Number of loops of size h in growing scale-free networks -: art. no. 078701 [J].

Bianconi, G ;

Capocci, A .

PHYSICAL REVIEW LETTERS, 2003, 90 (07) :4

[5] Class of correlated random networks with hidden variables -: art. no. 036112 [J].

Boguñá, M ;

Pastor-Satorras, R .

PHYSICAL REVIEW E, 2003, 68 (03) :13

[6] Scale-free networks from varying vertex intrinsic fitness -: art. no. 258702 [J].

Caldarelli, G ;

Capocci, A ;

De Los Rios, P ;

Muñoz, MA .

PHYSICAL REVIEW LETTERS, 2002, 89 (25)

[7] Resilience of the Internet to random breakdowns [J].

Cohen, R ;

Erez, K ;

ben-Avraham, D ;

Havlin, S .

PHYSICAL REVIEW LETTERS, 2000, 85 (21) :4626-4628

[8] Clique percolation in random networks -: art. no. 160202 [J].

Derényi, I ;

Palla, G ;

Vicsek, T .

PHYSICAL REVIEW LETTERS, 2005, 94 (16)

[9] Aggregation of topological motifs in the Escherichia coli transcriptional regulatory network -: art. no. 10 [J].

Dobrin, R ;

Beg, QK ;

Barabási, AL ;

Oltvai, ZN .

BMC BIOINFORMATICS, 2004, 5 (1)

[10]

Dorogovtsev S. N., 2003, EVOLUTION NETWORKS

← 1 2 3 →