# Diagonal Degree Correlations vs. Epidemic Threshold in Scale-Free Networks

Authors: M. L. Bertotti; G. Modanese
Journal: Complexity
 (2021)

---

## Abstract

We prove that the presence of a diagonal assortative degree correlation, even if small, has the effect of dramatically lowering the epidemic threshold of large scale-free networks. The correlation matrix considered isPh|k=1−rPhkU+rδhk, where PU is uncorrelated and r (the Newman assortativity coefficient) can be very small. The effect is uniform in the scale exponent γ if the network size is measured by the largest degree n. We also prove that it is possible to construct, via the Porto–Weber method, correlation matrices which have the same knn as the Ph|k above, but very different elements and spectra, and thus lead to different epidemic diffusion and threshold. Moreover, we study a subset of the admissible transformations of the form Ph|k⟶Ph|k+Φh,k with Φh,k depending on a parameter which leaves knn invariant. Such transformations affect in general the epidemic threshold. We find, however, that this does not happen when they act between networks with constant knn, i.e., networks in which the average neighbor degree is independent from the degree itself (a wider class than that of strictly uncorrelated networks).


---

## Body

## 1. Introduction

From the mathematical point of view, a network is completely characterized (up to isomorphisms corresponding to simple redenominations of the vertices) when a list of links or an adjacency matrix is given. In many applications involving large networks, however, one often summarizes the information on the network structure in a statistic-probabilistic form, by introducing the two fundamental quantitiesPk and Ph|k. Pk, called degree distribution, represents the probability that a randomly chosen vertex of the network has k neighbors. Ph|k, called degree correlation function, expresses the conditional probability that a vertex of degree k is connected to a vertex of degree h. An alternative but equivalent description involves the symmetric quantities ejk, defined as the probabilities that a randomly chosen link connects two vertices of degree j and k [1–3].When one considers in a purely axiomatic way a class of networks, called Markovian networks [4], which are completely defined by assigning the quantities Pk and Ph|k, one disregards higher-order correlations like Pj|h|k, which can in general be present. It is interesting to investigate the connections between real networks and the corresponding Markovian networks. In the case of Barabasi–Albert networks, for instance, it is possible to use recipes for constructing ensembles of the two kinds (preferential attachment vs. rewiring) and compare them [5].In any case, let us focus onPk and Ph|k. Imagine that we know them for a certain network and we want to study some dynamical processes on the network, e.g., epidemic diffusion processes [6]. It turns out [7, 8] that several features of these processes depend on a “contracted” form of the correlations, namely, the function knnk, called “average nearest neighbor degree” and defined as knnk=∑k=1nhPh|k, where n is the highest degree of the nodes of the network. This function of k is simpler to analyse than the full matrix Ph|k. Its increasing or decreasing character discriminates between assortative and disassortative networks (see [9–12] and refs.). We can further contract the information on the correlations into a single number, the Newman assortativity coefficient r, either using the ejk matrix or with one more summation procedure performed on knn.One may wonder whether it is possible, given an admissibleknn function (it must satisfy a normalization condition given below), to compute a full correlation matrix which returns that knn upon contraction on h. Porto and Weber have devised a method for this purpose [13], which has been used for some applications by themselves and Silva et al. [14]. However, while the correspondence Ph|k⟶knnk is univocal, this is not true for the opposite correspondence knnk⟶Ph|k. One first scope of this work is to show explicitly this ambiguity in an important specific example, namely, that of a linear knn. To this end, we introduce in Section 2.1 the correlation matrix PVaz−Weih|k of Vazquez–Weigt [15], which has the simple form 1−rPhkU+rδhk, where PU is an uncorrelated matrix. The corresponding knn is linear in k. Then, in Section 2.2, we recall the method by Porto and Weber for building a Ph|k starting from a knn, and in Section 2.3, we apply it to knn of Vazquez and Weigt. A comparison of the result with the original matrix PVaz−Weih|k shows remarkable differences. Also, in Section 2.4, we briefly discuss the case of real networks for which the knn function is only approximately linear.While examining the differences noted in Section2.3, we have been led to consider the eigenvalue spectra of the associated connectivity matrices Ckh=kPh|k. This has revealed a simple general property of the eigenvalues of CVaz−Wei, which has important consequences for the epidemic threshold in diffusion models based on this matrix (Section 3). In fact, the eigenvalues of CVaz−Wei are Λi=ri, where i=1,…,n and n is the largest degree in the network. It follows that the epidemic threshold λc=1/Λmax (Section 3.1) is proportional to n−1, for any fixed value of r. When r is small, the epidemic threshold λc is definitely greater than zero for small networks, but if n⟶∞, the threshold goes quickly to zero. The convergence is much faster than for other correlations, for which the largest eigenvalue typically grows as a root of n or even as lnn when the scale-free exponent γ is equal to 3 (Sections 3.2 and 3.3). The conclusion is that adding even a very small amount of assortative diagonal degree correlations to an uncorrelated network leads, in the large-n limit, to a fast vanishing of the epidemic threshold. Further, numerical results for the case in which the assortativity coefficient is not small are given in Section 3.4.In Section4, we discuss a family of transformations of the correlation matrices which keep their knn functions unchanged. We show that such transformations affect in general the epidemic threshold even if this does not happen when these transformations act on networks in which the average neighbor degree is independent from the degree itself; in this case, the transformations lead to networks for which the epidemic threshold remains unchanged and which, albeit having a constant knn, belong to a wider class than that of strictly uncorrelated networks.


## 2. The Correlation Matrix of Vazquez–Weigt vs. That of Porto–Weber Reconstruction

### 2.1. The Vazquez–Weigt Matrix

Vazquez and Weigt [15] have defined the following assortative correlation matrix:(1)PVaz−Weih|k=1−rhPhk+rδhk,where k=∑k=1nkPk (more generally, below, gk denotes ∑k=1ngkPk for any function g).This Ansatz has been used in several applications [16]. It is a linear combination of a perfectly uncorrelated matrix with elements hPh/k, giving a probability of connection independent from k and a perfectly assortative matrix δhk (giving a nonzero probability of connection only between nodes of the same degree). The coefficient r in the linear combination can vary in the range 0,1 and corresponds to the Newman assortativity coefficient.Theknn function for the Vazquez–Weigt correlation matrix is easily found as follows:(2)knnVaz−Weik=∑k=1nhPVaz−Weih|k=1−rk2k+rk.Since the first term is independent fromk, this is a linear function, with slope r.


### 2.2. The Recipe of Porto–Weber for a Correlation Matrix Having a Predefinedknn

In order to compute the correlation matrixPh|k starting from a given function knn (normalized as ∑kkPkknnk=k2 [12]), Porto and Weber define first the symmetric function as follows:(3)fh,k=1+knnh−kmeknnk−kmekknne−kme2,where(4)kme=k2k,kknne=∑hhPhkhknnh.In other words,kknne is the average of the quantity kknnk with a normalized “edge” probability distribution defined as Pek=kPk/k, giving the probability that a randomly chosen edge of the network is connected to a node of degree k.The conditional probabilityPh|k is then given by(5)Ph|k=hPhkfh,k.It is immediate to check thatPh|k defined in this way satisfies the normalization condition in h and the network closure condition as follows:(6)hPk|hPh=kPh|kPk,for allh,k=i=1,…,n.Also, it is straightforward to replacePh|k into the definition of knnk and obtain an identity.


### 2.3. Porto–Weber Recipe Applied to the Vazquez Correlation Matrix

Now, suppose we want to reconstructPVaz−Weih|k starting from knnVaz−Weik using the Porto–Weber recipe. Applying this recipe to the knn function of Vazquez–Weigt, one obtains(7)fh,k=1+rh−kmek−kmek3/k−kme2.One can check numerically that the insertion of this functionfh,k into the Porto–Weber recipe gives a correlation matrix PPor−Webh|k whose knn coincides element by element with knn of Vazquez–Weigt. However, PPor−Webh|k does not coincide with PVaz−Weih|k. The difference between the two matrices is evident looking at their dependence on h and k. Their traces and eigenvalues are markedly different as we shall show in the next section. A graphical representation showing the differences of the single elements is given in Figures 1 and 2.Figure 1
The correlation matrixPVaz−Weih|k with n=30 (maximum degree), r=0.25 (Newman assortativity coefficient), γ=2.5 (scale-free exponent). The diagonal elements are clearly visible. Like for any correlation matrix, each column is normalized to 1 (please note that row 0 and column 0 appear in the plot but do not actually belong to the matrix).Figure 2
The correlation matrixPPor−Webh|k with n=30, r=0.25, and γ=2.5. Note the difference with PVaz−Weih|k in Figure 1 in spite of the fact that the two matrices have the same (linear) knn function. In the “deep blue” lower part of the matrix, there are variations which are not visible in this plot but are obviously needed to keep each column normalized to 1. The example is compared in Figure 3.Figure 3
The elements of row 25 of the matrixPPor−Web of Figure 2. There is an increase in k which is not visible in the color scale of Figure 2 but is necessary to preserve the normalization of the columns. The same happens of course for the other rows.In conclusion, with the Porto–Weber recipe, it is possible to obtain from a givenknnk function a correlation matrix Ph|k which yields that knn, but such a correlation matrix is not the unique correlation matrix having the given knn as its average nearest neighbor degree function. This could and should in fact be expected since the definition of knn involves a summation, and thus any two matrices P1h|k and P2h|k, suitably normalized, such that(8)∑h=1nhP1h|k−P2h|k=0,yield the same knn.We also observe that there is no guarantee that the Porto–Weber method works for any normalizedknn. For instance, for a linear knn, some (unacceptable) negative values of PPor−Webh|k are obtained when r is greater than a value which is approximately 0.5. For the knn functions of Reference [14], of the form knn=ckα, one obtains negative values of PPor−Webh|k when α is greater than a value which is approximately 0.4.


### 2.4. The Case of Real Networks

Summarizing, from the purely mathematical point of view, our argument above shows explicitly that fixing aknn function of a network is not sufficient to define its full correlations. Actually, as proven in Section 4, there exists in general an infinite set of transformations of the correlations Ph|k which leave their knn invariant. One can say that PVaz−Wei and PPor−Web just represent mathematically two different Markovian networks (also having different connectivity spectra, as discussed in Section 3).However, when it comes to the modelization of diffusion on real networks, the following question may arise: if we know that a certain real network displays a linearknn function, is it more appropriate to compute its diffusion properties, and in particular the epidemic threshold, using a full correlation matrix of the PVaz−Wei type or the PPor−Web type? This question is motivated by the fact that “empirical” knn functions are often used to summarize in an efficient way the information available on correlations in real networks [3]. It is also known that a linear behavior of knn for real assortative networks is quite frequent but only approximate. Especially for large values of the node degree k, the linear behavior is not maintained in practice, and one observes instead a decreasing tail in knn. This happens also because in real scale-free networks, the largest hubs are present but rare, and the Markovian-probabilistic approach is stretched to its limits of applicability.It can be shown through numerical simulations based on degree-preserving rewiring [12] that in a real assortative scale-free networks (even with high r), the large hubs cannot be connected to a sufficient number of other hubs so as to keep knn increasing for large k simply because many hubs have in principle a nonzero probability but are missing in a random concrete realization of the network. In such cases, using the Porto–Weber method to construct the full correlations starting from a realistic knn function is clearly the more correct recipe.


## 2.1. The Vazquez–Weigt Matrix

Vazquez and Weigt [15] have defined the following assortative correlation matrix:(1)PVaz−Weih|k=1−rhPhk+rδhk,where k=∑k=1nkPk (more generally, below, gk denotes ∑k=1ngkPk for any function g).This Ansatz has been used in several applications [16]. It is a linear combination of a perfectly uncorrelated matrix with elements hPh/k, giving a probability of connection independent from k and a perfectly assortative matrix δhk (giving a nonzero probability of connection only between nodes of the same degree). The coefficient r in the linear combination can vary in the range 0,1 and corresponds to the Newman assortativity coefficient.Theknn function for the Vazquez–Weigt correlation matrix is easily found as follows:(2)knnVaz−Weik=∑k=1nhPVaz−Weih|k=1−rk2k+rk.Since the first term is independent fromk, this is a linear function, with slope r.


## 2.2. The Recipe of Porto–Weber for a Correlation Matrix Having a Predefinedknn

In order to compute the correlation matrixPh|k starting from a given function knn (normalized as ∑kkPkknnk=k2 [12]), Porto and Weber define first the symmetric function as follows:(3)fh,k=1+knnh−kmeknnk−kmekknne−kme2,where(4)kme=k2k,kknne=∑hhPhkhknnh.In other words,kknne is the average of the quantity kknnk with a normalized “edge” probability distribution defined as Pek=kPk/k, giving the probability that a randomly chosen edge of the network is connected to a node of degree k.The conditional probabilityPh|k is then given by(5)Ph|k=hPhkfh,k.It is immediate to check thatPh|k defined in this way satisfies the normalization condition in h and the network closure condition as follows:(6)hPk|hPh=kPh|kPk,for allh,k=i=1,…,n.Also, it is straightforward to replacePh|k into the definition of knnk and obtain an identity.


## 2.3. Porto–Weber Recipe Applied to the Vazquez Correlation Matrix

Now, suppose we want to reconstructPVaz−Weih|k starting from knnVaz−Weik using the Porto–Weber recipe. Applying this recipe to the knn function of Vazquez–Weigt, one obtains(7)fh,k=1+rh−kmek−kmek3/k−kme2.One can check numerically that the insertion of this functionfh,k into the Porto–Weber recipe gives a correlation matrix PPor−Webh|k whose knn coincides element by element with knn of Vazquez–Weigt. However, PPor−Webh|k does not coincide with PVaz−Weih|k. The difference between the two matrices is evident looking at their dependence on h and k. Their traces and eigenvalues are markedly different as we shall show in the next section. A graphical representation showing the differences of the single elements is given in Figures 1 and 2.Figure 1
The correlation matrixPVaz−Weih|k with n=30 (maximum degree), r=0.25 (Newman assortativity coefficient), γ=2.5 (scale-free exponent). The diagonal elements are clearly visible. Like for any correlation matrix, each column is normalized to 1 (please note that row 0 and column 0 appear in the plot but do not actually belong to the matrix).Figure 2
The correlation matrixPPor−Webh|k with n=30, r=0.25, and γ=2.5. Note the difference with PVaz−Weih|k in Figure 1 in spite of the fact that the two matrices have the same (linear) knn function. In the “deep blue” lower part of the matrix, there are variations which are not visible in this plot but are obviously needed to keep each column normalized to 1. The example is compared in Figure 3.Figure 3
The elements of row 25 of the matrixPPor−Web of Figure 2. There is an increase in k which is not visible in the color scale of Figure 2 but is necessary to preserve the normalization of the columns. The same happens of course for the other rows.In conclusion, with the Porto–Weber recipe, it is possible to obtain from a givenknnk function a correlation matrix Ph|k which yields that knn, but such a correlation matrix is not the unique correlation matrix having the given knn as its average nearest neighbor degree function. This could and should in fact be expected since the definition of knn involves a summation, and thus any two matrices P1h|k and P2h|k, suitably normalized, such that(8)∑h=1nhP1h|k−P2h|k=0,yield the same knn.We also observe that there is no guarantee that the Porto–Weber method works for any normalizedknn. For instance, for a linear knn, some (unacceptable) negative values of PPor−Webh|k are obtained when r is greater than a value which is approximately 0.5. For the knn functions of Reference [14], of the form knn=ckα, one obtains negative values of PPor−Webh|k when α is greater than a value which is approximately 0.4.


## 2.4. The Case of Real Networks

Summarizing, from the purely mathematical point of view, our argument above shows explicitly that fixing aknn function of a network is not sufficient to define its full correlations. Actually, as proven in Section 4, there exists in general an infinite set of transformations of the correlations Ph|k which leave their knn invariant. One can say that PVaz−Wei and PPor−Web just represent mathematically two different Markovian networks (also having different connectivity spectra, as discussed in Section 3).However, when it comes to the modelization of diffusion on real networks, the following question may arise: if we know that a certain real network displays a linearknn function, is it more appropriate to compute its diffusion properties, and in particular the epidemic threshold, using a full correlation matrix of the PVaz−Wei type or the PPor−Web type? This question is motivated by the fact that “empirical” knn functions are often used to summarize in an efficient way the information available on correlations in real networks [3]. It is also known that a linear behavior of knn for real assortative networks is quite frequent but only approximate. Especially for large values of the node degree k, the linear behavior is not maintained in practice, and one observes instead a decreasing tail in knn. This happens also because in real scale-free networks, the largest hubs are present but rare, and the Markovian-probabilistic approach is stretched to its limits of applicability.It can be shown through numerical simulations based on degree-preserving rewiring [12] that in a real assortative scale-free networks (even with high r), the large hubs cannot be connected to a sufficient number of other hubs so as to keep knn increasing for large k simply because many hubs have in principle a nonzero probability but are missing in a random concrete realization of the network. In such cases, using the Porto–Weber method to construct the full correlations starting from a realistic knn function is clearly the more correct recipe.


## 3. Differences in the Spectrum of the Connectivity Matrix

### 3.1. The Connectivity Matrix and Its Relation with the Epidemic Threshold

For a Markovian network with correlation matrixPh|k, the associated “connectivity matrix” is defined as follows [7, 8, 14]:(9)Ckh=kPh|k.This matrix plays an important role in studies of diffusion on networks. For instance, in the Homogeneous Mean Field approximation of the SI (Susceptible-Infected) epidemic model, the equation set which describes the behavior in time of the fractionρk of infected nodes with degree k is as follows (see [8]):(10)dρkdt=−ρk+1−ρkλ∑h=1nkPh|kρh,k=1,…,n.It can be generally shown that the solutions of this equation set are characterized by an “epidemic threshold”λc which separates different spreading scenarios: if λ>λc, the system reaches a stationary state with a finite fraction of infected population, while if λ<λc, the contagion dies out exponentially fast. The threshold λc turns out to be equal to 1/Λmax, where Λmax is the largest eigenvalue of the connectivity matrix C.


### 3.2. The Epidemic Threshold for Uncorrelated Scale-Free Networks

It is therefore important to know the largest eigenvalue of theC matrix, and a general result valid for scale-free networks [7, 8] states that this eigenvalue tends to +∞ when the size of the network grows. This means that for large scale-free networks, the epidemic threshold is essentially zero and the epidemics spreads and persists in the population also when the contagion probability is very small.In the absence of degree correlations (i.e., with uncorrelatedC, namely, CkhU=kPUh|k=khPh/k), it has been shown that(11)Λmax=k2k.For scale-free networks with scale exponent2<γ<3, k is finite when the maximum degree n tends to infinity, while k2 is divergent:(12)k2≃∫kminncγkγk2dk=k3−γ3−γkminn,where cγ is the normalization constant of the degree distribution Pk=cγ/kγ. The divergent part of (12) is of the form n3−γ; thus, limn⟶∞Λmax=+∞ for γ∈2,3. When γ=3, the limit is also infinite but only with slow divergence ∼lnn.


### 3.3. The Epidemic Threshold for the Assortative Networks of Vazquez–Weigt

It can be shown through general arguments that the divergence of the largest eigenvalueΛmax when n⟶∞ holds true independently from the degree correlations (see [4, 7]; see also some special cases in [12]). However, in the case of the diagonal assortative correlation matrices introduced by Vazquez and Weigt, a simple direct proof is possible, which is not yet available in the literature. Since for these correlations the assortativity level (expressed through the Newman coefficient r) is easily tunable in the range 0,1, the proof also has interesting consequences for the epidemic threshold in general.Figure 4
Behavior, as a function of the maximum degreen, of the largest eigenvalue Λmax of the connectivity matrix, with scale-free exponent γ=2.5. The two continuous lines represent the case of uncorrelated networks and networks with diagonal correlations of the Vazquez–Weigt kind and assortativity coefficient r=0.025. The dots represent the case of networks reconstructed with the Porto–Weber recipe from the knn function of the Vazquez–Weigt networks. Note that when n increases, the largest eigenvalue increases faster (linearly) for the Vazquez––Weigt networks than for uncorrelated networks even though the assortativity is very small. Also, for the Porto–Weber networks, the increase is faster than for uncorrelated networks, but it is less than linear, and this gets worse when γ increases (compare Figures 5 and 6).Figure 5
Behavior, as a function of the maximum degreen, of the largest eigenvalue Λmax of the connectivity matrix, with scale-free exponent γ=2.75. The case of γ=2.5 is compared in Figure 4.Figure 6
Behavior, as a function of the maximum degreen, of the largest eigenvalue Λmax of the connectivity matrix, with scale-free exponent γ=3. The cases of γ=2.5 in Figure 4 and γ=2.75 in Figure 5 are compared.The connectivity matrix associated toPVaz−Weih|k is(13)CkhVaz−Wei=1−rkhPhk+rkδkh.In order to compute its eigenvaluesΛi, we consider the determinant of the matrix C−ΛI, with elements(14)CkhVaz−Wei−Λδkh=1−rkhPhk+rk−Λδkh.It is immediate to note that whenrk−Λ=0, the determinant of this matrix is zero because the matrix khPh has rank 1. Thus, we immediately find the n eigenvalues as follows:(15)Λi=ri,i=1,…,n,the largest of them being Λmax=rn. When n⟶∞, this eigenvalue grows much faster than the largest eigenvalue for uncorrelated networks, especially if γ approaches 3. For large networks, even a small value of r like r=0.025 is sufficient for this to occur (see Figures 4–6).Reference [17] reports the results of numerical simulations which, in retrospect, can be understood as being referred to a similar case of small r. On the analytical side, however, no general treatment was given but only an approximated eigenvalue expansion valid for r close to 1.The conclusion is that for large scale-free networks, the presence of a small diagonal assortative correlation guarantees a quick convergence to zero of the epidemic threshold. We recall that according to the criterion by Dorogovtsev and Mendez [18], the relation between network size N (number of nodes) and maximum degree n is N∼nγ−1. Therefore, the behavior of Λmax is insensitive to γ as a function of n but not of N. Still, even for γ=3, the dependence of n on N is n∼N, which is fast compared with the very slow increase in Λmax in an uncorrelated network Λmax∼lnN.


### 3.4. Larger Values ofr

In the mathematical diffusion theory on scale-free networks, it is interesting to consider the correlation matrixPVaz−Wei in the limit of very small r because this shows the existence of networks which are practically uncorrelated but have an epidemic threshold converging to zero much more quickly than for purely uncorrelated networks. From the point of view of the “statistical mechanics of networks,” the set of these almost uncorrelated networks (say, with 0<r<ε, and ε small) is wider than the set of networks with r=0 exactly and can therefore be relevant in evaluations over statistical ensembles.On the other hand, as discussed in Section2.4, the alternative correlation matrix PPor−Web can improve the modeling of diffusion on real networks which display a knn function that is only approximately linear, especially at large k. For this purpose, it is also interesting to compare the largest eigenvalues of PVaz−Wei and PPor−Web for greater values of the assortativity coefficient r. Some results in this direction are reported in Table 1. The general trend is confirmed as follows: Λmax grows more quickly for PVaz−Wei.Table 1
Dependence of the largest eigenvalue of the connectivity matrix on the dimensionn (maximum degree) for some networks with assortativity index r not close to zero.
nΛUmaxΛPWVWmaxr=0.1ΛPWVWmaxr=0.21004.808.59 [10]13.8 [20]2005.9914.5 [20]25.5 [40]3006.8020.4 [30]36.9 [60]4007.4226.1 [40]48.3 [80]The networks considered in this table have scale-free exponentγ=2.75 and thus correspond to those of Figure 5 but with a larger r (for networks with exponents 2.5 and 3, the behavior is similar). The second column gives the maximum eigenvalue for an uncorrelated network, as reference. The third column gives the maximum eigenvalue computed numerically for Porto–Weber networks with r=0.1 reconstructed from a linear knn; in each bracket is reported the corresponding largest eigenvalue for the Vazquez–Weigt network with the same knn, which is exactly equal to rn. The fourth column gives the eigenvalues for r=0.2. For larger values of r, e.g., r=0.3, the Porto–Weber recipe cannot be applied since it produces some negative matrix elements. In general, one observes, like in the case of very small assortativity, that the fastest increase in the eigenvalues occurs with the Vazquez–Weigt networks.


## 3.1. The Connectivity Matrix and Its Relation with the Epidemic Threshold

For a Markovian network with correlation matrixPh|k, the associated “connectivity matrix” is defined as follows [7, 8, 14]:(9)Ckh=kPh|k.This matrix plays an important role in studies of diffusion on networks. For instance, in the Homogeneous Mean Field approximation of the SI (Susceptible-Infected) epidemic model, the equation set which describes the behavior in time of the fractionρk of infected nodes with degree k is as follows (see [8]):(10)dρkdt=−ρk+1−ρkλ∑h=1nkPh|kρh,k=1,…,n.It can be generally shown that the solutions of this equation set are characterized by an “epidemic threshold”λc which separates different spreading scenarios: if λ>λc, the system reaches a stationary state with a finite fraction of infected population, while if λ<λc, the contagion dies out exponentially fast. The threshold λc turns out to be equal to 1/Λmax, where Λmax is the largest eigenvalue of the connectivity matrix C.


## 3.2. The Epidemic Threshold for Uncorrelated Scale-Free Networks

It is therefore important to know the largest eigenvalue of theC matrix, and a general result valid for scale-free networks [7, 8] states that this eigenvalue tends to +∞ when the size of the network grows. This means that for large scale-free networks, the epidemic threshold is essentially zero and the epidemics spreads and persists in the population also when the contagion probability is very small.In the absence of degree correlations (i.e., with uncorrelatedC, namely, CkhU=kPUh|k=khPh/k), it has been shown that(11)Λmax=k2k.For scale-free networks with scale exponent2<γ<3, k is finite when the maximum degree n tends to infinity, while k2 is divergent:(12)k2≃∫kminncγkγk2dk=k3−γ3−γkminn,where cγ is the normalization constant of the degree distribution Pk=cγ/kγ. The divergent part of (12) is of the form n3−γ; thus, limn⟶∞Λmax=+∞ for γ∈2,3. When γ=3, the limit is also infinite but only with slow divergence ∼lnn.


## 3.3. The Epidemic Threshold for the Assortative Networks of Vazquez–Weigt

It can be shown through general arguments that the divergence of the largest eigenvalueΛmax when n⟶∞ holds true independently from the degree correlations (see [4, 7]; see also some special cases in [12]). However, in the case of the diagonal assortative correlation matrices introduced by Vazquez and Weigt, a simple direct proof is possible, which is not yet available in the literature. Since for these correlations the assortativity level (expressed through the Newman coefficient r) is easily tunable in the range 0,1, the proof also has interesting consequences for the epidemic threshold in general.Figure 4
Behavior, as a function of the maximum degreen, of the largest eigenvalue Λmax of the connectivity matrix, with scale-free exponent γ=2.5. The two continuous lines represent the case of uncorrelated networks and networks with diagonal correlations of the Vazquez–Weigt kind and assortativity coefficient r=0.025. The dots represent the case of networks reconstructed with the Porto–Weber recipe from the knn function of the Vazquez–Weigt networks. Note that when n increases, the largest eigenvalue increases faster (linearly) for the Vazquez––Weigt networks than for uncorrelated networks even though the assortativity is very small. Also, for the Porto–Weber networks, the increase is faster than for uncorrelated networks, but it is less than linear, and this gets worse when γ increases (compare Figures 5 and 6).Figure 5
Behavior, as a function of the maximum degreen, of the largest eigenvalue Λmax of the connectivity matrix, with scale-free exponent γ=2.75. The case of γ=2.5 is compared in Figure 4.Figure 6
Behavior, as a function of the maximum degreen, of the largest eigenvalue Λmax of the connectivity matrix, with scale-free exponent γ=3. The cases of γ=2.5 in Figure 4 and γ=2.75 in Figure 5 are compared.The connectivity matrix associated toPVaz−Weih|k is(13)CkhVaz−Wei=1−rkhPhk+rkδkh.In order to compute its eigenvaluesΛi, we consider the determinant of the matrix C−ΛI, with elements(14)CkhVaz−Wei−Λδkh=1−rkhPhk+rk−Λδkh.It is immediate to note that whenrk−Λ=0, the determinant of this matrix is zero because the matrix khPh has rank 1. Thus, we immediately find the n eigenvalues as follows:(15)Λi=ri,i=1,…,n,the largest of them being Λmax=rn. When n⟶∞, this eigenvalue grows much faster than the largest eigenvalue for uncorrelated networks, especially if γ approaches 3. For large networks, even a small value of r like r=0.025 is sufficient for this to occur (see Figures 4–6).Reference [17] reports the results of numerical simulations which, in retrospect, can be understood as being referred to a similar case of small r. On the analytical side, however, no general treatment was given but only an approximated eigenvalue expansion valid for r close to 1.The conclusion is that for large scale-free networks, the presence of a small diagonal assortative correlation guarantees a quick convergence to zero of the epidemic threshold. We recall that according to the criterion by Dorogovtsev and Mendez [18], the relation between network size N (number of nodes) and maximum degree n is N∼nγ−1. Therefore, the behavior of Λmax is insensitive to γ as a function of n but not of N. Still, even for γ=3, the dependence of n on N is n∼N, which is fast compared with the very slow increase in Λmax in an uncorrelated network Λmax∼lnN.


## 3.4. Larger Values ofr

In the mathematical diffusion theory on scale-free networks, it is interesting to consider the correlation matrixPVaz−Wei in the limit of very small r because this shows the existence of networks which are practically uncorrelated but have an epidemic threshold converging to zero much more quickly than for purely uncorrelated networks. From the point of view of the “statistical mechanics of networks,” the set of these almost uncorrelated networks (say, with 0<r<ε, and ε small) is wider than the set of networks with r=0 exactly and can therefore be relevant in evaluations over statistical ensembles.On the other hand, as discussed in Section2.4, the alternative correlation matrix PPor−Web can improve the modeling of diffusion on real networks which display a knn function that is only approximately linear, especially at large k. For this purpose, it is also interesting to compare the largest eigenvalues of PVaz−Wei and PPor−Web for greater values of the assortativity coefficient r. Some results in this direction are reported in Table 1. The general trend is confirmed as follows: Λmax grows more quickly for PVaz−Wei.Table 1
Dependence of the largest eigenvalue of the connectivity matrix on the dimensionn (maximum degree) for some networks with assortativity index r not close to zero.
nΛUmaxΛPWVWmaxr=0.1ΛPWVWmaxr=0.21004.808.59 [10]13.8 [20]2005.9914.5 [20]25.5 [40]3006.8020.4 [30]36.9 [60]4007.4226.1 [40]48.3 [80]The networks considered in this table have scale-free exponentγ=2.75 and thus correspond to those of Figure 5 but with a larger r (for networks with exponents 2.5 and 3, the behavior is similar). The second column gives the maximum eigenvalue for an uncorrelated network, as reference. The third column gives the maximum eigenvalue computed numerically for Porto–Weber networks with r=0.1 reconstructed from a linear knn; in each bracket is reported the corresponding largest eigenvalue for the Vazquez–Weigt network with the same knn, which is exactly equal to rn. The fourth column gives the eigenvalues for r=0.2. For larger values of r, e.g., r=0.3, the Porto–Weber recipe cannot be applied since it produces some negative matrix elements. In general, one observes, like in the case of very small assortativity, that the fastest increase in the eigenvalues occurs with the Vazquez–Weigt networks.


## 4. Examples of Variations of a MatrixPh|k Which Do Not Modify Its Average Nearest Neighbor Degree Function knn

In this section, we explore the more general question relative to multiplicity and concrete construction of variations of a correlation matrixPh|k which do not modify the average nearest neighbor degree function knn. If such a variation is represented as(16)Ph|k⟶Ph|k+Φh,k,then the elements Φh,k with h,k=1,…,n are required to(1)
Satisfy the Network Closure Condition (in this case, also the elementsPh|k+Φh,k do it as one can easily check);(2)
Satisfy the normalization according to which∑hPh|k+Φh,k=1 (for each k, the elements Ph|k+Φh,k give the probabilities that a vertex with degree k is connected to a vertex with degree h), which becomes in this case(17)∑hΦh,k=0,k=1,…,n,(3)
Leaveknn unchanged which only occurs when(18)∑hhΦh,k=0,k=1,…,n,holds true.In addition, the inequalities(19)Ph|k+Φh,k≥0,for allh,k=1,…,n,must hold true.To obtain condition (1), we start and assume, on the trail of Porto and Weber,(20)Φh,k=hphkϕh,k,where ϕh,k is a symmetric matrix. Notice that from now on we will write ph=Ph for the sake of brevity. Moreover, we will assume that each ph (for h=1,…,n) is different from zero. The two conditions (2) and (3) then take the form(21)∑hhphϕh,k=0for allk=1,…,n∑hh2phϕh,k=0for allk=1,…,n.We will first look for matricesϕ=ϕh,k which satisfy (9) and only afterwards, in connection with some specific Ph|k, will we check and specify when inequality (9) is satisfied too.We narrow our search to the family ofn×n symmetric matrices ϕ, whose only nonzero elements are, together with ϕ1,n and ϕn,1, those on the main diagonal and those on the first diagonal below and on the first diagonal above the main diagonal:(22)ϕ=ϕ1,1ϕ1,2000…0000ϕ1,nϕ1,2ϕ2,2ϕ2,300…000000ϕ2,3ϕ3,3ϕ3,40…00000……………………………00000…00ϕn−1,n−2ϕn−1,n−1ϕn−1,nϕ1,n0000…000ϕn−1,nϕn,n.For any such matrixϕ, solving system (9) amounts to solve a linear system of 2n equations in 2n variables (recall that ϕ is symmetric):(23)p1ϕ1,1+2p2ϕ1,2+npnϕ1,n=0p1ϕ1,1+2p2ϕ2,2+3p3ϕ2,3=02p2ϕ2,3+3p3ϕ3,3+4p4ϕ3,4=0……n−2pn−2ϕn−2,n−1+n−1pn−1ϕn−1,n−1+npnϕn−1,n=0p1ϕ1,n+n−1pn−1ϕn−1,n+npnϕn,n=0p1ϕ1,1+4p2ϕ1,2+n2pnϕ1,n=0p1ϕ1,1+4p2ϕ2,2+9p3ϕ2,3=04p2ϕ2,3+9p3ϕ3,3+16p4ϕ3,4=0……n−22pn−2ϕn−2,n−1+n−12pn−1ϕn−1,n−1+n2pnϕn−1,n=0p1ϕ1,n+n−12pn−1ϕn−1,n+n2pnϕn,n=0.We rewrite this system as(24)Mx=0,where the matrix M (also denoted by M=Mn) is given by(25)M=p100⋯002p200…0npn02p20…00p13p30…00003p3…0002p24p4…00……………………………⋯000…n−1pn−1000……npn0000…0npn00…0n−1pn−1p1p100…004p20000n2pn04p20…00p19p30…00009p3…0004p216p4…00………………………………000…n−12pn−1000……n2pn0000…0n2pn000…n−12pn−1p1,the unknown vector x is ordered as x=ϕ1,1,ϕ2,2,ϕ3,3,…,ϕn,n,ϕ1,2,ϕ2,3,ϕ3,4,…ϕn−1,n,ϕ1,n, and 0 is the vector with all 2n components equal to zero.It can be seen that, if eachph (for h=1,…,n) is different from zero, the matrix M has determinant zero whereas its rank is equal to 2n−1. Below, we first work out the calculations for the case n=4, which is the smallest positive integer for which the particular structure of the matrix ϕ is clearly recognisable. Then, we describe the procedure to handle the case with general n.Denote byM4 the matrix M with n=4.Proposition 1.
The8×8 matrix M4 has determinant equal to zero and rank equal to seven.Proof.
The matrixM4 has the form(26)M4=p10002p2004p402p200p13p300003p3002p24p400004p4003p3p1p10004p20016p404p200p19p300009p3004p216p4000016p4009p3p1.
By substituting the 5-th row with that obtained as the difference of the 5-th row minus the first row, we get a matrix, whose determinant is easily seen to be equal to(27)detM4=p1×detM4,7×7,where(28)M4,7×7=2p200p13p30003p3002p24p40004p4003p3p10002p20012p44p200p19p30009p3004p216p400016p4009p3p1.
By substituting the 5-th row with that obtained as the difference of the 5-th row minus 2 times the first row, we get a matrix, whose determinant is easily seen to be equal to(29)detM4,7×7=2p2×detM4,6×6,where(30)M4,6×6=3p3002p24p4004p4003p3p1002p20012p400−p13p3009p3004p216p40016p4009p3p1.
With two similar further steps (i.e., iteratively suitably substituting the 5-th row of a matrix), one easily finds that(31)detM4=p1×2p2×3p3×4p4×detM4,4×4,where(32)M4,4×4=2p20012p4−p13p3000−2p24p4000−3p3−3p1.
The Laplace expansion ofdetM4,4×4, iteratively applied, gives(33)2p2−3p13p34p4+−112p4−p1−2p2−3p3=0,which in turn implies that detM4=0.
In view of (31), in order to conclude that the rank of M4 is equal to seven; it is sufficient to prove that rankM4,4×4=3. And this can be immediately seen because, for example, the minor corresponding to the determinant of the triangular 3×3 matrix(34)2p200−p13p300−2p24p4,is different from zero (being pj≠0 for all indices j=1,…,n by assumption).
The proof strategy can be generalised for the case of the2n×2n matrix M leading to the following result.Proposition 2.
For the2n×2n matrix M, it is detM=0 and rankM=2n−1.Proof.
By performingn times a procedure similar to that in the proof of the previous proposition, namely,(i)
Step 1: substituting then+1-th row of the matrix M with that obtained as the difference of the n+1-th row minus the first row(ii)
Step 2: substituting then+1-th row of the 2n−1×2n−1 matrix M2n−1×2n−1 obtained after elimination of the first row and the first column from the matrix resulting from the previous step with that obtained as the difference of the n+1-th row minus 2 times the first row(iii)
…(iv)
stepn: substituting the n+1-th row of the n+1×n+1 matrix Mn+1×n+1 obtained after elimination of the first row and the first column from the matrix resulting from the previous step with that obtained as the difference of the n+1-th row minus n times the first rowone finds that(35)detM=p1×2p2×⋯×npn×detMn×n,where(36)Mn×n=2p200…00n2−npn−p13p30…0000−2p24p4…000…………………000…n−1pn−100000…−n−2pn−2npn0000…0−n−1pn−1−n−1p1.
The determinantdetMn×n can be calculated by iteratively applying the Laplace expansion. It is not difficult to convince oneself that(37)detMn×n=2p23p3,…,npn−n−1p1+−1n+1n2−npn−1n+1p12p2,…,n−1pn−1=p12p2,…,n−1pn−1−n2pn+npn+n2pn−npn=0.
Together, (35) and (37) imply that detM=0.
It only remains to be proved that the rank ofM is equal to 2n−1. Also here, similarly as in the proof of Proposition 1, we observe that the n−1×n−1 matrix obtained by deleting the last row and the last column in Mn×n has determinant equal to p12p2,…,npn≠0. Hence, rankMn×n=n−1 and, together with (35), this completes the proof.
Proposition2 implies that the eigenspace of M is one-dimensional, and this in turn means that equation (24) admits infinitely many solutions; precisely, there is a one-parameter family of them. By way of example, let us consider the following low-dimensional case.Example 1.
Letn=4 and let a Markovian network N4 with degree distribution Ph and correlation matrix Ph|k be given. Assume that ph=Ph≠0 for h=1,…,n. The function knn pertaining to N4 is also the average nearest neighbor degree of the networks which have the same degree distribution ph as N4 and correlation matrix of the form Ph|k+hph/kϕh,k, the only nonzero elements of the symmetric matrix ϕh,k being(38)ϕ1,1,ϕ2,2=3p124p22ϕ1,1,ϕ3,3=p123p32ϕ1,1,ϕ4,4=p1216p42ϕ1,1,ϕ1,2=−3p14p2ϕ1,1,ϕ2,3=−p124p2p3ϕ1,1,ϕ3,4=−p128p3p4ϕ1,1,ϕ1,4=p18p4ϕ1,1,all of them expressed in terms of a unique parameter ϕ1,1, together with those symmetrically positioned with respect to the main diagonal, provided the inequalities(39)ϕh,k≥−khphPh|k,for allh,k=1,…,n,are satisfied.
We recall here thatPh|k≥0 for all h,k=1,…,n. Therefore, the inequalities to be checked are in fact those relative to the nonzero elements ϕh,k. In this example n=4, they can be expressed as(40)ϕh,h≥−jhphPh|h,for allh=1,…,4,ϕ1,2≥max−jp1P1|2,−j2p2P2|1,ϕ2,3≥max−j2p2P2|3,−j3p3P3|2,ϕ3,4≥max−j3p3P3|4.−j4p4P4|3,ϕ1,4≥max−jp1P1|4,−j4p4P4|1.
Explicit treatment of an example requires fixing both the values of the elements of the degree distributionph and correlation matrix Ph|k. We here consider three cases, each of them relative to a scale-free network with ph=c/hγ, where γ∈2,3, and Ph|k is constructed according to the following algorithms (see [12, 19]):(i)
Case 1.We define P0h|k as follows: for h<k, P0h|k=h−k−1, for h=k, P0h|k=1, and(41)P0h|k=P0k|hh1−γk1−γ,ifh>k.CallCk=∑h=1nP0h|k for any k=1,…,n and let Cmax=maxk=1,…,nCk. Then, redefine the correlation matrix by setting the elements on the diagonal equal to(42)P1k|k=Cmax−Ck,k=1,…,n,and leaving the other elements unchanged:P1h|k=P0h|k for h≠k. Finally, normalize the entire matrix by setting(43)Ph|k=1Cmax−1P1h|k,h,k=1,…,n.(ii)
Case 2. Let P0h|k=1−1/Nh−k if h≤k and P0h|k with h>k as in (41). Then, proceed as in the previous case to get elements Ph|k which satisfy the normalization ∑h=1nPh|k=1.(iii)
Case 3. Let P0h|k=e−h−k2/n2 if h≤k and P0h|k with h>k as in (41). Again, proceed as above to get elements Ph|k which satisfy the normalization ∑h=1nPh|k=1.Straightforward calculations (performed with Mathematica) yield, for example, that inequalities (40) are satisfied in the following situations:In Case 1, withγ=2.1, provided 0≤ϕ1,1≤0.12908 holds trueIn Case 1, withγ=2.5, provided 0≤ϕ1,1≤0.06478 holds trueIn Case 1, withγ=2.9, provided 0≤ϕ1,1≤0.03369 holds trueIn Case 2, withγ=2.1, provided 0≤ϕ1,1≤0.12010 holds trueIn Case 2, withγ=2.5, provided 0≤ϕ1,1≤0.06012 holds trueIn Case 2, withγ=2.9, provided 0≤ϕ1,1≤0.03119 holds trueIn Case 3, withγ=2.1, provided 0≤ϕ1,1≤0.11247 holds trueIn Case 3, withγ=2.5, provided 0≤ϕ1,1≤0.05618holds trueIn Case 3, withγ=2.9, provided 0≤ϕ1,1≤0.02876 holds trueWhen calculating the connectivity matrixCk,h in correspondence to correlations Ph|k and then also in correspondence to correlations Ph|k+Φh,k in the Cases 1,2,and3 above, for γ=2.1,2.5,2.9 and (various) values of ϕ1,1 compatible with the intervals just found, one observes what follows. In passing from Ph|k to Ph|k+Φh,k (namely, by taking an admissibile positive ϕ1,1 rather than ϕ1,1=0), in all Cases, 1, 2, and 3, the largest eigenvalue of Ck,h increases (and, accordingly, the epidemic threshold decreases).In contrast, if one takes an uncorrelated network, by this meaning a network for which(iv)
Case 4.Ph|k=hPh/k,and considers then the matrixPh|k+Φh,k with elements Φh,k constructed according to (20) and (22), one notices the following fact: the largest eigenvalue of the connectivity matrix Ck,h remains equal to k2/k when the parameter ϕ1,1 varies in the interval which guarantees the meaningfulness of the variation −0.01234<ϕ1,1<0.01603. A subtle and interesting situation is taking place: on the one hand, for networks constructed considering the elements Ph|k+Φh,k as done here, it is no more true that the conditional probability that a vertex of degree k is connected to a vertex of degree h which is independent of k; on the other hand, the average nearest neighbor degree function knnk of these networks is the same of that of a strictly uncorrelated network; it is constant (and equal to k2/k, coinciding with knnk of the original uncorrelated network).Remark 1.
Beside the choice of taking symmetric matricesϕ as in (22), other choices can be performed. They lead both to cases in which the largest eigenvalue of the connectivity matrix in correspondence to the matrix Ph|k+Φh,k is greater than the one obtained in correspondence to the matrix Ph|k as to cases in which this eigenvalue is smaller.
In any case, one can conclude that networks with the sameknn but different correlation matrices can exhibit different epidemic thresholds.



---

*Source: 7704586-2021-10-08.xml*