{'fraction_non_alphanumeric': 0.043691067444036565, 'fraction_numerical': 0.013028143669473836, 'mean_word_length': 4.362408336549595, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, '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}}
The Dynamics of Hierarchical Evolution of Complex Networks

Introduced recently, the concept of hierarchical degree allows a more complete characterization of the topological context of a node in a complex network than the traditional node degree. This article presents analytical characterization and studies of the density of hierarchical degrees in random and scale free networks. The obtained results allowed the identification of a hierarchy-dependent power law for the degrees of nodes in random complex networks, with Poisson density for the first hierarchical degree (obtained through master equation approach). Exact results were obtained for the second hierarchical degree in scale free networks.


I. INTRODUCTION
The characterization and analysis of complex networks [1,2] involves the use of measurements capable of expressing important properties of the network. While traditional features such as the node degree and clustering coefficient have been successfully used for that purpose, such measurements are intrinsically local, in the sense that they are affected only by the immediate neighborhood of each reference node. Among more global measurements, such as the network diameter and the shortest path between any two network nodes, the concept of hierarchical node degree has been introduced recently and considered for the characterization and analysis of the connectivity of complex networks [4,5,6,7,8]. Given a reference node i, it is possible to define the k − th relative hierarchical level as corresponding to the network nodes which are exactly at minimal distance of k edges from node i. The hierarchical node degree at level k corresponds to the number of edges between the hierarchical levels k and k+1, therefore defining a natural hierarchical extension of the concept of node degree. Note that the hierarchical degree, starting at level 1 (which includes the immediate neighbors of i) tends first to increase with the hierarchical level k and then to decrease as a consequence of the finite size of the network [9]. Because the hierarchical node degree is a global measurement (i.e. it considers, in hierarchical fashion, all nodes in the network), it provides more information about the connectivity of the reference node with the remainder of the network. For instance, the number of hierarchical levels which are required in order to contain a percentage (e.g. 50%) of the network nodes, provides a valuable information about the accessibility of that reference node. The smaller this number of levels, the more connected the reference node is with the rest of the network. Several other topological properties characterizing the context of the reference node can be identified by using the hierarchical node degree and other related features [7,8].
An interesting question implied by the introduction of the concept of hierarchical node degree regards the analytical characterization of such features expected from random and scale free networks. The current work addresses such an issue by using mean field and the master equation methodologies [3,10]. It is shown that a power law is obtained for the hierarchical degrees of nodes in random networks, with Poisson density being obtained for the first hierarchical degree. We verified that the second order hierarchical degree for scale free networks involves a logarithmic correction of the first order degree studied in [1,2,3]. In addition, we obtain exact results for the second order hierarchical degree distributions in scale free networks.

A. Hierarchy and hierarchical degree
A set of hierarchy h is defined as that containing all the vertices which are located at a distance of h connections from a reference vertex. The hierarchical degree, or superior order degree, is the measurement of the number of connections in a set with a determined value of hierarchy. For h = 1, we have the first order degree which is well known in the literature [1,2,3]. In this article we are intended to study the behavior of graphs where h ≥ 2. We will denote k as the number of vertices having hierachical degree h equal to x, and N a,b,...,n will denote the number of vertices presenting the first order degree as a, the second order degree as b and so on.

II. DEGREE EVOLUTION OF A VERTEX
Mean field theory is widely applied in complex networks research [1,2,3]. Through this boarding, the degree evolution of the particular vertice is proportional its connection probability (kernel function -P J (t)). If this probability has a complex form, the equations become non-trivial.
Generally, the hierarchical degree h depends on the probability of connection of the vertices belonging to this set of hierarchy. Thus, we can write: In the following we consider random graphs where P j (t) is the same for all vertices, as well as scale-free networks proposed by Barabási-Albert [1] where P j (t) ∝ k (1) j .

III. DISTRIBUTION OF THE SECOND ORDER CONNECTIVITY DEGREE
In this section we will study the connectivity degree distribution, which is an intrinsic characteristic of the complex networks and is capable of distinguishing all types of graphs. Henceforth, for simplicity's sake, the probability of vertex j to make a connection will be represented as P k (1) j (t) and not P j (t).

A. Initial States and Structures
A vertex with first order degree k (1) and second order degree k (2) defines one or more structures which are topologically identic and are denoted by (k (1) , k (2) ). For example, Figure 1 shows all possible structures (3,3). An structure has one or more initial states. An structure (x 1 , x 2 ) is the initial state of another structure (y 1 , y 2 ) if the following condition is met: where: Therefore, two processes exist which take one structure into the other: The initial states of structure (3,3), given by (2, 3) and (3, 2) are represented in Figure 2.

B. Describing the Processes through the Master Equation
The probability of transition of the initial states in a structure give us the production rate of that structure. For example, let us study the formation of structures (k (1) , k (2) ). As we know, their initial states are: (k (1) − 1, k (2) ) and (k (1) , k (2) − 1). Then, the transition probabilities are given by: Therefore, the formation rate of the structure (k (1) , k (2) ) are: The transition probabilities of structure (k (1) , k (2) ) is: Therefore, the vanishing rate of the structure (k (1) , k (2) ) is: The master equation governing the evolution of N k (1) k (2) is as follows: In the following we will show the solution of the equation above for random graphs as well as for scale-free networks.

A. Random Graphs
In this work we use non-static version of non-directed random graphs. Instead of generating a network from a symmetric random matrix, we define the following procedure: Beginning with N disconnected points, we select two vertices in the network at a time and, with probability p, we establish a connection between them. Connections linking a vertex to itself are not allowed, that is to say, the two selected vertices must be different. The probability of a vertex j to be selected at a time t is given by:

Degree Evolution of a Vertex
Since P j (t) is constant, we will denote it as π. Therefore: By substituting Eq.(8) in Eq.(1), we have: Assuming that k

First Order Degree Distribution
The variation of the number of vertices with first order degree given as k (1) can be described through the master equation: As is known, N 0 (t = 0) = N and N j (t = 0) = 0, ∀j. Solving this equation for k (1) = 0, we have: And for k (1) = 1, we have: For other values of k (1) , we conclude that the solution of the master equation obeys the following formation rule: The solution for this recursion is: The distribution of the first order degree, given by P This is the Poisson distribution with mean value πt. Figure 3 shows the time evolution of the number of vertices with k (1) = 0, 1, 2 in a random graph with N = 100 and p = 0.9.

B. Scale-free Networks
The concept of scale free networks has been introduced by Barabási and Albert and refers to graphs whose first order degree distribution follows a power law [3]: N k (1) = A[k (1) ] −ν . Most scale free networks found in nature have ν in the interval between 2 and 3. The probability of connection in this model is given by: Also:

Evolution of Vertex Degree
Substituting Eq.(12) in Eq.(1), we have: ¿From the definition of hierarchical degree, we have: Therefore: For h = 1 and the following condition: k (1) j (t = t j ) = 1 we obtain the solution given by Barabási-Albert in [3]: For h = 2, we use the integrating factor t −3/2 and we obtain: If we consider that, in instant where the new vertice is enclosed to network its average second order degree is given by κ (2) j , then: k (2) j (t = t j ) = κ (2) j . From this condition, we have:   The curves intercept at t = τ , indicating that at this growth stage vertex j in the scale free network has the same second order degree as vertex j in the random network. The log-log plot in the inset shows how τ (tj) depends of tj, defining power laws τ (tj) ∝ t −α j .
Through numerical simulations, we can determine the value of κ (2) j in terms of j. From Fig(4) we note that κ (2) j = 1 + ln j. Thus, the solution for the second order degree variation is given by: Eq.(15) is not simple to be solved but, using the same integrating factor as above, we can obtain a solution as an integral recursive equation, as follows:

First Order Degree Distribution
In [10], Krapvisky establishes the following master equation which governs the evolution of N (1) k (1) , that is, the average number of vertices with first order degree k (1) : The first term takes into account the probability that the new vertex connects to one of the first order degree equal to k (1) −1. The second term expresses the probability of connection between a vertex with k (1) . The delta function accounts for the fact that every added vertex has degree 1. By making the normalization M (t) = 2t, the solution of Eq.(15) is given as: The distribution of the first order degree, i.e. P  k (1) (t)/N T , is given as: Figure 5 shows the evolution of k (2) 50 (t) for a random graph with N = 100 nodes and connection probability p = 0.9 as well as the same measurement for a scale free network. An intersection point can be observed at t = τ , meaning that at this growth stage the vertex j in the random and scale free networks have the same second order degree. For values of t larger than τ , the second order degree becomes larger for the random network than the scale free counterpart. This indicates that the second order degree in a scale free network tends to grow slower than in a random network. The log-log diagram in the inset, shows τ (t j ) in terms of t j for connection probabilities p = 0.9 and p = 0.6, which yields power laws τ (t j ) ∝ t −α j .

Second Order Degree Distribution
We now consider the number of vertices with first order degree equal to k (1) and second order degree equal to k (2) , which will be represented as N k (1) k (2) . The obtention of this quantity involves the solution of Eq.(6). Assuming a linear solution of the type: N k (1) k (2) = n k (1) k (2) t, we have: Substituting Eq.(13) into above expression: For simplicity's sake, we make It follows that In addition, we have to enforce that Developing the recurrence, we obtain Expressed in terms of the original variables, it follows that By Eq.(21) we know the value of n f (n f = N f (t)/t). Substituting in the above expression: When k (1) = 1, we have that This result is identical to the expression obtained by Krapivsky in [10] for correlation degree. Developing the first part of Eq. (30): (32) Figure 6 shows the curves obtained for n k (2) k (2) for several values of k (1) and k (2) varying from 0 to 50.
The total number of vertices with second order degree equal to k (2) is given as: (2) (33) Figure 7 shows a log-log graph of the distribution N (1) k (1) (given by Eq.(21)) and N (2) k (2) (obtained from Eq.(33)). Note that the initial values in this distribution deviate from the linear relation typically observed for scale free networks. The second order distribution, given by P

V. CONCLUDING REMARKS
This work addressed the analytical characterization of hierarchical degrees of random and complex networks. In the case of random networks, we have shown that the hierarchical degree follows a power law, i.e. k (h) (t) ∝ t h . By using the master equation approach, it has also been shown that the first order degree obeys a Poisson distribution. Unlike the first order degree, the evolution of the second order hierarchical degree can not be easily described by a master equation as Eq. (6). This is a consequence of the fact that the adopted approach of uniting two connected components from the network into a single component implies several combinations of effects and respective terms to be incorporated into the master equation. In addition, we verified that the second order degree tends to grow slower in scale free networks than in random networks, with the position where these two values become equal following a power law.
In the case of scale free models, namely the Barabási-Albert network, it has been verified that the second order hierarchical degree, for a particular node, can be expressed in terms of a logarithmic correction of the first order degree. Exact results have been obtained for the second order hierarchical degree. We observe that the generalization of such an approach to higher hierarchical Possible continuations of the reported developments include the extension of the analytical expressions of hierarchical node degree to higher levels, as well as the derivation of analytical expression for other hierarchical features such as the hierarchical clustering coefficient and hierarchical number of nodes [4].