{'fraction_non_alphanumeric': 0.04854840275754928, 'fraction_numerical': 0.01335081075832605, 'mean_word_length': 4.2294998730642295, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parallel Random Apollonian Networks

We present and study in this paper a simple algorithm that produces so called growing Parallel Random Apollonian Networks (P-RAN) in any dimension d. Analytical derivations show that these networks still exhibit small-word and scale-free characteristics. To characterize further the structure of P-RAN, we introduce new parameters that we refer to as the parallel degree and the parallel coefficient, that determine locally and in average the number of vertices inside the (d+1)-cliques composing the network. We provide analytical derivations for the computation of the degree and parallel degree distributions, parallel and clustering coefficients. We give an upper bound for the average path lengths for P-RAN and finally show that our derivations are in very good agreement with our simulations.


Introduction
During the last decade, the study of network topologies has become a useful way to tackle the understanding of information flow within complex natural or artificial systems. The applications range from sociology, logistics, epidemiology, immunology, neural networks characterization, granular packing analysis, networking, etc. Among a multitude of proposed models, scale-free and small world networks have been widely addressed, essentially because many empirical or real life networks display such properties [6,9]. This is the case for random graphs, social networks, the web and for gene networks for instance. Basically, scale free networks display a power-law degree distribution, p(k) ∼ k −γ , where k is connectivity (degree) and γ the degree exponent [2], while in small world networks, most vertices can be reached from any other by a small number of hops or steps. Small world networks are characterized by a high clustering coefficient, e.g. a high level of vertices interconnection, and small average path length, namely small minimum path length in average between any pairs of vertices in the network. Among the topologies that display scale free and small world properties, Apollonian networks [1] have recently attracted much attention [8,7]. Apollonian networks are constructed from a fractal generated from a set of hyper-spheres, where any hypersphere is tangent to the others. This fractal is also known as the Apollonian gasket, named after Greek mathematician Apollonius of Perga. The 2D Apollonian network, or Deterministic Apollonian Network (DAN) [1], is obtained by connecting the centers of touching spheres (interpreted as vertices) in a three-dimensional Apollonian gasket by edges, as shown in Fig 1.1. The first generation for this fractal network is characterized by disks vertices, the second generation is characterized by square vertices and the third generation is characterized by triangle vertices. Extension to higher dimension have been provided in [11].
Ramdom Apollonian Networks (RAN) [15], differ from the recursive construction of DANs, as a RAN starts from a (d+1)-clique (a triangle in dimension 2) containing d + 1 vertices. Then, at each time step, a single (d+1)-clique is randomly selected from the set of (d+1)-clique in the network that do not already contain a vertex connected to all the vertices composing the (d+1)-clique. The selected (d+1)-clique is then used to insert a new vertex linking to all of the d + 1 vertices of the selected (d+1)-clique. 2D Random Apollonian Networks (RAN) have been extensively studied in [15,14], and extension to high dimension RAN (HDRAN) provided in [12].
Some recent attempts to make use of RAN like structures in P2P application [refs] faces the requirement to maintain such topologies in dynamic conditions, e.g. when vertices almost freely enter and leave the network. For RAN or HDRAN topologies, the repairing process when vertices leave the network is quite costly and limits the range of potential applications. In order to simplify the topology repairing process (that is beyond the scope of this paper), we are considering an extension of the RAN or HDRAN topologies to what we call Parallel RAN (P-RAN). This new topology that differs slightly from RAN or HDRAN allows to insert several vertices inside a (d+1)-clique, each inserted vertices being fully connected to all the vertices composing the clique. This extension constructs parallel random Apollonian structures that we formally study through out the paper.
After a short presentation of Parallel Deterministic Apollonian Networks (P-DAN) and Parallel Random Apollonian Networks (P-RAN) in the first two sections, we introduce in the third section the parallel degree distribution and parallel coefficient for such networks and study their asymptotic statistical properties for any dimension. The fourth, fifth and sixth sections give the derivations respectively for the degree distribution and the degree exponent, the clustering coefficient and the average path length for P-RAN. Extensive simulation results are provided through out these sections to validate as far as possible the analytical derivations. A short conclusion ends the paper.

Parallel Deterministic Apollonian Networks
A parallel deterministic Apollonian network in dimension d is constructed recursively from an initial (d+1)-clique allowing to insert at step t more than one vertex into (d+1)-cliques composing the network at step t − 1. Various rules can be adopted for the construction of Parallel Apollonian networks. Some of them lead to Expanded Apollonian networks [10] or recursive clique trees [4] for which at each time step, a new vertex is inserted in every (d+1)-clique composing the network. In the following subsection, as an example, we propose other rules that lead to a different topology. To characterize the parallel nature of this kind of networks, we introduce what we call the parallel degree m ≥ 0 of a (d+1)-cliques that characterizes the number of vertices inside the clique and fully connected to the vertices composing the clique. This constructing process is detailed in Algorithm 1 Data: d: dimension of the P-DAN; tMax: maximum number of steps; m the parallel degree Result: r a d-dimensional P-DAN t ← 0; Initialize r to a (d+1)-clique, c (r contains 1 (d+1)-cliques); C ← c the set of (d+1)-cliques composing the P-DAN ; while t < tMax do C ′ ← C; for all c in C do Insert m new vertices into c, fully connected to the vertices composing c ; Algorithm 1: P-DAN constructing algorithm

Parallel Random Apollonian Networks
We define Parallel Random Apollonian Networks as RAN for which a new vertex can be inserted at time step t in any (d+1)-clique composing the network, whatever its creation time step is. This means that a (d+1)-clique can contain in its inside more than one vertex fully connected to the vertices composing the clique as detailed in Algorithm 2. To our knowledge, no previous work have been reported specifically on P-RAN. Nevertheless, some similarity can be found for simple topologies described in one dimension in [5]. We study in the following sections P-RAN for any dimensions. Initialize r to a (d+2)-clique (r contains d + 1 (d+1)-cliques); C ← c1, c2, c3 the set of (d+1)-cliques composing the initial (d+2)-clique ; while t < tMax do Select randomly a (d+1)-clique, c, in C ; Insert a new vertex into c, fully connected to the vertices composing c ; Add to C the d + 1 new (d+1)-cliques created by the insertion of the new vertex and update r ; t ← t + 1 ; end Algorithm 2: P-RAN constructing algorithm Initially, a network containing d + 2 vertices and d + 2 (d+1)-cliques is created. At each time step, a new vertex is added into a (d+1)-clique selected at random. The new vertex is connected to each vertex of the selected clique, creating d+1 new (d+1)-cliques.
Thus, comparatively to RAN for which new vertices are inserted into (d+1)-cliques that contain no vertex inside, for P-RAN, any (d+1)-clique can be selected to insert a new vertex, what ever the number of inside vertices is. Figure 3.1 shows the first four steps of construction of a P-RAN. A parallel embranchment is created at the third step since a clique containing already a vertex is selected for the insertion of a second inner vertex.

Parallel degree distribution and parallel coefficient
The parallel degree is a characteristic that applies to (d+1)-cliques. We show hereinafter that the discrete parallel distribution for P-RANs follows asymptotically a geometrical law.
Definition We define the parallel degree of a (d+1)-clique as the number of vertices "inside" the (d+1)-clique, e.g. the number of vertices that are connected to every vertices of the (d+1)-clique but are not in the set of vertices that compose the (d+1)clique.

Estimating the parallel degree distribution
Proof At time t = 0, the networks is composed with d + 2 vertices forming d + 2 (d+1)-cliques. Each time a new vertex is inserted into the network, the number of (d+1)-cliques increases by d + 1. If Nc t is the number of (d+1)-cliques at time t, we have Nc t = d + 2 + t.(d + 1). Furthermore, each time a (d+1)-clique c j is selected for the insertion of a new vertex, its parallel degree m j increases by 1. Thus, if Nc t (m) is the number of (d+1)cliques having a parallel degree equal to m at time t we get the following growth rate for Nc t (m) Let P c t (m) be the probability to select a (d+1)-clique with parallel degree m at time t. P c t (m) can be approximated by the ratio N ct(m) d+2+t.(d+1) . Thus Nc t (m) = Nc t .P c t (m) = (d + 2 + t.(d + 1)).P c t (m) and we get from Eq.1 Thus As P c t (m) is bounded for all m and t, from Eq.3 we get that P c t (m) is a Cauchy sequence, which shows that lim t→+∞ P c t (m) = P c(m) exists and that for large t, P c t (m) ∼ P c t−1 (m) ∼ P c(m). Rewriting the previous equation for large t we get It is easy to show by induction on t that the probability to select at any time t a (d+1)-clique having a null parallel degree is P c(0) = (d + 1)/(d + 2). Thus for large t This ends the proof and shows that the parallel degree for P-RAN scales as a geometrical distribution.

Average parallel degree and parallel coefficient
Definition The average parallel degree M of a P-RAN is defined as the mathematical expectation of the parallel degree, i.e.
Thus, M measures the average number of vertices inside (d+1)-cliques of a P-RAN.
Definition We define the parallel coefficient of a d-dimensional P-RAN ρ as M −P c(1), i.e.
For d = 2 we get M = 1/3 for P-RAN, which is also the case for RAN, and ρ = 7/48 for P-RAN while ρ = 0 for RAN. Figure 4.2 shows the parallel coefficients for P-RANs estimated experimentally for each dimension from the construction of 10 networks utterances containing 100000 vertices each. The figure gives also the absolute error and its corresponding standard deviation measured comparatively to the theoretical expectation.

Estimating the degree distribution
The degree of a vertex in a network is the number of connections it shares with other vertices and the degree distribution is the probability distribution of these degrees over the whole network.

Lemma 5.1 The degree distribution of a d-dimensional P-RAN is given by the following recursion
.
Proof We note that, once a new vertex is added into the P-RAN network, the number of (d+1)-cliques available for the insertion of a new vertex is increased by d + 1. After t iterations, the number of (d+1)-cliques available for the insertion of a new vertex is d + 2 + t(d + 1). Thus, given a vertex v i , when its degree increases by 1 the number of (d+1)-cliques that contain vertex v i increases by d. So the number of (d+1)-cliques available for selection containing vertex Let N t be the total number of vertices into the P-RAN at step t (N t = d + 2 + t) and let N t (k) be the number of vertices having a degree k at time t. We can write the following difference equation Let P t (k) be the probability to select a vertex with degree k at time t. P t (k) can be approximated by the ratio Nt(k) d+2+t . Hence Nc t (k) = (d + 2 + t).P t (k) and we get from Eq.9 As P t (k) is bounded for all k and t from Eq.10 we get that P t (k) is a Cauchy sequence, showing that lim t→+∞ P t (k) = P (k) exists, and that for large t, P t (k) ∼ P t−1 (k) ∼ P (k). Rewriting the previous equation for large t we get and finally This recursive equation is defined for k ≥ d + 1. We show next that P (d + 1) = 1/2 for all dimensions.
• Let N d+1,t be the expected number of vertices into the network having a degree equal to d + 1 at time t, • let n t be the expected total number of (d+1)-cliques having a parallel degree equal to 0, • let n ′ t be the expected total number of (d+1)-cliques having a parallel degree equal to 0 for which all vertices have a degree k > (d + 1) at time t, • let n ′′ t be the expected total number of (d+1)-cliques having a parallel degree equal to 0 for which all vertices have a degree k > d + 1 except one vertex that has a degree k = d + 1 at time t.
For sufficiently large t, every vertex v i in the network has a degree k i ≥ d + 1, and every (d+1)-clique v j has either all its vertices with a degree k > d + 1 or only one vertex with a degree k = 3. Thus, when we insert a new vertex in a (d+1)-clique c j , only three cases arise for the (d+1)-clique selected for the insertion: (i) If the clique has a parallel degree m > 0 then N d+1 (t) is increased by one, n ′ t is unchanged and n ′′ t is increased by d + 1 (ii) If the clique has a parallel degree m = 0 and all its d + 1 vertices has a degree k > d + 1, in this case the N d+1 (t) is increased by one, n ′ t is decreased by one and n ′′ t is increased by d + 1 (iii) If the clique has a parallel degree m = 0 and all its d + 1 vertices have a degree k > d + 1 except one with a degree equal to d + 1, N d+1 (t) is unchanged, n ′ t is increased by d and n ′′ t is unchanged. In Section 4 we have shown that the probability to select randomly a (d+1)-clique with a parallel degree m = 0 is P (m = 0) = (d + 1)/(d + 2) and n t ∼ t. (d+1) 2 d+2 . Previous statements lead to the following equations Assuming that lim t→+∞ n ′ t /n t exists (this is obviously the case since P (k = d + 1) exists), n ′ t ∼ a.t where a is a constant. Replacing n ′ t in Eq.13 we get This completes the recursive equation that gives the degree spectrum distribution.
To our knowledge, there is no simple analytical expression for P (k) in any dimension. Nevertheless, for d = 1, we get This result in dimension one has already been reported in [5].

Degree exponent
For scale free networks, the degree distribution follows asymptotically a power law whose exponent is called the degree exponent. In the following, we show that P-RANs are scale free networks and derive their degree exponents.
To show that the degree distribution follows a power law, we evaluate the asymptotic value of the following ratio Thus and for large k This shows that for large k P (k) ∼ k −γ with γ = 2.d+1 d . For d = 2, we theoretically get γ = 5/2. We evaluate the empirical degree exponent using the mean of the maximum likelihood estimate computed according to the following formula proposed in [3] : where k i , i = 1, 2, ..., n are the observed values of k such that k i ≥ k min . Figure 5.1 gives the estimated degree exponent according to k min for networks containing 500000 nodes. Results are well correlated with theory for k min ∈ [30; 300]. When x min is lower than 30, a bias is introduced in the power law by low degree vertices while when k min is higher than 300, the set of vertices having a high degree becomes too small to give an accurate estimate.

Clustering coefficients
The clustering coefficient C i that characterizes vertex v i is the proportion of links between the vertices within its neighborhood (v i excluded) divided by the number of links that could possibly exist between them. For undirected graph, considering two vertices v i and v j , the edges v i → v j and v j → v i are considered identical. Therefore, if a vertex v i has k i neighbors, k i (k i −1) 2 edges could exist among the vertices within its neighborhood. The clustering coefficient for the whole network is the average of the clustering coefficients C i over the set of vertices composing the network, i.e. this is the expectation of the clustering coefficient distribution.
When a vertex is inserted into the network, it is connected to all the vertices of a selected (d+1)-clique. It follows that every vertex having a degree k i = d + 1 has a clustering coefficient of one. Furthermore, when a vertex v i having a degree k i belongs to a (d+1)-clique in which a new vertex is inserted, its degree increases by one and the new inserted neighbor connects to d vertices among the k i vertices that compose its neighborhood previously to the insertion. This leads to the following clustering coefficient for a vertex having a degree k This local clustering coefficient is exactly the same as the one obtained for vertices in RAN [13]. Eq.22 shows that the local clustering coefficient scales as C(k) ∼ k − 1 We average these coefficients using the discrete degree distribution (Eq.8) as follows For d = 2, we get C = 0.813. Figure 6.1 shows that the clustering coefficient increases from 0.813 for d = 2 to 1 as d tends towards infinity. Comparatively, HDRANs have a significantly lower clustering coefficient at low dimension, e.g. for d = 2, a RAN has a clustering coefficient C = .768. Figure 6.1 gives the clustering coefficients for P-RANs estimated experimentally for each dimension from the construction of 10 networks utterances containing 100000 vertices each. The figure gives also the absolute error and its corresponding standard deviation measured comparatively to the theoretical expectation, showing a good match between simulation and the theoretical model.

Average path length
The average path length (APL) is a characteristic of the network topology that is defined as the average number of edges along the shortest paths for all possible pairs of network vertices. Following exactly the derivations already presented in [15,14] for RAN, we address below the average path length for P-RAN.
First, we suppose that any vertex of the P-RAN network is ordered according to its insertion time stamp t that we consider discrete (t ∈ N). It is straightforward to establish that for P-RAN the following property holds (as well as for DAN or RAN) For any two arbitrary vertices i and j all shortest paths from i to j does not pass through a vertex k if k > max(i, j).
Let d(i, j) denotes the distance between vertices i and j, namely the length of a shortest path between vertices i and j. Let σ(N) be the sum of all distances between all the pairs of vertices into the network with order N, e.g. containing N vertices.
Following exactly the approach given in [13] we get the following recursive inequality for σ(N) Considering the inequality Eq.26 as an equation we get the same upper bound for the variation of σ(N) than for RAN where S is a constant. As σ(N) is asymptotically upper bounded by ∼ N 2 .log(N), L(N) is asymptotically upper bounded by log(N), e.g. L(N) increases at most as log(N) with N. Figure 7.1 compares for dimensions 2, 4 and 6 average path lengths for HDRANs and P-RANs and shows that, for a given dimension, average path lengths are shorter for P-RANs than for HDRANs. Nevertheless, as the dimension increases, differences between path lengths vanish. This result was expected since P-RANs have a higher clustering coefficient than RANs.

Conclusion
From previous works on Apollonian Networks, mainly RAN and HDRAN networks, we have introduced what we call Parallel Deterministic or Parallel Random Apollonian Networks. These topologies, for which (d+1)-cliques may accept in their inside more than one vertex fully connected to the vertices composing the clique, are still small world and scale free. This paper reports the main statistical properties of P-RANs. For such networks, the degree exponent is in between 2 (2 being attained at the limit when the dimension tends towards infinity) and 2.5 (when the dimension of the network is 2) or 3 if we accept the limit case of Apollonian networks in dimension one. We have shown analytically that, comparatively to RAN or HDRAN, P-RAN networks are characterized with higher clustering coefficients and shorter average path lengths. P-RAN are also characterized by their parallel degree distribution and parallel coefficient that quantify the number of vertices inside the (d+1)-cliques that compose P-RAN networks. The simulations results provided through out the paper are in very good conformance with the analytical expectations.