Non-homogeneous weighted hierarchical modular networks

In order to construct our model, we have referred to a large number of references. The number of the initial nodes is 5 in [1] and un-weight in [1, 2]. By contrast, we may expand the number of initial nodes to M+1 and add a weight to each edge of the network. So the results in [1, 2] are just special cases. Recently, Carletti [4] proposed a non-homogeneous weighted fractal network aiming to construct weighted networks with some a priori prescribed topology depending on two kinds of parameters: the number of copies and the scaling factors. Enlightened by Carletti’s network, we will build weighted hierarchical networks depending on M scaling factors (i.e., r₁,r₂,⋯,r_M).

Now let us introduce a new model for the weighted hierarchical networks in our paper, which is controlled by a positive integer M and M real numbers r₁,r₂,⋯,r_M ∈ (0,1) with a modular structure which can be constructed in an iterative way. We denote by G_k the network model after k (k ≥ 1) iterations.

(1) Initially k = 1, the network G₁ consists of a central node, called the hub (root) node A, and M peripheral (external) nodes with M ≥ 2. All these initial M+1 nodes are fully connected to each other, forming a complete graph. Each of the edges carries a standard initial weight w = 1.

(2) At the second generation (k = 2), we generate M copies of G₁ whose weighted edges have been scaled respectively by a factor r₁,r₂,⋯,r_M. The M copies are labeled as $G_1^{(1)},G_1^{(2)},\cdots ,G_1^{(M)}$. And we connect the M external nodes of each replica $G_1^{(i)}(i=1,2,\cdots ,M)$ to the root of the original G₁ through edges of unitary weight. The original G₁ in G₂ has label $G_1^{(0)}$. The hub of the original $G_1^{(0)}$ and M² peripheral nodes in the replicas $G_1^{(i)}(i=1,2,\cdots ,M)$ become the hub and peripheral nodes of G₂, respectively. The hub node in G₂ also has label A. The process is described in Fig. 1.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 1. (color online) The iterative construction process from G₁ to G₂ for the case of M = 3.

G₁ includes 4 initial nodes and 6 edges with unit weight; in G₂, $G_1^{(i)}$ is a copy of G₁ scaled by a factor r_i(i = 1,2,3). The 3 external nodes of each replica $G_1^{(i)}(i=1,2,3)$ to the root of the original G₁ through edges of unitary weight.

https://doi.org/10.1371/journal.pone.0121946.g001

(3) Suppose one has G_k−1, the next generation network G_k can be obtained from G_k−1 by adding M replicas of G_k−1, whose weighted edges have been scaled respectively by a factor r₁,r₂,⋯,r_M. The M copies are labeled as $G_{k-1}^{(1)},G_{k-1}^{(2)},\cdots ,G_{k-1}^{(M)}$. And their external nodes are linked to the hub of the original G_k−1 through edges of unitary weight. The original G_k−1 in G_k has label $G_{k-1}^{(0)}$. In G_k, its hub is the hub of the $G_{k-1}^{(0)}$, and its external nodes are composed of all the peripheral nodes of the $G_{k-1}^{(i)}(i=1,2,\cdots ,M)$. The hub node in G_k always has label A. Moreover, hub node A is always the same, that there are N_k (order of the network) external nodes at each stage. The classification of nodes is described in Fig. 2.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 2. (color online) Classification of nodes in network G₃ for the case of M = 3.

The filled circles, open circles, full square and triangles represent peripheral nodes, locally peripheral nodes, hub nodes and locally hub nodes, respectively. In G₃, $G_2^{(i)}$ is a copy of G₂ scaled by a factor r_i(i = 1,2,3). The 9 external nodes of each replica $G_2^{(i)}(i=1,2,3)$ to the root of the original G₁ through edges of unitary weight.

https://doi.org/10.1371/journal.pone.0121946.g002

(4) Repeating the replication and connection steps, we obtain the weighted hierarchical modular networks.

Average degree and average node strength

In G_k, the number of nodes, often called order of the network denoted as N_k, is and the number of edges at the time of k is Therefore, the average degree is asymptotically given by when k increases to infinity.

Denote by $w_i^k$ the weighted degree of node i at iteration k, we also call it node strength [17] and the node strength satisfies the following formula $w_i^k={\displaystyle \sum _j}{w}_{ij}^{(k)}$, where $w_{ij}^{(k)}$ stands for the weight of the edge (ij) ∈ G_k. According to the recursive construction in our weighted hierarchical networks, we can explicitly compute the total node strength, $w_k={\displaystyle \sum _i}{w}_i^{(k)}$, and easily show that where $r={\displaystyle \sum _{j=1}^M{r}_j}$. In view of r_j < 1(j ∈ i,2,⋅⋅⋅,M), it trivially follows that r < M, so we can conclude the average node strength goes to zero when k increases to infinity:

Average weighted shortest path

By definition, the average weighted shortest path [18] of the graph G_k is given by (1) where (2) being $p_{ij}^{(k)}$ the weight shortest path linking nodes i and j in G_k. Taking advantage of the recursive construction, we can decompose the sum Λ_k into two terms: (3) where the first contribution takes into account all paths starting from and arriving at nodes belong to the same $G_{k-1}^{(\alpha )}(\alpha =0,1,2,\cdots ,M)$. Using the scaling mechanism for the edges, the first contribution can be easily identified with (1+r)Λ_k−1. The second term takes into account all paths starting from and arriving at nodes belong to the different $G_{k-1}^{(\alpha )}(\alpha =0,1,2,\cdots ,M)$. Note that the paths that contribute to Ω_k−1 must all go through at least hub node A in G_k. The analytical expression for Ω_k−1, called the length of crossing paths, is found below.

Denote ${\Omega }_{k-1}^{\alpha ,\beta }$ as the sum of length for all shortest paths with starting from nodes belong to $G_{k-1}^{(\alpha )}$ and arriving at nodes belong to $G_{k-1}^{(\beta )}$, respectively. Then the sum Ω_k−1 is

In order to find ${\Omega }_{k-1}^{\alpha ,\beta }$, we define Then (4) being ${\Delta }_{k-1}={\Delta }_{k-1}^{(0)}+{\Delta }_{k-1}^{(1)}+\cdots +{\Delta }_{k-1}^{(M)}$.

Thus, the problem of determining Ω_k is reduced to find Δ_k.

We can prove that (5)

It is obtained as follow.

According to the particular construction of the weighted hierarchical modular network, we can find that Δ_k obeys the following recursive relation. Then we have

1. (a). Δ₁ = Δ₀ + (r + M) + M², (see Fig. 1)
2. (b). Δ₂ = Δ₁ + rΔ₀ + (M + 1)(r + M) + (r² + M²) + M³, (see Fig. 2)
3. (c). Δ₃ = Δ₂ + rΔ₁ + r²Δ₀ + (M + 1)²(r + M) + (M + 1)(r² + M²) + (r³ + M³) + M⁴,
4. (d). Δ₄ = Δ₃ + rΔ₂ + r²Δ₁ + r³Δ₀ + (M + 1)³(r + M) + (M + 1)²(r² + M²) + (M + 1)(r³ + M³) + (r⁴ + M⁴) + M⁵,
   ⋮
5. (e). Δ_k−2 = Δ_k−3 + rΔ_k−4 + r²Δ_k−5 + ⋯ + r^k−3Δ₀ + (M + 1)^k−3(r + M) + (M + 1)^k−4(r² + M²) + ⋯ + (r^k−2 + M^k−2) + M^k−1,
6. (f). Δ_k−1 = Δ_k−2 + rΔ_k−3 + r²Δ_k−4 + ⋯ + r^k−2Δ₀ + (M + 1)^k−2(r + M) + (M + 1)^k−3(r² + M²) + ⋯ + (r^k−1 + M^k−1) + M^k,
7. (g). Δ_k = Δ_k−1 + rΔ_k−2 + r²Δ_k−3 + ⋯ + r^k−1Δ₀ + (M + 1)^k−1(r + M) + (M + 1)^k−2(r² + M²) + ⋯ + (r^k + M^k) + M^{k + 1}.

From the above equations, it is not difficult to have

${\left(r+1\right)}^{k-2}\left((\text{b})-r\times (\text{a})\right):$

${\left(r+1\right)}^{k-3}\left((\text{c})-r\times (\text{b})\right):$

$(r+1)((\mathrm{\text{f}})-r\times (\mathrm{\text{e}})):$

(g)−r × (f): Adding up these equations, we have

Using Δ₁ = M + (r + M) + M² = M² + 2M + r. So we have

Inserting the obtained result for Δ_k given in Equation (5) into Equation (4), we obtain (6) Considering the initial condition, from Equation (3) and Equation (6), we can obtain

Therefore (7) which provides the following asymptotic behavior in the limit of large k, when k → ∞ (8)

Thus the network grows unbounded but with the logarithm of the network size, while the weighted shortest distances stay bounded. In other words, in the infinite network order (which implies infinite number of nodes), the average weighted shortest path tends to a constant value which depends only on the size of the original graph and the weight.

Average shortest path

In the preceding text we have studied the average weighted shortest path on the non-homogeneous weighted hierarchical modular network. Now we can also compute the average shortest path, l_k, formally obtained by setting r₁ = r₂ = ⋯ = r_M = 1 in the previous formulas Equation (1) and Equation (2). Hence

We make thus we obtain the expression of Z as Then, from the above equations we get the following relation

So, we can get

Taking the initial condition Λ₁ = (M+1)M into account, we obtain

In the above expression, so, we get the result

Therefore, (9) which provides the following asymptotic behavior, when k → ∞ (10) (11) From the above quantity, the average shortest path grows as the logarithm of the total number of nodes. T. Carletti and S. Righi [4] have defined a class of weighted fractal networks. The average shortest path, l_k of weighted fractal networks grows as the logarithm of the total number of nodes.

We have made the comparisons of theoretical predictions and simulation results of the average weighted shortest path. Under Floyd algorithm, data points are obtained by simulating the network at generation k = 2,3,4,5 respectively (see Fig. 3).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. The comparisons of theoretical predictions and simulation results the renormalized average weighted shortest path $\widetilde{{\lambda }_k}$ of λ_k.

versus the iteration, where M = 3 and ${\tilde{\lambda }}_k=\frac{{\lambda }_k-\min \{{\lambda }_k\}}{\max \{{\lambda }_k\}-\min \{{\lambda }_k\}}$. Under Floyd algorithm, data points are obtained by simulating the network at generation k = 2,3,4,5, respectively.

https://doi.org/10.1371/journal.pone.0121946.g003