{'fraction_non_alphanumeric': 0.03607314832855513, 'fraction_numerical': 0.01024299273526874, 'mean_word_length': 4.342453531598513, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Hierarchy in directed random networks

In recent years, the theory and application of complex networks have been quickly developing in a markable way due to the increasing amount of data from real systems and to the fruitful application of powerful methods used in statistical physics. Many important characteristics of social or biological systems can be described by the study of their underlying structure of interactions. Hierarchy is one of these features that can be formulated in the language of networks. In this paper we present some (qualitative) analytic results on the hierarchical properties of random network models with zero correlations and also investigate, mainly numerically, the effects of different type of correlations. The behavior of hierarchy is different in the absence and the presence of the giant components. We show that the hierarchical structure can be drastically different if there are one-point correlations in the network. We also show numerical results suggesting that hierarchy does not change monotonously with the correlations and there is an optimal level of non-zero correlations maximizing the level of hierarchy.


Introduction
The application of complex networks in a broad range of social and biological systems has been the subject of much interest recently [1][2][3][4][5]. These applications involve -among others -the description of "small-world" property of the networks [6] or the consequences of scale-free degree distributions [7]. Many aspects of the real systems can be studied in the framework of undirected networks [8][9][10][11]. The most important property of the network is the degree distribution p k which is the probability of a randomly chosen node having k edges [7]. Other features of the network can be understood through the degree distribution (average length of the shortest path between nodes, average number of edges between a node's neighbors [12], the characteristics of epidemics on the network [10] or robustness against failures and attacks [13]).
However, most of the real networks are directed, i.e., the connection between two units of the system is not symmetric. Many structural properties of a directed network can be derived from undirected networks in a straightforward way [8], but the appearance of directionality also opens the door to features that are essentially different from those in undirected graphs (Fig. 1). In the presence of directed edges, the organization level of the nodes on a large scale can be very complex and flow hierarchy can emerge. It is a global structure of the network that is the result of the different roles of the nodes (see Fig. 2 for the comparison of different hierarchy types). As the growing number of findings show, hierarchy is a frequently appearing property of real networks, especially of networks describing social interactions [17][18][19][20][21]. The concept of hierarchy has led to different definitions ( Fig. 2) and also to algorithms for measuring it in both directed and undirected networks [22][23][24][25][26][27]. In this paper we investigate flow hierarchy by a corresponding measure, the global reaching centrality (GRC), that has the intention to quantify that [28]. In the following sections we show that the behavior of the GRC is different below and above the critical average degree k c , i.e., in the absence and presence of the giant components. We also give an approximation to its dependence on the average degree for different random network models when there are no degree correlations. In the last section we study the effects of degree correlations.  Figure 1: The difference between undirected (a) and directed (b) graphs. On large scale, the structure of the undirected graph (c) can be described by the largest connected component (the giant component or GC) and the small components (SC) [14]. In the case of a directed graph (d), the giant components are best summarized in the "bow-tie" diagram [15,16]: the primary core is the giant strongly connected component (GSCC). Inside the GSCC, every node can reach every other. There are nodes that can reach the whole GSCC but not vice verse (IN) and together with the GSCC they form the giant in component (GIN). The similar is true for the giant out component (GOUT) but in the reversed direction. There are nodes that connect the GIN and GOUT components but are not in the GSCC, they form the tubes. There are also tendrils that attach to the GIN and GOUT components. The rest of the nodes are in the small disconnected components (DC).  In a (complete) flow hierarchy, nodes can be layered in different levels so that the nodes that are influenced by other nodes (via an out-edge) are at lower levels. As the figures illustrate, each type can be transformed into a flow hierarchy. In the order hierarchy one can introduce a directed edge between every pair of adjacent nodes in the hierarchy. In the nested hierarchy one can assign a virtual node to each cluster and link a cluster to its contained clusters.
2 Reaching centralities in uncorrelated random networks 2.1 Local and global reaching centrality Given a directed graph G(V, E) with N = |V | vertices and M = |E| edges, the local reaching centrality of node i is defined as the number of reachable nodes via out-degrees divided by the total number of nodes: is the set of nodes that has finite, non-zero outdistance from node i. We will denote the size of the reachable set (i.e., the local reaching centrality without normalization) by C R . The global reaching centrality of the graph is the normalized sum of the distances from the maximum local reaching centrality: The normalization factor is the maximum possible value of the sum in a graph with N nodes (this can be achieved in a star graph). The definition of the GRC can be written in a more expressive form: Hence, the GRC is proportional to the difference between the average and the maximum size of the reachable sets.

Generating function method in directed networks
The calculation of the reachable set of a node is equivalent to the problem of finding the out-component, which is the union of the reachable set and the node itself. The outcomponent can be determined by the generalization of the generating function formalism developed by Newman et al. [8,12] to directed networks. Assuming that our graph has joint degree distribution p ij , that is the probability of a randomly chosen node having i in-degree and j out-degree, the corresponding double generating function can be defined as and the generating functions for the excess in-and out-degree distributions [8]: Let π out s denote the probability that a randomly chosen node has out-component of size s and ρ out s the probability that a randomly chosen edge points to an out-component of size s. Their generating functions are: If we assume that the graph is locally tree-like (i.e., loops are infrequent), they satisfy the following equations [8]: Using these equations for the generating functions, it is possible to derive a closed formula for the out-components in directed graphs (for the details see Appendix A): Thus, if we know the joint degree distribution, we can calculate P (C R ) (and thus the distribution of the local reaching centralities as well, since it differs from P (C R ) only by a scale factor). In order to calculate P (C R ), we have to determine the out-components and apply the s = C R + 1 substitution. With the knowledge on P (C R ), we are able to calculate the GRC at different average degrees.
Before applying these equations to random networks with different degree distributions, we determine the GRC for the case of a hierarchical tree.

Hierarchical tree 2.3.1 Local reaching centralities
In a tree graph with N vertices and branching number of d, nodes in the same level have the same local reaching centrality. Let us denote the size of reachable set of a node in the ℓ-th level by C (ℓ) R . The number of nodes and the size of the reachable set in the ℓ-th level are the following (see Fig. 3): The probability that a randomly chosen node has a reachable set of size C (ℓ) R is k ℓ /N. Substituting Eq. (12) in Eq. (13) gives: In the asymptotic limit of N → ∞, we get the following approximation for the probability of the normalized local reaching centrality (we also omit the ℓ index, since in the mentioned limit, the allowed discrete values of C Comparison with numerical results is plotted in Fig. 4. In the simulations, the number of nodes were 10 4 and thus Eq. (12) and (13) do not hold for every level. The number of nodes in the lowermost level is smaller than d ℓ which causes a smaller relative frequency for small local reaching centralities. An other effect is that the nodes below the topmost node have smaller reachable sets, shifting the corresponding points to the left (to smaller reaching centralities). The appearance of individual nodes with c R values other than the allowed values (as in Eq. (13)) is also the artifact of the number of nodes. Besides these differences, the theoretical distribution is qualitatively descriptive.

Global reaching centrality
Using the equations for the number of nodes and size of reachable sets in the ℓ-th level, we can easily calculate the size of the reachable sets: where L denotes the number of levels (the level of the root is zero). This number can be determined by the constraint that the sum of the nodes in all levels gives the number of nodes: Arranging for L and simplifying it: Calculating the sum in the right hand side of Eq. (16) gives: Substituting L into the last equation and using Eq. (3) we get: In the asymptotic case of N → ∞: In

Erdős-Rényi graph 2.4.1 Local reaching centralities
In the case of uncorrelated in-and out-degrees, the joint degree distribution of an Erdős-Rényi (ER) graph [14,29] is the product of two independent Poisson distributions: where k denotes the average degree. The double generating function has the form: which is also the generating function of the excess degree distributions in this case. Now, using Eq. (11) we get: And for the size of reachable set: Fig. 6 shows this result compared with the numerical distributions. It is important to understand the limits of Eq. (25). It is only the distribution for the size of the small reachable sets, i.e., it does not contain the GSCC 1 . This can be seen on the plots. Before the transition, all of the nodes are in separated small components and the reaching centrality distribution vanishes very quickly. Above the transition point, they start to aggregate in the GSCC. Note that in this regime, where the giant component appears, a large amount of nodes have a large reachable set. More precisely, the nodes in the GIN component can reach every node in GOUT. The distribution of the local reaching centralities becomes more and more a delta function at c R ≈ 1.

Relative frequency
Size of reachable set Theoretical, 〈k〉 = 1.3 Figure 6: Distribution of the reachable set sizes for the ER graph, based on the assumption that the graph is locally tree-like. Below the transition point, there is no node that can reach any finite part of the graph. This changes when the GSCC appears at k = 1.
The numerical results are the averages of 1000 independent calculations on networks with N = 10 4 . Note that Eq. (25) describes the distribution of the small components, thus the emerging GSCC (the peak at large reachable sets) is out of its scope.

Global reaching centrality
We have to distinguish between the graph without the GSCC and with the GSCC [8].
Below the transition point k c , there are only small components. All of the nodes can reach only infinitesimal part in the graph, thus having an average reachable set size of order unit ( C R = O(1)). In this regime, the GRC is dominated by the maximum value of the local reaching centrality. Since most of the nodes can reach very few other nodes and the distribution vanishes quickly, we can assume that the largest reachable set belongs to only one node (and that the corresponding out-component has the smallest relative frequency). Given a graph with N nodes, this condition translates as P ( Thus, finding the reachable set size that has only one realization can lead us to find the largest component. In the C max R ≫ 1 limit we can use the Stirling-formula to approximate P (C R ): Writing the P (C R ) ≈ 1/N condition and rearranging it for C R we get the following exponential equation: This equation can be solved in terms of the Lambert W function [30]. The equation of the form has the solution of so the final expression for the largest local reaching centrality: Now we turn our attention to the case when the GSCC is already present. In this case, for a good approximation, we can ignore those nodes that are not in the bow-tie (they are relevant only in the average local reaching centrality, but they have only an infinitesimal contribution). Thinking of the "bow-tie" picture, we can assume that there are some nodes that can reach the whole bow-tie. Thus, C max R ≈ |GIN| + |GOUT| − |GSCC|. The average is slightly different and nontrivial, but let assume that it is equivalent to the size of the giant out-component GOUT. If we assume that most of the nodes are gathering in the GSCC, it is also reasonable that the average size of reachable sets is dominated by the nodes in the GSCC and they can reach the whole GOUT component (see Fig. 1d). Using these assumptions, the size of the reachable sets is approximately |GOUT|. The relative sizes of these components are quite the same as the local reaching centrality. In the generating function formalism they are given by: where u and v are the smallest non-zero solutions of the following equations [8]: Since the generating function is symmetrical in its variables, we have u = v. Using Eq. (23), the solution can be written in terms of the Lambert W function giving: And for the GRC above the phase transition: The theoretical curve and the measurements are shown in Fig. 7. The theoretical curve in the k c < k < 2 range is a little below the numerical results. This is in good accordance with the assumptions used in deriving Eq. (39): the average reachable set is approximated by the GOUT component, however at small average degrees, there are many small outcomponents that decrease the average. The relative sizes of the giant components are depicted on Fig. 8. It is clearly seen that near the critical average degree, an appreciable portion of the nodes is outside of the giant components and they all have very small reachable set. Thus, the difference between the largest and average reaching centrality is larger in the real network, resulting in a larger GRC. The theoretical curve below k c predicts lower GRC, which indicates that the distribution of P (C R ) described by Eq. (25) is no more valid for the whole network when approaching the critical average degree.   (Fig. 1d). Although GOUT grows quickly with the average degree, at low edge densities ( k < 2) both component contain less than 80% of the nodes.

Exponential network 2.5.1 Local reaching centralities
In this section we calculate P (C R ) and the GRC for the exponential network, motivated by the finding that the distribution of many real world networks can be well fitted by an exponential [31]. An uncorrelated exponential network has joint degree distribution of the form where the average degree can be obtained from the κ parameter: k = (e 1/κ − 1) −1 . The double generating function and its derivatives are: By the formula for the out-components we have: Substituting e 1/κ = k +1 k we get: Translating this to the reachable set (see Fig. 9 for comparison with numerical calculations):

Global reaching centrality
The first task is to find the smallest solution of the u = g 01 (u, 1) and v = g 10 (1, v) equations. Since we assumed uncorrelated exponential distributions, we have u = v. The equation is quadratic in u and has two solutions: u 1 = 1 and u 2 = 1/ k , thus for k < 1 there are no giant components and we can use the "rarest component" assumption as before with the ER graph. For this to do, we have to solve the following equation for C R : Using the Stirling-formula (without going into the details), this equation can be approximated by the following: We assume that the rarest component is much larger than one, thus C R +1 C R C R ≈ e. This reduces our equations and we can rewrite it: Where we used the following shorthand notations: And neglected the additional 1 in the left hand side. The solution of Eq. (49) is then: If k > 1, this approximation fails because of the appearance of the giant components.
Using the solution of Eq. (47), the relative sizes of the parts in the bow-tie diagram are: By the same argument as with the ER graph, we get for the GRC: This result is shown on Fig. 10 along with the numerical results. The same argument can be applied for the exponential network as in the previous section. The predicted curves fit well in the very small and in the large average degree regimes.

Scale-free network
Without exponential cutoff, the probability distribution and double generating function of a scale-free network [32,33] are the following: and the generating function of the excess degree distributions: Newman showed in [8] that the condition of the existence of the giant components is For the scale-free network, this equation reads as Now, if make use of the relation between the exponent and the average degree: k = ζ(γ−1) ζ(γ) , and substitute x = 1, y = 1 we get: or equivalently k > 1 So, there is a giant component if the average degree is larger than one. But if we look at the function we can conclude that this condition gives giant components for any γ ≥ 2. Numerical simulations show that this is not the case (see Fig. 11). If we substitute g 00 (x, y) and its derivatives in Eq. (3) and Eq. (36)-(37) we observe that there are giant components of unit size for every exponent larger than two, since the formula gives exactly zero for any s and the equation has always two solutions: u 1 = 0 and u 2 = 1. These suggest that the generating function formalism can be barely applied to the directed scale-free networks. The limits of the formalism is well-known for undirected networks as well [9]. However, it is possible to give a rather qualitative approximation for the GRC in the γ > 2 regime. We use our observation from the simulations that there is no GSCC, and that in scale-free networks, very large degrees can appear. Since very large amount of the nodes have few out-degrees, the GRC is obviously dominated by C max R . Let us assume that the network breaks down into small components whose are the neighborhoods of the nodes with large out-degrees (i.e., every component gathers around a hub). In this case, the largest reachable set is the largest out-degree. In a scale-free network with degree distribution of p k ∝ k −γ , the largest degree is well approximated by k max ≈ N 1 γ−1 [34]. Using this approximation for the out-degrees and not taking into account the in-degrees we get: Comparison of the real GRC and this approximation is shown in Fig. 12. For large exponents, Eq. (69) fits well to the numerical results. Below γ = 3, it becomes less accurate. Note that the lower the exponent is the more portion of the nodes has large degrees. The predicted GRC becomes larger than the real value at some point (γ ≈ 2.3), that is the number of large hubs increases which results in larger average reaching centrality as well.

Degree-correlations
In the above sections we assumed that the joint probability distribution of the in-and outdegrees is simply the product of two independent distributions, i.e., there are no degreecorrelations. However, it is known that there are such correlations in real networks [35]. It is also known that these correlations have markable effects on the different properties of networks (percolation thresholds, epidemic thresholds, etc) [36,37]. In this paper, we study the effect of two types of correlations on the GRC: one-point correlations and directed assortative mixing. One-point correlation is the Pearson correlation between the in-and out-degree of a node: The brackets denote averages over the nodes and σ V (k) = k 2 V − k 2 V is the standard deviation of the corresponding degrees. Somewhat similarly, one can define the Pearson correlation between the out-degree of the start of an edge and the in-degree of its end term [35]: Here j in is the in-degree of the node an edge points to and k out is the out-degree of the node that edge comes from. The averages run over the edges. We will refer to this quantity as two-point correlation or directed assortativity, since it is a plausible generalization of the assortativity in undirected networks.  [3] 2.442 0.924 -0.174 E. coli [3] 2.533 0.923 -0.167 S. Cerevisiae [3] 2.537 0.923 0.182

Numerical results
In order to study the effect of the one-point correlation, we generated the in-and outdegree lists for the network with a given distribution and average degree. After randomizing both lists, we fixed the out-degree list while we successively swapped randomly chosen elements in the in-degrees. After every swap, we calculated ρ(k in , k out ) and accepted the new list whenever the correlation increased (decreased). We measured the GRC when the difference between the correlation of the current state and the last measured state was larger than 0.01 (this is the resolution of the measured GRC(ρ) function) 2 . The dependence of the GRC on the one-point correlation is shown in Fig. 13. It is clearly seen that the behavior of the GRC varies and depends strongly on the average degree. In the ER and exponential graphs, even the monotonity of the curves change. In the scale-free network, the GRC saturates at some level of correlation and the exponent effects only the threshold above which further correlations do not change the GRC.

Analytical approach
To have a qualitative insight of this behavior, let us consider the following joint degree distribution: Where the only criteria for the m jk matrix are: With these conditions, the one-point degree-correlation of the above joint degree distribution is exactly ρ [35]. Note that we assumed the same distribution for the in-and out-degrees (σ V (k in ) = σ V (k out ) = σ p ). The generating function of the modified distribution: where the g p 00 is the generating function of the original joint degree distribution and we introduced the following function: x j y k m jk (76)  Above the critical average degree, we have to solve and the GRC is given by the modified generating function: The exact solution of Eq. (77) depends on the actual choice of m jk and in most cases not possible to find in closed form. However, for small correlations (ρ ≪ 1), we can describe the change in the GRC at given average degree. In this case, the solution of Eq. (77) is very close to the solution of the original equation without the correlations: u = u 0 + u ρ . Expanding both sides and keeping only the linear terms in ρ and u ρ , we get: The coefficient β(u) is negative above the transition point for the model networks we are interested in (for the proof, see Appendix B). In the linear approximation, the GRC looks like: where and In the derivation of GRC ρ , we used the observations that when the joint degree distribution factorizes, the generating function is also a product of the single distributions, i.e., g p 00 (x, y) = g p 0 (x)g p 0 (y) and also Now we have to interpret the result we obtained for the change in the GRC. First, for simplicity, let us choose the m jk as proposed in [35]: Figure 14: The largest reachable set below the transition point (a) and one of the nodes with large out-degree in the largest reachable set (A). Without degree-correlations, the expected number of in-degrees of A is the average degree and the maximum out-degree of its in-neighbors is also moderate (b). With degree-correlations, the nodes with large out-degree has large in-degree as well (c). And with increasing number of in-neighbors the expected maximum out-degree of its neighbors increases as well.
where φ j is an arbitrary normalized distribution and k φ is its average. Moreover, choose the φ j distribution such that k φ = 1 which is the critical point of the ER and exponential networks. In this case χ 00 (u 0 , u 0 ) ≥ 0 and also note that above the transition point. The behavior of GRC ρ is governed by the relation of the two terms in the right hand side of Eq. (82). It is easy to check that near the critical point (u 0 ≈ 1), the second term is very close to zero, and GRC ρ is dominated by the first term which is positive. This means that when the average degree is small, but the graph already has giant components of finite size, small one-point correlations increase its hierarchical structure, as in Fig. 13. For large average degrees, u 0 → 0 and both terms in Eq. (82) becomes negative, resulting in a decreasing effect of small correlations, in good accordance with the numerical results (see Fig. 13a and Fig. 13b). In the regime where the GRC has a maximum (u 0 = 1 2 ), Eq. (82) predicts a negative coefficient for ρ, but as Fig. 13b shows, this is not the case for the exponential network. This discrepancy suggests that the change in the slope near this point is not trivial and strongly depends on the details of the addition of correlations.
Below the transition point, there are no giant components and the GRC is dominated by the largest reachable set. We can assume that the node with the largest reachable set (node C on Fig. 14a) or some of its out-neighbors have large out-degree, since this increases the probability of reaching more other nodes. Consider this neighbor with the large out-degree (node A in Fig. 14a). In the case of negative or zero correlations, the expected maximum of the out-degree of its in-neighbors is small (Fig. 14b). But in the presence of positive one-point correlations, the number of in-and out-edges tend to be similar, in other words, the node in question has large in-degree as well. In this case, the expected maximum of the out-degree of its in-neighbors (and thus of the candidate node for the largest local reaching centrality) increases and there are more reachable nodes. The scale-free network is a special case in the sense that the largest reachable set is with good approximation the neighborhood of a hub. Because of the correlations, this hub tends to have many in-neighbors as well and it is more likely to have a neighbor with many links (Fig. 14d). The numerical results in Fig. 13c suggest that the maximum out-degree of the nearest neighbors reaches its saturation level at relatively small correlations.

Two-point correlations
The two-point correlation of the type we investigate in this paper is the generalization of the assortativity to directed networks [35]. In order to introduce this correlation in our calculations, let P(j in , j out ; k in , k out ) denote the probability that a randomly chosen edge starts at a node with j in in-and j out out-degree and points to a node with k in in-and k out out-degree. This probability satisfies the following equations: which also create its connection to the joint degree distribution. Without two-point correlations (and other correlations), the two-node joint distribution factorizes: We can modify it by adding a correlation between p jout and p k in : However, if we recover the joint degree distribution, the added term vanishes: because the sum of any row or column of the matrix m joutk in must be zero (Eq. (82)). This means that the assortativity defined by Eq. (71) does not affect the GRC directly (via the joint degree distribution). Fig. 15 depicts the numerical results that were produced by  the same protocol as in the previous subsection. In the case of the ER and exponential networks, a small decrease in the GRC can be observed, regardless of the average degree. The SF network has a non-monotonous behavior, but for larger assortativity, a decreasing in the GRC can be seen. These results point out that, although two-point correlation does not affect the joint degree distribution directly, it changes the hierarchical structure of the network a little. This small effect can be understood if we look at the different typical structures around an edge (Fig. 16). In the case of large two-point correlations, the nodes with large out-degree (those that are expected to have larger reachable set) have out-neighbors with also large in-degrees (Fig. 16a). This means that the nodes they can directly reach are also reachable from many other nodes (that also have large out-degrees). This reduces the difference between the local reaching centralities among nodes with large C R or, in other words, introduces higher c R (i) in the definition of GRC (see Eq. (2)). Positive two-point correlation also introduces bottlenecks in the network (Fig. 16b). These structures accumulate many nodes on the in-edges that has similar reachable set, thus also reducing the differences. On the other hand, if the graph has negative two-point correlations, nodes with large out-degree can reach their out-neighbors uniquely (Fig. 16c). Nodes that are reachable from independent directions also emerge (Fig. 16d). These nodes have in-neighbors with small out-degree. Both effects decrease the ratio of overlapping reachable sets which results in a reduced similarity in the C R values.
(a) r > 0 In the case of r > 0, the reachable sets of hubs tend to be similar (a) and bottlenecks emerge (b), causing an increase in the overlap of reachable sets. In negatively correlated networks (r < 0), hubs can have their own reachable sets (c) and nodes with large in-degree tend to be reachable from independent parts of the network (d), decreasing the overlap between reachable sets.
The global reaching centrality (GRC) is a measure constructed to provide a characteristic number for the flow hierarchy of a directed network. In this paper we investigated the behavior of this measure and its dependence on the joint degree distribution. We have shown that the hierarchical structure of a random network strongly depends on the existence of the giant strongly connected component (GSCC) and other giant components in the network. In the regime of low average degree, the GRC is dominated by the node with the largest reachable set that can be approximated from the distribution of the local reaching centralities. This distribution is connected to the distribution of small out-components in a network and can be analytically determined using the generating function method generalized to directed networks. In the presence of the GSCC, the GRC can be well approximated by the difference in the sizes of the giant in-component (GIN) and the GSCC, and both can be calculated exactly for some network models with given degree distribution. Using the approximations for the GRC, we calculated its dependence on the average degree for different network models: a directed random tree, the Erdős-Rényi graph (ER), the exponential the scale-free (SF) network. The results show that in the sense of hierarchy, there is an optimal average degree at which the GRC has a maximum value. It is a result of the competition between the size of the largest reachable set (which can be found by nodes in the GIN) and the average size of reachable sets (which is dominated by the nodes in the GSCC). Near to the transition point, the size of the GIN is close to the size of the GSCC and the difference is increasing since the GIN grows faster in the beginning. In the limit of large average degree, the sizes of both giant components tend to become equal, since even the two set of nodes tend to be the same.
We also investigated the dependence of the GRC on two types of degree-correlations: one-point correlation (in-degree and out-degree of a node) and two-point correlation (the out-degree of the source and the in-degree of the target of a directed edge). Numerical results show that the hierarchical structure changes systematically with the one-point correlation. This is in accordance with the fact that the GRC can be expressed with the joint degree distribution, and latter is directly affected by the one-point correlations.
We have pointed out that in the two limiting case of the average degree, the qualitative effect of small correlations can be understand by the addition of a correlation term to the uncorrelated joint degree distribution. When the average degree is very low, small correlations have a positive effect on the GRC. This is not true for denser graph, in which correlations decrease the GRC. There is also a regime of the average degree in which a given level of correlations can maximize the hierarchy.
Both numerical and analytical results suggest that two-point correlation (which is the generalization of the assortativity for directed networks) does not effect the GRC directly. However, a small negative effect can be observed. It can be understand by looking at the effect of the two-point correlation on the neighborhood of an edge.
The results on the random network models have shown a deeper insight of the be-havior of the GRC but we have to keep in mind that they are only the first steps in the understanding of hierarchy. The main message of the results is that hierarchy is sensible to the edge density of a network and tends to emerge more likely in sparse networks. This is in good accordance with the observation that most of the real world networks are in the range of low density and many of them has an inherent hierarchical structure. The results also point out that correlations can have a large effect and can change the the hierarchical structures fundamentally (they can produce a finite magnitude of GRC even if the network would have an infinitesimal GRC otherwise). This is another indicator of the well-known fact that one has to take into account the presence of correlations when dealing with real networks.

Acknowledgement
The author would like to thank Tamás Vicsek, Péter Pollner and Gergely Palla for the fruitful conversations that facilitated the interpretation of the results and for their advices during the preparation of the manuscript. This research was fully supported by the EU ERC FP7 COLLMOT Grant No: 227878.

A Out-components in directed graphs
Using the definition of the generating function h 0 (y), we can obtain the probabilities for the out-components: The contour goes around the origin and has an infinitesimal radius, ensuring that it does not enclose poles. In our calculations y 0 = 0. In the last equation we just changed variables. We have to note that when y → 0, h 1 also converges to zero. This can be easily seen from Eq. (10). We can eliminate y from the argument using Eq. x j km jk where the only criteria for m jk are Eq. (73)-(74). They can be satisfied by the following choice [35]: here φ j is an arbitrary normalized distribution and k φ is the corresponding average. With this form of m jk , the numerator looks like: here g p 0 (u) and g φ 0 (u) are the corresponding generating functions for the distributions p j and φ j . Assume that k > k φ and fix the φ j distribution such that k φ = k c . It can be easily seen that for the ER and exponential networks, g p 0 (u) < g φ 0 (u) for any u. We only have to show that ∂ x g p 01 (u, 1) < 1 above the transition point. For this to see, let us consider the function in question as a function of the average degree: and note that F (k c ) = 1. Furthermore, F (x) is a decreasing function of its argument: The first term of the right hand side is positive for all 0 < u < 1, because it is a sum of positive numbers. In contrast, the second term is negative in the ER and exponential networks, because the size of the giant components increase with the average degree. Thus F ( k ) < 1 (see Fig. 17).