Concepts of dynamic Estrada indices

We first review the dynamic Estrada index [18] and then introduce the related concepts of dynamic (normalized) Laplacian Estrada indices with some general properties.

Let G be a simple graph with n vertices. Denote by A = A(G) the adjacency matrix of G, and λ₁(A), λ₂(A), ⋯, λ_n(A) the eigenvalues of A. Since A is a real symmetric matrix, we assume that the eigenvalues are labeled in a non-increasing manner as λ₁(A) ≥ λ₂(A) ≥ ⋯ ≥ λ_n(A). Let tr(⋅) represent the trace of a matrix. For k = 0, 1, ⋯, define $M_k(A)={\sum }_{i=1}^n{\lambda }_i^k(A)$ the kth spectral moment of the adjacency matrix. It follows from (1) that the Estrada index of G can be written as (2) where the power-series expansion of matrix exponential e^A is employed: (3) with I being the n-dimensional identity matrix. An extension to weighted graphs can be found in [30].

Suppose we have an evolving graph, namely, a time-ordered sequence of simple graphs G₁, G₂, ⋯, G_N over a fixed set V of n vertices, at the time points 1, 2, ⋯, N. Let A_t = A(G_t) be the adjacency matrix for the snapshot graph G_t for t = 1, 2, ⋯, N. Let m_t denote the number of edges of G_t and λ₁(A_t) ≥ λ₂(A_t) ≥ ⋯ ≥ λ_n(A_t) the eigenvalues of A_t.

Definition 1. [18] The Estrada index of an evolving graph G₁, G₂, ⋯, G_N is defined as (4) The following concept of dynamic walk in an evolving graph is introduced in [3].

Definition 2. A dynamic walk of length k from vertex v₁ ∈ V to vertex v_k+1 ∈ V consists of a sequence of edges {v₁, v₂}, {v₂, v₃}, ⋯, {v_k, v_k+1} and a non-decreasing sequence of time points 1 ≤ t₁ ≤ t₂ ≤ ⋯ ≤ t_k ≤ N such that the (v_i, v_i+1) element of A_ti, (A_ti)_{vi, vi+1} ≠ 0 for 1 ≤ i ≤ k.

In the light of (3), the product of matrix exponentials $e^{A_{t_1}}{e}^{A_{t_2}}\cdots e^{A_{t_k}}$ is equal to the summation of all products of the form where t_s1 < t_s2 < ⋯ < t_sr are all the distinct values in the time sequence t₁ ≤ t₂ ≤ ⋯ ≤ t_k, and the multiplicity of t_si is δ_i, namely, δ_i = ∑_{tj = tsi} η_j, 1 ≤ i ≤ r. Note that the matrix product A_t1 A_t2 ⋯ A_tk has (v_p, v_q) element that counts the number of dynamic walks of length k from v_p to v_q on which the ith step of the walk takes place at time t_i, 1 ≤ i ≤ k. Thus, by setting $\ell ≔{\sum }_{i=1}^r{\delta }_i={\sum }_{j=1}^k{\eta }_j$, we observe that the dynamic Estrada index (4) is a weighted sum of the numbers of closed dynamic walks of all lengths, where the number of walks of length ℓ (with δ_i edges followed at time t_si, 1 ≤ i ≤ r) is penalized by a factor $\frac{1}{{\eta }_1!{\eta }_2!\cdots {\eta }_k!}$, naturally extending the (static) Estrada index (2).

Dynamic normalized Laplacian Estrada index.

The normalized Laplacian matrix ℒ = ℒ(G) is defined as [19] where deg_G(v_i) is the degree of vertex v_i in G. If there is no isolated vertex in G, we have ℒ(G) = D^−1/2(G)L(G)D^−1/2(G). Assume that λ₁(ℒ) ≥ λ₂(ℒ) ≥ ⋯ ≥ λ_n(ℒ) = 0 are the normalized Laplacian eigenvalues of G.

The normalized Laplacian Estrada index is put forward in [35] as (7) See also [22] for an essentially equivalent definition. ℒEE(G) has been addressed for a class of tree-like fractals [36]. Following the same reasoning in (2), we obtain ℒEE(G) = tr(e^ℒ). In analogy to (4) and (6), we have the following

Definition 4. The normalized Laplacian Estrada index of an evolving graph G₁, G₂, ⋯, G_N is defined as (8) where ℒ_t = ℒ(G_t), t = 1, 2, ⋯, N.

The following basic properties of the dynamic normalized Laplacian Estrada index can be easily deduced.

1. 5^∘. For N ≤ 3, and, for general N,
2. 6^∘. If $G_N=\overline{K_n}$,
3. 7^∘. Suppose that G₁ = G₂ = ⋯ = G_N. Then whereas $ℒEE(G_1^{(N)})=ℒEE(G_1)$.
4. 8^∘. If G₁ = G₂ = ⋯ = G_N is an r-regular bipartite graph (r ≥ 1). Then

To see 8^∘, we have where the equality is attained if and only if λ₂(ℒ₁) = ⋯ = λ_n(ℒ₁) = 0. This condition is equivalent to $G_1=\overline{K_n}$ or $G_1=K_2\cup \overline{K_{n-2}}$, which contradicts the assumption. Theorem 3.4 in [35] can be reproduced by setting N = 1.

Bounds for dynamic Laplacian Estrada index

Proposition 1. Let G₁, G₂, ⋯, G_N be an evolving graph over a set V of size n. Then

1. (i). $LEE(G_1,G_2,\cdots ,G_N)\le {\left({\prod }_{t=1}^{N}LEE(G_t^{(N)})\right)}^{1/N}\le \frac{1}{N}{\sum }_{t=1}^{N}LEE(G_t^{(N)})$.
   The equalities are attained if and only if G₁ = G₂ = ⋯ = G_N.
2. (ii). max{LEE(G₁), LEE(G₂)} ≤ LEE(G₁, G₂) ≤ min{e^λ₁(L₁) LEE(G₂), e^λ₁(L₂) LEE(G₁)}.
   The equalities are attained if and only if $G_1=\overline{K_n}$ or $G_2=\overline{K_n}$.

Proof. (i) Since the matrices ${\left\{e^{L_t}\right\}}_{t=1}^N$ are positive definite, it follows from the extended Bellman inequality ([37, p. 481] or [38]) that The last inequality follows from the arithmetic-geometric means inequality. Both equalities are attained if and only if G₁ = G₂ = ⋯ = G_N.

(ii) Note that Therefore, LEE(G₁, G₂) ≥ e^λ_n(L₁)tr(e^(L₂) = LEE(G₂) since λ_n(L₁) = 0, and LEE(G₁, G₂) ≤ e^λ₁(L₁)tr(e^(L₂) = e^λ₁(L₁) LEE(G₂). Since λ_i(L₁) = 0 for all i is equivalent to $G_1=\overline{K_n}$, the above two equalities hold if and only if $G_1=\overline{K_n}$. The desired result then follows from the property 1^∘.

Remark. By counting the number of closed walks, it is shown in [18, Prop. 1] that (9) However, this does not hold for LEE even in the case of N = 2. To see this, we take $G_1=\overline{K_n}$. Then,

Recall that m_t is the number of edges in G_t, t = 1, 2, ⋯, N.

Proposition 2. The Laplacian Estrada index of an evolving graph G₁, G₂, ⋯, G_N over a set of n vertices with N = 2 is bounded by The equality on the left-hand side is attained if and only if $G_1=G_2=\overline{K_n}$; and the equality on the right-hand side is attained if and only if $G_1=G_2=\overline{K_n}$ or $G_1=G_2=K_2\cup \overline{K_{n-2}}$.

Proof. Lower bound. Based on the well-known Golden-Thompson inequality (see e.g. [38]) we obtain Therefore, (10)

Using Proposition 1 (i), we obtain where the second inequality comes from the interlacing theorem in which the equality holds if and only if $G_1=G_2=\overline{K_n}$. Note that L₁ + L₂ = L(G₁ ⊔ G₂). Then, (11)

On the other hand, the arithmetic-geometric means inequality yields (12) Combining (10) with (11) and (12), we have Since ${(LEE(G_1,G_2)-\frac{1}{2})}^2\ge \frac{1}{4}+n(n-1)e^{\frac{4(m_1+m_2)}{n}}\ge 0$, we arrive at The equality is attained if and only if $G_1=G_2=\overline{K_n}$.

Upper bound. Since (e^L₁ − e^L₂)² is a positive semi-definite matrix, we obtain where $Zg(G)≔{\sum }_{i=1}^n{\mathrm{deg}}_G^2(v_i)$ is called the first Zagreb index of graph G [39].

Note that ${\sum }_{i=1}^n{(2{\lambda }_i(L_1))}^k\le {({\sum }_{i=1}^{n}2{\lambda }_i(L_1))}^k$ with equality if and only if at most one of λ₁(L₁), λ₂(L₁), ⋯, λ_n(L₁) is non-zero, or equivalently, $G_1=\overline{K_n}$ or $G_1=K_2\cup \overline{K_{n-2}}$. Hence, (13)

For t = 1, 2, denote by n_t the number of non-isolated vertices in G_t. We have with equality if and only if G_t = K_n or $G_t=K_2\cup \overline{K_{n-2}}$. Consequently, which yields the desired upper bound, in which equality is attained if and only if G₁ = G₂ = K_n or $G_1=G_2=K_2\cup \overline{K_{n-2}}$.

The previously communicated bounds for EE(G₁, G₂) in [18, Prop. 4] can not be attained. Here, we get tight bounds for LEE(G₁, G₂) thanks to the nice properties of Laplacian eigenvalues. We mention that a version of the thermodynamic inequality might also be used here [40, Lem. 1]. Let δ(G) and Δ(G) be the minimum and maximum degrees of graph G, respectively. We in the following establish new tight bounds with the help of the minimum and maximum degrees.

Proposition 3. The Laplacian Estrada index of an evolving graph G₁, G₂, ⋯, G_N over a set V of n vertices with N = 2 is bounded by where δ₁₂ ≔ δ(G₁ ⊔ G₂) and Δ₁₂ ≔ Δ(G₁ ⊔ G₂). The equalities are attained if and only if $G_1=G_2=\overline{K_n}$.

Proof. Lower bound. As in the proof of Proposition 2, we have (10) and (12). In the following, we aim to obtain a new estimate involving δ₁₂ and Δ₁₂ for the first term on the right-hand side of (10).

We have (14) since by the Cauchy-Schwarz inequality. The equality holds if and only if G₁ ⊔ G₂ is regular.

By using Proposition 1 (i), as in the proof of Proposition 2, we obtain (15) where the last inequality follows from the fact with equality attained if and only if G₁ ⊔ G₂ is a regular graph. Indeed, this can be seen by expanding the expression ∑_{v ∈ V}(deg_{G1 ⊔ G2}(v) − δ₁₂)(deg_{G1 ⊔ G2}(v) − Δ₁₂), which is clearly non-positive.

Combining (10) with (12), (14) and (15), we obtain Therefore, (16) where the last inequality follows from the following three basic estimates: The desired lower bound then readily follows from (16).

Upper bound. As commented above, for t = 1, 2, we have with equality attained if and only if G_t is a regular graph. Owing to (13), we obtain which concludes the proof.

Remark. The bounds established in Proposition 2 and Proposition 3 are incomparable in general. In fact, for the lower bound, we note that for the upper bound, we note that

We mention here that in the case of N = 1, some researchers bound the Laplacian Estrada index by using some more complicated graph-theoretic parameters, including graph Laplacian energy [31], namely, ∑_i∣λ_i(L)∣, and the first Zagreb index [41]. For more results on the graph energy, see e.g. [42–45]. The first Zagreb index was generalized to the zeroth-order general Randic index by Bollobás and Erdos [46], which was also useful in chemistry [47, 48]. In contrast, we only employ some of the most plain quantities to estimate the dynamic Laplacian Estrada index since (i) they are relatively easily accessible for real-life complex networks of interest to us, and (ii) our motivation comes from the potential application in gauging robustness for large-scale networks [9, 13, 16], where computational complexity matters.

Bounds for dynamic normalized Laplacian Estrada index

The following proposition can be proved similarly as Proposition 1. Hence, we only state the result and omit its proof.

Proposition 4. Let G₁, G₂, ⋯, G_N be an evolving graph over a set V of size n. Then

1. (i). $ℒEE(G_1,G_2,\cdots ,G_N)\le {\left({\prod }_{t=1}^N\mathrm{\text{tr}}(e^{N{ℒ}_t})\right)}^{1/N}\le \frac{1}{N}{\sum }_{t=1}^N\mathrm{\text{tr}}(e^{N{ℒ}_t})$.
   The equalities are attained if and only if G₁ = G₂ = ⋯ = G_N.
2. (ii). max{ℒEE(G₁), ℒEE(G₂)} ≤ ℒEE(G₁, G₂) ≤ min{e^{λ₁(ℒ₁)}ℒEE(G₂), e^{λ₁(ℒ₂)}ℒEE(G₁)}.
   The equalities are attained if and only if $G_1=\overline{K_n}$ or $G_2=\overline{K_n}$.

Remark. The inequality (9) does not hold for ℒEE either (even in the case of N = 2). To see this, we take $G_1=\overline{K_n}$. Then,

Proposition 5. The normalized Laplacian Estrada index of an evolving graph G₁, G₂, ⋯, G_N over a set of n (n ≥ 2) vertices with each snapshot graph being connected and N = 2 is bounded by

Proof. Lower bound. From the well-known Neumann inequality, we obtain An elementary result of the normalized Laplacian eigenvalues [19] indicates that 1 ≤ e^λ_i(ℒ₁) ≤ e² and 1 ≤ e^λ_i(ℒ₂) ≤ e² for all 1 ≤ i ≤ n. Hence, applying an inverse of the Hölder inequality (see [37, p. 18] or [49]) gives (17)

By the arithmetic-geometric means inequality, we obtain (18) where in the last equality we used the equation ${\sum }_{i=1}^n{\lambda }_i({ℒ}_1)=n$ since G₁ is connected [19].

Define a function $f(x)≔1+2e^{2x}+(n-2)e^{\frac{2(n-x)}{n-2}}$. It is easy to check that $f^{\prime }(x)=4e^{2x}-2e^{\frac{2(n-x)}{n-2}}\ge 0$ if $x\ge \frac{2n-(n-2)\ln 2}{2(n-1)}$. Since ${\lambda }_1({ℒ}_1)\ge \frac{n}{n-1}\ge \frac{2n-(n-2)\ln 2}{2(n-1)}$ for all n ≥ 2 [19], it follows from (18) that (19) Likewise, we have (20) Combining these with (17) gives the desired lower bound

Moreover, note that if the equalities in (19) and (20) are attained, then n = 2, namely, G₁ = G₂ = K₂. But $ℒEE(K_2,K_2)=e^4+1>\frac{2e^2(1+2e^4)}{e^4+1}$, which means that the equality can not hold.

Upper bound. Again from the Neumann inequality, we arrive at (21) where the last inequality follows from the Cauchy-Schwarz inequality.

Define the Randić index of a connected graph G as $R_{-1}(G)={\sum }_{u,v\mathrm{\text{adjacent}}}{\mathrm{deg}}_G^{-1}(u){\mathrm{deg}}_G^{-1}(v)$. It is elementary that ${\sum }_{i=1}^n{\lambda }_i^2(ℒ(G))=n+2R_{-1}(G)$; see e.g. [50]. We have (22) Since G₁ is connected, we have [50] (23) Thus, (22) leads to the following estimation Combining this and an analogous estimation for ℒ₂ yields the desired upper bound by using (21).

Finally, we note that the equalities in (23) hold if and only if G₁ is a 1-regular graph, namely, $G_1=\underset{n/2\mathrm{\text{multiples}}}{\underbrace{K_2\cup K_2\cdots \cup K_2}}$. But the first inequality in (22) is not tight for such choice of G₁. Therefore, the equality in the upper bound can not be attained.

Remark. Recall that δ(G_t) is the minimum degree of G_t. The above proof actually gives a strong upper bound: (24)

Proposition 6. The normalized Laplacian Estrada index of an evolving graph G₁, G₂, ⋯, G_N over a set of n (n ≥ 2) vertices with each snapshot graph being connected and N = 2 is bounded by

Proof. As in the proof of Proposition 5, we have inequality (21).

Now that G₁ is connected, we know that λ_n(ℒ₁) = 0, λ₁(ℒ₁) ≤ 2, and ${\sum }_{i=1}^n{\lambda }_i({ℒ}_1)=n$ [19]. Therefore, (25)

Define a function f(x) = e^x − x, which is non-decreasing on [0, +∞). Thus, (23) and (25) indicate that An analogous estimate for G₂ also holds. Combining these with (21) yields the desired upper bound.

Finally, note that the second equality is attained in (25) if and only if λ₁(ℒ₁) = 0, which is equivalent to $G_1=\overline{K_n}$. However, this contradicts the assumption that G₁ is connected. Therefore, the equality in the upper bound can not be attained. The proof is complete.

Remark. It is direct to check that if the above upper bound is better than that in (24).

Similarly as commented at the end of the above section, for the static case of N = 1, some bounds for the normalized Laplacian Estrada index are reported in the literature by involving more complicated graph-theoretic parameters, including normalized Laplacian energy [22], and the Randic index [35, 51], which are a bit cumbersome when large-scale network applications are taken into account.

Numerical study

We consider a random evolving network G₁, G₂ (see Fig. 1), which is introduced in a seminal paper by Watts and Strogatz [52]. This network is often called WS small-world model, which enables the exploration of intermediate settings between purely local and purely global mixing. As demonstrated in [52], when the rewiring probability is taken around 0.01 (as we considered here), the model is highly clustered, like regular lattices, yet has small characteristic path lengths, like random graphs. This qualitative phenomenon is prevalent in a range of networks arising in nature and technology [53].

Download:

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

Fig 1. Illustration of an evolving small-world graph G₁, G₂.

G₁ is a ring lattice over a vertex set V of size n. It is a 4-regular graph, where each vertex is connected to its 4 nearest neighbors. G₂ is obtained by rewiring each edge—i.e., choosing a vertex v ∈ V and an incident edge, reconnecting the edge to a vertex that is not a neighbor of v—with probability p = 0.01 uniformly at random. In the simulations below, we take n ∈ [100, 1000].

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

Fig. 2 shows the variations of the (dynamic) Estrada indices with the network size n. The results gathered in Fig. 2 allow us to draw several interesting comments. First, as expected from the mathematical result [18, Prop. 4], the numerical values of EE(G₁, G₂) lie between our general upper and lower bounds (remarkably much closer to one than the other; see the main panel). Second, both the Estrada index and the dynamic Estrada index grow gradually as the network size increases. Third, the Estrada indices EE(G₂) and EE(G₁ ∪ G₂) are close to each other. However, both of them are significantly smaller than the dynamic Estrada index EE(G₁, G₂), underscoring the relevance of dynamic Estrada index—neither the static snapshot graph nor the aggregated graph constitutes a reasonable approximation to the evolving graph itself.

Download:

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

Fig 2. Logarithm of the dynamic Estrada index ln(EE(G₁, G₂)) as a function of network size n.

Main panel: numerical results (red circles) and theoretical bounds (upper and lower bars) given by [18, Prop. 4]. Each data point is obtained for one network sample. Inset: simulation results for EE(G₁, G₂) (dotted line), EE(G₁ ∪ G₂) (dashed line), and EE(G₂) (solid line) via an ensemble averaging of 100 independent random network samples.

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

In Fig. 3 and Fig. 4, we display the variations of the (dynamic) Laplacian Estrada indices and the (dynamic) normalized Laplacian Estrada indices, respectively, with the network size. Analogous observations can be drawn. For example, the behavior of LEE(G₁, G₂) (and ℒEE(G₁, G₂)) differentiates from that of LEE(G₂) (and ℒEE(G₂)) or LEE(G₁ ∪ G₂) (and ℒEE(G₁ ∪ G₂)) dramatically. Moreover, when comparing Fig. 2 with Fig. 3 and Fig. 4, we see that the difference between dynamic and static cases turns out to be much more prominent in the Laplacian matrix and normalized Laplacian matrix settings than the adjacency matrix setting. For example, when the network size is taken as n = 1000, the difference ∣EE(G₁, G₂) − EE(G₁ ∪ G₂)∣ ≈ 4 × 10³; but ∣LEE(G₁, G₂) − LEE(G₁ ∪ G₂)∣ ≈ 7 × 10⁵ and ∣ℒEE(G₁, G₂) − ℒEE(G₁ ∪ G₂)∣ ≈ 1.4 × 10⁴.

Download:

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

Fig 3. Logarithm of the dynamic Laplacian Estrada index ln(LEE(G₁, G₂)) as a function of network size n.

Main panel: numerical results (red circles) and theoretical bounds (upper and lower bars) given by Proposition 2. Each data point is obtained for one network sample. Inset: simulation results for LEE(G₁, G₂) (dotted line), LEE(G₁ ∪ G₂) (dashed line), and LEE(G₂) (solid line) via an ensemble averaging of 100 independent random network samples.

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

Download:

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

Fig 4. Logarithm of the dynamic normalized Laplacian Estrada index ln(ℒEE(G₁, G₂)) as a function of network size n.

Main panel: numerical results (red circles) and theoretical bounds (upper and lower bars) given by Proposition 5. Each data point is obtained for one network sample. Inset: simulation results for ℒEE(G₁, G₂) (dotted line), ℒEE(G₁ ∪ G₂) (dashed line), and ℒEE(G₂) (solid line) via an ensemble averaging of 100 independent random network samples.

https://doi.org/10.1371/journal.pone.0123426.g004

Two remarks are in order. First, the theoretical upper and lower bounds for all the three dynamic Estrada indices shown in Figs. 2, 3, and 4 are fairly far apart, due to the fact that our bounds are general and valid for all graphs. This is similar to the situation of static graph case, see [12]. Thus, it would be interesting to identify the specific locations of concrete graphs (such as the WS small-world model studied here) in the spectrum. Second, extensive simulations have been performed for some different values of rewiring probability p and ring lattice degree k, all yielding quantitatively similar phenomena.