A continuous-time network evolution model is studied. The basic units of the model are edges and triangles. The evolution of the units is governed by a continuous-time branching process. The asymptotic behaviour of the model is studied. It is proved that the number of edges and triangles have the same magnitude on the event of non-extinction, and it is , where is the Malthusian parameter.
events occur at time = 1, 2, . . . ) and it describes connections of two nodes.
The meaning of connection can be cooperation or any interaction. Therefore the
connections of more than two nodes are also important. For example, Backhausz
and Móri in [
In this paper we shall study the following random graph evolution model. Parameter ∈ [0, ∞) will denote the time. At the initial time = 0 we start with a single object, it can be either an edge or a triangle. We call this object the ancestor. This ancestor object produces ofspring objects which can be also edges or triangles. Then these ofspring objects also produce their ofspring objects, and so on. The reproduction times of any object, including the ancestor, are given by its own Poisson process with rate 1. We assume that during the evolution, the reproduction processes of diferent objects are independent. The reproduction processes of the triangles are independent copies of the generic triangle’s reproduction mechanism. Similarly, the reproduction processes of the edges are independent copies of the reproduction mechanism of the generic edge.
Consider the generic edge and its Poisson process Π2 ( ). When the Poisson process jumps, then a new vertex appears an it is connected to our generic edge. The probability that this new vertex is connected to the generic edge by one new edge is 1, 0 ≤ 1 ≤ 1. The end point of this new edge is chosen from the two vertices of the generic edge uniformly at random. So in this step an edge produces one edge. The other possibility is that the new vertex is connected to both vertices of the generic edge. It has probability 2 = 1 − 1. In this case the ofspring of the generic edge is a triangle consisting of the generic edge and the two new edges. It is important to fix that in this case the generic edge and the new triangle will produce ofspring, but the two new edges will not do it.
For the generic triangle the reproduction is the following. Let Π3 ( ) , ≥ 0, denote the Poisson process with rate 1 corresponding to our triangle. The jumping points of Π3 ( ) are the birth times of the generic triangle. At every birth time a new vertex is added to the graph which can be connected to our generic triangle with edges ( = 1, 2, 3). Let denote the probability that the new vertex will be connected to vertices of our generic triangle. The vertices to be connected to the new vertex are chosen uniformly at random. It follows from the definition of the above evolution process that at each birth step we always add 1 new vertex. With probability 1 the generic triangle gives birth to a new edge. However, in the remaining cases we count only the new triangles and not the new edges. So, with probability 2 the generic triangle produces one child triangle, moreover, with probability 3, the generic triangle produces three children triangles.
We shall consider that any edge is of type 2 object and it will be denoted by subscript 2, while for a triangle it will be denoted by 3. So let us denote by , ( ) the number of type ofspring of the type generic object up to time (, = 2, 3).
As usual, , , , = 2, 3, are point processes. Then 2( ) = 2,2( ) + 2,3( ) 3( ) = 3,2( ) + 3,3( ) is the number of all ofspring (either edge or triangle) of the generic edge up to time . Similarly, time . is the number of all ofspring (either edge or triangle) of the generic triangle up to
Let us denote by 3(1), 3(2), . . . the birth times of the generic triangle and let 3(1), 3(2), . . . be the corresponding total litter sizes. That is the generic triangle bears 3( ) children being either triangles or edges at the th birth event. Then 3(1), 3(2), . . . are independent identically distributed discrete random variables with distribution P ( 3( ) = ) = , ≥ 1. We have
P ( 3( ) = 1) = 1 = 1 + 2, P ( 3( ) = 3) = 3 = 3,
P ( 3( ) = ) = = 0, if /∈ {1, 3} .
Throughout the paper we assume that 1 < 1, because otherwise there were no reproduction of the triangles. We assume that the litter sizes are independent of the birth times.
Let the finite, non-negative random variable 3 be the life-length of the generic triangle.
We assume that the reproduction terminates at the death of the individual, therefore 3 ( ) = 3 ( 3) for > 3. Then the reproduction process of a triangle can be given by 3 ( ) =
︁∑ 3( )≤ ∧ 3
3( ) = 3 (Π3 ( ∧ 3)) , where Π3 ( ) is the Poisson process, 3( ) = 3(1) + · · · + 3( ) gives the total number of ofspring of the generic triangle before the ( + 1)th birth event and ∧ denotes the minimum of {, } function of 3. Then the survival function of a triangle’s life-length is 1 − 3 ( ) = P ( 3 > ) = exp ⎝ −
3 ( ) d ⎠ , ⎛ ︁∫ 0
⎞ where Π2 ( ) is the Poisson process. the life-length of an edge is where 3 ( ) is the hazard rate of the life-length 3. We assume that the hazard rate depends on the total number of ofspring, so that
3 ( ) = + 3 ( ) with positive constants and . As the edge always gives birth to one ofspring (which can be an edge or a triangle), so the total number of ofspring of the generic edge is
2 ( ) = Π2 ( ∧ 2) , Let 2 ( ) denote the distribution function of 2. Then the survival function of 1 − 2 ( ) = exp ⎝ −
2 ( ) d ⎠ , ⎛ ︁∫ 0 ⎞ where we assume that the hazard rate of the life-length 2 is of the form 2 ( ) = + 2 ( ).
We have to mention that we do not delete any triangle or edge when it dies, because its edges and vertices can belong to other triangles or edges, too. So we consider a dead triangle or edge as an inactive object not producing new ofsprings.
Here we summarize the theoretical results of our paper [
ofspring of a type mother until time .
Proposition 3.1. For any ≥ 0 we have Let us denote by , ( ) = E , ( ) the expectation of the number of type 2,2 ( ) = 1 ( ), 2,3 ( ) = 2 ( ), (1 − 2 ( )) d = −( +1)
Let be the matrix of the Laplace transforms. By direct calculation we obtain that the characteristic roots of ( ) are 1,2( ) = ( 2+3 3) ( )+ 1 ( )±√(( 2+3 3) ( )− 1 ( ))2+4 1 ( ) 2 ( ). (3.1) 2 The greater of these values is called the Perron root, that is ( ) = 1( ) = ( 2+3 3) ( )+ 1 ( )+√(( 2+3 3) ( )− 1 ( ))2+4 1 ( ) 2 ( ) 2 is the Perron root.
We assume that the process is supercritical, that is 1(0) > 1. Now, that value of for which the Perron root is equal to 1 is called the Malthusian parameter. In the usual notation, is the Malthusian parameter if ( ) = 1. We assume the existence of the Mathusian parameter. From relation ( ) = 1 and (3.1) we obtain, that for the Malthusian we have 1 ( )( 2 + 3 3) ( ) − ( 1 ( ) + ( 2 + 3) ( )) = 2 ( ) 1 ( ) − 1. (3.2) We shall need the eigenvectors of ( ). So let be the Malthusian parameter and let ( 2, 3)⊤ be the right eigenvector of ( ) satisfying condition 2 + 3 = 1. Then direct calculation shows, that
( 1 − 1) ( ) , 3 = (2 1 1− 1() )(−)1− 1. 2 = (2 1 − 1) ( ) − 1 (3.3) Again let be the Malthusian parameter and let ( 2, 3)⊤ be the left eigenvector of ( ) satisfying condition 2 2 + 3 3 = 1. Direct calculation shows, that 2 = 1 ( 1)((1−)(1()2 1(−)1−)( (1 )−( 1))−1)2 , 3 = 1(1(− )1( 1(−1)))((2( 1)−−1()1 (()−)−11))2 . (3.4)
In the following theorem we shall need the next formulae.
3 ( ) = ∑︁ ︀( − *, ( ))︀ ′.
, =2 Here and are from equations (3.4) and (3.3). Moreover, by Proposition 3.1 or by Proposition 3.2, we have that ︀( − 2*,2( )︀) ′ = 1 (− ′( )) , (︀ − 2*,3( )︀) ′ = 2 (− ′( )) where − ′( ) = ∞ ︁∫ 0 d = − 2 1 ∫︁ 0 1 − −( +1) 0 1 almost surely for = 2, 3.
ln(1 − ) (1 − )
We turn to the limit of the edges and triangles. at the same time.
Proposition 3.3. Assume that (3.2) has a finite positive solution . Assume that 0 ≤ 1 < 1, 0 < 1 ≤ 1 and it is excluded, that both 1 = 0 and 1 = 1 are satisfied
Let 2 ( ) and 3 ( ) denote the number of all edges being born up to time if the ancestor of the population was an edge and triangle, respectively. Then l→im∞ − ( ) = almost surely for = 2, 3.
Let 2 ˜( ) and 3 ˜( ) denote the number of all edges alive at time if the ancestor of the population was an edge and triangle, respectively. Then almost surely for = 2, 3.
Let 2 ( ) and 3 ( ) denote the number of all triangles being born up to time if the ancestor of the population was an edge and triangle, respectively. Then almost surely for = 2, 3.
Let 2 ˜( ) and 3 ˜( ) denote the number of all triangles alive at time if the ancestor of the population was an edge and triangle, respectively. Then l→im∞ − ˜( ) = 2 ( ) l→im∞ − ( ) = l→im∞ − ˜( ) = 3 ( )
To get a closer look on the theoretical results, we made some simulations about
them. We generated our code in Julia language [
Our first step in the simulation was to check if the parameters have a root for Equation 3.1. In Figure 1 we see that ( ) − 1 has a root at = 0.9133 with the parameters 1 = 0.1, 2 = 0.9 1 = 0.2, 2 = 0.6, 3 = 0.2, = 0.25, = 0.25. This numerical value can be considered as the Malthusian parameter .
If the conditions were given by the existence of the Malthusian parameter, we simulated 220 = 1, 048, 576 events and calculated the number of edges and triangles up to time . We have to mention that all the events are processed till the end time of the simulation thanks to structure of the priority queue. For the above demonstration we used the parameter set 1 = 0.1, 2 = 0.9, 1 = 0.2, 2 = 0.6, 3 = 0.2, = 0.25, = 0.25 again. On Figure 2 and Figure 3 the ancestor object was a triangle. Here we show 3 ( ) by Figure 2a, 3 ˜( ) by Figure 2b, 3 ( ) by Figure 3a and 3 ˜( ) by Figure 3b for the same simulation. On each plot the simulation result can be obtained by a straight line on a logarithmic scale and the theoretical result with a dashed linear line with slope. The parallel lines show us a good support for our Proposition 3.3.
(a) The number of edges alive.
(b) The number of edges being born. els with the same parameters until the slope stabilized at a large fixed and saved the last values for the number of edges and triangles being born and being alive. After it we multiplied each result by the correct constant values of Proposition 3.3. ∼ − ∼ − ( ) ( ) 2
It was also important to know that the experimented 3 has the same distribution for the diferent kinds of extractions.
For this purpose we made the Kolmogorov-Smirnov test for each pair of extractions. Table 1 shows us the values. In the table
denotes the empirical distribution of 3 number of edges being born, ˜ denotes the empirical distribution of 3 came from the came from the number of edges being alive, denotes the empirical distribution of 3 came from the number of triangles being born and ˜ denotes the empirical distribution of 3 came from the number of edges being alive.