Gamma radiation effects on vitamins, antioxidant, internal and molecular structure of Purslane seeds

1.   Introduction

The consensus problem has been primarily investigated in management science, and statistics ^[1,2,3]. Nowadays, it has become a challenging and hot research area for multiagent systems ^[4,5,6]. In these settings, consensus means that all agents reach an agreement on one common issue. Consensus problems have emerged in various disciplines, such as graph decision making ^[7,8], distributed computing ^[9], sensor networks ^[10,11], biological systems ^[12,13], and human group dynamics ^[14]. Due to their broad applications, consensus problems have attracted considerable attention in recent years ^{[15,16,17,18,19,20,21]}.

Convergence speed, communication time-delay robustness, and network coherence are the three primary aspects of the consensus protocol. Convergence speed measures the time of convergence of the consensus algorithm. It has been proved that convergence speed is determined by the second smallest Laplacian eigenvalue $\lambda_2$ ^[4,22]. Communication time-delay robustness refers to the ability of the consensus algorithm to resist against communication delay between agents ^[23,24], with the maximum delay allowable being determined by the largest Laplacian eigenvalue $\lambda_N$ ^[4,22]. Network coherence quantifies the robustness of the consensus algorithm against stochastic external disturbances, and it is governed by all nonzero Laplacian eigenvalues ^[22,25]. As we all know, $\lambda_2(G)\geq \lambda_2(H)$ when $H$ is a spanning subgraph of $G$ ^[26,27]. It means that adding edges to a graph may increase its second smallest Laplacian eigenvalue. Zelazo et al. ^[28] provided an analytic characterization of how the addition of edges improves the convergence speed. It is well-known that $\Delta+1\leq \lambda_N \leq 2\Delta$, where $\Delta$ is the maximum vertex degree ^[26]. Wu and Guan ^[29] found that we can improve the robustness to time-delay by deleting some edges linking the vertices with the maximum degree. As for network coherence, Summers et al. ^[30] considered how to optimize coherence by adding some selected edges. Recently, network coherence on deterministic networks has become a new focus. Previously studied networks include ring, path ^[31], star, complete graph, torus graph ^[25], fractal tree-like graph ^[5,32], Farey graph ^[33], web graph ^[34], recursive trees ^[35,36], Koch network ^[37], hierarchical graph, Sierpinski graph ^[22], weighted Koch network ^[38], windmill-type graphs ^[15], 4-clique motif network, and pseudofractal scale-free web ^[39]. Among all these graphs, the complete graph presents optimal structure and the best performance for noisy consensus dynamics. However, the complete graph is a dense graph, resulting in high communication costs. In the real-world, it has been shown that networks are often sparse, small-world, and scale-free. As such, Yi et al. ^[39] asked two open questions: What is the minimum scaling of the first-order coherence for sparse networks? Is this minimal scaling achieved in real scale-free networks? We will give a positive answer to these two questions in this paper.

Another interesting question about network coherence is how network structural characteristics affect network coherence ^[22,33,39]. It has been shown that the scale-free behavior and the small-world topology can significantly improve network coherence ^[33,39]. Clearly, the star ^[31] cannot be small-world for its small clustering coefficient. But the first-order coherence of a large star will converge to a small constant. The pseudofractal scale-free web ^[40] and the Farey graph ^[41] are two famous small-world networks with high clustering coefficient. However, the scale of the first-order coherence on the Farey graph is much larger than that on the pseudofractal scale-free web ^[22,33]. So, some other network structural characteristics can affect the first-order coherence. Yi et al. ^[22] pointed to the scale-free behavior, which is absent on the Farey graph. However, the Koch network ^[42] is small-world and scale-free, and the first-order coherence on the Koch network scales with the order of the network. In addition, it is clear that the complete graph and the star are not scale-free, but the first-order coherence on these two graphs are very small. As a result, something else can affect the network coherence. In this paper, by analyzing and comparing several studied networks, we will give our answer to the above question.

The outline of this work is as follows: In Section 2, we present some notations and definitions in graph theory and consensus problems. In Section 3, we construct the hierarchical small-world network. In Section 4, we compute the Laplacian eigenvalues and the network coherence. In Section 5, we make a conclusion.

2.   Preliminaries

Let $G = (V, E)$ be a connected and undirected graph (network). $|S|$ denotes the cardinality of the set $S$. The order (number of vertices) and the size (number of edges) of $G$ are $n = |V|$ and $m = |E|$, respectively. If $e = \{u, v\}$ is an edge of $G$, we say vertices $u, v$ are adjacent by $e$, and $u$ is a neighbor of $v$. Let $N_G(v)$ denote the set of neighbors of $v$ in graph $G$. The degree of vertex $v$ in graph $G$ is given by $d_G(v) = |N_G(v)|$. We denote the maximum and minimum vertex degrees of $G$ by $\Delta$ and $\delta$, respectively. Let $S$ be a subset of vertex set $V$. $G-S$ is the graph obtained from $G$ by deleting all vertices in $S$. If $G-S$ is disconnected, we call $S$ a vertex cut set of $G$. The vertex connectivity $c_v$ of graph $G$ is defined as the minimum order of all vertex cut sets. Similarly, we can define the edge connectivity $c_e$.

The density of graph $G$ is given by ^[43]

Clearly, $0\leq d\leq1$. $G$ is a sparse graph if and only if $d\ll1$.

In order to improve readability and help the readers follow the derivations more easily, we list all frequently used symbols in Table 1.

2.1.   Key graph matrices

The adjacency matrix of graph $G$ is a symmetric matrix $A = A(G) = [a_{i, j}]$, whose $(i, j)$-entry is

The degree matrix of graph $G$ is a diagonal matrix $D = D(G) = [d_{i, j}]$ where

The Laplacian matrix of graph $G$ is defined by $L = D-A$. $X$ is a column vector of order $n$. We write $(LX)_i$ as the element corresponding to the vertex $v_i$ in the vector $LX$.

Theorem 2.1. ^[26,27] Let $G$ be a connected and undirected graph with vertex set $V(G) = \{v_1, v_2, \cdots, v_n\}$. $X = (x_1, x_2, \cdots, x_n)^{\top}$ is a column vector. Then the following assertions hold.

(i) $LX = \lambda X$ if and only if, for each $i$,

(ii) The rank of $L$ is $N-1$.

(iii) The row (column) sum of $L$ is zero.

According to $(iii)$, we know that $0$ is an eigenvalue of $L$ with corresponding eigenvector $\mathbf{1} = (1, 1, \cdots, 1)^{\top}$. Since the rank of $L$ is $n-1$, we can write the eigenvalues of $L$ as $0 = \lambda_1 < \lambda_2\leq \lambda_3\leq \cdots\leq \lambda_n$. The second smallest Laplacian eigenvalue $\lambda_2$ is called the algebraic connectivity of the graph. This concept was introduced by Fiedler ^[44]. A classical result on the bounds for $\lambda_2$ is given by Fiedler ^[44] as follows:

We call the largest eigenvalue $\lambda_N$ the Laplacian spectral radius of the graph $G$.

Lemma 2.2. ^[45] Let $G$ be a connected graph on $n$ vertices with at least one edge, then $\lambda_n \geq \Delta+1$, where $\Delta$ is the maximum degree of the graph $G$, with equality if and only if $\Delta = n-1$.

The transition matrix of graph $G$ is a $N$-order matrix $P = [p_{i, j}]$ in which $p_{ij} = \frac{a_{i, j}}{d_G(v_i)}$. So $P = D^{-1}A$. Since $P$ is conjugate to the symmetric matrix $D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$, all eigenvalues of $P$ are real. We denote these eigenvalues as $1 = \theta_1 > \theta_2\geq\cdots\geq\theta_N$.

2.2.   Consensus problems

In this subsection, we give a simple introduction from a graph theory perspective to consensus problems ^[5,22]. We refer the readers to references ^[4,5,22,25] for more details. The information exchange network of a multiagent system can be modeled via graph $G$. Each vertex of graph $G$ represents an agent, and each edge of graph $G$ represents a communication channel. Two endpoints of an edge can exchange information with each other through the communication channel. Usually, the state of the system at time $t$ is given by a column vector $X(t) = (x_1(t), x_2(t), \cdots, x_n(t))^{\top}\in \mathbb{R}^{n}$, where $x_i(t)$ denotes the state (e.g., position, velocity, temperature) of the agent $v_i$ at time $t$. Each agent can update its state according to its current state and the information received from its neighbors. Generally, the dynamic of each agent $v_i$ can be described by $\dot{x}_i(t) = u_i(t)$, where $u_i(t)$ is the consensus protocol (or algorithm).

2.2.1.   Consensus without communication time-delay and noise

Olfati-Saber and Murray ^[4] proved that if

then, the state vector $X(t)$ evolves according to the following differential equation:

and asymptotically converges to the average of the initial states (i.e., for each $i$, $lim_{t\rightarrow \infty}x_i(t) = \frac{1}{n}\sum_{k = 1}^nx_k(0)$, where $x_k(0)$ is the initial state of agent $v_k$). This means that the system with protocol (2.4) can reach an average-consensus. In addition, the convergence speed of $X(t)$ can be measured by the second smallest Laplacian eigenvalue $\lambda_2$ ^[4], i.e.,

Thus, the larger the value of $\lambda_2$, the faster the convergence speed ^[22].

2.2.2.   Consensus with communication time-delay

There are some finite time lags for agents to communicate with each other in many real-world networks. Olfati-Saber and Murray ^[4] showed that if the time delay for all pairs of agents is independent on $t$ and fixed to a small constant $\epsilon$,

then, the state vector $X(t)$ evolves according to the following delay differential equation:

In addition, $X(t)$ asymptotically converges to the average of the initial states if and only if $\epsilon$ satisfies the following condition:

Eq (2.9) shows that the largest Laplacian eigenvalue $\lambda_n$ is a good measure for delay robustness: The smaller the value of $\lambda_n$, the bigger the maximum delay $\epsilon_{max}$ ^[22]. Moreover, similarly to the system with protocol (2.4), the convergence speed of the system with protocol (2.7) is also determined by the second smallest Laplacian eigenvalue $\lambda_2$ ^[4,22].

2.2.3.   Consensus with white noise

In order to capture the robustness of consensus algorithms when the agents are subject to external perturbations, Patterson and Bamieh ^[5] introduced a new quantity called network coherence.

First-order network coherence: In the first-order consensus problem, each agent has a single state $x_i(t)$. The dynamics of this system are given by ^[5,22,25]

where $w(t) \in \mathbb{R}^n$ is the white noise.

It is interesting that if the noise $w(t)$ satisfies some particular conditions, the state of each agent $x_i(t)$ does not necessarily converge to the average-consensus, but fluctuates around the average of the current states ^[5,22]. The variance of these fluctuations can be captured by network coherence.

Definition 2.3. (Definition 2.1 of ^[5]) For a connected graph $G$, the first-order network coherence $H_1$ is defined as the mean (over all vertices), steady-state variance of the deviation from the average of the current agents states,

where $\bf{var\{\cdot\}}$ denotes the variance.

It is amazing for algebraic graph theorists that $H_1$ is completely determined by the $N-1$ nonzero Laplacian eigenvalues ^[25]. Specifically, the first-order network coherence equals

Lower $H_{1}$ implies better robustness of the system irrespective of the presence of noise, i.e., vertices remain closer to consensus at the average of their current states ^[5,22].

3.   Network construction and properties

The hierarchical small-world network was introduced by Chen et al. ^[46] and can be created following a recursive-modular method, see Figure 1. Let $M^r_g \; (g\geq 0, r\geq 2)$ denote the network after $g$ generations of evolution. For $g = 0$, the network $M_0$ is a single vertex. For $g\geq 1$, $M^r_g$ can be obtained from $r$ copies of $M^r_{g-1}$ and a new vertex by linking the new vertex to every vertex in each copy of $M^r_{g-1}$.

Remark: From Figure 1, it is easy to see that the network is self-similar. The self-similarity is a common property of deterministic networks ^[47], which promises to advance our understanding of the way complex networks behave and grow.

A rooted tree $T$ is a tree with a particular vertex $v_0$, see Figure 2. We call $v_0$ the root of $T$. Let $v$ be a vertex of $T$. If $v$ has only one neighbor, $v$ is a leaf of $T$; if $v$ has at least two neighbors, $v$ is a non-leaf vetex of $T$. The level of vertex $v$ in $T$ is the length of the unique path from $v_0$ to $v$. Note that the level of the root $v_0$ is $0$. The height of rooted tree $T$ is the largest level number of all vertices. We always use a directed tree to describe a rooted tree by replacing each edge with an arc (directed edge) directing from a vertex of level $i$ to a vertex of level $i+1$. Figure 2 shows a root tree of height $3$.

If $(u, v)$ is an arc of the rooted tree $T$, then $u$ is the parent of $v$, and $v$ is a child of $u$. If there is a unique directed path from a vertex $v$ to a vertex $w$, we say that $v$ is an ancestor of $w$, and $w$ is a descendant of $v$. For $r\geq 2$, a rooted tree is called a full $r$-ary tree if all leaves are in the same level and every non-leaf vertex has exactly $r$ children. The rooted tree illustrated in Figure 2 is a full $2$-ary (binary) tree. The $r$-ary tree is one of the most important data structures in computer science ^[48,49] and mathematics ^[50,51,52]. It is not difficult to see that the hierarchical network $M^r_g$ can also be obtained from a rooted tree $T_g$ of height $g$ by linking every non-leaf vertex to all its descendants, and we call the rooted tree $T_g$ the basic tree of $M^r_g$.

Let $N_g$ and $E_g$ denote the order and size of the hierarchical small-world network $M^r_g$, respectively. According to the two construction algorithms, we have

and

According to Eq (2.1), the density of $M_g^r$ is given by

If $N_g\gg1$, then $\frac{g+1}{(r-1)N_g(N_g-1)}\rightarrow 0$ and also $\frac{g-\frac{1}{r-1}}{N_g-1}\ll 1$, that is $d\ll 1$. Hence, the hierarchical small-world network $M_g^r$ is a sparse network.

In an arbitrary level $i$ of the basic tree $T_g$, there are $r^i$ vertices. We randomly choose a vertex $v$. The probability that it comes from level $i$ is

Since all vertices in level $i$ have the same degree $k_i = \frac{r^{g+1-i}-1}{r-1}+i-1$, and vertices in different levels have different degrees, the degree distribution $P(k)$ of the hierarchical small-world network is

The degree distribution of a real-world network always follows a power-law distribution $P(k)\sim k^{-\gamma}$ with $\gamma > 1$ ^[53]. For the hierarchical small-world network, according to the result in ^[46], we know that $\gamma$ would approach $1$ when $M_g^r$ is large enough. That is abnormal. However, this network model exists in real life since it is a good model for the benefit transmission web of the pyramid scheme ^[54] in China and many other countries.

4.   Calculations of network coherence

4.1.   Eigenvalues and their corresponding eigenvectors

Let $T_g$ be the basic tree of $M^r_g$ and $V(T_g) = V(M^r_g) = \{v_0, v_1, \cdots, v_{N_g-1}\}$. The root of $T_g$ is $v_0$. For each vertex $v_i\in T_g$, we denote the set of descendants (ancestors) of $v_i$ by $des(v_i) \; (anc(v_i))$. Let $D_i = |des(v_i)|$ and $A_i = |anc(v_i)|$. Let $d_g(v_i)$ be the degree of $v_i$ in $M_g^r$. It is important to note that $d_g(v_i) = D_i+A_i$ for each $i$. Let $l_g(v_i)$ denote the level of $v_i$ in $T_g$. It is not difficult to see that $l_g(v_i) = A_i$.

In order to help the readers to get a direct impression of the following theorem and a better understanding of the proof, we introduce an example.

Example 4.1. As shown in Figure 2, root $v_0$ is a non-leaf vertex of the basic tree $T_3$, and $d_3(v_0)\; = \; 14, \; l_3(v_0) = 0$. $v_1$ is the left child of root $v_0$. Let $\alpha = d_3(v_0)+1 = 15$, $\beta = l_3(v_0)+1 = 1$. Then $\alpha$ is a Laplacian eigenvalue of $M_3^2$ with the corresponding eigenvector $X$ shown in Figure 3(a), because Eq (2.2) holds for every vertex of $M_3^2$. For instance, equations $(LX)_0 = 14\cdot (-14)-1\cdot 14 = 15\cdot(-14) = \alpha x_0$ and $(LX)_1 = 7\cdot 1+14-6\cdot1 = 15\cdot1 = \alpha\cdot x_1$ show that Eq. (2.2) holds for root $v_0$ and vertex $v_1$, respectively. Similarly, $\beta$ is also a Laplacian eigenvalue of $M_3^2$ with the corresponding eigenvector $X'$ shown in Figure 3(b). For instance, equations $(LX')_0 = 0+7\cdot 1-7\cdot 1 = 0 = \beta x'_0$ and $(LX')_1 = 7\cdot (-1)+6\cdot1 = -1 = \beta x'_1$ verify that Eq (2.2) holds for root $v_0$ and vertex $v_1$, respectively.

Theorem 4.2. The nonzero Laplacian eigenvalues of the hierarchical small-world network $M^r_g$ are the following:

1. $d_g(v_i)+1$, repeated exactly once for each non-leaf vertex $v_i$;

2. $l_g(v_i)+1$, repeated $r-1$ times for each non-leaf vertex $v_i$.

Proof. Let $L_g$ be the Laplacian matrix of $M_g^r$. As mentioned above, $0$ is a special eigenvalue of $L_g$ with corresponding eigenvector $\mathbf{1}_{N_g} = (1, 1, \cdots, 1)^{\top}$. Since $M^r_g$ is connected, $L_g$ has $N_g-1$ non-zero eigenvalues. It is clear that, in the full $r$-ary tree $T_g$, each vertex of level $g$ is a leaf, and each vertex of level $i \; (i\leq g-1)$ is a non-leaf vertex. Thus, $T_g$ has $\frac{r^g-1}{r-1}$ non-leaf vertices. So the total number of eigenvalues mentioned in the statement of this theorem add up to $\frac{r^g-1}{r-1}\cdot r = \frac{r^{g+1}-r}{r-1}$, which equals $N_g-1$.

Case 1: When $\lambda_g = d_g(v_i)+1$, where $v_i$ is a non-leaf vertex in $T_g$.

Let $X_g = \left(x_0, x_1, \cdots, x_{N_g-1}\right)^{\top}$ be a column vector, and

Since the number of descendants of $v_i$ is just $D_i$, we have $\sum_{j = 1}^{N_g}x_j = 1\cdot D_i-D_i-0 = 0$. Then, $X_g$ is orthogonal to the vector $\mathbf{1}_{N_g}$. We now have to prove that $X_g$ is indeed an eigenvector corresponding to the given eigenvalue $\lambda_g = d_g(v_i)+1$. In the proof, our main tool is Eq (2.2).

For the vertex $v_i$, $x_i = -D_i$. $x_j = 1$ if $v_j$ is a descendant of $v_i$; $x_j = 0$ if $v_j$ is an ancestor of $v_i$. Thus, we have

For the vertex $v_k$, which is an ancestor of $v_i$, $x_k = 0$. $x_j = -D_i$ if $v_j$ is $v_i$; $x_j = 1$ if $v_j$ is a descendant of $v_i$; $x_j = 0$ if $v_j$ is one of other neighbors of $v_k$. Hence, we have

For the vertex $v_k$, which is a descendant of $v_i$, $x_k = 1$. $x_j = -D_i$ if $v_j$ is $v_i$; $x_j = 1$ if $v_j$ is a descendant of $v_k$; $x_j = 1$ if $v_j$ is a ancestor of $v_k$ and also a descendant of $v_i$; $x_j = 0$ if $v_j$ is one of other neighbors of $v_k$. It is important to note that the number of ancestors of $v_k$, which are also descendants of $v_i$, is $A_k-A_i-1$, i.e., $|anc(v_k)\cap des(v_i)| = A_k-A_i-1$. We minus $1$ here because vertex $v_i$ is not a descendant of itself, so it should be removed. Also, $d_g(v_k) = D_k+A_k$ and $d_g(v_i) = D_i+A_i$. Then, we have

It is clear that the equation $(L_gX_g)_k = (\lambda_gX_g)_k$ holds for all other vertices. Therefore, we have proved $L_gX_g = \lambda_gX_g$.

Case 2: When $\lambda_g = l_g(v_i)+1$ where $v_i$ is a non-leaf vertex in $T_g$.

We denote the $r$ children of $v_i$ by $c_{1}, c_{2}, \cdots, c_{r}$. For each $t \in \{1, 2, \cdots, r\}$, let $F_{t} = c_t\cup des(c_t)$. Let $|F_{1}| = f$. Since $T_g$ is a full $r$-ary tree, we have $|F_{t}| = f$ for every $t\in \{1, 2, \cdots, r\}$. For each $s\in \{2, 3, \cdots, r\}$, let $X_g^s = \left(x_0^s, ,x_1^s, \cdots, x_{N_g-1}^s\right)^{\top}$ be a column vector, and

Since $|F_s| = |F_1| = f$, $\sum_{j = 1}^{N_g}x_j^s = f\cdot1+f\cdot(-1)-0 = 0$. Hence, $X_g^s$ is orthogonal to the vector $\mathbf{1}_{N_g}$. We now have to prove that $X_g^s$ is indeed an eigenvector corresponding to the given eigenvalue $\lambda_g = l_g(v_i)+1$.

For the vertex $v_k$, which is an ancestor of $c_{1}$, $x_k^s = 0$. $x_j^s = -1$ if $v_j\in F_1$; $x_j^s = 1$ if $v_j\in F_s$; $x_j^s = 0$ if $v_j$ is one of the other neighbors of $v_k$. According to Eq (2.2), we have

For the vertex $v_k \in F_{1}$, $x_k^s = -1$. $x_j^s = -1$ if is $v_j$ a descendant of $v_k$; $x_j^s = -1$ if $v_j$ is an ancestor of $v_k$ and also a descendant of $v_i$; $x_j^s = 0$ if $v_j$ is one of the other neighbors of $v_k$. Note that, $d_g(v_k) = D_k+A_k$ and $l_g(v_i) = A_i$. According to Eq (2.2), we have

For the vertex $v_k \in F_{s}$, $x_k^s = 1$. $x_j^s = 1$ if $v_j$ is a descendant of $v_k$; $x_j^s = 1$ if $v_j$ is an ancestor of $v_k$ and also a descendant of $v_i$; $x_j^s = 0$ if $v_j$ is one of the other neighbors of $v_k$. According to Eq (2.2), we have

It is clear that the equation $(L_gX_g^s)_k = (\lambda_gX_g^s)_k$ holds for all other vertices. Thus, we have proved that $L_gX_g^s = \lambda_gX_g^s$. So $X_g^s$ is an eigenvector corresponding to the given eigenvalue $\lambda_g = l_g(v_i)+1$. Then eigenvalue $l_g(v_i)+1$ has $r-1$ linear independent vectors $X_g^2$, $X_g^3$, $\cdots$, $X_g^r$. Therefore, the multiplicity of the eigenvalue $l_g(v_i)+1$ is $r-1$.

For each $i\in \{0, 1, \cdots, g-1\}$, there are $r^i$ vertices in level $i$. If $v$ is a vertex in level $i$, then $d_g(v) = \frac{r^{g-i+1}-1}{r-1}+i-1$. Hence, we have the following corollary. Here, we write multiplicities as subscript for convenience and so that there is no confusion.

Corollary 4.3. The nonzero Laplacian eigenvalues of the hierarchical small-world network $M^r_g$ are

Example 4.4. From Corollary 4.3, we know the nonzero Laplacian eigenvalues of the network $M_3^2$ are $\{1, 15, 2, 2, 8, 8, 3, 3, 3, 3, 5, 5, 5, 5\}$, which can also be obtained by calculating directly the eigenvalues of the Laplacian matrix of $M_3^2$.

4.2.   Convergence speed and delay robustness

As shown in Corollary 4.3, the second smallest Laplacian eigenvalue of the hierarchical small-world network $M_g^r$ is $\lambda_2 = 1$ for all $g\geq 0$ and $r\geq 2$. From Eq (2.6), we know that the convergence rates of these networks have the same upper bound. The largest Laplacian eigenvalue of $M_g^r$ is $\lambda_{N_g} = \frac{r^{g+1}-1}{r-1}$. Figure 4 shows that $\lambda_{N_g}$ is an increasing function with respect to $r$ and $g$. Therefore, the consensus protocol (2.7) on $M_g^r$ is more robust to delay with smaller $r$ and $g$.

The convergence speed and delay robustness in different networks have been widely studied ^[4,22,31]. From the second column of Table 2, we find that the convergence speed of the consensus protocol (2.7) on the hierarchical small-world network $M_g^2$ is faster than that on other sparse graphs. At the same time, the third column shows that the consensus protocol (2.7) on other sparse graphs is much more robust to delay than that on the hierarchical small-world network $M_g^2$. As proved by Olfati-Saber and Murray ^[4], there is a trade-off between convergence speed and delay robustness. They also claimed another trade-off between high convergence speed and low communication cost. Here, we can see this trade-off by comparing the hierarchical small-world network $M_g^2$ with the complete graph $K_N$. The complete graph has much more edges than the hierarchical small-world network $M_g^2$ does. So the convergence speed of the consensus protocol (2.7) on the complete graph $K_N$ is faster than that on the hierarchical small-world network $M_g^2$. From Table 2, we know that the complete graph $K_N$ and the hierarchical small-world network $M_g^2$ have the same delay robustness. It is clear that these two networks have the same maximum degree $N-1$. We can see that all vertices in the complete graph $K_N$ have the maximum degree, while there is only one vertex in $M_g^2$ with maximum degree. So the delay robustness of the consensus protocol (2.7) is independent from the number of vertices with the maximum degree.

4.3.   Network coherence of $M_g^r$: An answer to two open questions

In ^[39], Yi et al. proposed two open questions: What is the minimum scaling of $H_1$ for sparse networks? Is this minimal scaling achieved in real scale-free networks? Now we want to answer these two questions.

According to Corollary 4.3 and Eq (2.11), the following theorem can be easily observed.

Theorem 4.5. For the hierarchical small-world network $M_g^r$, the first-order coherence is

Figure 5 shows that the theoretical results coincide with the numerical results when $r = 2$. The theoretical values are obtained from Theorem 4.5. The numerical results are derived from Eq (2.11) by calculating directly the eigenvalues corresponding to the Laplacian matrix. Since $N_g = \frac{r^{g+1}-1}{r-1}$, we have $g = \frac{ln((r-1)N_g+1)}{lnr}-\; 1$. Thus, as $N_g\rightarrow \infty$, from the numerical results showed in Figure 6, we find the scaling of the network coherence with network order $N$, that is, $H_1\sim \frac{1}{lnNlnlnN}$. This result shows that the hierarchical small-world network $M_g^r$ has the best performance for noisy consensus dynamics among sparse graphs. Therefore, we have provided an answer to the above two open questions.

4.4.   How the structural characteristics affect the network coherence

Figure 7 shows that the differences between the network coherence with different $r$ are very small when $g$ is large enough. Hence, the effect of the parameter $r$ is very limited.

Yi et al. ^[39] provided two bounds for the fist-order coherence in terms of the average path length $\mu$ and the average degree $\langle k\rangle$ of a graph. They proved that

So networks with constant $\mu$ must have limited $H_1$, and the first-order coherence of networks with constant $\langle k\rangle$ can not be $0$. For example, when $N$ is large enough, the complete graph $K_N$, the star $X_N$, and the hierarchical small-world network have constant $H_1$, and the first-order coherence of the star graph $X_N$ is a non-zero constant, see Table 3. But when $\mu$ is an increasing function of the order $N$, we can not estimate the scale of $H_1$ from the upper bound.

From Eq (2.11), we can find that the algebraic connectivity $\lambda_2$ plays an important role in determining the value of $H_1$. If $\lambda_2$ is close to $0$, $H_1$ will become very large. From the classical Fiedler inequality (2.3), we know that $\lambda_2$ is bounded by the vertex connectivity $c_v$ and the edge connectivity $c_e$, which measure respectively the robustness to vertex and edge failure. So graphs with large vertex connectivity and edge connectivity tend to have small $H_1$. In other words, high robustness to vertex and edge failures mean high robustness against uncertain disturbance. For example, the Koch network has the same scale of the maximum degree $\Delta$ and the average path length $\mu$ as the pseudofractal scale-free web, but the scale of the first-order coherence $H_1$ in the Koch network is very high, see Table 3. This is because the Koch network is not robust to vertex failure.

The Kirchhoff index $R(G) = N\sum_{i = 2}^N\frac{1}{\lambda_i}$ is a famous and important graph invariant ^[55]. The relation between $R(G)$ and $H_1$ is given by $H_1 = \frac{R(G)}{2N^2}$. We have the following bounds for $R(G)$ ^[55],

where $\theta_i$ are the eigenvalues of the transition matrix $P$ defined in Section 2. Thus, we have two new bounds for $H_1$,

Hence, the maximum degree is a good predictor for $H_1$. Small $\Delta$ means large $H_1$. For example, the Farey graph has the same scale of the average path length as the pseudofractal scale-free web, but the scale of $H_1$ in the Farey graph is much larger. This is due to the scale of the maximum degree in the Farey graph being low, see Table 3.

5.   Conclusions

In this paper, by applying the spectral graph theory, we studied three important aspects of consensus problems in a hierarchical small-world network, which is a good model for the benefit transmission web of pyramid schemes ^[54]. Compared with several previous studies, the consensus algorithm in the network converges faster but less robust to communication time delay. It is well-known that pyramid schemes create serious social problems. Since the network is not robust to communication time delay, this could be a good way to to prolong the trading hours for high-risk accounts under supervision. It is worth mentioning that the hierarchical small-world network has optimal network coherence, which captures the robustness of consensus algorithms when the agents are subject to external perturbations. These results provide a positive answer to two open questions of Yi et al. ^[39]. Finally, we argue that some particular network structure characteristics, such as large maximum degree, small average path length, and large vertex and edge connectivity, are responsible for the strong robustness with respect to external perturbations.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was supported by Normandie region France and the XTerm ERDF project (European Regional Development Fund) on Complex Networks and Applications, the National Natural Science Foundation of China (11971164), the Major Project of the National Philosophy and Social Science Fund of China: Statistical Monitoring, Early Warning, and Countermeasures for Food Security in China (23&ZD119). The authors would like to thank the reviewers for their constructive comments and recommendations, which have helped to improve the quality of the manuscript.

Conflict of interest

The authors declare there is no conflict of interest.