WORKING PAPERS SERIES
WP06-09
Effect of degree correlations on the
loop structure of scale-free networks
Ginwestra Bianconi and Matteo Marsili
arXiv:cond-mat/0511283v2 [cond-mat.dis-nn] 14 Jul 2006
E!ect of degree correlations on the loop structure of scale-free networks
Ginestra Bianconi and Matteo Marsili
The Abdus Salam International Center for Theoretical Physics, Strada Costiera 11, 34014 Trieste, Italy
In this paper we study the impact of degree correlations in the subgraph statistics of scale-
free networks. In particular we consider loops, simple cases of network subgraphs which encode
the redundancy of the paths passing through every two nodes of the network. We provide an
understanding of the scaling of the clustering coe!cient in modular networks in terms of the maximal
eigenvector of the average adjacency matrix of the ensemble. Furthermore we show that correlations
a"ect in a relevant way the average number of Hamiltonian paths in a three-core of real world
networks. We prove our results in the two-vertex correlated hidden variable ensemble and we check
the results with exact counting of small loops in real graphs.
PACS numbers: : 89.75.Hc, 89.75.Da, 89.75.Fb
I.
INTRODUCTION
The dynamics and the function of many complex sys-
tems strongly a!ect their network structure [1, 2, 3, 4].
In fact both large-scale properties (like the scale-free de-
gree distribution [5]) and local properties (like recurrence
of small motifs [6, 7]) must be selected for widespread
robustness requirements and specific preferential uses in
real graphs. A large number of di!erent networks [1, 2, 3],
from the Internet to the protein interaction networks in
a cell, share a scale-free degree distribution P (k) ! k!!
with ! < 3 and a high clustering coe"cient respect to
random Erdòˆs-Renyi graphs [8]. The scale-free degree
distribution of a network a!ects the statistics of sub-
graphs present in it showing that large-scale properties
and local properties of scale-free networks are strongly
related to each other. Spec