Class of correlated random networks with hidden variables

Class of correlated random networks with hidden variables Maria ´n Bogun ˜ a ´1and Romualdo Pastor-Satorras2 1Departament de Fı ´sica Fonamental, Universitat de Barcelona, Avinguda Diagonal 647, 08028 Barcelona, Spain 2Departament de Fı ´sica i Enginyeria Nuclear, Universitat Polite `cnica de Catalunya, Campus Nord, Mo ´dul B4, 08034 Barcelona, Spain 共Received 3 June 2003; published 15 September 2003兲 We study a class of models of correlated random networks in which vertices are characterized by hidden variables controlling the establishment of edges between pairs of vertices. We find analytical expressions for the main topological properties of these models as a function of the distribution of hidden variables and the probability of connecting vertices. The expressions obtained are checked by means of numerical simulations in a particular example. The general model is extended to describe a practical algorithm to generate random networks with an a priori specified correlation structure. We also present an extension of the class, to map nonequilibrium growing networks to networks with hidden variables that represent the time at which each vertex was introduced in the system. DOI: 10.1103/PhysRevE.68.036112 PACS number共s兲: 89.75.⫺k, 87.23.Ge, 05.70.Ln I. INTRODUCTION A large effort has been recently devoted to the study of a very large ensemble of interacting systems that can be described in terms of complex networks 共or graphs兲, in which the vertices represent typical units and the edges represent the interactions between pairs of units 关1–3兴. Stimulated by this finding, a theory of complex networks, deeply rooted in the classical graph theory 关4兴, has hence been developed, finding fruitful applications in fields as diverse as the Internet 关5–8兴, the WorldWideWeb 关9兴, social communities 关10兴, food webs 关11兴, or biological interacting networks 关12–15兴. The study of complex networks, boosted by the new availability of powerful computers capable of dealing with very large databases, was initially focused in the study of global properties such as the average shortest path length, the average clustering coefficient, or the degree distribution 关1–3兴. This work led to the discovery that most natural complex networks usually exhibit two typical properties: 共i兲the small-world property 关16兴, which is defined by an average path length—average distance between any pair of vertices—increasing very slowly 共usually logarithmically兲 with the network size Nand 共ii兲ascale-free degree distribution. If we define the degree distribution P(k) as the probability that a vertex is connected to kother vertices, then scale-free networks are characterized by a power-law behavior P(k)⬃k⫺ ␥ , where ␥ is a characteristic degree exponent. These properties imply a large connectivity heterogeneity and a short average distance between vertices, which have considerable impact on the behavior of physical processes taking place on top of the network, such as the resilience to random damage 关17–19兴or the spreading of infective agents 关20–23兴. It was soon realized, however, that these properties do not provide a sufficient characterization of natural networks. In particular, these systems seem to exhibit also ubiquitous degree correlations, which translate in the fact that the degrees of the vertices at the end points of any given edge are not independent 关7,8,24,25兴. This observation has led to a classification of networks according to the nature of their degree correlations 关24兴: In the presence of positive correlations 共vertices with large degree tend to connect more preferably with vertices with large degree兲, the network is said to show assortative mixing. On the other hand, negative correlations 共highly connected vertices are preferably connected to vertices with low degree兲imply the presence of dissortative mixing. At the same time, it has been pointed out that the presence of correlations might have important consequences in dynamical processes taking place in the topology defined by the network 关26–29兴. Motivated by these observations, several works have been recently devoted to set up a general framework to study the origin of correlations in random networks 关30,31兴. At this respect, it is particularly interesting the models introduced by Caldarelli et al. 关32兴and So ¨derberg 关33兴. These models consider graphs in which each vertex has assigned a tag 共type or fitness兲, randomly drawn from a fixed probability distribution. Edges are assigned to pairs of vertices with a given connection probability, depending on the values of the tags assigned at the edge end points. This construction generates random networks that exhibit peculiar correlation and percolation properties 关32,33兴. In this paper we present a generalization of the models described in Refs. 关32,33兴, which can be encompassed in a general class of models with hidden variables tagging the vertices, and completely determining the topological structure of the ensuing network. We develop a detailed analysis of the correlations present in this class of network models, providing explicit analytical expressions for both two and three vertices degree correlations. We distinguish between sparse networks 共with finite average degree 具 k 典 ) and nonsparse networks 共with diverging 具 k 典 for a number of vertices N→⬁). Even though both cases are enclosed in this class of networks, analytical expressions are simpler in the former case. As an example of our formalism, we consider the intrinsic fitness model introduced in Ref. 关32兴, which belongs to the subset of nonsparse networks, and which has attracted a great deal of attention as an alternative to generate scalefree networks without growth nor preferential attachment 关34兴. The solution of this model in the continuous degree approximation is compared with extensive numerical simulations, yielding a remarkable agreement for all the topological properties considered. As a particular case of the general PHYSICAL REVIEW E 68, 036112 共2003兲 1063-651X/2003/68共3兲/036112共13兲/$20.00 ©2003 The American Physical Society68 036112-1 class of models with hidden variables, we propose a practical algorithm to generate correlated random networks with a given correlation structure. The algorithm levers in the assignation of hidden variables with the structure of the degrees of a real network. Following this approach, it is possible to easily generate networks matching any desired correlation pattern, as we show by means of analytical calculations and numerical simulations. Finally, we present the extension of this class of models to nonequilibrium growing networks. By mapping the hidden variables to the time in which vertices are introduced in the network 关33兴, and by means of an appropriately chosen connection probability, we define an algorithm that yields networks exhibiting all the properties 共in particular aging兲exhibited by traditional scale-free growing models. The paper is organized as follows. In Sec. II we review some general results concerning the measure of correlations in complex networks, which will be useful through the rest of the paper. In Sec. III we introduce the general analytical formulation of the class of correlated networks with hidden variables. Section IV is devoted to the analytical and numerical study of the intrinsic fitness model introduced in Ref. 关32兴. In Sec. V we present an algorithm to generate correlated random networks with a given a priori correlation structure. Sec. VI deals with the mapping into this class of models of nonequilibrium growing networks. Finally, in Sec. VII we draw our conclusions and perspectives. II. MEASURING CORRELATIONS IN COMPLEX NETWORKS A. Two vertices correlations Let us consider the class of unstructured undirected networks, in which all vertices with the same degree can be considered to be statistically equivalent. In this sense, the following results will not apply to structured networks, in which a distance ordering can be defined; for instance, when the small-world property is absent 关27,35兴. A network is said to be uncorrelated when the probability that an edge departing from a vertex of degree karrives at a vertex of degree k⬘ is independent of the degree of the initial vertex k. Most natural networks are not uncorrelated, in the sense that the degrees at the end points of any given edge are not independent. This kind of two vertices degree correlation can be measured in undirected networks by means of the conditional probability P(k⬘ 兩 k) that a vertex of degree kis connected to a vertex of degree k⬘. From the point of view of correlations, it is useful to consider the restricted subset of undirected Markovian random networks 关26兴, which are completely defined by the degree distribution P(k) and the conditional probability P(k⬘ 兩 k). The Markovian nature of this class of networks implies that all higher order correlations can be expressed as a function of P(k⬘ 兩 k). The functions P(k) and P(k⬘ 兩 k) are assumed to be normalized, i.e., 兺 kP共k兲⫽兺 k⬘ P共k⬘ 兩 k兲⫽1, 共1兲 and they are constrained by a degree detailed balance condition 关26兴stating the physical conservation of edges among vertices: The total number of edges pointing from vertices with degree kto vertices with degree k⬘must be equal to the number of edges that point from vertices k⬘to vertices k. There is an intuitive way to derive the degree detailed balance condition 关36兴. Let us denote by Nkthe number of vertices of degree k. Since 兺kNk⫽N, where Nis the size of the network, we can define the degree distribution as P(k) ⫽Nk/N关37兴. To completely define the network, we need to specify also how the different degree classes are connected. To this end, let us define the symmetric matrix Ekk⬘that gives the number of edges between vertices of degree kand k⬘, for k⫽k⬘, and two times the number of self-connections for k⫽k⬘共the number of connections between vertices in the same degree class兲. This matrix fulfills the identities 兺 k⬘ Ekk⬘⫽kNk,共2兲 兺 k,k⬘ Ekk⬘⫽ 具 k 典 N⫽2E,共3兲 where Eis the total number of edges in the network. This last identity allows us to define the joint distribution P共k,k⬘兲⫽Ekk⬘ 具 k 典 N,共4兲 where the symmetric function (2⫺ ␦ k,k⬘)P(k,k⬘) is the probability that a randomly chosen edge connects two vertices of degrees kand k⬘. The conditional probability P(k⬘ 兩 k) defined as the probability that an edge from a kvertex points to ak⬘vertex can be easily written as P共k⬘ 兩 k兲⫽Ek⬘k kNk ⫽ 具 k 典 P共k,k⬘兲 kP共k兲.共5兲 From the symmetry of P(k,k⬘) it follows immediately the degree detailed balance condition kP共k⬘ 兩 k兲P共k兲⫽k⬘P共k 兩 k⬘兲P共k⬘兲⫽ 具 k 典 P共k,k⬘兲.共6兲 The joint distribution P(k,k⬘) conveys all the information needed to construct a Markovian random network. In fact, it is easy to see that P共k兲⫽ 具 k 典 k兺 k⬘ P共k,k⬘兲.共7兲 This relation, together with Eq. 共5兲, completely defines the network properties, i.e., P(k) and P(k⬘ 兩 k), as a function of the joint distribution P(k,k⬘). Notice that Eqs. 共5兲and 共7兲 define the degree distribution and the conditional probability in the whole krange, except for k⫽0. This fact does not represent a problem, however, since vertices without edges are usually not considered in natural complex networks. The empirical evaluation of P(k,k⬘)关or P(k⬘ 兩 k)] is, in most real networks, a quite difficult task, since the available M. BOGUN ˜ A ´AND R. PASTOR-SATORRAS PHYSICAL REVIEW E 68, 036112 共2003兲 036112-2 data, restricted to finite sizes, usually yield results extremely noisy and difficult to interpret. For this reason, it is more useful for practical purposes to analyze instead the average degree of the nearest neighbors 共ANND兲as a function of the vertex degree, defined by 关7兴 k ¯ nn共k兲⫽兺 k⬘ k⬘P共k⬘ 兩 k兲.共8兲 For uncorrelated networks, in which P(k⬘ 兩 k) does not depend on k, application of the normalization condition 共1兲into Eq. 共6兲yields P0(k⬘ 兩 k)⫽k⬘P(k⬘)/ 具 k 典 . In this case, we obtain k ¯ nn 0(k)⫽ 具 k2 典 / 具 k 典 , independent of k. Therefore, a function k ¯ nn(k) with an explicit dependence on ksignals the presence of degree correlations in the network. Based on the ANND, it is possible to characterize the correlation properties of the network 关24兴: When k ¯ nn(k) is an increasing function of k, the network shows assortative mixing. Examples of assortative behavior can be found in several social networks 关24兴. On the other hand, when k ¯ nn(k) is a decreasing function of k, the network shows disassortative mixing, as found, for example, in technological systems such as the Internet 关7兴. B. Three vertices correlations Correlations among three vertices can be measured by means of the probability P(k⬘,k⬙ 兩 k) that a vertex of degree k is simultaneously connected to two vertices with degrees k⬘ and k⬙. In the particular case of Markovian networks, this function is related to the two vertices correlation through P(k⬘,k⬙ 兩 k)⫽P(k⬘ 兩 k)P(k⬙ 兩 k). For non-Markovian networks, however, the functions P(k⬘,k⬙ 兩 k) and P(k⬘ 兩 k) are in principle not related. Information about three vertices correlations can be obtained from the clustering coefficient. The concept of clustering in a graph refers to the tendency to form cliques 共complete subgraphs 关4兴兲 in the neighborhood of any given vertex. In this sense, clustering implies that if vertex iis connected to vertex j, and at the same time jis connected to l, then, with high probability, iis also connected to l. The probability that two vertices with a common neighbor are also connected to each other is called the clustering coefficient of the common vertex 关16兴. Numerically, the clustering coefficient ciof vertex ican be computed as the ratio between the number of edges existing between kineighbors of i,ei, and its maximum possible value ki(ki⫺1)/2, that is, ci⫽2ei ki共ki⫺1兲.共9兲 On the other hand, the clustering coefficient of a vertex of degree k,c ¯ (k)关8兴, can be formally computed as the probability that it is connected to vertices k⬘and k⬙, and that those two vertices are, on their turn, joined by and edge, averaged over all the possible values of the degrees of the neighbor vertices. Therefore, we can write c ¯ (k) as a function of the three vertices correlations as c ¯ 共k兲⫽兺 k⬘,k⬙ P共k⬘,k⬙ 兩 k兲pk⬘,k⬙,共10兲 where the function pk⬘,k⬙is the probability that the vertices k⬘and k⬙are connected 关38兴. The quantity c ¯ (k) has been recently used to study the level of hierarchy and modularity in real complex networks 关39兴. III. HIDDEN VARIABLE MODELS OF CORRELATED NETWORKS Recently, Caldarelli et al. 关32兴and So ¨derberg 关33,40兴共see also Refs. 关25,41兴兲 have proposed different models of inhomogeneous random graphs that represents a natural generalization of the classical Erdo ¨s-Re ´nyi random graph model 关42,43兴. These models consider inhomogeneous graphs in which each vertex is characterized by a different type or fitness. Types can be either discrete or continuous variables and are assigned to vertices according to a certain probability distribution. Then, pairs of vertices are independently joined by an undirected edge with a probability depending on the type of the respective end points. This construction leads to an ensemble of undirected random networks, which inherits the simplicity of the Erdo ¨s-Re ´nyi model while allowing freedom for general forms of the degree distribution and correlation structure. References 关33,40兴were mainly concerned with the component distribution and the onset of the giant component in these kinds of models, and Ref. 关32兴reported numerical simulations for different model parameters, and analytical arguments for the form of the degree distribution. The models defined in Refs. 关32,33兴can be generalized as a class of models with hidden variables. The hidden variables play the role of tags assigned to the vertices, and they completely determine the topological properties of the network through their probability distribution and the probability to connect pairs of vertices. We define the class of models with hidden variables as follows. Let us consider a set of Ndisconnected vertices and a general hidden variable h, which can be a natural or a real number. An undirected graph is generated by the following two rules. 共1兲Each vertex iis assigned a variable hi, independently drawn from the probability distribution ␳ (h). 共2兲For each pair of vertices iand j, with respective hidden variables hiand hj, an undirected edge is created with probability r(hi,hj)共the connection probability兲, where r(h,h⬘)⭓0 is a symmetric function of hand h⬘. Given the independent assignment of hidden variables and edges among vertices, this procedure generates correlated random networks with neither loops nor multiple edges, which are Markovian at the hidden variable level 关44兴and whose degree distribution and correlation properties are encoded in the two functions ␳ (h) and r(h,h⬘). Here we will focus in the case in which the distribution ␳ (h)isindependent of the network size N. The case in which ␳ (h) is allowed to depend on Nwill be considered in Sec. VI. In this section we will provide analytic expressions for the correlation function and clustering coefficient of the networks generated with this class of models as a function of CLASS OF CORRELATED RANDOM NETWORKS WITH . . . PHYSICAL REVIEW E 68, 036112 共2003兲 036112-3 the distribution of hidden variables and the probability to connect pairs of vertices. A. Degree distribution The degree distribution P(k) is defined as the probability that any given vertex has kedges attached to it. Therefore, in order to compute it, we need to know the conditional probability g(k 兩 h)共propagator兲that a vertex with initial hidden variable hends up connected to other kvertices. The degree distribution can then be written as P共k兲⫽兺 hg共k 兩 h兲 ␳ 共h兲,共11兲 where the summation sign must be exchanged by an integral for continuous h. The propagator, which is obviously normalized, 兺kg(k 兩 h)⫽1, provides full information about the dependence of the actual degree kon the hidden variable h. In particular, we can see that the average degree of the vertices with hidden variable h,k ¯ (h), is given by k ¯ 共h兲⫽兺 kkg共k 兩 h兲,共12兲 and the average degree can be expressed as 具 k 典 ⫽兺 kkP共k兲⫽兺 hk ¯ 共h兲 ␳ 共h兲.共13兲 On the other hand, the probability that a vertex of actual degree khas associated a hidden variable h,g*(h 兩 k), can be computed as the inverse of the propagator by means of Bayes’ formula 关45兴, P共k兲g*共h 兩 k兲⫽ ␳ 共h兲g共k 兩 h兲.共14兲 In order to get an explicit expression for the propagator, we start by noticing that it can be written as g共k 兩 h兲⫽兺 k1,...,kc g1 (h)共k1 兩 h1兲g2 (h)共k2 兩 h2兲•••gc (h)共kc 兩 hc兲 ⫻ ␦ k1⫹k2⫹•••⫹kc,k,共15兲 where gi (h)(ki 兩 hi) is the probability that a vertex with hidden variable hends up with kiconnections with vertices of hidden variable hi,hcbeing the maximum value of h. Since the connections between vertices with hidden variables hand h⬘ are independently drawn with probability r(h,h⬘), the probability gi (h)(ki 兩 hi) is simply given by a binomial distribution, i.e., gi (h)共ki 兩 hi兲⫽ 冉 Ni ki 冊 r共h,hi兲ki关1⫺r共h,hi兲兴Ni⫺ki,共16兲 where Ni⫽N ␳ (hi) is the number of vertices with hidden variable hi. Let us define now the generating function 关46兴 g ˆ共z 兩 h兲⫽兺 kzkg共k 兩 h兲.共17兲 Since the propagator is given by a convolution, Eq. 共15兲,we can write its generating function as the product of the generating functions of the partial propagators gi (h)(ki 兩 hi), which on their turn, being binomial distributions, yield g ˆi (h)共z 兩 hi兲⫽关1⫺共1⫺z兲r共h,hi兲兴Ni.共18兲 Inserting this expression into the definition of g ˆ(z 兩 h) and taking logarithms on both sides we are led to the equation ln g ˆ共z 兩 h兲⫽N兺 h⬘ ␳ 共h⬘兲ln关1⫺共1⫺z兲r共h,h⬘兲兴.共19兲 For general probabilities ␳ (h) and r(h,h⬘), Eq. 共19兲must be solved and inverted in order to obtain the corresponding propagator. The degree distribution is then obtained applying Eq. 共11兲. Even without solving the previous equation, however, it is already possible to obtain some information on the connectivity properties of the network. From the definition, Eq. 共17兲, the first moment of g(k 兩 h) is given by the first derivative of g ˆ(z 兩 h) evaluated at z⫽1. Therefore we have k ¯ 共h兲⫽N兺 h⬘ ␳ 共h⬘兲r共h,h⬘兲,共20兲 and 具 k 典 ⫽N兺 h,h⬘ ␳ 共h兲r共h,h⬘兲 ␳ 共h⬘兲,共21兲 where we have used Eq. 共19兲in computing these expressions. At this point we must consider the possibility of two different kinds of networks: Sparse networks, with a welldefined thermodynamic limit for the average degree 具 k 典 , and nonsparse networks, in which the average degree diverges with the network size. In the case of sparse networks, the number of edges grows linearly with the system size and, therefore, the joint distribution is a well-defined quantity, independent of N. In the opposite case, nonsparse networks have a number of edges growing faster than linearly, which causes the breakdown of the thermodynamic limit and the emergence of the phenomenon of condensation of edges 共see Sec. IV兲. In order to distinguish between sparse and nonsparse networks we must consider the value of the average degree, given by Eq. 共21兲. If the density ␳ (h) is independent of the size of the system, the only possibility to have a sparse network is that the connection probability scales as N⫺1. This scaling behavior turns out to have a strong implication in the form of the propagator. Defining r(h,h⬘) ⬅C(h,h⬘)/N共as considered in Ref. 关33兴兲, where C(h,h⬘)is a bounded symmetric function, independent of N,wecan expand the right-hand side of Eq. 共19兲in the limit N→⬁to obtain M. BOGUN ˜ A ´AND R. PASTOR-SATORRAS PHYSICAL REVIEW E 68, 036112 共2003兲 036112-4 g ˆ共z 兩 h兲⫽exp 再 共z⫺1兲兺 h⬘ ␳ 共h⬘兲C共h,h⬘兲 冎 .共22兲 The generating function of the propagator is a pure exponential, which indicates that the propagator itself is a Poisson distribution, g共k 兩 h兲⫽e⫺k ¯ (h)k ¯ 共h兲k k!,共23兲 where in this case k ¯ (h)⫽兺h ␳ (h⬘)C(h,h⬘). Equation 共23兲is, indeed, a strong result, since it states the universality of the propagator for sparse networks regardless of the form of the connection probability. It is worth mentioning that the degree distribution, Eq. 共19兲, has been derived on the basis of a microcanonical ensemble, in the sense that the number of vertices of each class, Nh⫽N ␳ (h), is a fixed quantity. This is in contrast to the canonical ensemble in which the fixed quantity is the average number of vertices of each class. However, given the equivalence between ensembles, both approaches are equivalent in the thermodynamic limit 关47兴. B. Degree correlations Degree correlations are completely characterized by means of the conditional probability P(k⬘ 兩 k), which gives the probability that an edge emanating from a vertex of degree kis connected to a vertex of degree k⬘. In order to construct the function P(k⬘ 兩 k) we consider a vertex of degree k, which with probability g*(h 兩 k) has associated a hidden variable h. Let us define p(h⬘ 兩 h) the conditional probability that a hvertex is connected to a h⬘vertex. Then, the conditional probability P(k⬘ 兩 k) can be written as P共k⬘ 兩 k兲⫽兺 h,h⬘ g共k⬘⫺1 兩 h⬘兲p共h⬘ 兩 h兲g*共h 兩 k兲,共24兲 where the propagator g(k⬘⫺1 兩 h⬘) gives the probability that the h⬘vertex ends up with degree k⬘共since one connection has already been used up for the conditional edge with h). Using the form of g*(h 兩 k) given by Eq. 共14兲we have P共k⬘ 兩 k兲⫽1 P共k兲兺 h,h⬘ g共k⬘⫺1 兩 h⬘兲p共h⬘ 兩 h兲 ␳ 共h兲g共k 兩 h兲, 共25兲 valid for k,k⬘⫽1,2,....Inorder to close Eq. 共25兲, we need, finally, to provide an expression for the conditional probability p(h⬘ 兩 h). In order to do so, we consider that the probability of drawing an edge from hto h⬘is proportional to the probability of finding an h⬘vertex, times the probability of creating the actual edge. Taking into account normalization, we have that p共h⬘ 兩 h兲⫽ ␳ 共h⬘兲r共h,h⬘兲 兺 h⬙ ␳ 共h⬙兲r共h,h⬙兲 ⫽N ␳ 共h⬘兲r共h,h⬘兲 k ¯ 共h兲.共26兲 Finally, using Eqs. 共25兲and 共26兲we can compute the ANND as k ¯ nn共k兲⫽1⫹1 P共k兲兺 hg共k 兩 h兲 ␳ 共h兲k ¯ nn共h兲,共27兲 where we have defined the ANND of a hvertex 关see Eq. 共8兲兴 as k ¯ nn共h兲⬅兺 h⬘ k ¯ 共h⬘兲p共h⬘ 兩 h兲.共28兲 C. Clustering coefficient The clustering coefficient is defined as the probability that two vertices, adjacent to a third vertex, are also connected to each other. In the space of hidden variables, consider a h vertex, which is connected to two other vertices h⬘and h⬙ with probability p(h⬘,h⬙ 兩 h). On the other hand, h⬘and h⬙ are connected with probability r(h⬘,h⬙). Therefore, the clustering coefficient of a vertex his given by ch ⫽兺h⬘,h⬙p(h⬘,h⬙ 兩 h)r(h⬘,h⬙). Note that this is the natural counterpart of Eq. 共10兲in the space of hidden variables. Now, since the network is Markovian at the hidden variable level, we have that p(h⬘,h⬙ 兩 h)⫽p(h⬘ 兩 h)p(h⬙ 兩 h). Thus we have that ch⫽兺 h⬘,h⬙ p共h⬘ 兩 h兲r共h⬘,h⬙兲p共h⬙ 兩 h兲.共29兲 The clustering coefficient of the vertices of degree k,c ¯ (k), will be given by the probability that a vertex khas hidden variable h,g*(h 兩 k), times ch, averaged over all the possible values of h. Thus c ¯ 共k兲⫽1 P共k兲兺 h ␳ 共h兲g共k 兩 h兲ch,k⫽2,3,..., 共30兲 where we have used the form of g*(h 兩 k) given by Eq. 共14兲. The results derived in this section represent the general solution of the class of networks with hidden variables. In the rest of the paper we will show how this formalism is able to deal with a wide variety of models, from sparse to nonsparse networks, and from equilibrium to nonequilibrium ones. IV. THE INTRINSIC FITNESS MODEL As an example of the general class of models with hidden variables, Caldarelli et al. 关32兴considered the model defined by the probability distributions ␳ 共h兲⫽e⫺hfor h苸关0,⬁关,共31兲 r共h,h⬘兲⫽ ␪ 共h⫹h⬘⫺ ␨ 兲,共32兲 where ␪ (x) is the Heaviside step function and ␨ is a constant. In this model, hereafter referred to as the intrinsic fitness 共IF兲model, vertices have assigned an exponentially distributed hidden variable 共fitness兲, and are joined by an edge CLASS OF CORRELATED RANDOM NETWORKS WITH . . . PHYSICAL REVIEW E 68, 036112 共2003兲 036112-5 whenever the sum of the fitness of the end points is larger than a given threshold ␨ . By means of numerical simulations and analytical arguments, Caldarelli et al. 关32兴showed that the degree distribution in this model is power-law distributed. This observation led to the very interesting conclusion that it is possible to generate scale-free networks without growth not preferential attachment 关34兴. A. Analytic solution Using the general formalism developed in the preceding section, we can provide analytic expressions for the main properties of the IF model. In order to do so, let us compute in the first place the propagator g(k 兩 h). Inserting Eqs. 共31兲 and 共32兲into Eq. 共19兲, we have, substituting the summation by an integral, lng ˆ共z 兩 h兲⫽N 冕 0 ⬁dh⬘e⫺h⬘ln关1⫺共1⫺z兲 ␪ 共h⫹h⬘⫺ ␨ 兲兴 ⫽Nlnz 再 eh⫺ ␨ if 0⭐h⭐ ␨ 1ifh⬎ ␨ ,共33兲 from where we obtain g ˆ(z 兩 h)⫽zNeh⫺ ␨ for 0⭐h⭐ ␨ , and g ˆ(z 兩 h)⫽zNfor h⬎ ␨ . In order to invert this generating function, we approximate kby a continuous variable. In this case, the propagator takes the simple form g共k 兩 h兲⫽ ␦ 共k⫺Neh⫺ ␨ 兲 ␪ h共0, ␨ 兲⫹ ␦ 共k⫺N兲 ␪ 共h⫺ ␨ 兲, 共34兲 where ␦ (x) is the Dirac delta function and we have introduced the window function ␪ x共a,b兲⫽ 再 1 for a⭐x⭐b 0 otherwise. 共35兲 This approximation is expected to perform poorly for small values of k, as we will see when comparing the analytical results with computer simulations of the IF model. Inserting the propagator, Eq. 共34兲, into the general expression 共11兲, and performing the integrals corresponding to the Dirac ␦ functions, we obtain the degree distribution P共k兲⫽Ne⫺ ␨ 1 k2 ␪ k共Ne⫺ ␨ ,N兲⫹e⫺ ␨ ␦ 共k⫺N兲.共36兲 That is, the networks generated by the IF model exhibit a scale-free degree distribution, with degree exponent ␥ ⫽2, for degrees in the range Ne⫺ ␨ ⭐k⭐N, plus an accumulation point at k⫽N, given by the ␦ function, with weight e⫺ ␨ . This accumulation point signals the presence of a condensation of edges in the fraction e⫺ ␨ of the vertices of the network with h⬎ ␨ , which establish connections to all the other vertices 关48兴. This condensation, reminiscent to that observed in models with nonlinear preferential attachment 关49兴, is the result of the nonsparse nature of the network, which, from Eq. 共21兲, has average degree 具 k 典 ⫽Ne⫺ ␨ ( ␨ ⫹1). In order to characterize the correlations of the model, we compute the ANND, given by Eq. 共27兲. In the continuous k approximation, the function k ¯ (h) takes the form k ¯ 共h兲⫽Neh⫺ ␨ ␪ h共0, ␨ 兲⫹N ␪ 共h⫺ ␨ 兲.共37兲 Inserting this expression into the formula for the ANND, we obtain k ¯ nn共k兲⫽1⫹Ne⫺2 ␨ P共k兲 冋 共1⫹ ␨ 兲 ␦ 共k⫺N兲 ⫹N2 k3 再 1⫹ ␨ ⫹ln 冉 k N 冊 冎 ␪ k共Ne⫺ ␨ ,N兲 册 .共38兲 The regular part of this expression 共discarding the ␦ function singularities, signaling again the effect of the condensation of edges in the correlation function兲takes the form k ¯ nn r共k兲⫽1⫹N2e⫺ ␨ k 冋 1⫹ ␨ ⫹ln 冉 k N 冊 册 ␪ k共Ne⫺ ␨ ,N兲.共39兲 That is, the regular part of the ANND is proportional to k⫺1, times a logarithmic correction term. We are therefore in the presence of disassortative mixing. Note that, in the limit N →⬁, we have that k ¯ nn r(k)→⬁, in agreement with the theoretical prediction made in Ref. 关29兴. Finally, to estimate the clustering coefficient, we have to compute first the conditional probability at the level of hidden variables, given by Eq. 共26兲. Using Eqs. 共31兲and 共32兲, we obtain p共h⬘ 兩 h兲⫽e⫺h⬘ ␪ 共h⬘⫹h⫺ ␨ 兲关e ␨ ⫺h ␪ h共0, ␨ 兲⫹ ␪ 共h⫺ ␨ 兲兴. 共40兲 From this expression we can obtain the clustering coefficient at the level of the hidden variables ch⫽ ␪ h共0, ␨ /2兲⫹e ␨ ⫺2h共2h⫺ ␨ ⫹1兲 ␪ h共 ␨ /2, ␨ 兲 ⫹e⫺ ␨ 共 ␨ ⫹1兲 ␪ 共h⫺ ␨ 兲,共41兲 and the clustering coefficient as a function of the degree k, c ¯ 共k兲⫽Ne⫺ ␨ k2P共k兲 ␪ k共Ne⫺ ␨ ,Ne⫺ ␨ /2兲⫹N3e⫺2 ␨ k4P共k兲 ⫻ 冋 2ln 冉 k N 冊 ⫹ ␨ ⫹1 册 ␪ k共Ne⫺ ␨ /2,N兲⫹1 P共k兲 ⫻e⫺2 ␨ 共 ␨ ⫹1兲 ␦ 共k⫺N兲.共42兲 The regular part of this formula is finally c ¯ r共k兲⫽ ␪ k共Ne⫺ ␨ ,Ne⫺ ␨ /2兲⫹N2e⫺ ␨ k2 ⫻ 冋 2ln 冉 k N 冊 ⫹ ␨ ⫹1 册 ␪ k共Ne⫺ ␨ /2,N兲.共43兲 M. BOGUN ˜ A ´AND R. PASTOR-SATORRAS PHYSICAL REVIEW E 68, 036112 共2003兲 036112-6 That is, for k⭐Ne⫺ ␨ /2, the clustering coefficient is constant and equal to its maximum possible value 1. The presence of this flat region in the clustering coefficient is easy to understand. The degree range k⭐Ne⫺ ␨ /2 corresponds, from Eq. 共37兲, to vertices with fitness h⬍ ␨ /2. These vertices can only establish connections with vertices with h⬘⬎ ␨ /2, which are on their turn fully interconnected among them. From here, it follows a maximum clustering coefficient equal to 1 for all vertices with h⬍ ␨ /2. On the other hand, for Ne⫺ ␨ /2⭐k ⭐N, the clustering coefficient decreases as k⫺2, modulated again by a logarithmic correction term. B. Numerical simulations In order to check the validity of the proposed analytical expressions, we have performed numerical simulations of the IF model. To simplify the comparison, we have considered the particular case ␨ ⫽lnN, in which the relevant expressions take the form P共k兲⫽1 k2 ␪ k共1,N兲⫹1 N ␦ 共k⫺N兲,共44兲 k ¯ nn r共k兲⫽ 冋 1⫹N1⫹lnk k 册 ␪ k共1,N兲,共45兲 c ¯ r共k兲⫽ ␪ k共1,N1/2兲⫹2N k2 冋 ln 冉 k N1/2 冊 ⫹1 2 册 ␪ k共N1/2,N兲. 共46兲 Simulations were performed for networks of size N⫽104 共corresponding to ␨ ⫽ln104⬇9.2103), averaging all statistical distributions over 103to 105network realizations. In Fig. 1 we depict the results corresponding to the degree distribution. As we can see, the theoretical prediction 共solid line兲overestimates the value of the actual degree distribution for small k. This is a natural effect of the continuous kapproximation, which can be readily understood from the form of Eq. 共44兲: The form P(k)⬃k⫺2cannot be correct in a discrete approximation, since it does not fulfill the normalization condition. The condensation of edges at k⫽Nis clearly visible in the presence of an isolated peak, of height approximately equal to N⫺1. Figures 2 and 3, on the other hand, represent the ANND and the clustering coefficient as a function of the degree k, respectively. As we can see, the fit between the computer simulations and the analytical expressions is quite good. V. A PRACTICAL ALGORITHM TO GENERATE CORRELATED RANDOM NETWORKS The hidden variable class of models represents a natural extension of the Erdo ¨s-Re ´nyi random graph model that allows to generate a broad class of correlated networks from which it is possible to compute the most relevant topological properties. From a practical point of view, however, it is still FIG. 1. Comparison between the theoretical prediction Eq. 共44兲 for the degree distribution 共solid line兲and computer simulations 共hollow circles兲of the IF model. The isolated point at k⫽Ncorresponds to the analytical Dirac ␦ function, with strength e⫺ ␨ ⫽N⫺1. FIG. 2. Comparison between the theoretical prediction, Eq. 共45兲, for the ANND 共solid line兲and computer simulations 共hollow circles兲of the IF model. FIG. 3. Comparison between the theoretical prediction, Eq. 共46兲, for the clustering coefficient as a function of degree k共solid line兲 and computer simulations 共hollow circles兲of the IF mode. CLASS OF CORRELATED RANDOM NETWORKS WITH . . . PHYSICAL REVIEW E 68, 036112 共2003兲 036112-7 missing an important point. Indeed, there are many situations in which it is desirable to generate a network with a particular correlation structure given by a certain joint distribution P(k,k⬘). For a hidden variable model it is possible to compute this quantity as a function of the initial probabilities ␳ (h) and r(h,h⬘). However, this relation is nontrivial, and it is generally not possible to invert it. Therefore, in order to implement an algorithm capable of generating networks with any a priori correlation structure, one must carefully choose the distribution of hidden variables and the connection probability. One possible way to proceed is to define hidden variables hthat have themselves the structure of the degrees of a real network 共hidden degrees兲, with correlations given by a joint distribution P ˜ (h,h⬘). Those hidden degrees will then be natural numbers that are assigned to the vertices according to the probability distribution 关see Eq. 共7兲兴 ␳ 共h兲⫽ 具 h 典 h兺 h⬘ P ˜ 共h,h⬘兲,共47兲 with 具 h 典 ⫽兺hh ␳ (h). In order to define the connection probability, we consider that, if the hidden degrees were the actual degrees characterizing the network, then the total number of edges between vertices hand h⬘would be Ehh⬘ ⫽ 具 h 典 P ˜ (h,h⬘)N. Since the total number of hvertices is Nh ⫽N ␳ (h), it is therefore natural to define r共h,h⬘兲⫽ 具 h 典 N P ˜ 共h,h⬘兲 ␳ 共h兲 ␳ 共h⬘兲.共48兲 On the other hand, the conditional probability that a vertex h is connected to a vertex h⬘is given by 关see Eq. 共5兲兴 p共h⬘ 兩 h兲⫽ 具 h 典 P ˜ 共h,h⬘兲 h ␳ 共h兲.共49兲 The quantities ␳ (h) and p(h⬘ 兩 h) will be, in this case, related through the hidden degree detailed balance condition, hp共h⬘ 兩 h兲 ␳ 共h兲⫽h⬘p共h 兩 h⬘兲 ␳ 共h⬘兲⫽ 具 h 典 P ˜ 共h,h⬘兲,共50兲 as can be checked by inserting into the definition of p(h⬘ 兩 h), Eq. 共26兲, the expression of Eq. 共48兲. It is interesting to note that, if two-point correlations are absent at the level of the hidden variables, then we have that P ˜ 0(h,h⬘) ⫽hh⬘ ␳ (h) ␳ (h⬘)/ 具 h 典 2. Thus, the connection probability reads r0共h,h⬘兲⫽hh⬘ N 具 h 典 ,共51兲 recovering the model recently introduced by Chung and Lu 关50兴共see also Ref. 关51兴兲. Assuming that the connection probability is bounded and decreases for large network sizes as N⫺1, we can compute the propagator g(k 兩 h) applying Eq. 共23兲with k ¯ (h) ⫽N兺h⬘ ␳ (h⬘)r(h,h⬘)⫽h, where we have used Eq. 共48兲. Therefore, the propagator is a simple Poisson distribution, with average value h, i.e., g共k 兩 h兲⫽e⫺hhk k!.共52兲 Note that the validity of this result levers on a quite strong assumption for the boundedness of the connection probability r(h,h⬘). The nature of this condition is more clearly seen in the case of uncorrelated networks, with r0(h,h⬘) ⫽hh⬘/N 具 h 典 .Ifr0(h,h⬘) has to decrease as N⫺1, then the maximum value of the hidden degree must be smaller than hc(N)⫽(N 具 h 典 )1/2 关50兴, a condition that imposes restrictions on the maximum degree available for any vertex. From the propagator, Eq. 共52兲, the degree distribution as a function of ␳ (h) follows immediately from Eq. 共11兲: P共k兲⫽兺 h e⫺hhk k! ␳ 共h兲.共53兲 This relation between distributions implies a relation between the respective moments. Indeed, it is straightforward to prove that 具 hn 典 ⫽ 具 k共k⫺1兲•••共k⫺n⫹1兲 典 ,共54兲 and, in particular, the first two moments read 具 h 典 ⫽ 具 k 典 , 具 h2 典 ⫽ 具 k2 典 ⫺ 具 k 典 .共55兲 It is also instructive to see how we can recover the classical Erdo ¨s-Re ´nyi random graph model from this formalism. The Erdo ¨s-Re ´nyi model corresponds to joining pairs of vertices with a constant probability p. Such connection probability results from imposing uncorrelated hidden degrees with distribution ␳ ER(h)⫽ ␦ 具 k 典 ,h, which yields a Poisson degree distribution with average degree 具 k 典 . In order to compute the ANND function from Eq. 共27兲, we observe that in this case k ¯ (h)⫽h. From here we obtain k ¯ nn共k兲⫽1⫹1 P共k兲兺 h e⫺hhk k! ␳ 共h兲h ¯ nn共h兲,共56兲 where, in this case, the average hidden degree of the nearest neighbors as a function of h关see Eq. 共28兲兴 is h ¯ nn共h兲⫽兺 h⬘ h⬘p共h⬘ 兩 h兲⫽ 具 h 典 h ␳ 共h兲兺 h⬘ h⬘P ˜ 共h,h⬘兲.共57兲 For uncorrelated networks at the hidden level, the ANND yields k ¯ nn 0共k兲⫽1⫹ 具 h2 典 具 h 典 ⫽ 具 k2 典 具 k 典 ,共58兲 recovering the well-known result 关52兴. Finally, the clustering coefficient takes, from Eq. 共30兲, the form M. BOGUN ˜ A ´AND R. PASTOR-SATORRAS PHYSICAL REVIEW E 68, 036112 共2003兲 036112-8 c ¯ 共k兲⫽1 P共k兲兺 h e⫺hhk k! ␳ 共h兲ch,共59兲 where the clustering coefficient in terms of the hidden degrees is given by ch⫽兺 h⬘,h⬙ p共h⬘ 兩 h兲r共h⬘,h⬙兲p共h⬙ 兩 h兲 ⫽ 具 h 典 3 h2 ␳ 共h兲2N兺 h⬘,h⬙ P ˜ 共h,h⬘兲P ˜ 共h⬘,h⬙兲P ˜ 共h⬙,h兲 ␳ 共h⬘兲 ␳ 共h⬙兲.共60兲 When correlations are missing in the hidden degree distribution, we obtain c ¯ 0共k兲⫽ 具 h2 典 2 N 具 h 典 3⫽共 具 k2 典 ⫺ 具 k 典 兲2 N 具 k 典 3,共61兲 recovering the result previously derived by Newman 关53兴. The key point to notice in the above expressions is that the Poisson propagator, Eq. 共52兲, is a sharply peaked function at k⫽h, which in the large klimit is analogous to a delta function ␦ h,k. Therefore, in the limit k→⬁, we expect to observe the behavior P共k兲⬃ ␳ 共k兲,共62兲 k ¯ nn共k兲⬃1⫹h ¯ nn共k兲,共63兲 c ¯ 共k兲⬃ck.共64兲 That is, the main topological properties referred to the actual degree ktend to their analogs computed for the hidden degree h, with the sole exception of a constant of order unit added to the ANND function. We can take advantage of this observation to propose the following algorithm to generate a correlated random network with theoretical degree distribution Pt(k) and joint distribution Pt(k,k⬘). 共1兲Assign to each vertex ian integer random variable k ˜ i, i⫽1,...,N, drawn from the probability distribution Pt(k). 共2兲For each pair of vertices iand j, draw an undirected edge with probability r(k ˜ i,k ˜ j)⫽ 具 k 典 Pt(k ˜ i,k ˜ j)/ NPt(k ˜ i)Pt(k ˜ j). The outcome of this process will be a random network whose actual degree structure, in the large klimit, will be distributed according to the probability Pt(k), with correlations given by Pt(k,k⬘). In order to check the accuracy of the previous algorithm, we have tested it with the joint probability distribution Pt共k,k⬘兲⫽Aqkk⬘,k,k⬘⫽1,2,..., 共65兲 where Ais a normalization constant and q⬍1 is a constant parameter. With this choice, the degree distribution takes the form Pt共k兲⫽ 具 k 典 Aqk k共1⫺qk兲,共66兲 which, for q→1, approaches a power-law distribution with exponent ␥ ⫽2. In Figs. 4–6 we present the results for the degree distribution, the ANND function, and the clustering coefficient, respectively, from computer simulations of the proposed algorithm, using the joint probability distribution given by Eq. 共65兲. The plots have been obtained for networks of size N⫽104and a parameter q⫽0.999, averaging over 103realizations. In the same graphs we also represent the theoretical values corresponding to a network with a correlation structure given by Pt(k,k⬘), plus the transformed functions given by Eqs. 共53兲,共56兲, and 共59兲, respectively, that correspond to the actual topological properties of the network. As discussed previously, and to ease the comparison of the plots, a factor 1 has been subtracted to the ANND function obtained from computer simulations and the transformation, Eq. 共56兲. We can see that for all three quantities, the matching between the computer simulations and the theoretical results is very good for values of klarger than 10. Being the discrepancy limited to such small degree values, FIG. 4. Degree distribution obtained from numerical simulations of the proposed algorithm, applied to the joint distribution, Eq. 共65兲, compared with the theoretical and transformed values. FIG. 5. ANND function obtained from numerical simulations of the proposed algorithm, applied to the joint distribution, Eq. 共65兲, compared with the theoretical and transformed values. CLASS OF CORRELATED RANDOM NETWORKS WITH . . . PHYSICAL REVIEW E 68, 036112 共2003兲 036112-9