Eur. Phys. J. Special Topics 146, 145–154 (2007) c EDP Sciences, Springer-Verlag 2007
DOI: 10.1140/epjst/e2007-00175-x

THE EUROPEAN PHYSICAL JOURNAL SPECIAL TOPICS

Optimal communication schemes in a complex network: From trees to bottleneck networks R. Criadoa , J. Floresb , J. Pelloc , and M. Romanced Departamento de Matem´ atica Aplicada, Universidad Rey Juan Carlos, 28933 Mostoles, Madrid, Spain

Abstract. The robustness of a communication scheme in a complex network may depend on the location of distinguished nodes. We collect different approaches to the idea of vulnerability and we give methods that help us to decide the good spots for the leader nodes. More specifically, we present a constructive method that yields the best location in a communication scheme for a leader node in the case that the underlying network is tree-shaped and show how it can be used for more general networks. In order to do that we consider a local approach via the bottleneck tree associated to a given node, as well as a uniform a approach by means of the so-called bottleneck network for several communication topologies.

1 Introduction Complex networks may be used to describe and analyse a huge variety of systems composed by a large number of highly interconnected dynamical units. Particularly, complex networks are used to model several tasks that can only be carried out in a cooperative way. For example, when we work on parallel computation machines with few processors but fast inter-processor communication (see, for example [1]), we can use a computer network as a suitable tool for studying the distributed performance. An appropriate and realistic approach to the study of this type of systems must proceed by considering a suitable set of network properties (usually reduced to associated parameters which are to be measured over the network) which should comprise a sufficiently rich and complete picture of the problem under investigation. This approach should be done while defining a sufficiently tractable framework: the parameters to be evaluated must be simple and interpretable enough, as well as computable in practice for real systems. In this sense, very different possible approaches of this kind can be traced back in the literature, where characteristic path length, node and edge betweenness, clustering coefficient,vulnerability and efficiency are presented and studied as examples of this type of parameters [2–14]. Communication networks stand out among complex networks. Several examples fit into this category, such as the Internet, the World Wide Web, the subway, air, train and road traffic networks. These are communication networks without a distinguished (leader) node, although certain nodes may play a special role. For example, in the case of computer network traffic, we can find at least two types of nodes: hosts, which can generate and receive messages, and routers, which can only store and forward messages. Another important example related with communication schemes in complex networks arises in the realm of cryptography and information security, where key establishment is one of the a b c d

e-mail: e-mail: e-mail: e-mail:

[email protected] [email protected] [email protected] [email protected]

146

The European Physical Journal Special Topics

basis for security in electronic communications. In this example, cryptographic algorithms for encryption cannot perform their function unless secure keys have been established and the users know which parties share such keys. Several key transfer protocols consider and analyse security for multi-party key establishment (see [15]), showing that it is not always adequate to consider all nodes in the network equally important, for instance to distribute a message from a central server to a group of users or a key for private communication. So, it is needed to require secure communication between the leader (or the initiator) and all other members in order to initially establish the key. Thus the existence of a leader is a natural assumption in this setting. In [16] the authors considered the problem of locating a leader node on a complex network. The interest of this problem lies in the fact that in practical applications, under lack of resources, a point to point connection may not be possible and the role played by some nodes may be essential. The criterium for choosing such a leader will depend, in general, on our concern with the vulnerability, efficiency or other aspects of our network (see, for example [4,7,8,17,18]). The concept of robustness is related with the ability of a network (communication network in this case) to avoid malfunctioning when a fraction of its constituents is damaged due to random failures or intentional attacks, and the efficiency is an indicator of the traffic capacity of a network. The procedure designed in [16] offers a unifying approach from both robustness and efficiency points of view, although the tree pattern is essential to design a simple and effective method to locate the good spot for the leader. However there exist other situations which are better described by more general networks where only connectedness is assumed. For example, Mayer and Young (cf. [[15], Par. 6.6.2) have dealt with the following key transport protocol: a leader node distributes a key and it is only after all the recipients accept the key (by sending a confirmation reply) that the leader confirms back the validity of that key. The protocol guarantees that, if all parties accept the key, they have all received the same value from the leader and, furthermore, that an adversary cannot obtain the key. In this context the underlying network needs not be a tree and yet finding the right spot to place the leader (which can be assumed invulnerable and perfectly trustworthy) is essential for designing a robust network. See also [19] for an extension of the Burmester-Desmedt Tree-Based Key Transport to arbitrary networks. In this paper we extend the results in [16] to this new non-tree scenario, by means of the bottleneck graph associated to a given node in the network (see below for the precise definition). This bottleneck network will allow us to compute a vulnerability measure for each node if it were to be chosen as the leader and so the best possible leader will be that with the lower vulnerability. The paper is divided in three sections: after this introduction (section 1), section 2 is devoted to review the concepts of robustness and vulnerability and some related results, distinguishing between networks with and without a leader node. In section 3, we consider a general complex network and we construct a tree for each one of its nodes (the bottleneck tree) which is used to measure how a good node is as a leader (a local approach). In addition, for each general complex network, we compute a new network (the bottleneck graph) which allows us to choose the optimal leader in the network.

2 Vulnerability and robustness in complex networks When a complex network is modelling a communication scheme it should be obvious that the robustness of the network is an aspect to take into account. In other words we would like to have at our disposal some tools which help us to choose between two possible networks the one that will prove more invulnerable to unexpected failures or malicious attacks. There are two essentially different situations to be considered. One of them is when all nodes in our network are equally important (this is the traditionally assumed setting in the literature). The other one arises when a distinguished node is bound to play an overriding role (such as in the example

New Trends, Dynamics and Scales in Pattern Formation

147

above regarding key transference protocols in cryptography). We pass to consider these two situations separately. 2.1 Networks without distinguished nodes Robustness and vulnerability are related with the resistance of a network to random damage and malicious attack respectively [4–6,9,20–22]. There are several different approaches in the literature to measure the vulnerability of a complex network without distinguished nodes, but, in general, they can be divided in two types. On the one hand we find the static vulnerability which analyses the response of the structural properties of the networks when some of its nodes or links are removed, while, on the other hand, the dynamical vulnerability is considered to measure the redistribution of flow in the network when a failure or attack occurs. Despite the fact that both types of robustness share common ideas, the tools and techniques involved with each type of vulnerability are quite different, since the static vulnerability uses topological methods and tools from percolation theory, while the dynamical properties rely on numerical simulations. In this paper we will consider static vulnerability related to structural properties of the complex network that allows us to spot its critical components in order to improve the security. Hence, we will study structural and topological properties of a network in order to predict how it will behave when a damage occurs. When we talk about damage, there are two different kinds of damages which have been considered: failures and intentional attacks. A failure is a breakdown that may occur at random in any node or link while an intentional attack is the disfunction of one component of the network caused by a malicious agent in order to produce the maximum damage in the network. Note that both types of network damages are essentially different since it is easy to find a network which is robust if we consider random failures but quite sensitive to intentional attacks. A first (and classic) example of static robustness refers to the ability of a network to maintain its connectivity when some of its nodes or links are damaged and it measures the size of the giant component when such attack occurs (see [17]). The main tool used to analyse this problem is the percolation theory (see, for example, [17] or the chapter of Cohen et al. in [23]), since the study of random failures in a complex network can be stated as a standard percolation problem. Despite the fact that the tools from percolation theory allow to get deep results concerning the static vulnerability of the network, these techniques are mainly related to random phenomena (such as random failures) and therefore they give almost no information if we are dealing with intentional attacks (which are essentially deterministic). In order to avoid this problem, different alternatives have been proposed in the literature, for example, in [7,11,24,25]. Let us briefly show some of these new approaches. In [13,25] the vulnerability of the network is related to the stability of other parameter that measures the performance of the network. If G = (X, E) is a complex network with n nodes and |E| links, it is consider that the performance of G is a single function Φ(G) > 0 that measures the behaviour of G. Some examples of the performance of a network G are the characteristic path length of the network L(G), the mean flow-rate information over G or the efficiency E(G), defined (see [12,13]) as
1 1 E(G) = , (1) n(n − 1) dij i
=j∈X

where dij stands for the shortest distance between the nodes i and j. Once a performance function is considered, we take a damage d, such as the removal of one precise (or several) nodes or links, and denote Gd to the network after the damage occurs. Then the vulnerability G under the damage d is V (G, d) =

∆Φ− (G) Φ(G) − Φ(Gd ) = . Φ(G) Φ(G)

(2)

Note that if the performance Φ(G) decreases when some damage occurs, then V (G, d) ∈ [0, 1]. If we consider a class of damages D, (for example the class of removal of one single node), then

148

The European Physical Journal Special Topics

the vulnerability of the network G under the class of damages D is Vmax (G, D) = max {V (G, d); d ∈ D} ,

(3)

which describes the worst performance of the network after a damage of the class D occurs, i.e. an intentional attack of the class D that a malicious agent should make. By using this approach we can also analyse the robustness of a complex network G under random failures of class D, if we consider 1
1
Φ(G) − Φ(Gd ) Vrand (G, D) = , (4) V (G, d) = |D| |D| Φ(G) d∈D

d∈D

where |D| is the number of damages of the class D. Hence, these techniques allow to get an analytical measure of the resilience of a complex network under random or intentional attacks. Despite the evident advantages of an unified approach to the robustness of a complex network (either to random or intentional attacks), this method has some drawbacks. First, it cannot distinguish many networks that should have different vulnerabilities. For example, if we consider as performance function the efficiency E(·) and the failure of a single node as the damage, it is easy to check that the cycle C4 and the complete graph K4 have the same vulnerability under random or intentional attacks (see [7]), but the intuition suggests that K4 should be more robust than C4 . Another inconvenience of this approach is that it makes the robustness performance-dependent. The definition of robustness relies not only on the stability of the performance function selected but also on the type of damage considered, thus it might be the case that a network is robust for some setting and very vulnerable if we change the performance function or the class of damages. An alternative approach to this topic is introduced in [7], where an axiomatic description of the robustness is presented and some candidates for vulnerability functions are proposed based on the network regularity. Roughly speaking, a vulnerability function is a normalised function v(G) intrinsic to the topology of G that increases if we remove some components of the network. Note that Vrand (·) and Vmax (·) are vulnerability functions when we consider the efficiency, the characteristic path length or the mean flow-rate information as performance functions, but this new approach also allows to introduce other measures of vulnerability that are not related to the stability of a performance function. In [7] it is considered that the vulnerability is related to the node regularity and the number of alternative links that can balance a random or intentional attack. The basic idea is that the more similar the nodes are, the more robust the network is, assumed that we had fixed the number of links and nodes in the network. Hence, in addition to the number of nodes and links, also the dispersion of the degree distribution should play a central role in the vulnerability of the network, and it was introduced the vulnerability function V1 (G) of a network G = (X, E) with n nodes and |E| links as   M −m 2 V1 (G) = exp + n − |E| − 2 + , (5) n n where M = max{gr(i); i ∈ X}, m = min{gr(i); i ∈ X} and gr(i) is the degree of node i ∈ X. This definition can be computed easily and gives a good estimation of the robustness of a complex network but the fact that only the nodes of extremal degrees are considered makes it not as sharp as desirable from a statistical point of view. To avoid this problem, a sharper estimator of the regularity of the degree distribution must be considered, leading to the vulnerability function V2 (G) given by   σ 2 V2 (G) = exp + n − |E| − 2 + , (6) n n where n is the number of nodes of G, |E| stands for the number of links and σ denotes the standard deviation of the degree distribution, i.e.   2 1/2 1
2|E| . (7) σ= gr(i) − n n i∈X

New Trends, Dynamics and Scales in Pattern Formation

149

It is clear that the definitions of V1 (·) and V2 (·) do not depend on the stability of some performance parameter of the network, but we can prove that the vulnerability functions associated to some performance functions and V1 (·) (or V2 (·)) are related. Let us consider as the performance parameter the efficiency E(·) introduced before and as class of damages D the failures of one single link. By using some results about the stability of E(·) (see [8]), it is easy to check that if G = (X, E) is a complex network with n nodes and N links, then 2 n(n − 1) − 2(|E| − 1) ≤ Vmax (G, D) ≤ , 2|E| + n(n − 1) 4|E|

(8)

while we can get some easy estimates for V1 (G) simply by considering the extreme deviations of the degree distribution obtaining that n − |E| +

2 2 n−2 ≤ log V1 (G) ≤ + n − |E| + . n n n

(9)

Combining these estimates for Vmax (G, D) and log V1 (G), we get that Vmax (G, D) ≤

1 n(n − 1) − 2 − , 4(1 − log V1 (G)) 2

(10)

which shows a lower-bound estimate for Vmax (G, D) in terms of n and V1 (G). Note that similar upper estimates can be shown and the same phenomenon occurs if we replace Vmax (G, D) by Vrand (G, D) or V1 (G) by V2 (G). 2.2 Networks with a leader node In [16] tree shaped networks with a distinguished node are considered from the point of view of vulnerability. The idea is to design a procedure that gives us the best spot in the tree graph to be occupied by the leader in order to reduce most the vulnerability of the network. The main point is the following remark: Let i be the leader on a given tree G = (X, E). Then the average number of nodes disconnected from i due to the failure of a random node (other than i) is 1
dij , n−1

(11)

j∈X

where dij stands for the shortest distance between the nodes i and j (see [16]). This way, the expression
dij , (12) j
=i

becomes, up to a constant, a measure of the vulnerability of the network against random attacks. Analogously, we can give a measure of the efficiency of a network with the (simple) formula max{ dij |j = i } that computes the maximum distance from the leader to any other node. This maximum distance gives estimates of how long the information transference process may take. As in [16] we can combine these two definitions into some kind of p-distance, to unify the approach. Thus, given a tree G and a given node i of G we define , for every 1 ≤ p < ∞,  Dp (i) = 




1/p dpij 

.

(13)

j∈X

For p = ∞, we define D∞ (i) = max dij . j∈X

Thus D1 (i) becomes the vulnerability of the network when the node i is chosen as a leader, while D∞ (i) is an inverse measure of the efficiency with the same leader. The measures Dp (i) for 1 < p < ∞ represent values in between, approaching D1 (i) when p goes to 1 (robustness is

150

The European Physical Journal Special Topics

given more weight than efficiency) and approaching D∞ (i) when p goes to infinity (efficiency is given more wight than robustness). However, as it can be seen in [16] this is not always the case for every possible network. The nice feature of this measures is that the node where the minimum is attained can be easily found, just by comparing adjacent nodes. The precise formulation depends upon the following remark: Let G be a tree and let a, b and c be distinct nodes in G such that b is linked to both a and c. Then Dp (b) < max{Dp (a), Dp (c)}, (14) for every 1 ≤ p ≤ ∞. An iteration process actually shows that for a given tree G and m-distinct consecutive nodes x1 , x2 , . . . , xm in G, we have Dp (xi ) < max{D(x1 ), D(xm )},

(15)

for every 2 ≤ i ≤ m − 1. Thus our “follow the slope”-algorithm begins by randomly choosing a node in the network. Then at most one adjacent node can have a lower Dp , by the remark above, so we visit every adjacent node until we find one with a lower Dp . Next, we move on to that node and repeat the process with its neighbours. If no such node exists, the iteration process above tells us that we have found a minimum. This method shows that for a given tree with an invulnerable node (leader) the D1 -measures on the different nodes help us to choose an optimal location for the leader. Another related problem is the following: assume that we have two possible tree networks for a given number of nodes and links, each with its distinguished node. Which one is preferable from the point of view of robustness? The following example where G and G are two tree-shaped graphs illustrates the situation:

G

G'

Fig. 1. An example of vulnerability of two trees with a leader node.

Since G and G have the same number of nodes and their corresponding incidence degrees coincide, there is no hope that any vulnerability function whose definition is based on those two parameters might be of use when it comes to preferring G over G , or conversely. In contrast the D1 -measures prove useful to our choice. In fact G should be preferred over G as the next table shows:
D1G (1) = 10, D1G (1) = 12,
D1G (2) = 9, D1G (2) = 11,
D1G (3) = 17, D1G (3) = 11,
G D1G (4) = 10, D1 (4) = 16,
D1G (5) = 14, D1G (5) = 16,
D1G (6) = 15, D1G (6) = 16,
D1G (7) = 160, D1G (7) = 15.

New Trends, Dynamics and Scales in Pattern Formation

151

Note that the algorithm above yields node 1 as the best possible leader for G and node 2 as the best one for G . Hence selecting G and node 2 in G as the leader would be the wisest option since node 2 has the lowest D1 -vulnerability not only among the nodes of G but among all nodes.

3 Bottleneck graphs We will now turn our attention to the more general case where a network with a leader is not necessarily tree-shaped; the network can be either directed or not, as our results are valid in both cases. Our goal, again, is to pick the “right spot” for a leader node that will act as the source for some kind of communication to every other node in the network, and we would like to choose the one that minimises the expected number of disconnected nodes (from the chose node) when a random node failure occurs. First of all, it should be said that our previous work, in which the problem dealt with in the case of a tree-shaped network, is not directly applicable to the general case. The reason is that, in a tree, it is immediate to determine which nodes become disconnected after a node failure, since there is only one simple path between any two nodes. This does not hold if the network has an arbitrary shape, so additional considerations are in order. To this end, we will say that a node y is a bottleneck from x to z if every path from x to z necessarily goes through y. We will denote by Π(x, z) the set of all bottlenecks from x to z. This concept is related to the expected number of disconnected nodes under a random breakdown of a node other than the leader. (We will always assume that the leader itself is not subject to failure, since we only care about communications originating from it; if it failed, then no communication would take place, so the possibility of its failing does not help at all to distinguish which node makes the best root.) If we denote by D(r) the expected number of nodes that become disconnected from r as a result of a failure at some other node, we have that  1


D(r) = |Π(r, z)|−1 (16) n−1 z∈X

where |Π(r, z)| is the number of bottlenecks from r to z. Indeed, given a failure in a node y = r, the nodes that become disconnected as a result of this failure are precisely those for which y is a bottleneck from r to them. If we take |A| to be the cardinality of A, we have D(r) =


1 |{ z ∈ X | y ∈ Π(r, z) }| n−1 r
=y∈X

=


1 n−1

r
=y∈X

=


z∈X y∈Π(r,z)

1=

(17)



1 n−1

1


1
1 (|Π(r, z)| − 1) = (|Π(r, z)| − 1). n−1 n−1 r
=z∈X

(18)

r
=z∈X r
=y∈Π(r,z)

(19)

z∈X

It is easy to check that if G = (X, E) is a tree then |Π(r, z)| − 1 is the distance between the nodes r and z, since there is a unique simple path from r to z and every node in that path is a bottleneck. Therefore the last formula extends the results obtained in [16], but it is straightforward to prove that this phenomenon does not necessarily occur when G = (X, E) is not a tree. However, we will see that, given any node in G, it is possible to construct an auxiliary tree in G (the bottleneck tree) such that measuring distances in that tree gives us the same information about disconnected nodes in the original network. First of all, it can be seen that the nodes in any bottleneck set Π(x, y) are linearly ordered; in fact, every simple path from x to y runs through the nodes in Π(x, y) in the same order. To see this, take v, w ∈ Π(x, y) and consider a simple path from x to y. By definition, this path must run through both v and w, and one of them must come before the other. Without loss of

152

The European Physical Journal Special Topics

generality, we will assume that v comes first. Now, if there existed another simple path from x to y in which w came before v, we could construct a new path by joining the first part of our former path (up to v) with the last part of our second path (starting at v), and this new path would not go through w, contradicting that w ∈ Π(x, y). Thanks to this ordering, it is possible to define what we will call the direct bottleneck of a node for a given root. If we have two different nodes r and x ∈ X, the last node in Π(r, x), excluding x itself, will be called the direct bottleneck of x from r, and will be denoted by πr (x). Note that given distinct r, x ∈ X, we always have r, x ∈ Π(r, x), so this definition always makes sense. The link that will help us establish a connection between the case of a general network and that of a tree-shaped one is the so called bottleneck tree. Given a node r ∈ X, the bottleneck tree of G rooted at r will be another network BTr with the same set of nodes and exactly those edges of the form (πr (x), x), where x = r. For example if we consider the graph N9 , figure 2 shows the bottleneck tree rooted at 1.

Graph N9

Bottleneck tree for N9 rooted at 1

Fig. 2. A bottleneck tree for the graph N9 .

It should be said that bottleneck trees deserve their name in the sense that they are always trees. This is because, given r = x and Π(r, x) = {r = v0 , v1 , . . . , vn = x}, we always have Π(r, vi ) = {r = v0 , v1 , . . . , vi−1 , vi }, so πr (vi ) = vi−1 . This ensures that (r, v1 ), (v1 , v2 ), . . . , (vn−1 , x) is a path from r to x in the bottleneck tree BTr , so every node can be reached from r. Additionally, it can be checked that BTr has no cycles as it has exactly n−1 links. The main reason why this bottleneck tree is useful in helping locate the right place for the leader is that measuring the distance from r to any other node is exactly the same as counting how many bottlenecks there are in Π(r, x). In other words, we have that D(r) =

1
BTr drx , n−1

(20)

x∈X

r where dBT rx is the distance from r to x in the bottleneck tree for G rooted at r. We can see the formal similarities between this formula and (11), since D(r) extends the notion of vulnerability from trees to general networks with a leader node. Despite this fact, if we consider a non treeshaped network, different leaders yield different bottleneck trees. For example, if we consider again the graph N9 we can obtain essentially tree different bottleneck trees depending on which root we choose (see figure 3). We now have a formula that allows us to compute the expected number of disconnections from a given leader, so, by comparing these expectations, we can easily decide which is the best leader. Also, the previous formula links the case of a general complex network with the easier case of a tree. However, this has been done at a price: while in the scheme for trees presented in section 2.2 there was a very simple algorithm for finding that best node, now not only is there

New Trends, Dynamics and Scales in Pattern Formation

Rooted at 1 or 3 D(1) = 19 D(3) = 12

Rooted at 5, 7, 8 or 9 D(5) = 10 D(7) = D(8) = 17 D(9) = 22

153

Rooted at 6 (Similarly for 2 and 4) D(2) = D(4) = D(6) = 13

Fig. 3. All the bottleneck trees for the graph N9 .

not such an algorithm but we must, in principle, build a different tree for each of the nodes to compute its goodness as leader. In practice, however, we will now see that the general situation does admit some simplifications and, while it is true that the case of a tree remains easier, the general case does not fall far behind. We will see that, in fact, there is a generic construction that allows to compute the values D(r) for every node r without actually using each of the bottleneck trees. We will define the bottleneck graph BG for a given network as a new graph with the same set of nodes and the original set of edges plus edges linking every pair of nodes (x, y) between which there are no bottlenecks (that is, Π(x, y) = {x, y}). This graph has the property that measuring distances between nodes r and x gives the same result as in BTr , so D(r) =


1 dBG rx , n−1

(21)

r
=x∈X

where dBG rx is the distance from r to x in the common bottleneck graph BG (and not only in the bottleneck tree BTr rooted at r). The name of bottleneck graph comes from the fact that this network is actually the union of the bottleneck trees for every possible leader, and that these trees can be recovered from it. When the network is undirected there is a very simple way to construct the bottleneck graph for a network, which is adding a link between every pair of nodes that share a cycle. It can be readily seen that this procedure leads to the bottleneck graph from the fact that, if two different nodes share a cycle, then no other bottleneck can exist between them, as there are two disjoint paths to get from one to the other. Back to the graph N9 its bottleneck graph is shown in figure 4, which can be constructed as the union of all of its nine bottleneck trees (one per possible root) that appeared in figure 3. Note that despite the fact that the bottleneck trees rooted at 2 and 4 are isomorphic to that rooted at 6, when we add them up each of them brings along its own different links.

Fig. 4. The bottleneck graph for the graph N9 .

154

The European Physical Journal Special Topics

The bottleneck graph BG contains all the information that is required to select the best leader for the network, simply by picking the one with the lowest D. For example, once we have obtained the bottleneck graph of N9 , we can compute the values of D for each node, obtaining D(1) = 19, D(4) = 13, D(7) = 17,

D(2) = 13, D(5) = 10, D(8) = 17,

D(3) = 12, D(6) = 13, D(9) = 22,

and therefore the best leader node in N9 is node 5.

References 1. K. Burrage, Parallel and Sequential Methods for Ordinary Differential Equations (Numerical Mathematics and Scientific Computation) (Oxford University Press, 1997) 2. R. Albert, A.L. Barab´ asi, Rev. Mod. Phys. 74, 47 (2002) 3. Y. Bar-Yam, Dynamics of Complex Systems (Addison-Wesley, 1997) 4. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang, Phys. Rep. 424, 175 (2006) 5. R. Cohen, K. Erez, D. Ben-Avraham, S. Havril, Phys. Rev. Lett. 85, 4626 (2000) 6. R. Cohen, K. Erez, D. Ben-Avraham, S. Havril, Phys. Rev. Lett. 86, 3682 (2001) 7. R. Criado, J. Flores, B. Hern´ andez-Bermejo, J. Pello, M. Romance, J. Math. Mod. Algor. 4, 307 (2005) 8. R. Criado, A.G. del Amo, B. Hern´ andez-Bermejo, M. Romance, J. Comput. App. Math. 192, 59 (2006) 9. P. Crucitti, V. Latora, M. Marchiori, A. Rapisarda, Physica A 320, 622 (2003) 10. A. H. Dekker, B.D. Colbert, Proceedings of ACSC04, the 27th Australasian Computer Science (Cairns, Australia, 2004), p. 685 11. P. Holme, J.-H. Kim, Phys. Rev. E 65, 066109 (2002) 12. V. Latora, M. Marchiori, Phys. Rev. Lett. 87, 198701 (2001) 13. V. Latora, M. Marchiori, Chaos, Solit. Fract. 20, 69 (2004) 14. M.E.J. Newman, M. Girvan, Phys. Rev. E. 69 026113 (2004) 15. C. Boyd, A. Mathuria, Protocols for Authentication and Key Establishment (Information Security and Cryptography) (Springer, 2003) 16. R. Criado, J. Flores, M.I. Gonzalez-Vasco, J. Pello, J. Comput. Appl. Math. (to appear) 17. M.E.J. Newman, SIAM Rev. 45, 167 (2003) 18. S.H. Strogatz, Nature 410, 268 (2001) 19. J.M. Bohli, M.I. Gonz´ alez-Vasco, R. Steinwandt (preprint) 20. R. Albert, H. Jeong, A.L. Barab´ asi, Nature 406, 378 (2000) 21. B. Bollobas, O. Riordan, Internet Math. 1, 1 (2003) 22. D.S. Callaway, M.E.J. Newman, S.H. Strogatz, D.J. Watts, Phys. Rev. Lett. 85, 5468 (2000) 23. S. Bornholdt, H.G. Schuster, From the Genome to the Internet (Wiley-VCH, Germany, 2003) 24. J.-H. Kim, K.-I. Goh, B. Kahng, D. Kim, Phys. Rev. Lett. 91, 058701 (2003) 25. V. Latora, M. Marchiori, Phys. Rev. E 71, 015103 (2005)