Structural properties and average tapping time on scale-free graphs with smallest diameter
Fei Ma Ping Wang
physics.soc-ph




 Structural properties and average tapping time on scale-free graphs with smallest diameter 

Fei Ma^a,[ The author's E-mail: mafei123987@163.com. ],  Ping Wang^b,c,d,[ The corresponding author's E-mail: pwang@pku.edu.cn.] 

^a School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China

^b National Engineering Research Center for Software Engineering, Peking University, Beijing, China

^c School of Software and Microelectronics, Peking University, Beijing  102600, China

^d Key Laboratory of High Confidence Software Technologies (PKU), Ministry of Education, Beijing, China






Abstract: In this paper, we propose a class of graphs G^⋆(m,t) and first study some structural properties, such as, average degree, on them. The results show that (1) graphs G^⋆(m,t) have density feature because of their average degrees proportional to time step t not to a constant in the large graph size limit, (2) graphs G^⋆(m,t) obey the power-law distribution with exponent equal to 2, which is rarely found in most previous scale-free models, (3) graphs G^⋆(m,t) display small-world property in terms of ultra-small diameter and higher clustering coefficient, and (4) graphs G^⋆(m,t) possess disassortative structure with respect to Pearson correlation coefficient smaller than zero. In addition, we consider the trapping problem on the proposed graphs G^⋆(m,t) and then find that they all have more optimal trapping efficiency by means of their own average trapping time achieving the theoretical lower bound, a phenomenon that is seldom observed in existing scale-free models. We conduct extensive simulations that are consistent with our theoretical analysis.


Keywords: Scale-free graph, Structural properties, Trapping problem, Average trapping time, Maximum independent set. 




1cm

The past two decades have witnessed an upsurge of complex network study <cit.>-<cit.>. One of significant reasons for this is that various complex systems, both synthetic and real-world, can be naturally represented as complex networks, for instance, the World Wide Web, protein-protein interaction network, metabolic network, as well as friendship network, and so forth <cit.>. In general, the underlying structure of a complex network is a graph, denoted by G(V,E) in this paper. Here, symbol V is vertex set and E represents edge set, and then |V| denotes vertex number of graph G(V,E), also called the order of graph, and |E| is the total number of edges in graph G(V,E), also defined as size of graph. At the same time, all graphs discussed in this paper are simple and connected, i.e., no loops and multi-edges. Hereafter, the terms network and graph will be used indistinctly.

A large number of empirical observations on complex networks in the last have shown that there are many interesting properties popularly found in various networks, such as, small-world phenomena <cit.> and scale-free feature <cit.>. Since then, in order to better understand these properties, numerous networked models have been developed. As such, this further triggers the research of graphs themselves.

There are two main directions in graph research at present. The one is to study some structural properties on graph, for example, diameter and clustering coefficient (defined in detail later). Here, in the jargon of graph theory, diameter of a graph G(V,E), denoted by D, is the maximum over distances of all possible vertex pairs. For a pair of vertices u and v, distance between them, denoted by d_uv, is the edge number of any shorted path joining vertex u and v. As known, graph with diameter equal to one must be the complete one. The structural properties related to the complete graph have been well studied over the past decades mainly because of their own specific structure. Interested reader can refer to <cit.> for more detail. On the other hand, for a graph with diameter 2, some commonly-focused structural properties will are significantly different from that of the complete graph with the same vertex set as will be shown shortly. Motivated by this, in this paper, we will generate a class of graphs with diameter exactly equivalent to 2 and then study many other structural properties including degree distribution on them. Meanwhile, we precisely determine some closed-form solutions of quantities corresponding to those structural properties. One of them is that our graphs have scale-free feature because their degree distribution follow  power-law with exponent 2 in form, which is rare in the context of complex network.

The other is to learn about dynamics taking placing on graphs, such as, random walks <cit.>, percolation phase transition <cit.> and synchronization <cit.>, and understand how the underlying structure of graph affects the dynamical behavior under consideration. To make further progress, this can in turn serve as instruments for designing more available graphs. Here, we focus mainly on a special kind of random walks, i.e., the trapping problem, on the proposed graph of great interest, at least, with diameter 2. As above, by using a quantity, average trapping time (ATT) (defined in detail later), related to the trapping problem, we compare the exact solution to ATT on our graph to that of complete graph and find that there are remarkable difference between them. In another words, a slight change of diameter results in a tremendous influence on determining formulas of ATT. For example, when placing traps at some vertices of our scale-free graph, the analytical value for ATT can be asymptotically equal to 1. Meantime, such an assignment of traps uncovers a unique maximum independent set on our graph. This reveals that it is considerably necessary to probe the nature of some interesting graphs like models introduced herein.

The rest of this paper is organized as follows. In Section 2, we provide a generative framework for constructing graphs with diameter 2. Next, we study some structural properties on the proposed graphs and exactly derive the solutions corresponding to some related parameters in Section 3. Following the preceding section, the goal of Section 4 is to consider the trapping problem on the presented graphs and determine closed-form formula for average trapping time. Finally, we conclude our work in Section 5.





§ CONSTRUCTION


This section aims to provide a framework for generating graph G^⋆(m,t). As will be stated shortly, the candidate graph G^⋆(m,t) is in fact built up upon a hierarchical graph G(m,t) in our prior work <cit.>. First, let us construct graph G(m,t) in an iterative manner.


  * At t=0, the initial graph G(m,0) is a star graph with m (≥2) leaf vertices, as illustrated in the top-left panel of Fig.1.

  * At t=1, the young graph G(m,1) is generated by connecting a new vertex to each leaf vertex in number m of graphs G_i(m,0) (i=1,2,…,m) that are in essence duplications of graph G(m,0). Such a process is depicted in the left-most panel in line 2 of Fig.1. For convenience, let that newly added vertex be at the layer 0 of graph G(m,1), all the centers from number m of duplications G_i(m,0) at the layer 1 and the remaining of vertices in graph G(m,1) at the layer 2. After adopting such a rearrangement of vertices in graph G(m,1), the hierarchical structure can be easily observed.


  * At t≥ 2, the newborn graph G(m,t) can be obtained from the preceding graph G(m,t-1) in a similar manner as in the second time step. Additionally, the only adjustment is to let the label of layer in graph G(m,t-1) increase by a factor 1.

The procedure above can be implemented iteratively until one anticipated graph G(m,t) is obtained. After that, our graph G^⋆(m,t), the object discussed in this paper, may be established in an additional manipulation.


  * For a graph G(m,t) (t≥1), the corresponding graph G^⋆(m,t) is constructed from graph G(m,t) by connecting that vertex at the layer 0 to each vertex at the layer i (1≤ i≤ t). An illustrative example is shown in the bottom-right panel of Fig.1. Hereafter, that vertex at the layer 0 in graph G^⋆(m,t) is regarded as the hub, denoted by ℋ(t), since it has the greatest degree.






Obviously, the diameter of graph G^⋆(m,t) is exactly equal to 2. And then, according to the hierarchial structure, the order |𝒱^⋆_m(t)| and size |ℰ^⋆_m(t)| of graph G^⋆(m,t) follow




    |𝒱^⋆_m(t)|=|𝒱_m(t)|=m|𝒱_m(t-1)|+1,


    |ℰ^⋆_m(t)|=|ℰ_m(t)|+m^t+1-m/m-1,    |ℰ_m(t)|=m|ℰ_m(t-1)|+m^t+1,


where |𝒱_m(t)| and |ℰ_m(t)| denote, respectively, the order and size of graph G(m,t). Using the initial conditions |𝒱_m(0)|=m+1 and |ℰ_m(0)|=m, the precise formulas of |𝒱^⋆_m(t)| and |ℰ^⋆_m(t)| can be derived in a recursive fashion, as follows


    |𝒱^⋆_m(t)|=m^t+2-1/m-1,    |ℰ^⋆_m(t)|=(t+1)m^t+2-t× m^t+1-m/m-1.


So far, we have accomplished the generative construction of graph G^⋆(m,t). In the following, as tried in the context of complex networked models <cit.>-<cit.>, some commonly studied structural parameters  on graph G^⋆(m,t) will be considered in more detail, such as average degree. Besides that, a specific type of discrete-time unbiased random walks, namely, the trapping problem, is also studied on graph G^⋆(m,t) and we then precisely calculate the solution to average trapping time, an important quantity that is closely related to the trapping problem.







§ STRUCTURAL PROPERTIES


It is convention to understand the topological structure of a deterministic graph G(V,E) in question by studying some structural parameters of considerable interest. Some of them, for instance, average degree, can be precisely calculated by means of some simple arithmetics. In this section, we will focus mainly on determining several structural parameters, for instance, average degree, vertex degree distribution, clustering coefficient and Pearson correlation coefficient, of graph G^⋆(m,t) built.




 §.§ Average degree


Mathematically, the average degree ⟨ k⟩ of a given graph G(V,E) can be defined as the ratio of the summation over degrees k_i of all vertices in graph G(V,E) and the order |V|, namely,


    ⟨ k⟩=∑_i∈ Vk_i/|V|=2|E|/|V|.


In the study of complex networks, the average degree is a simple yet useful measure that indicates whether a network is sparse or not. Roundly speaking, in the limit of large graph size, a graph G(V,E) is considered sparse if its average degree is approximately equivalent to an invariable. Otherwise, it is dense. By definition, we can have the following proposition

Proposition 1 The average degree ⟨ k^⋆(m;t)⟩ of the proposed graph G^⋆(m,t) is given by


    ⟨ k^⋆(m;t)⟩=O((2-1/m)t),

which is a variable varying linearly with time step t, suggesting that graph G^⋆(m,t) has density feature.

 Proof Inserting the results from Eq.(<ref>) into Eq.(<ref>) outputs


    ⟨ k^⋆(m;t)⟩   =2(t+1)m^t+2-t× m^t+1-m/m^t+2-1
       ≈ 2(t+1)-1/mt.

This completes the proof of Proposition 1.

As opposed to some previous graphs in <cit.>, graph G^⋆(m,t) shows density feature. So, such a structural property can be viewed as one virtue of our graph G^⋆(m,t). It is worth noting that the novel generation way mentioned in Section 2 leads graph G^⋆(m,t) to be dense. Besides that, the graph G^⋆(m,t) itself has many other interesting features in comparison with graphs in <cit.> as will be reported shortly.




 §.§ Degree distribution


In the last, as one fundamental structure feature related to a graph G(V,E), degree sequence has been widely studied in various scientific community <cit.>, especially in graph theory. In the jargon of graph theory, the degree sequence of a graph G(V,E) consisting of vertices v_1, v_2,…, v_|V| can defined as (k_1, k_2,…, k_|V|). Apparently, this is a set of discrete values. It is well known that for a given graph G(V,E), the degree sequence can be equivalent to the degree distribution. Here, the probability for at random choosing a vertex with degree k_j in graph G(V,E) is defined to be


    P(k_j)=N_k_j/|V|

where N_k_j is the total number of vertices whose degrees are exactly equal to k_j.


Indeed, such a convenient transformation from degree sequence into degree distribution has helped us to uncover some fundamental properties on a large number of graphs, for example, the degree distribution of ER-graph obeys Poisson one in form, implying that the degrees of a great body of vertices are close to that average value ∑_k=k_min^k_maxkP(k) <cit.>. In addition, in the past two decades, a lot of empirical observations on complex networks have shown that most networks follow the power-law degree distribution


    P(k_j)∼ k_j^-γ,    2< γ≤ 3

meaning that a small fraction of vertices possess a large fraction of connections. Graphs of such type always exhibit heterogeneous structure significantly distinct from the underlying structure of ER-graph mentioned above.

In what follows, we will determine which type of degree distribution the presented graph G^⋆(m,t) obeys. Before starting our calculations, we need to introduce the accumulate degree distribution, a well-used technique that is suitable to calculating degree distribution of deterministic graph G(V,E),


    P_cum(k_j)=∑_k≥ k_jN_k/|V|

where N_k has the same definition as above.

Proposition 2 In an overwhelm range, the degree distribution of graph G^⋆(m,t) follows


    P(k)∼ k^-γ,   γ=2.


 Proof This suffices to divide all the vertices of graph G^⋆(m,t) into different classes according to vertex degree in order to consolidate Proposition 2. Taking into consideration the development of graph G^⋆(m,t), we can capture a list as below





  
  k_m(t_i,t)     m^t+2-1/m-1-1     m^t+1     ...     m^t_i+1     ...     m^2+1     m+1     t+1 

   N_m(t_i,t)     1     m     ...     m^t-t_i+1     ...     m^t-1     m^t    m^t+1 

  


in which symbol N_m(t_i,t) denotes the total number of vertices with degree equal to k_m(t_i,t). It is obvious to see that the degree value t+1 must be smaller than m^j+1 for some parameter j. Without loss of generality, suppose that t<m^j_t and then it is clear to find that most degree values fall into the range Γ_m(t) from m^j_t+1 to m^t+1, an overwhelm range that has been demonstrated in Proposition 2.

Now, for a given degree value k=m^s+1 in range Γ_m(t), the accumulate degree distribution can by definition in Eq.(<ref>) be expressed as


    P_cum(k)=∑_k_i≥ kN_k/|𝒱^⋆_m(t)|=1+∑_i=s^tm^t-i+1/|𝒱^⋆_m(t)|∼ m^-s.


Meantime, one can solve for s from equality k=m^s+1 to get s=ln(k-1)/ln m. And then, plugging that value for s into Eq.(<ref>) produces


    P_cum(k)∼ k^-1.


At present, taking differential on the both sides of Eq.(<ref>), we have


    P(k)∼ k^-2,

a result that is completely the same as that in Proposition 2, revealing that Proposition 2 holds true.

A similar approach to the above can be adopted to determine the degree distribution of those vertices with degrees smaller than t+1, so we omit it here.

Token together, in the large graph size limit, our graph G^⋆(m,t) obeys the power-law degree distribution and thus has scale-free feature, a character that is prevalent in a wide variety of complex networked models <cit.>. On the other hand, it is worth noting that theoretical models with power-law exponent 2 are rarely reported in the literature of complex networked models. Hence, the lights shed by generating graph G^⋆(m,t) may be helpful to create many other scale-free models with density feature in the future.




 §.§ Clustering coefficient


As another fundamental structure parameter, clustering coefficient ⟨ C⟩ of a graph G(V,E) under consideration, defined as the average over all vertices v, has attracted much attention in the past few years <cit.>. Here, the clustering coefficient c_v for a vertex v in graph G(V,E) is commonly regarded as the ratio of number n_v of edges actually existing in the neighbor set of vertex v and all possible edges number k_v(k_v-1)/2 where k_v is the degree of vertex v, i.e., c_v=2n_v/k_v(k_v-1). Thus, for a given graph G(V,E), the clustering coefficient ⟨ C⟩ is


    ⟨ C⟩=∑_v∈ Vc_v/|V|.


By definition, it is evident to see that clustering coefficient ⟨ C⟩ measures the level of “cluster" of a graph in question. The higher the value for ⟨ C⟩ is, the more clustered graph is. As such, this parameter has been used in complex networks study as an index for determining whether a networked model considered is small-world or not <cit.>.

To evaluate the “cluster" phenomena of our graph G^⋆(m,t) as a whole, the next task is to first derive the exact formula of clustering coefficient for each vertex in G^⋆(m,t) and then average those values over all vertices. Doing so leads to the following proposition.

Proposition 3 The clustering coefficient ⟨ C(m;t)⟩ of graph G^⋆(m,t) is equal to


    ⟨ C(m;t)⟩= 2m-2/m^t+2-2m+1+∑_i=1^t2m^t-i+1/m^i+1+2m^t+1/t+1/m^t+2-1/m-1.


 Proof According to the hierarchical structure of graph G^⋆(m,t), we can observe that all vertices lying at the same layer have a local structure in common. Hence, determining the clustering coefficients for those vertices at the same layer reduces to determining the clustering coefficient for an arbitrary vertex at that layer. The next discussions will be in progress by means of evaluating the clustering coefficients for vertices from number t+2 of different layers.



  * For the hub, the degree value is equal to m^t+2-1/m-1-1 and the number of edges actually existing in its neighbor set is m|V^⋆(m,t-1)|=m×m^t+1-1/m-1. So, the clustering coefficient c_0 satisfies
    
    c_0= 2/m^t+2-1/m-1-2.



  * For an arbitrary vertex at the layer i (1≤ i≤ t), its degree is equivalent to m^t+1-i+1 and the number of already existing edges between vertices in its neighbor set equals m^t+1-i. By definition, one has the clustering coefficient c_i

   
    c_i= 2/m^t+1-i+1.



  * Finally, for an arbitrary vertex from the bottom-most layer, it is obvious to find the degree value to be t+1 and there are number t of edges allocated between vertices in its neighbor set. As previously, one may calculate the clustering coefficient c_t+1 to obtain
    
    c_t+1= 2/t+1.




Now, armed with both Eq.(<ref>) and the results from Eqs.(<ref>)-(<ref>), one is able to capture the closed-form solution for clustering coefficient ⟨ C(m;t)⟩ of graph G^⋆(m,t)

    
    ⟨ C(m;t)⟩=2/m^t+2-1/m-1-2+2∑_i=1^tm^t-i+1/m^i+1+2m^t+1/t+1/m^t+2-1/m-1.

This is consistent with that in Eq.(<ref>), indicating that Proposition 3 is valid.

As a case study, assume that parameter m is equal to 2, the value for ⟨ C(2;t)⟩ can be asymptotically close to ∑_i=1^t1/2^i(2^i+1)+1/t+1>0.217 in the limit of large t. This suggests that graph G^⋆(2,t) has a non-zero clustering coefficient. Similarly, for many other smaller parameters m, graph G^⋆(m,t) always displays “cluster" property because its clustering coefficient ⟨ C(m;t)⟩ is strictly larger than 0.




 §.§ Pearson correlation coefficient


The previous three subsections focus mainly on characterizing properties closely correlated to vertex itself, while this subsection aims at investigating the feature of edge by virtue of its two endpoint degrees. In theory, such an investigation is to quantify tendency of connections taking place between vertices in a graph G(V,E) indirectly. For instance, in social network research, a large volume of empirical observations imply a fact that it is mostly likely for two persons with the similar status to make friend and such a relationship between them is often stable overtime. On the other hand, in biological networks, it is popular to observe connections between vertices with distinct importance. In the language of mathematics, the two types of networks above can be naturally transformed into graphs considered here. After that, “status" and “importance" can be simply defined as the degree (or weight) of corresponding vertex. In order to plausibly evaluate phenomena of such kind on graphs G(V,E), Newman provided in <cit.> a measurement, called Pearson correlation coefficient r, that is referred to as



    r=|E|^-1∑_e_ij∈ E k_ik_j-[|E|^-1∑_e_ij∈ E1/2(k_i+k_j)]^2/|E|^-1∑_e_ij∈ E1/2(k^2_i+k^2_j)-[|E|^-1∑_e_ij∈ E1/2(k_i+k_j)]^2

in which k_i is the degree of vertex i and e_ij denotes an edge connecting vertex i to j.

By estimating the value for r of graph G(V,E), one can plausibly classify graph G(V,E) into reasonable graph family. Graph G(V,E) is considered assortative if r is larger than zero, disassortative if r is less than zero, non-assortative otherwise (i.e., r=0). In the same article <cit.>, Newman had experimentally shown that most social networks belong to the assortative mixing family and however almost all both biological and technological networks fall into the scope of disassortative mixing. In what follows, the task to answer is to determine which type of graph family the proposed graph G^⋆(m,t) is in.


Proposition 4 The Pearson correlation coefficient r(m;t) of graph G^⋆(m,t) can be written as


    r(m;t)=Λ_1/|E^⋆(m,t)|-(Λ_2/|E^⋆(m,t)|)^2/Λ_3/|E^⋆(m,t)|-(Λ_2/|E^⋆(m,t)|)^2,

where Λ_1=∑_e_ij∈ E^⋆(m,t) k_ik_j, Λ_2=∑_e_ij∈ E^⋆(m,t)1/2(k_i+k_j), Λ_3=∑_e_ij∈ E^⋆(m,t)1/2(k^2_i+k^2_j), as well as  
    Λ_1=(m^t+2-1/m-1-1)[(2t+1)m^t+1+m^t+1-m/m-1]+m^t+1(t+1)(t+m^t+1-m/m-1),
 
    Λ_2=m^t+2-1/2(m-1)(m^t+1-m/m-1+m^t+1)+m^t+1/2(t^2+4t+m^t+1-m/m-1),


    Λ_3=1/2(m^t+1-m/m-1+m^t+1)(m^t+2-1/m-1-1)^2+(t+1)^3m^t+1/2+m^t+1/2∑_i=1^t(m^i+1)^3/m^i.


 Proof As explained above, it is sufficient to divide all the edges in graph G^⋆(m,t) into different classes according to two endpoint degrees of each edge. Again, we recall the concrete generation of graph G^⋆(m,t), which allows us to find that there are in fact number 2t+1 of distinct edge subsets. Therefore, we will deal with such a computation for precisely deriving formula of Pearson correlation coefficient r(m;t) as follows




  * For the hub, there exist number t+1 of different types of edges connecting all other vertices but it in graph G^⋆(m,t) with respect to two endpoint degrees of edge. Let E_1 denote a set consisting of those edges. Accordingly, the number of edges whose another endpoint degree is equal to m^i (1≤ i≤ t) and t+1 equal m^t+1-i and m^t+1, respectively. Thus, one can have

  


    Λ_11=∑_e_ij∈ E_1 k_ik_j=(m^t+2-1/m-1-1)[∑_i=1^t(m^i+1)m^t+1-i+m^t+1(t+1)],


    Λ_21=∑_e_ij∈ E_11/2(k_i+k_j)=∑_i=1^tm^t+1-i(m^t+2-1/m-1+m^i/2)+m^t+1(t+m^t+2-1/m-1/2),


    Λ_31=∑_e_ij∈ E_11/2(k^2_i+k^2_j)   =(m^t+2-1/m-1-1)^2∑_i=0^tm^i/2 +m^t+1(t+1)^2/2
       +∑_i=1^tm^t+1-i(m^i+1)^2/2.




  * For an arbitrary vertex at the layer i (1≤ i≤ t), there exist two distinct kinds of edges. The only one of those such edges has the other endpoint degree m^t+2-1/m-1-1. The contribution from such an edge to calculation of Pearson correlation coefficient r(m;t) has been considered in the first case. Each of all other edges composing set E_2 connects to some vertex allocated at the layer 0 and thus has the other endpoint degree equal to t+1. After that, one may obtain a group of equations

  


    Λ_12=∑_e_ij∈ E_2 k_ik_j=m^t+1∑_i=1^t(t+1)(m^i+1),


    Λ_22=∑_e_ij∈ E_21/2(k_i+k_j)=m^t+1∑_i=1^t(t+1)+(m^i+1)/2,


    Λ_32=∑_e_ij∈ E_21/2(k^2_i+k^2_j)=m^t+1∑_i=1^t(t+1)^2+(m^i+1)^2/2.






Till now, all possible cases are exhaustively enumerated. Next, we may obtain Λ_1 based on Λ_11 plus Λ_12 by using some simple arithmetics, namely, Λ_1=Λ_11+Λ_12. With an in spirit similar method to the above, the closed forms for Λ_2 and Λ_3 can be precisely calculated. Token together, we accomplish the proof of Proposition 4.


To better observe the behavior of Pearson correlation coefficient r(m;t) in the limit of large graph size, we take as input the result from Eq.(<ref>) and find a consequence shown in Fig.2. Apparently, in the limit of large graph size, the behavior of Pearson correlation coefficient r(m;t) not only has a tendency to zero but also is always smaller than 0. This reveals that our graph G^⋆(m,t) is disassortative.











§ AVERAGE TRAPPING TIME (ATT)



Our main goal in the preceding section is to study some structural properties planted on the graph G^⋆(m,t). The results show that graph G^⋆(m,t) has some particular structural features, for instance, obeying power-law distribution with exponent 2, unfound in most early models. In order to further probe many other properties of graph G^⋆(m,t), this section will aim at considering a special type of discrete-time unbiased random walk, i.e., the trapping problem, on graph G^⋆(m,t).





 §.§ Trapping problem


The trapping problem on graph G(V,E) is a special random walk with a deep trap allocated at an arbitrary vertex θ(∈ V). Here, random walk is a paradigmatic dynamical process on graph G(V,E) and has attracted a wide range of attentions in the past decades. It has been proven useful in many practical applications, such as, finding community structure on complex networks <cit.>. Mathematically, during a random walk on graph G(V,E), a walker will hop on each vertex v in its neighbor set with the probability 1/k_u from its current position u. Such a description can be interpreted by the transition matrix 𝐏=𝐃^-1𝐀 of graph G(V,E) where 𝐀 is adjacency matrix defined as


    a_ij={   1,   vertex i is adjacent to j
       0,  otherwise.

and 𝐃 is the diagonal matrix which is referred to as 𝐃=diag[k_1,k_2,…,k_|V|] where the ith diagonal entry is k_i=∑_j=1^|V|a_ij, while all non-diagonal elements are zero. After that, the jumping probability P_u→ v for a walker starting out from u to v can be given by the following master equation



    P_u→ v(t+1)=∑_i∈ Va_iv/k_iP_u→ i(t).

In addition, there are more information about random walk on graph encapsulated in the transition matrix 𝐏 above. For example, with the help of some techniques from matrix theory, one can study some quantities correlated to random walk of graph by matrix 𝐏 more conveniently.

In this paper, we focus on a quantity associated with the trapping problem that is usually called the trapping time, denoted by TT. The TT_iθ is the expected time taken by a walker starting out from its present location i to first reach to the trap θ. As known, by using some methods from spectral graph theory <cit.>, the quantity TT_iθ can be written as


    TT_iθ=2|E|∑_s=2^|V|1/1-λ_s(ψ_si/k_θ-ψ_sθψ_si/√(k_θk_i)),

where we make use of some notations as follows, 1=λ_1>λ_2≥λ_3≥…≥λ_|V| are the |V| eigenvalues of matrix
Γ=𝐃^1/2𝐏𝐃^-1/2=𝐃^-1/2𝐀𝐃^1/2 and ψ_1, ψ_2, ψ_3,…, ψ_|V| represent the corresponding mutually orthogonal eigenvectors of unit length in which ψ_i=(ψ_i1,ψ_i2,…,ψ_i|V|). For graph G(V,E) as a whole, the average trapping time may be immediately obtained

    ATT_θ=1/|V|-1∑_i∈ V, i≠θ TT_iθ.


Inserting Eq.(<ref>) into Eq.(<ref>), the ATT_θ can be rearranged as


    ATT_θ=1/1-π_θ∑_i=2^|V|(1/1-λ_iψ_iθ^2∑_j=1^|V|k_j/k_θ)

where π_θ is equal to k_θ/∑_j=1^|V|k_j. As said in <cit.>, the theoretical lower bound for ATT_θ in Eq.(<ref>) may be induced as




    ATT_θ≥1/1-π_θ∑_j=1^|V|k_j/k_θ(1-π_θ)^2=∑_j=1^|V|k_j/k_θ-1.

As will be shown later, this is a sharp bound in the sense that it can be achieved in some graphs.


It is obvious to see that one of most important approaches to the task, calculating the average trapping time ATT_θ on a graph G(V,E) with a trap θ, is to first determine the adjacency matrix 𝐀. In the past, it is using such a technique that the exact solutions to average trapping time on some graphs <cit.>, most of which are generated in an iterative fashion, have been derived.  While the proposed graph G^⋆(m,t) is also built up in an iterative manner like some previous graphs mentioned above, it is in practice slightly difficult to obtain the desirable solution by some arithmetics based on the adjacency matrix corresponding to graph G^⋆(m,t). To deal with this issue, we will take advantage of another tool based on master equation as in Eq.(<ref>).



As a warm-up exercise before beginning with discussion on the trapping problem over scale-free graph G^⋆(m,t), let us consider some simple yet helpful examples. By using these examples, we will develop the first theorem in this paper.



 §.§ Star-type graph



Example 1 For a complete graph K_n, the average trapping time ATT_1 to an arbitrary vertex v selected as the trap θ is


    ATT_1=n-1.



 Proof Here, let x denote the trapping time for a walker starting out from a vertex u (≠ v) to first hit the trap θ. In terms of the structure of complete graph K_n, x should follow


    x=1/n-1+ n-2/n-1(1+x).


Plugging the value of x derived from Eq.(<ref>) into Eq.(<ref>) leads to the same result as that shown in Eq.(<ref>). This is complete.


Example 2  For a wheel graph W_(1,n) <cit.>, the average trapping time ATT_2 to the center o chosen as the trap θ follows


    ATT_2=3.


 Proof As above, let y represent the trapping time for a walker starting out from a vertex u (≠ o) to first reach to the trap θ. Due to the structure of wheel graph W_(1,n), y obeys


    y=1/3+ 2/3(1+y).

It is straightforward to obtain y=3. And then, by definition in Eq.(<ref>), we may prove Eq.(<ref>).


Example 3 For a star graph S_(1,n), the average trapping time ATT_3 to the center s designated as the trap θ satisfies


    ATT_3=1.


The proof of Eq.(<ref>) can be easily obtained in a similar manner adopted in the two examples above and thus we omit detailed calculations.


Based on the demonstration in Eq.(<ref>), it is not hard to show that the three graphs (i.e., K_n, W_(1,n) and S_(1,n)) all have most optimal topological structure by achieving the theoretical lower bound for average trapping time in the trapping problem considered here. In fact, we can formalize the consequences obtained above to hold in a more general situation. One approach to this generalization is to seek for common attributes among the three graphs according to their own underlying structures. There have to be not much effort to see that they indeed share a structural feature with each other in common as will be shown shortly. In the following, we will introduce a formalized version of graphs of such kind.

Definition Given a regular graph 𝒢_(n,m) consisting of number n of vertices with degree m each, we may take an external vertex u and then connect it to each vertex v in graph 𝒢_(n,m) by one new edge, resulting in a new graph 𝒢'_(n,m) that is referred to as the star-type graph in this paper.

By definition, complete graph K_n-1, cycle C_n and empty graph O_n are regular and so the three graphs mentioned in examples 1-3 all belong to star-type graph family. Fig.3 illustrates some concrete example graphs. In what follows, our goal is to generalize the aforementioned results to hold in star-type graph family 𝒢'_(n,m).


Theorem 1 For an arbitrary star-type graph 𝒢'_(n,m) upon regular graph 𝒢_(n,m), the solution to average trapping time ATT to the center u, i.e., that newly added vertex, set to the trap θ is


    ATT=m+1.


 Proof As previously, the trapping time TT_v for each vertex v but center u can be written in the following term


    TT_v=1/m+1+m/m+1(TT_v+1),

here we already make use of the symmetric structure of regular graph 𝒢_(n,m). Solving for TT_v from Eq.(<ref>) yields

    TT_v=m+1.


Substituting the value for TT_v into Eq.(<ref>) produces the same result as that in Eq.(<ref>), implying that Theorem 1 holds true. At the same time, all the star-type graphs 𝒢'_(n,m) show most optimal topological structure with respect to the trapping problem with a single trap where ATT_v in Eq.(<ref>) is identical to the theoretical lower bound calculated from Eq.(<ref>).

Obviously, star-type graph 𝒢'_(n,m) displays some specific structural features, such as its seed 𝒢_(n,m) with symmetric character. In addition, as shown above, all vertices but that trap have the same trapping time m+1. Mathematically, the important reason for this is that these such vertices are all in a completely common local environment. In another words, it is the significantly specific structure of graph 𝒢'_(n,m) that plays a key role in the deductions of average trapping time. Thus, we can ask whether there are many other graphs with distinct topological structures from star-type graph 𝒢'_(n,m) whose average trapping times are subject to the theoretical lower bound in the trapping problem considered here. Towards this end, we will consider the trapping problem on scale-free graph G^⋆(m,t) built in Section 2 in more detail and then, fortunately, find graph G^⋆(m,t) to approximately achieve the the theoretical lower bound for average trapping time in the large graph size limit. This suggests that scale-free graph G^⋆(m,t) has some features of great interest that have not been observed in most networked graphs obeying power-law distribution <cit.>.


In the discussions above, the trap is always placed at that vertex with greatest degree in star-type graph 𝒢'_(n,m) mainly because in general, the greatest degree vertex is considered to play a crucial role in the trapping problem. Indeed, the results obtained illustrate this viewpoint. In other words, the analytic value for average trapping time is precisely equal to the theoretical lower bound when placing the trap at the greatest degree vertex in graph 𝒢'_(n,m). Motivated by this, in the subsequent sections, we will in-detail consider the trapping problem on scale-free graph G^⋆(m,t) in which some vertices with specific features, such as, greatest degree, may be chosen as candidates that are assigned traps.










 §.§ ATT to hub vertex ℋ(t)


From now on, let us turn our attention to discussions about the trapping problem on scale-free graph G^⋆(m,t).
Similar to the generation of star-type graph 𝒢'_(n,m), our scale-free graph G^⋆(m,t) is also constructed by connecting an external vertex to each vertex belonging to ingredients G_i(m,t-1). Yet, there still exist some considerable differences between the both types of graphs. The most remarkable one compared to graph 𝒢'_(n,m) is the proposed graph G^⋆(m,t) has heterogeneous structure, i.e., a small fraction of vertices having a large number of connections. Specifically speaking, graph G^⋆(m,t) obeys power-law degree distribution, a feature that is popular in a great number of complex networks. As will be shown later, most interestingly, such a considerably structural property seems to have no prominent influence on the closed-form solution for average trapping time.


First of all, using Eq.(<ref>), we can without difficulty obtain the theoretical lower bound for average trapping time ATT_ℋ(t) when allocating a trap at the hub ℋ(t), as below


    ATT'_ℋ(t)=2|ℰ^⋆_m(t)|/k_ℋ(t)-1≈ 2t-t-1/m+1.


In fact, the approximate value for ATT_ℋ(t) in the above equation can be reached with respect to analytical calculation to average trapping time. Below provides a detailed proof.

Theorem 2 The closed-form solution to average trapping time ATT_ℋ(t) is given by


    ATT_ℋ(t)=O(t+1/2+1/m).

In the limit of large t, the graph G^⋆(m,t) exhibits the approximately most optimal topological structure by means of holding the theoretical lower bound for ATT_ℋ(t) in Eq.(<ref>).


 Proof Before proceeding further, we need to come up with some notations that help to accomplish the proof to Eq.(<ref>). Let symbol P_ℋ(t)(L;s) (1≤ L ≤ t+1) denote the probability for a walker originally set to a vertex u at the layer L to first visit that trap ℋ(t) in s steps. And then, it is clear to the eye that probabilities P_h(L;s) (1≤ L ≤ t+1) satisfy the following master equations




    P_ℋ(t)(t+1;s)=δ_s,1/k_t+1+1/k_t+1∑_L=1^tP_ℋ(t)(L;s-1),


    P_ℋ(t)(L;s)=δ_s,1/k_L+k_L-1/k_LP_ℋ(t)(t+1;s-1).


Here k_L is the degree of vertex lying at the layer L (1≤ L ≤ t+1) and δ_s,1 represents the Kronecker delta function where δ_s,1 is equal to 1 when s=1 and 0 otherwise. In general, one well-used approach to addressing the both equations above is probability generating function. Therefore, for our purpose, we denote by 𝒫_ℋ(t)(L;z) the probability generating function corresponding to probability P_ℋ(t)(L;s). After that, using methods from probability generating function, Eqs.(<ref>) and (<ref>) are able to be rearranged as




    𝒫_ℋ(t)(t+1;z)=z/k_t+1+z/k_t+1∑_L=1^t𝒫_ℋ(t)(L;z),


    𝒫_ℋ(t)(L;z)=z/k_L+(k_L-1)z/k_L𝒫_ℋ(t)(t+1;z).



Using a trivial fact associated to probability generating function 𝒫_ℋ(t)(t+1;z), that is, the first-order differential of 𝒫_ℋ(t)(t+1;z) at value z=1 defined to be the expected trapping time as follows


    TT_ℋ(t)(t+1)=.ddz𝒫_ℋ(t)(t+1;z)|_z=1,

we can perform differential on the both sides of Eqs.(<ref>) and (<ref>) and then write a series of iterative equations




    TT_ℋ(t)(t+1)=.ddz𝒫_h(t+1;z)|_z=1=1+1/k_t+1∑_L=1^tTT_ℋ(t)(L),


    TT_ℋ(t)(L)=.ddz𝒫_h(L;z)|_z=1=1+k_L-1/k_LTT_ℋ(t)(t+1).



According to Eqs.(<ref>) and (<ref>), the exact solution for trapping time TT_ℋ(t)(t+1) can be solved to express


    TT_ℋ(t)(t+1)=2t+1/t+1-∑_L=1^tk_L-1/k_L.


Thus,


    TT_ℋ(t)(L)=1+k_L-1/k_L(2t+1/t+1-∑_L=1^tk_L-1/k_L).


Substituting Eqs.(<ref>) and (<ref>) into Eq.(<ref>) produces the precise solution for ATT_ℋ(t)


    TT_ℋ(t)(L)≈ t+1/2+1/m.

This proves Theorem 2.

By far, the trapping problem with a single trap has been completely answered. Additionally, we are also interested in the multi-traps problem since many real-world applications, for example, target search, contain many destination objects that might be abstractly thought of as the traps considered in this paper. Hence, to some extents, it is quite meaningful to handle the issue with multi-traps. The following subsections aim at reporting some consequences correlated to the multi-traps problem on the proposed graph G^⋆(m,t).




 §.§ ATT to multiple vertices


As said above, one of most significant reasons for assigning the trap at vertex ℋ(t) is that all vertices but vertex ℋ(t) in graph G^⋆(m,t) are connected to the hub. It is obvious to see that an arbitrary vertex v at the layer L (0≤ L≤ t) is also connected to some vertex at the bottom-most layer. If we unify all the vertices at the layer t+1 into a hyper-vertex α, then one finds that the newly unified vertex  α connects to all other vertices in graph G^⋆(m,t). Similarly, we want to learn about what the average trapping time ATT_α is when the hyper-vertex α is occupied by number m^t+1 of traps.




  §.§.§ ATT to hyper-vertex α


With the help of Eq.(<ref>), in such a situation where each vertex at the bottom-most layer is filled with one trap, we can calculate the the theoretical lower bound for average trapping time ATT_α and write



    ATT'_α=2|ℰ^⋆_m(t)|/m^t+1(t+1)-1=O(1+1/t).


And then, the analytic value for ATT_α is follows.

Theorem 3 The closed-form solution to average trapping time ATT_α is calculated equal to


    ATT_α=1+∑_i=1^tm^i/k_0/1-1/k_0∑_i=1^tm^i/k_i+∑_i=1^tm^i[1+1/k_i(1+∑_i=1^tm^i/k_0/1-1/k_0∑_i=1^tm^i/k_i)]/m^t+2-1/m-1-m^t+1,

where k_i (0≤ i≤ t) is the degree of vertex at the layer i.

 Proof As previously, we have to introduce some notations as follows (i) symbol P_α(0;s) represents the probability that a walker at the hub first hop on some vertex at the layer t+1 in s steps and (ii) P_α(L;s) is viewed as the probability for a walker at an arbitrary vertex at the layer L (1≤ L≤ t) to first hit some vertex at the bottom-most layer. And then, we can obtain a group of master equations




    P_α(0;s)=m^t+1/k_0δ_s,1+∑_i=1^tm^i/k_0P_α(i;s-1),


    P_α(i;s)=k_i-1/k_iδ_s,1+1/k_iP_α(0;s-1),


in which δ_s,1 is the Kronecker delta function as above and k_i is the degree of vertex at the layer i.

Using technique from probability generating function, we denote by 𝒫_α(i;z) generating function associated with the probability P_α(i;s). After that, Eqs.(<ref>) and (<ref>) can be rewritten as




    𝒫_α(0;z)=m^t+1/k_0z+∑_i=1^tm^iz/k_0𝒫_α(i;s),


    𝒫_α(i;z)=k_i-1/k_iz+z/k_i𝒫_α(0;s).



Similar to the development of Eq.(<ref>), taking differential on the both sides of Eqs.(<ref>) and (<ref>) produces, respectively,




    TT_α(0)=.ddz𝒫_α(0;z)|_z=1=1+∑_i=1^tm^i/k_0TT_α(i),


    TT_α(i)=.ddz𝒫_α(i;z)|_z=1=1+1/k_iTT_α(0)


where TT_α(i) denotes the expected time taken by a walker originally starting out from one vertex allocated at the layer i to first visit some vertex lying at the layer t+1.



Inserting Eq.(<ref>) into Eq.(<ref>) outputs


    TT_α(0)=k_0+∑_i=1^tm^i/k_0-∑_i=1^tm^i/k_i.


And then, for 1≤ i≤ t, we have


    TT_α(i)=1+1/k_i(k_0+∑_i=1^tm^i/k_0-∑_i=1^tm^i/k_i).


Upon Eq.(<ref>), the precise formula for average trapping time ATT_α can be obtained


    ATT_α=k_0+∑_i=1^tm^i/k_0-∑_i=1^tm^i/k_i+∑_i=1^tm^i[1+1/k_i(k_0+∑_i=1^tm^i/k_0-∑_i=1^tm^i/k_i)]/m^t+2-1/m-1-m^t+1,

in which we have made use of a fact that the total number of vertices with trapping time TT_α(i) is equivalent to m^i.

Using some simple arithmetics, the result from Eq.(<ref>) reduces to that of Eq.(<ref>). This proves Theorem 3.

Nonetheless, we want to know about whether such an analytic value ATT_α in Eq.(<ref>) is asymptotically equal to the theoretical lower bound ATT'_α in Eq.(<ref>) in the limit of large t. To this end, we denote by parameter Δ_α the ratio of ATT_α and ATT'_α and then feed the three parameters, i.e., ratio Δ_α, m and t, into computer. As illustrated in Fig.4, our scale-free graph G^⋆(m,t) still exhibits the more optimal trapping efficiency when we assign the traps to all vertices at the bottom-most layer.







By the theoretical analysis above, the hub acts as a similar role to that hyper-vertex α since the average average trapping times corresponding to the both vertices hold on the theoretical lower bound, separately. Compered to the demonstration in Theorem 2, the result in Theorem 3 shows that choosing all vertices at the layer t+1 as potential trap locations leads to the most optimal trapping efficiency. In another words, on average, a walker from an arbitrary vertex at the layer i (0≤ i≤ t) takes only one step to first hit some vertex at the layer t+1. Generally speaking, one hop should be the smallest measure for a walker that is doing random walk in the trapping problem. Hence, we are able to state that the assignment of traps to the hyper-vertex α is perfect[In the trapping problem on a graph G(V,E), a scheme ξ for assigning traps to a set of vertices V_1 (≠ V) may be considered perfect such that a walker coming from an arbitrary vertex v∈ V-V_1 spends only one step arriving some vertex u∈ V_1 on average.] in the trapping problem considered in subsection 4.4.1.

As reported above, the potential trap locations have crucial effect on average trapping time. For a given graph G(V,E), it is intriguing and challenging to seek for a perfect assignment of traps in the trapping problem. In fact, such an issue is closely related to one of the classic combinatorics problems, i.e., looking for maximum independent set on graph in question. As known, there is no polynomial algorithm for solving the problem of determining maximum independent set of a given graph. Here, based on both the specific structure of our graph G^⋆(m,t) and the concrete expression of average trapping time ATT_α, we find the hyper-vertex α to be the maximum independent set of graph G^⋆(m,t). On the other hand, there are significant differences between the both problems in nature. The scheme for placing traps at a maximum independent set of a graph is not always perfect. For example, as discussed above, the maximum independent set of complete graph K_n consists only of a single vertex and however Eq.(<ref>) says that designating the trap at that vertex is not perfect. Yet, star graph S_(1,n) in practice has a perfect assignment scheme that is not that considered in example 3. This perfect project, however, is to allocate traps at each leaf vertex that in fact together constitute the maximum independent set of star graph S_(1,n) <cit.>. In a word, we would like to stress that finding perfect trap assignment has considerably practical applications and greatly theoretical flavor. As future direction, we will pay more attention to building up available approaches to addressing this interesting and challenging issue for more general graphs. At the same time, we also wish to witness some meaningful consequences related to perfect trap assignment in the trapping problem developed by other interested researchers in the days to come.


By far, we already study the trapping problem on the proposed graph G^⋆(m,t) where traps are placed at some vertices of great interest, such as with largest degree or together spanning a maximum independent set. Some related results have been listed above. In order to make progress further, the next subsection will continue to consider the trapping problem with multi-traps. By analogy with the discussions above, the trap is now distributed to each vertex belonging to some designated layer i (1≤ i≤ t). Here, those vertices at the layer i can be identified to a hyper-vertex β_i (1≤ i≤ t) for convenience too.




  §.§.§ ATT to hyper-vertex β_j


Along the same line as the aforementioned subsection, the first task is to calculate the theoretical lower bound for average trapping time ATT_β_j on the basis of Eq.(<ref>), as below


 
    ATT'_β_j=2|ℰ^⋆_m(t)|/m^t+1+m^j-1=O(2t+1).

This has the same order of magnitude as that of Eq.(<ref>) in the limit of large graph size.

Interestingly, the value for ATT'_β_j can also be approximately hold by the analytic value for average trapping time ATT_β_j in the limit of large t as will be proved later. For our purpose, below puts forward some useful notations Ω_i (i=0,1,…, 4) and Ψ_i (i=0,1) whose corresponding implications will be clarified in the process of validating Theorem 4.


 
    {   Ω_0=∑_i=1^j-11/k_i+∑_i=j+1^t1/k_i,    Ω_1=∑_i=1^j-1k_i-1/k_i+∑_i=j+1^tk_i-1/k_i,
       Ω_2=∑_i=1^j-1m^i/k_0+∑_i=j+1^tm^i/k_0,    Ω_3=1/k_0(∑_i=1^j-1m^i/k_i+∑_i=j+1^tm^i/k_i),
       Ω_4=∑_i=1^j-1m^i/k_0k_i-1/k_i+∑_i=j+1^tm^i/k_0k_i-1/k_i,
       Ψ_1=1+Ω_2+(m^t+1/k_0+Ω_4)(k_t+1+t-1/k_t+1)/1-[Ω_3+(m^t+1/k_0+Ω_4)(1+Ω_0/k_t+1-Ω_1)],
       Ψ_2=k_t+1+t-1/k_t+1-Ω_1+(1+Ω_0/k_t+1-Ω_1)Ψ_1,
    .

here k_i indicates the degree of vertex at the layer i (0≤ i≤ t+1) as above.

Theorem 4 The closed-form solution to average trapping time ATT_β_i is written in the next term


    ATT_β_j=m^t+1-m^j+1+m^j-m+(m-1)[(m^t+1+k_0Ω_4)Ψ_2+(1+k_0Ω_3)Ψ_1]/m^t+2-m^j+1+m^j-1.


 Proof Using a similar approach to proving Theorem 3, let notations P_β_j(t+1;s), P_β_j(i;s) (i≠ j) as well as P_β_j(0;s), respectively, denote the probability that a walker moves from its original location v, a vertex that is at the layer i, to some trap in the layer j in s steps. And then, these probabilities satisfy the following master equations





    P_β_j(t+1;s)=δ_s,1/k_t+1+(1/k_t+1∑_i=0^j-1P_β_j(i;s-1)+1/k_t+1∑_i=j+1^tP_β_j(i;s-1)),


    P_β_j(i;s)=1/k_iP_β_j(0;s-1)+k_i-1/k_iP_β_j(t+1;s-1),


    P_β_j(0;s)=m^j/k_0δ_s,1+(∑_i=1^j-1m^i/k_0P_β_j(i;s-1)+∑_i=j+1^t+1m^i/k_0P_β_j(i;s-1)).



Following Eqs.(<ref>)-(<ref>), the probability generating functions corresponding to quantities P_β_j(t+1;s), P_β_j(i;s) and P_β_j(0;s) can be obtained




    𝒫_β_j(t+1;z)=z/k_t+1+(z/k_t+1∑_i=0^j-1𝒫_β_j(i;z)+z/k_t+1∑_i=j+1^t𝒫_β_j(i;z)),


    𝒫_β_j(i;z)=z/k_i𝒫_β_j(0;z)+(k_i-1)z/k_i𝒫_β_j(t+1;z),


    𝒫_β_j(0;z)=m^j/k_0z+(∑_i=1^j-1m^iz/k_0𝒫_β_j(i;z)+∑_i=j+1^t+1m^iz/k_0𝒫_β_j(i;z)).



After performing differential on the two sides of Eqs.(<ref>)-(<ref>), the expected trapping time TT_β_j(i) (i≠ j) can be derived




    TT_β_j(t+1)   =.ddz𝒫_β_j(t+1;z)|_z=1
       =1+1/k_t+1TT_β_j(0)+1/k_t+1(∑_i=1^j-1TT_β_j(i)+∑_i=j+1^tTT_β_j(i))
    ,


    TT_β_j(i)=.ddz𝒫_β_j(i;z)|_z=1=1+1/k_iTT_β_j(0)+k_i-1/k_iTT_β_j(t+1),


    TT_β_j(0)   =.ddz𝒫_β_j(0;z)|_z=1
       =1+m^t+1/k_0TT_β_j(t+1)+(∑_i=1^j-1m^i/k_0TT_β_j(i)+∑_i=j+1^tm^i/k_0TT_β_j(i))
    .



For brevity, we now introduce two notations Ω_0=∑_i=1^j-11/k_i+∑_i=j+1^t1/k_i and Ω_1=∑_i=1^j-1dk_i-1/k_i+∑_i=j+1^tk_i-1/k_i. After that, Eq.(<ref>) can be reorganized as


    TT_β_j(t+1)=1+t-1/k_t+1+1+Ω_0/k_t+1TT_β_j(0)+Ω_1/k_t+1TT_β_j(t+1).


Analogously, according to three new notations, Ω_2=∑_i=1^j-1m^i/k_0+∑_i=j+1^tm^i/k_0, Ω_3=1/k_0(∑_i=1^j-1m^i/k_i+∑_i=j+1^tm^i/k_i) along with Ω_4=∑_i=1^j-1m^i/k_0k_i-1/k_i+∑_i=j+1^tm^i/k_0k_i-1/k_i, Eq.(<ref>) may be converted into


    TT_β_j(0)=1+Ω_2+(m^t+1/k_0+Ω_4)TT_β_j(t+1)+Ω_3TT_β_j(0).


In terms to Eqs.(<ref>) and (<ref>), we may use simple arithmetics to rearrange TT_β_j(0) as


    TT_β_j(0)   =1+Ω_2+(m^t+1/k_0+Ω_4)(k_t+1+t-1/k_t+1)
       +[Ω_3+(m^t+1/k_0+Ω_4)(1+Ω_0/k_t+1-Ω_1)]TT_β_j(0).


In what follows, the precise solution for trapping time TT_β_j(0) is


    TT_β_j(0)=1+Ω_2+(m^t+1/k_0+Ω_4)(k_t+1+t-1/k_t+1)/1-[Ω_3+(m^t+1/k_0+Ω_4)(1+Ω_0/k_t+1-Ω_1)].


Plugging the value for TT_β_j(0) into Eq.(<ref>) yields



    TT_β_j(t+1)=k_t+1+t-1/k_t+1-Ω_1+(1+Ω_0/k_t+1-Ω_1)1+Ω_2+(m^t+1/k_0+Ω_4)(k_t+1+t-1/k_t+1)/1-[Ω_3+(m^t+1/k_0+Ω_4)(1+Ω_0/k_t+1-Ω_1)].


Taking into account Eqs.(<ref>), (<ref>) and (<ref>), by definition in Eq.(<ref>), we finally derive the closed-form solution to average trapping time ATT_β_j


    ATT_β_j=(m^t+1-m/m-1-m^j)+(m^t+1+k_0Ω_4)TT_β_j(t+1)+(1+k_0Ω_3)TT_β_j(0)/m^t+2-1/m-1-m^j.


Utilizing two notations Ψ_1=1+Ω_2+(m^t+1/k_0+Ω_4)(k_t+1+t-1/k_t+1)/1-[Ω_3+(m^t+1/k_0+Ω_4)(1+Ω_0/k_t+1-Ω_1)] and Ψ_2=k_t+1+t-1/k_t+1-Ω_1+(1+Ω_0/k_t+1-Ω_1)Ψ_1, Eq.(<ref>) may easily reduce to Eq.(<ref>), implying that Theorem 4 is complete.


In terms of space limitation, we omit the related comparison between Eq.(<ref>) and  Eq.(<ref>). Interested reader can prove the equivalence between them in a similar manner mentioned in subsection 4.4.1.


















§ CONCLUSION


In summary, we have presented a class of graphs G^⋆(m,t) with diameter 2 and then considered some widely-studied structural properties on graphs G^⋆(m,t). Based on theoretical analysis and experimental simulations, we find that graphs G^⋆(m,t) show some intriguing structural properties including density feature, scale-free feature (degree distribution obeying power-law with exponent 2 in form), small-world character and disassortative structure. At the same time, we have studied the trapping problem on graphs G^⋆(m,t) and precisely derived the closed-from solution to average trapping time. The results reveal that our graphs are able to have more optimal trapping efficiency by holding the theoretical lower bound for average tapping time.

It is worth noting that the goal of this work is to only study graphs of great interest from the theoretical point of view. In another words, all models considered may be artificial and rarely found in real-world situation. Yet, as shown above, we introduce a generative framework for creating scale-free graphs with exponent 2, a class of models that are seldom addressed in early study. Furthermore, the methods developed for discussing the trapping problem of graphs may be useful to study many other models in the study of complex networks.











§ ACKNOWLEDGE


The research was supported in part by the National Key Research and Development Plan under grant 2017YFB1200704 and the National Natural Science Foundation of China under grant No. 61662066.






9




Newman-2018 M.E.J. Newman. Networks. Oxford university press. 2018

Albert-2016 A.-L. Barabási. Network science. Cambridge university press. 2016

Shanker-2010 O. Shanker. Complex network dimension and path counts. Theoretical Computer Science, 411 (2010): 2454-2458

Hao-2018 L. Hao. Overlapping community detection with least replicas in complex networks. Information Sciences. 453 (2018): 216-226

Staudt-2016 C.L. Staudt, A. Sazonovs, H. Meyerhenke. NetworKit: A tool suite for large-scale complex network analysis. Network Science. 4 (2016): 508-530

Watts-1998 D.J. Watts, S.H. Strogatz. Collective dynamics of small-world networks. Nature. 393 (1998): 440-442

Albert-1999-1 A.-L. Barabási, R. Albert. Emergence of Scaling in Random Networks. Science. 5439 (1999): 509-512

 Bondy-2008 J.A. Bondy. U.S.R. Murty. Graph Theory. Springer. 2008

 Sarma-2015 A.D. Sarma, A. R. Molla , G. Pandurangan. Distributed computation in dynamic networks via random
walks. Theoretical Computer Science. 581 (2015): 45-66

Colomer-de-Simon-2014 P. Colomer-de-Simon. M, Boguna. Double Percolation Phase Transition in Clustered Complex Networks. Phys. Rev. X. 4 (2014)041020

Ling-2019 S.Y. Ling, R.T. Xu, A.S. Bandeira. On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization. SIAM Journal on Optimization. 29 (2019): 1879-1907



MF-2019-1 F. Ma, P. Wang, B. Yao. An extremal problem: How small scale-free graph can be. To submit. 	arXiv:1911.09253

Wang-2019 Y.C. Wang, Q. Bao, Z.Z. Zhang. Combinatorial properties of Farey graphs. Theoretical Computer Science. 796 (2019): 70-89

Ferretti-2017 S. Ferretti. On the modeling of musical solos as complex networks. Information Sciences. 375 (2017): 271-295

Ma-2018 F. Ma, B. Yao. An iteration method for computing the total number of spanning trees and its applications in graph theory. Theoretical Computer Science. 708 (2018): 46-57

Chen-2007 M. Chen, B.M. Yu, P. Xu, J. Chen. A new deterministic complex network model with
hierarchical structure. Physica A.  385 (2007): 707-717

Albert-2001 A.-L. Barabási, E. Ravasz, T. Vicsek. Deterministic scale-free networks. Physica A. 299 (2001): 559-564

Ma-2019 F. Ma, P. Wang, B. Yao. Generating Fibonacci-model as evolution of networks with vertex-velocity and time-memory. Physica A. 527 (2019)121295

Ravasz-2003  E. Ravasz,  A.-L. Barabási. Hierarchical organization in complex networks. Phys. Rev. E. 67 (2003)026112


Definition-2020-2 Generally speaking, a graph G(V,E) is defined as small-world if it has a smaller diameter D and a higher clustering coefficient ⟨ C⟩. Here, it is convention to require D=O(ln|V|) and ⟨ C⟩→α (a non-zero constant ) in the large graph size limit.

Newman-2002 M.E.J. Newman. Assortative mixing in networks. Phys. Rev. Lett. 89, (2002) 208701.

Rosvall-2008 M. Rosvall. C.T. Bergstrom. Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci U S A. 105 (2008): 1118-1123

Chung-1997 F.R. Chung. Spectral Graph Theory. American Mathematical Society. Providence. 1997


Aldous-1999 D. Aldous, J. Fill. Reversible Markov chains and random walks on graphs (1999), http://www.stat.berkeley.edu/aldous/RWG/Chap2.pdf

Zhang-2009 Z.Z. Zhang, Y. Qi, S.G. Zhou, Y. Lin, J.G. Guan. Recursive solutions for Laplacian spectra and eigenvectors of a class of growing treelike networks. Phys. Rev. E. 80 (2009)016104.

Benichoua-2014 O. Benichoua, R. Voituriez. From first-passage times of random walks in confinement to geometry-controlled kinetics. Physics Reports. 539 (2014): 225-284


Definition-2020-1 In general, it is a trivial fact that the scheme for assigning number |V|-1 of traps to all vertices but an arbitrary vertex in a given graph G(V,E) must be perfect.

J. Stelling-2002 J. Stelling, S. Klamt, K. Bettenbrock, S. Schuster, E.D. Gilles. Nature. 420 (2002): 190-193

A. Akhmanova-2008 A. Akhmanova, M.O. Steinmetz. Nature Reviews Molecular Cell Biology. 9 (2008): 309-322







