Influence of reciprocal edges on degree distribution and degree correlations

Reciprocal edges represent the lowest-order cycle possible to find in directed graphs without self-loops. Representing also a measure of feedback between vertices, it is interesting to understand how reciprocal edges influence other properties of complex networks. In this paper, we focus on the influence of reciprocal edges on vertex degree distribution and degree correlations. We show that there is a fundamental difference between properties observed on the static network compared to the properties of networks, which are obtained by simple evolution mechanism driven by reciprocity. We also present a way to statistically infer the portion of reciprocal edges, which can be explained as a consequence of feedback process on the static network. In the rest of the paper, the influence of reciprocal edges on a model of growing network is also presented. It is shown that our model of growing network nicely interpolates between Barabási-Albert (BA) model for undirected and the BA model for directed networks.

Figure 1

(Color online) In this figure, we present an excellent agreement between simulations of transformation process and our semianalytical treatment. On $x$ coordinate is parameter $p$, which represents the probability of edge transformation. The $y$-coordinate represents the ratio of the numerical value of the given correlations and the maximum value of that correlation, in such a way that we can present the correlations with very different magnitudes in the same figure. With $E(\cdot )$ are designated expectations calculated from equations similar to Eqs. (20, 21), as an input we used the measured correlations in the network before the start of the process. Simulations are designated with $⟨\cdot ⟩$. The initial networks we used for this figure are a Barabási-Albert directed network of ${10}^5$ vertices for the case of one-vertex degree correlations and for the correlations of unidirectionally connected vertices and a Spanish Wikipedia for the case of the degree correlations of bidirectionally connected vertices. The simulations are averaged over 1000 realizations of the process in the case of a directed BA networks and over 100 realizations in the case of the Spanish Wikipedia. It can be seen that the expected values of degree correlations between the bidirectionally connected vertices deviate a bit from simulational results, which is probably a consequence of approximation (16).

Figure 2

(Color online) The correlations $⟨k_r^{\prime }{q}_o^{\prime }|\to ⟩$ resulting from the transformation process compared with the expected correlations of configuration model ${⟨k_r^{\prime }{q}_o^{\prime }|\to ⟩}_{Rand}=\frac{⟨k_r{k}_o⟩⟨k_i{k}_o⟩}{{⟨k_o⟩}^2}$. In this case, the transformation process clearly amplifies observed degree correlations.

Figure 3

(Color online) The event-set lattice used to calculate the stable distribution. The borders of the lattice segment in which paths contribute to the probability are designated with cyan color. Dashed red designates one of the possible paths and arrows represent the possible directions of paths.

Figure 4

(Color online) In this figure, it can be seen that the agreement between distributions of in degrees of the process simulated over 100 different realizations (markers) and the analytical solution (full line). The parameter $r$ has the value of 0.2.

Figure 5

(Color online) The lattice used to calculate the stable distribution of the model for the parameter $m=4$. Cyan color designates the borders of the lattice area within which the paths contribute to the joint probability $P\left(k_i=7,k_o=8\right)$, while the dashed red path represents one of the possible contributing paths. Arrows represent the allowed directions of movement on the lattice, while the loops on the sites represent the additional coefficients $a_l$ contributing to the joint degree probability on these sites.

Figure 6

(Color online) The marginal distribution of the in degree calculated from theory (full line) and simulations (markers), for three different sizes of final networks. The averaging was performed over 100 simulation realizations and parameters used are $r=0.15$ and $m=18$. There is an excellent agreement between theory and simulations.

Figure 7

(Color online) The marginal distribution of the in degree calculated from the theory for $m=10$ and different values of parameter $r$. The tail of distribution clearly depends on the parameter $r$ and the power-law character of the tail is easily checked. The shape and the position of the mode also depend on the value of $r$.

Figure 8

(Color online) The marginal distribution of the in degree calculated from the theory for $r=0.4$ and different values of parameter $m$. The existence and the position of the mode strongly depend on the value of parameter $m$. The tail of distribution is independent of the parameter $m$ and the power-law character of the tail is easily checked.

Figure 9

(Color online) In this figure, we present cumulative in-degree distributions for the different choices of the initial out-degree distribution of the vertex introduce at time $t$. The simulations are presented for the parameters $m=10$, $r=0.2$, $N={10}^6$, and 100 realizations. It is clear that different choices of out-degree distributions for the new vertices do not change the general behavior of the in-degree distribution. The broader distributions of initial out degree result with a lower maximal degree, which we explain by a stronger competition for the new vertices.