Efficiency of informational transfer in regular an

a r X i v :c o n d -m a t /0410174v 2 [c o n d -m a t .d i s -n n ] 27 D e c 2004

Efficiency of informational transfer in regular and complex networks

I.Vragovi´c ,1E.Louis,1and A.D ´iaz-Guilera 2

1

Departamento de F ´isica Aplicada,Instituto Universitario de Materiales and Unidad Asociada CSIC-UA,Universidad de Alicante,E-03080Alicante,Spain

2Departament de F ´isica Fonamental,Universitat de Barcelona,E-08028Barcelona,Spain

(Dated:February 2,2008)We analyze the process of informational exchange through complex networks by measuring net-work efficiencies.Aiming to study non-clustered systems,we propose a modification of this measure on the local level.We apply this method to an extension of the class of small-worlds that includes declustered networks,and show that they are locally quite efficient,although their clustering coeffi-cient is practically zero.Unweighted systems with small-world and scale-free topologies are shown to be both globally and locally efficient.Our method is also applied to characterize weighted net-works.In particular we examine the properties of underground transportation systems of Madrid and Barcelona and reinterpret the results obtained for the Boston subway network.

PACS numbers:87.10.+e,87.18.Sn,.75.-k

I.INTRODUCTION

Modelling of complex systems as networks of coupled elements,such as chemical systems [1,2],neural networks [3],epidemiological [4,5]and social networks [6]or the Internet [7],has been a subject of intense study in the last decade.Networks can be classified into three broad groups:i)regular networks,ii)random networks,and iii)systems of complex topology,including small-world [8,9]and scale-free networks [6,10,11,12,13].In addition,networks can be unweighted or weighted,depending on whether links are equal or different.Weights can be:physical distances,times of propagation of informational packets,inverse velocity of chemical reactions,strength of interactions,etc.[14,15,16,17].

Commonly used regular networks are square or cubic lattices,both having squares as basic cycles [17,18,19].Aiming to describe clustering in social networks,i.e.to account for triangles of connected nodes as basic cy-cles [20],clustered rings were introduced,in which each site was linked to all its neighbors from the first up to the K -th [4,14,21,22].The study of random graphs [23,24,25,26]was motivated by the observation of real networks that often appeared to be random.Complex networks having a topology in between those of random and regular networks were later introduced.An out-standing example is the small-world model [8,27].Small worlds are constructed by randomly rewiring links of a regular graph [8](so that the number of links remains constant,while the structure is changed)or adding new links to it [28](changing both the structure and the num-ber of links)with a probability p .In this way,shortcuts between distant nodes are created.The rewiring/adding probability p indicates,on average,the degree of disorder of the network (it varies from p =0for a regular up to p =1for a random graph).Small-worlds are highly clus-tered showing triangles of nodes like regular networks,while having small distances between sites as in random systems [4,5,29,30,31].Recently,it was realized that

many social and biological networks had a degree (con-nectivity)distribution that was not Poisson-like,as in random and small-world networks,but rather a power law.Such systems were called scale-free [10,11,12,13]and are continuously growing open systems constructed by attaching new nodes preferentially to nodes of higher degree [11].Various modifications of this basic procedure have been proposed:nonlinear preferential attachment [32],initial attractiveness [33],and aging of sites and degree constraints [13]or node fitness [34].Moreover,introducing a finite memory of the nodes,large highly clustered systems can be obtained,representing a com-bination of scale-free networks and regular lattices [35].

FIG.1:Illustrates the link structure in clustered rings (upper)with connections to the second nearest-neighbors (K =2),and declustered rings (lower)with connections to the third nearest-neighbors (K =¯3).

Our aim is to compare the efficiency of informational transfer on the regular and complex networks described

above.In Section II we describe the networks and de-fine the quantities used to characterize them.In II A an extension of the class of small-world,referred to as declustered,is proposed.In II C we discuss the efficiency measures reported in the literature and propose the alter-natives required to handle non-clustered systems.Some of the new measures defined here are an extension of those reported in[36].Section III is devoted to discuss the properties of various unweighted networks.Introduc-ing physical distances,efficiencies of weighted networks are defined in Section IV and used to examine under-ground transportation systems.Our achievements are summarized in Section V.

II.METHODS

A.Types of Networks

The networks analyzed here are:clusters of the square lattice,clustered and declustered regular rings,as ex-amples of regular systems;clustered Watts-Strogatz and declustered small-worlds,and ordinary Albert-Barab´a si scale-free networks,representing complex systems.All networks are chosen so that the ratio between the num-ber of links N l and the number of sites N is kept constant N l/N=2(this gives an average connectivity=4). Concerning regular two-dimensional networks,calcula-tions were performed for l×l clusters of the square lat-tice,with periodic boundary conditions:node(i+l,j)= node(i,j)and node(i,j+l)=node(i,j).In the case of regular rings,we analyze the simplest clustered lat-tices with additional connections only to the next-nearest neighbors(K=2)[29,37],see Fig. 1.In addition,we study rings with a zero clustering coefficient constructed by adding links from each site to only its n-th neighbors. We call them declustered regular ring networks and desig-nate their coordination parameter as K=¯n,(shown also in Fig.1).Therefore,in our notation K=n means that each site is additionally linked to all of its ring neigh-bors from the second to the n-th,while K=¯n implies that only links to its n-th neighbors are added.For such declustered networks,basic loops are squares for any¯n, with edges on sites i,i+n,i+1and i+n+1.Our mo-tivation to analyze networks with a negligible clustering comes from the fact that such systems can be quite often found in nature or artifacts(for instance in transporta-tion underground networks).Such networks are usually very sparse with N l≈N[36].

We differentiate between ordinary clustered small-world and declustered small-world,depending on the ini-tial regular network.We will construct small-world net-works starting from clustered and declustered regular networks with K=2and K=¯3,respectively.More-over,as our focus is on the effects of network topology,we compare networks with the same links to size ratio.Thus, shortcuts are created by randomly rewiring links between each site and its more distant neighbors with probability 2p≤1,while connections to the nearest neighbors are kept unchanged.In this way,the ring structure is pre-served and the problem of disconnected graphs is avoided [28].The total number of rewired links would approach pN≤N/2for large N.Finally,we construct scale-free networks starting with a fully connected graph of m0=5 nodes and n0=10links.At each step a new node is added,with m=2edges to the old nodes,so that the ratio N l/N=2is kept constant.

FIG.2:Average path length versus network size(N)for the networks investigated in this work(all with average connec-tivity k =4).Regular rings:clustered K=2(circle), declustered K=¯3(diamond)and clusters of the square lat-tice(square).Complex:small-worlds with a probability of rewiring of p=10%-clustered K=2(triangle up),declus-tered K=¯3(triangle down);scale-free networks with m0=5 and m=2(star).Lines arefits of the numerical results in the range N=10−400:clustered ring L=0.13N+0.39,declus-tered ring L=0.083N+0.77,cluster of the square lattice L=0.59N0.47,clustered small world L=1.61ln N−2.24, declustered small world L=1.48ln N−2.08and scale-free network L=2.16lnln N−0.32.

B.Average path length and clustering coefficient The structural properties

of a graph are usually quan-tified by the average path length L and the clustering co-efficient C[8,13].The average path length is calculated as the network average of the shortest graph distances between two nodes(d ij)for all possible pairs:

L=

1calculated as a network average:

C=

1

N(N−1)

i=j

1

N

i

1

d0

jk/i

.(4)

Here d0

jk/i

is the shortest path length between sites j and

k passing only through other elements of that local sub-

graph of neighbors(Γ1),which is indicated by superscript

0.In such a way,the clustering coefficient is equal to the

local efficiency when only direct connections between j

and k are considered.

We propose a new definition of local efficiency,taking

into account that neighbors of each reference site i can

actually exchange information along paths including sites

which do not necessarily belong to the local subgraph of

i’s neighbors(m/∈Γ1).In order to measure the effi-

ciency of communication between the

nearest-neighborsof i when it is removed,we must only exclude site i from such a path(d jk/i):

E l1=1

k i[k i−1]

j=k∈Γ1

1

N/2

[42].Random graphs,in its turn,are known to obey a logarithmic scaling(L rand∼ln N)[13]. Such a behavior is also observed in the case of Watts-Strogatz small-world.As Fig.2clearly shows declus-tered small-world behaves qualitatively in the same way as Watts-Strogatz networks,in both cases the average path length is proportional to ln N.The average path length in declustered small-world is shorter than in the standard small-world,as edges of basic square cycles of the initial declustered network couple more distant sites. Finally,scale-free systems appear to be ultra-small[44], with a double logarithmic scaling L sf∝ln ln N(see Fig.

2).

In order to differentiate between random graphs and small-worlds,both having the same scaling of the aver-age path length and a Poisson distribution of degrees, the clustering coefficient is used.Switching from highly clustered regular graphs to small-worlds by introducing a few shortcuts does not significantly alter the cluster-ing coefficient[8,13].It remains quite large up to high values of the rewiring parameter p.For p≈1most tri-angle loops are broken,leading to random graphs with negligible values of C.The small-world behavior shows up at small p,when both the average path length and the clustering coefficient have large values[8,13].

B.Efficiencies

The aforementioned criteria identify declustered small-worlds as random networks.But,is this actually the case?.Applying the concept of global and the redefined local efficiency,we clearly identify the crucial differences between various networks.The clustered regular ring-lattice with K=2is locally very efficient E l1=0.722,due to its high clusterization,see Table I.Global efficiency is quite low E g(N=100)=0.154,which corresponds to a long average path length L(100)=12.88.From ourstandpoint,a declustered ring-lattice with K=¯3has the same characteristics.Local efficiency E l1=0.458is relatively good,although the clustering coefficient and the originally proposed local measure of efficiency[36] are both zero.Globally,we obtain slightly a larger value of E g(100)=0.188(or shorter L(100)=9.09),due to the presence of longer range links.Therefore,regular rings are in general locally efficient and globally inefficient. TABLE I:Average path length,clustering coefficient,and global and local efficiencies for homogeneous networks.

regular clustered

9.0900.1880.458

2D square

3.400.020.3280.2806

FIG.6:Global(empty symbols)and local(filled symbols) efficiencies normalized to the value of the initial regular ring versus the rewiring parameter p,for clustered(triangle up) and declustered(triangle down)

small-worlds.

FIG.7:Global(full line)and local(dashed line)efficiencies versus network size(N)for regular networks with a constant connectivity(k i=4):clustered K=2(circle),declustered K=¯3(diamond)and clusters of the square lattice(square). the contrary,it increases with size for the square lattice, small-world and scale-free networks.This normalization is necessary if we want to examine how a pure change of topology improves

transfer of information,without ad-dition of new links.Eq.(3)tells us how efficient is a network on a global scale relatively to the ideal case of a fully connected graph.Such a comparison can be mis-leading,because does not take into account that graphs are commonly sparse.Increasing the size,while keep-ing the N l/N ratio constant,global efficiency decreases for any kind of sparse networks.In contrast to a fully connected graph,each type of network would be seen FIG.8:Global(full line)and local(dashed line)efficiencies versus the network size(N)of complex networks with a con-stant average connectivity( k =4).Small-worlds with a rewiring parameter p=0.1:clustered K=2(triangle up), declustered K=¯3(triangle down).Scale-free networks with m0=5and m=2(star).

as inefficient,no matter what is the underlying topol-ogy.Therefore our opinion is that a particular network should be compared with a corresponding basic network with the same number of sites N and links N l.The basic network is a periodic system with the longest possible average path length or the smallest possible global effi-ciency for given(N,N l).It can be constructed in the following way:

a)Start from an initial standard ring of N sites and N links.

b)Add links between each site and its closest sur-rounding sites(the next-nearest neighbors,the next-next-nearest neighbors,and so on),up to all N l links are used.The result is a K=N l/N regular ring.

c)In case that the ratio N l/N is not an integer,the last set of n lIn such a way,complex systems such as small-worlds or scale-free networks,are identified to be globally efficient in comparison with the corresponding inefficient basic (regular)networks.

IV.WEIGHTED NETWORKS

A.Efficiency measures

In this section we focus on a particular type of weighted graphs,where physical distances are introduced.A real network is described by both the connectivity matrix and the matrix of physical distances[36].The shortest phys-ical path length˜d ij between two sites i and j is the path

7

FIG.9:Normalized global efficiency versus network size (N )with a constant average connectivity ( k =4).The global ef-ficiency of each particular network is normalized to the value for the regular clustered K =2network of the same size.Reg-ular:declustered K =¯3(diamond)and clusters of the square lattice (square).Complex:small-worlds with a rewiring pa-rameter p =0.1-clustered K =2(triangle up),declustered K =¯3(triangle down);scale-free networks with m 0=5and m =2(star).Fully connected graph:full line.

with the smallest sum of distances,no matter the num-ber of links the network has.Only in the case of links of equal lengths (λ),the physical and the graph short-est paths coincide,i.e.˜d

ij =λd ij .The efficiencies of a real network

could be

calculated using the formulas

given in Sec.II C,replacing d ij by ˜d

ij .In order to keep these quantities dimensionless,a suitable normalization should be performed.The originally proposed efficiency measures [36]are normalized to the values for the fully connected graph of the same size:

˜E g 1= i =j

1 i =j 1

N (N −1)

i =j

l ij

k i [k i −1]

j =k ∈Γ1

1

i

1

l jk

.(8)

Allowing for paths going through the rest of the network

we define ˜E l 1by simply replacing ˜d 0jk/i

by ˜d jk/i .Finally,we can again normalize each path separately,instead of normalizing the whole sum by the value for fully con-nected network (˜E l 2

).B.Analysis of subway transportation systems

Underground transportation networks are important

complex (but not random)systems with negligible clus-tering coefficient.Despite being small in size,they are ideal examples for demonstrating the strength of our method for the analysis of local efficiency.We have made a reinterpretation of the results obtained for the

Boston subway network[36]and performed an analysis of Barcelona(B)and Madrid(M)underground systems. The Boston underground transportation system,con-sisting of N=124stations and N l=124tunnels,was described both as an unweighted and a weighted graph in[36].In the unweighted case,it was found that it is neither globally nor locally efficient,having E g=0.1and E l0=0.006.This small value for E g gives a false impres-sion of low global efficiency.Although it is only10% of the largest value for fully connected graph,we should check how much the complex topology of the Boston sub-way system improves its efficiency,compared to a regu-lar ring with the same number of sites and links.We found out that such a ring has E g r=0.076,so that the Boston network is by32%more efficient!.Locally,the original measure relying heavily on the presence of tri-angles of neighbors has a very small value E l0=0.006 [36],as a consequence of the typically low clustering in underground transportation systems.Another compar-ison could be made against a hub consisting of a cen-tral node of degree k c=125and125peripheral nodes. Such a graph has the highest possible global efficiency of E g

hub≈0.5for the given number of125links,but lo-cal efficiency(E l0or E l1)is zero.Any attempt to locally increase efficiency of a hub by rearranging links,would eventually lead to a decrease of it on the global scale. Therefore,we consider that in real systems,such as the Boston subway network,an appropriate pay-offbetween global and local efficiencies is achieved.Taking physical distances into account,the global efficiency is increased to˜E g1=0.63,while locally remains quite low˜E l0=0.03 [36].Only after the network is extended to include the Boston bus system,it becomes efficient on both scales, with˜E g1=0.72and˜E l0=0.46[36].Thisfinal result was interpreted as a small-world behavior.On the basis of our previous discussion of weighted regular networks it is evident that such an interpretation is not correct.A sim-ple weighted regular ring with K=2is both globally and locally very efficient,due to the constant speed of trains and high clustering coefficient,respectively.Weighted efficiencies in real networks with constant speed of infor-mational transfer are not appropriate measures to give clear criteria for its classification.They can only give a hint on up to which extent a particular real network can replace the ideal fully connected weighted graph.Fur-thermore,it seems that only the comparison with the ideal graph is plausible.In most of the cases it is hard tofind out what should be the corresponding weighted ”regular”network,because the geographical positions of the nodes in a real complex network are given andfixed, and usually not equidistant.

In the following analysis of Barcelona and Madrid sub-ways we will include several technical details and make a step outside a pure theoretical research,offering pro-posals on how efficiencies of these networks could be im-proved.Concerning the Barcelona system[46],we do not take into account connections by a regular train, but only consider six metro lines.The number of sta-tions and tunnels are N(B)=104and N l(B)=115,re-spectively.When viewed as an unweighted graph,this

system has the average path length of L(B)=9.85, very small clustering coefficient C(B)=0.008(which is the most important contribution to E l0),global effi-ciency of E g(B)=0.153and a redefined local efficiency of E l1(B)=0.080(see Table II).Comparing with the corresponding basic(regular)network with L b=23.58 and E g

b

=0.095,we see that the average path length is more than two times shorter and the global efficiency improved by61%,due to the complex topology of the Barcelona system.Furthermore,the local efficiency is nine to ten times larger than if it would have been es-timated on the basis of the original equation[36]or the clustering coefficient.Similar results are obtained for the Madrid system[47].It consists of13metro lines(includ-ing the ring MetroSur),forming an unweighted network of N=188nodes and N l=223links.Due to its larger size,the average path length L(M)=12.36is longer than in the Barcelona system and the global efficiency is smaller E g(M)=0.127,see Table II.Nevertheless, the values of these two quantities are much better than for the corresponding basic network with L b=38.and

E g

b

=0.0.The complex topology improves the global efficiency by more than98%!The clustering coeffi-cient is larger than in Barcelona(C(M)=0.011),be-cause several triangles are formed(particularly around stations Gran Via and Goya).The higher redefined lo-cal efficiency of E l1(M)=0.115is a consequence of the larger clustering coefficient,as well as the presence of two rings(metro lines number6Circular and number12 MetroSur).Cutting offa reference site belonging to one of these two rings,its ring-neighbors can still exchange trains along the rest of the ring.

TABLE II:Performances of Barcelona and Madrid subway systems.

N

115223

L

0.0080.011

0.1530.127

E l0

0.0800.115

0.734-

˜E g

2

0.019-

˜E l

1

0.131-9

˜E l 1(B)=0.136or˜E l2(B)=0.131,that are about seven

times larger than when calculated using the original equation[36],see Table II.The efficiencies could be fur-ther improved by directly connecting a few stations that are separated by a long path,although physically close to each other.Adding only two links,one between stations Can Serra and Can Vidalet,and another between Vall-daura and Horta,two new rings are created.The number of links is increased by only1.7%,while the increase of the global efficiency isδ˜E g1(B)=3.3%and that of the local efficiencyδ˜E l1(B)=26.5%.Obviously,we can even assume that the stations within these pairs are connected or represent a single station,as we can simply walk from one to the other.

V.CONCLUDING REMARKS

In this work we focused on two objectives:

1.Introducing a new definition of local efficiency that does not depend exclusively on the clustering coefficient, and

2.Use that definition,to show that there is another class of complex networks with short average path length and Poisson distribution of degrees,that is not random although its clustering coefficient is negligible.

After accomplishing thefirst task,we proceeded with a systematic analysis of different types of regular and complex networks.Calculating global and modified local efficiencies,and taking into account the distribution of connectivity,we were able to make a clear classification of unweighted complex networks.The main conclusions that emerge from this study are:

i)The class of small-worlds can be generalized to in-clude systems with negligible clustering coefficient.We introduced a new type of networks that has a small num-ber of triangle cycles,but still clearly distinguishable from random systems due to its relatively good local transfer of information.

ii)Small-worlds(both clustered and declustered)as homogeneous systems,and scale-free networks,as het-erogeneous systems,are identified to be both globally and locally efficient.

Showing that declustered small-worlds behave quali-tatively in the same way as standard clustered small-worlds,we addressed today’s paradigm of the importance of the clustering coefficient.

Applying our method to real networks with physical distances and a constant speed of informational transfer, we found that weighted efficiencies can be used only to compare a particular real network with the ideal fully connected weighted graph.As highly clustered weighted regular rings can be both globally and locally efficient, it is hard to establish clear criteria for identification of small-world behavior.In particular our analysis of the underground transportation systems of Boston[36], Barcelona and Madrid reveals a proper balance between global and local performance.Despite the constraints on the number of tunnels,global efficiency is noticeably high due to the complex topology of these networks.On the other hand,allowing for the use of alternative paths after one station is cut off,the local efficiency turns to befive to ten times larger than the results reported in Ref.[36].

ACKNOWLEDGMENTS

Financial support by Fet Open Project COSIN IST-2001-33555and the Universities of Barcelona and Alicante is gratefully acknowledged.

[1]A.Scala,L.A.N.Amaral and M.Barth´e l´e my,Europhys.

Lett.55,594(2000).

[2]L.A.N.Amaral,A.Scala,M.Barth´e l´e my and H.E.

Stanley,Proc.Natl.Acad.Sci.U.S.A.97,11149(2000).

[3]Luis F.Lago-Fern´a ndez,Ram´o n Huerta,Fernando Cor-

bacho and Juan A.Sig¨u enza,Phys.Rev.Lett.84,2758 (2000).

[4]S.A.Pandit and R.E.Amritkar,Phys.Rev.E60,

1119(R)(1999).

[5]Marcelo Kuperman and Guillermo Abramson,Phys.Rev.

Lett86,2909(2001).

[6]F.Liljeros,C.R.Edling,L.A.N.Amaral,H.E.Stanley

and Y.Aberg,Nature(London)411,907(2001).

[7]M.Faloutsos,P.Faloutsos and C.Faloutsos,Comput.

Commun.Rev.29,251(1999).

[8]D.J.Watts and S.H.Strogatz,Nature(London)393,

440(1998).

[9]D.J.Watts,Small Worlds:The Dynamics of Networks

between Order and Randomness,Princeton University, Princeton,NJ(1999).

[10]R.Albert,H.Jeong,and A.-L.Barab´a si,Nature(Lon-

don)401,130(1999).

[11]A.-L.Barab´a si and R.Albert,Science286,509(1999).

[12]M.E.J.Newman,Phys.Rev.E,016132(2001).

[13]R.Albert and A.-L.Barab´a si,Rev.Mod.Phys.74,47

(2002).

[14]N.Mathias and V.Gopal,Phys.Rev.E63,021117

(2001).

[15]M.Kuperman and G.Abramson,Phys.Rev.E,

047103(2001).

[16]C.F.Moukarzel and M.Argollo de Menezes,Phys.Rev.

E65,056709(2002).

[17]I.Graham and C.C.Matthai,Phys.Rev.E68,036109

(2003).

[18]J.H.E.Cartwright,Phys.Rev.E62,1149(2000).

[19]C.Degli Esposti Boschi,E.Louis and G.Ortega,Phys.

Rev.E65,012901(2002).

[20]S.Wasserman and K.Faust,Social Network Analysis:

Methods and Applications,Cambridge University,Cam-bridge(1994).

[21]Z.Gao, B.Hu and G.Hu,Phys.Rev.E65,016209

(2001).10

[22]H.Hong,M.Y.Choi and B.J.Kim,Phys.Rev.E65,

026139(2002).

[23]P.Erd˝o s and A.R´e nyi,Publ.Math.(Debrecen)6,290

(1959).

[24]P.Erd˝o s and A.R´e nyi,Publ.Math.Inst.Hung.Acad.

Sci.5,17(1960).

[25]P.Erd˝o s and A.R´e nyi,Bull.Inst.Int.Stat.38,343

(1961).

[26]B.Bollob´a s,Random Graphs,Academic,London(1985).

[27]S.Milgram,Psychol.Today1,60(1967).

[28]M.E.J.Newman and D.J.Watts,Phys.Rev.E60,

7332(1999).

[29]D.H.Zanette,Phys.Rev.E65,041908(2002).

[30]F.Bagnoli and M.Bezzi,Phys.Rev.E,021914(2001).

[31]C.F.Moukarzel,Phys.Rev.E60,R6263(1999).

[32]P.L.Krapivsky,S.Redner and F.Leyvraz,Phys.Rev.

Lett.85,4629(2000).

[33]S.N.Dorogovtsev,J.F.F.Mendes and A.N.Samukhin,

Phys.Rev.Lett.85,4633(2000).

[34]G.Bianconi and A.-L.Barab´a si,Europhys.Lett.54,436

(2001).

[35]K.Klemm and V.M.Egu´iluz,Phys.Rev.E65,036123.

[36]V.Latora and M.Marchiori,Phys.Rev.Lett.87,198701

(2001).[37]S.Y.Huang,X.W.Zou,Z.J.Tan,Z.G.Shao and Z.Z.

Jin,Phys.Rev.E68,016107(2003).

[38]G.Caldarelli,R.Pastor-Satorras,and A.Vespignani,

cond-mat/0212026

[39]R.Guimer´a,X.Guardiola,A.Arenas,A.D´iaz-Guilera,

D.Streib,and L.A.N.Amaral,Quantifying the Creation

of Social Capital in a Digital Community,unpublished.

[40]P.Crucitti,V.Latora and M.Marchiori,Phys.Rev.E

69,045104(R)(2004).

[41]W.Li and X.Cai,Phys.Rev.E69,046106(2004).

[42]Explicit formulae for the average path length of clustered

rings with K=2and declustered rings with an arbitrary K as well as for clusters of the square lattice with periodic bounday consitions are reported in Ref.[43].

[43]I.Vragovic,E.Louis,C.Degli Esposti Boschi and G.Or-

tega,cond-mat/0410171.

[44]R.Cohen and S.Havlin,Phys.Rev.Lett.90,058701

(2003).

[45]R.Pastor-Satorras,A.V´a zquez and A.Vespignani,Phys.

Rev.Lett.87,256701(2001).

[46]www.tmb.net

[47]www.metromadrid.es