The entire mean weighted first-passage time on a family of weighted treelike networks

Abstract

In this paper, we consider the entire mean weighted first-passage time (EMWFPT) with random walks on a family of weighted treelike networks. The EMWFPT on weighted networks is proposed for the first time in the literatures. The dominating terms of the EMWFPT obtained by the following two methods are coincident. On the one hand, using the construction algorithm, we calculate the receiving and sending times for the central node to obtain the asymptotic behavior of the EMWFPT. On the other hand, applying the relationship equation between the EMWFPT and the average weighted shortest path, we also obtain the asymptotic behavior of the EMWFPT. The obtained results show that the effective resistance is equal to the weighted shortest path between two nodes. And the dominating term of the EMWFPT scales linearly with network size in large network.

A

Dai, Yanqiu Sun, Yu Sun Xi & Shuxiang

In recent years, the study of networks associated with complex systems has received the attention of researchers from many dierent areas. Especially, weighted networks1,2 represent the natural framework to describe natural, social, and technological systems3. The deterministic weighted networks have attracted increasing attentions because many network characteristics are exactly solved through their quantities, such as mean weighted rst-passage time, average weighted shortest path4 etc.

Several recent works have studied the mean rst-passage time (MFPT) for some self-similar weighted network models. Dai et al.5 found that the weighted Koch networks are more efficient than classic Koch networks in receiving information when a walker chooses one of its nearest neighbors with probability proportional to the weight of edge linking them (weight-dependent walk). Then Dai et al.6 introduced non-homogenous weighted Koch networks, and dened the mean weighted rst-passage time (MWFPT) inspired by the denition of the average weighted shortest path. Sun et al.4 discussed a family of weighted hierarchical networks which are recursively dened from an initial uncompleted graph. Zhu et al.7 reported a weighted hierarchical network generated on the basis of self-similarity, and calculated analytically the expression of the MFPTs with weight-dependent walk by using a recursion relation of the hierarchical network structure. Sun et al.8 obtained the exact scalings of the mean rst-passage time (MFPT) with random walks on a family of small-world treelike networks.

For un-weighted networks, calculating the entire mean rst-passage time (EMFPT) generally use three methods, i.e., the denition of the EMFPT8,9, the average shortest path10, and Laplacian spectra11,12. Sun et al.8 used the denition of the EMFPT for the considered networks to obtain the analytical expressions of the EMFPT and avoided the calculations of the Laplacian spectra.

In this paper, there are two methods to calculate the entire mean weighted rst-passage time (EMWFPT), Fn, for the weighted treelike networks as follows. Method 1 is to get the asymptotic behavior of the EMWFPT directly by the denition of the EMWFPT. Method 2 is to get the asymptotic behavior of the EMWFPT based on the relationship between Fn and n, i.e, Fn=(Nn1)n, where Nn is the total number of nodes. The obtained consistent results show that Method 2 is entirely feasible. Thus the eective resistance mean exactly the weight between two adjacency nodes for the weighted treelike networks. Our key nding is profound, which can help us to compute the EMWFPT by the weighted Laplacian spectra.

The organization of this paper is as follows. In next section we introduce a family of weighted treelike networks. Then we give the denition of the EMWFPT and use two methods to calculate it. In the last section we draw conclusions.

SCIENTIFIC REPORTS

1

www.nature.com/scientificreports/

Figure 1. Take the Sierpinski weighted treelike networks Gn, for example, Gn is regarded as merging

Gn( ) 1

1 ,

Gn( ) 1

2 ,

Gn( ) 1

3 and central Node an, n=0, 1, 2.

Recently, there are several literatures on the preferential-attachment (scale-free) method of generating a random by adding a very specic way of generating weights1,13,14. Based on Barabasi-Albert model, deterministic networks have attracted increasing attention because they have an advantage with precise formulations on some attributes. In this section a family of weighted treelike networks are introduced1517, which are constructed in a deterministic iterative way. The recursive weighted treelike networks are constructed as follows.

Let r(0<r< 1) be a positive real numbers, and s(s> 1) be a positive integer.

(1) Let G0 be base graph, with its attaching node a0 and the other nodes "

a a a a

(1) , , , , s

0

(2)

(3)

0

0

0

( ). Each node of

a a a a

(1) , , , , s

0

(2)

(3)

( ) links the attaching node a0 with unitary weight. We also call the attaching node a0 as the central node.(2) For any n1, Gn is obtained from Gn1: Gn has one attaching node labelled by an, that we call an as the central node of Gn. Let

"

0

0

"

0

( ) be s copies of Gn1, whose weighted edges have been scaled by a weight factor r. For = "

i s

1, 2, , , let us denote by

ani 1

( ) the node in

Gni 1

( ) image of

G G G

(1) , , ,

n n n

s

(2)

1

1

1

a G

n n

1 1, then link all those

ani 1

( ) to the attaching node .. through edges of unitary weight. Let Gn = G(Vn, En) be its associated weighted treelike network, with vertex set Vn(|Vn|=Nn) and edge set En(|En|=Nn1). Similarly, =

G G V E

( , )

n

( )

i

1

n

i

1

n

i

( ) ( ) ,

1

= "

i s

1, 2, , . In Fig.1, we schematically illustrate the process of the rst three iterations.

The weighted treelike networks are set up.

According to the construction method of Gn (n1), Gn can be regarded as merging s+ 1 groups, sequentially denoted by

"

( ) . (see Fig.1).

From the construction of the weighted treelike networks, one can see that Gn, the weighted treelike networks of n-th generation, is characterized by three parameters n, s and r: n being the number of generations, s being the number of copies, and r representing the weight factor. The total number of nodes Nn in Gn satisfy the following relationship, i.e. = +

N sN 1

n n 1 . Then

a G G G

, , , ,

n n n n

s

(1)

(2)

1

1

1

SCIENTIFIC REPORTS

2

www.nature.com/scientificreports/

=

+ .

N s s

11 (1)

n 2

n

Assuming that the walker, at each step, starting from its current node, moves uniformly to any of its nearest neighbors. For two adjacency nodes i and j, the weighted time is dened as the corresponding edge weight wij.

The mean weighted rst-passing time (MWFPT) is the expected rst arriving weighted time for the walks starting from a source node to a given target node. Let the source node be i and the given target node be j, denote Fij(n) by

the MWFPT for a walker starting from node i to node j. We consider here the entire mean weighted rst-passage time Fn as the average of Fij(n) over all pair of vertices,

F N N F

1( 1)

n n n i j V i j

ij

= .

, ,

n

To calculate the asymptotic behavior of the Fn for this model, we focus on the two methods, the denition of the EMWFPT and the average shortest path, respectively.

In this section, we compute the EMWFPT using the denition of the EMWFPT. Step 1, we study the rst quantity Qtot(n), i.e, the sum of MWFPTs for all nodes in

Gn 1

(1) to absorption at the central node an. Step 2, we study the second quantity Htot(n), i.e, the sum of MWFPTs for central node an to arrive all nodes in

Gn 1

(1) of Gn. Step 3, we use the denition to obtain the asymptotic behavior of the MWFPT between all node pairs and the asymptotic behavior of the EMWFPT in the limited of large n.

We study the rst quantity Qtot(n), i.e, the sum of MWFPTs for all nodes in

Gn 1

(1) to absorption at the

, n be the MWFPT of a walker from node i to the central node an for the rst time. We denote by Ttot(n) the sum of MWFPTS for all nodes of Gn to absorption at the central node an.

We have already arrived the result about Ttot(n)15, i.e.

= +

T n sT n sN F n

tot ( ) ( 1) ( ), (2)

tot n a a

1 ,

n n

1

central node an. Dening F n

( )

i a

(1)

where

F n

( )

a a

,

n n

1

(1) be the MWFPT from Node

an 1

(1) to the central node an. Thus, the problem of determining Ttot(n)

is reduced to nding

F n

( )

a a

,

n n

1

(1) . Note that the degree of the node

ani 1

( ) = "

i s

( 1, 2, , ) is s+ 1, we obtain

= + + +

F n s

ss r F n F n

a ( ) 1 1 1 ( 1) ( ) (3)

(1) a a a a a

, , ,

n n n n n n

1

+ + .

(1)

(1)

1

1

Through the reduction of Eq.(3), we obtain

= + + .

F n sF n sr

a ( ) ( 1) 1 (4)

(1) a a a

, ,

n n n n

1

(1)

1

With the initial condition of = =

F (0)

a a

F

s

=

i

s i a tot

(1)

0

T

s

,

1 , 0 , Eq.(4) is inductively solved as

=

+

(0)

F n T s

srs s

a a

tot n ,

n n

1

(1) ( ) (0) 1 1

11 (5)

+

sr s

+ .

+ and Eq.(5) into Eq.(2), we obtain the exact solution of MWFPT from all other

nodes to the central node on the networks Gn as follow

= +

= +

Inserting =

Nn

s

n 1

1

1 1

s

T n sT n sN F n

sT n T s s

srs s s

s srs s

tot tot n a a

tot

tot n n

( ) ( 1) ( )

( 1) (0)

( 1)

1 ,

(1)

n n

2 2 1

+

+

( 1) ( )

( 1)( 1) ( 1)

1 2

+ +

+

.

n

+

1

2

Then,

T n T s s

srs s

tot

( ) (0)

( 1)

1

+

tot n 2 3

2 3

+

+

.

( 1) (6)

From the denition of Ttot(n), Ttot(n) is given by

SCIENTIFIC REPORTS

3

www.nature.com/scientificreports/

T n F n

F n F n F n

s F n

sQ n

( ) ( )

( ) ( ) ( )

( )

( ), (7)

tot

=

= + + +

=

=

n

i V a

i a

n n

\{ }

,

i a

i a

"

, , ,

,

(1)

n

n

i a

i V

i V

(2)

( )

n

n

1

i V

s n

1

n

1

i a

i V

(1)

n

n

1

tot

( ) . Recalling that Eq.(1), the asymptotic behavior of Qtot(n) in the limited of large n is as follows,

where = = =

"

(1) F n F n F n

( ) ( ) ( )

i V i a i V i a i V i a

, , ,

n n n n n

s

(2)

1

1

1

n

Q n T s s

srs s

N

tot n

tot

( ) (0) ( 1)

1

( 1)

+

+

+

2 3

2 2

2

n

.

(8)

We study the second quantity Htot(n), i.e, the sum of MWFPTs for central node an to arrive all nodes in

Gn 1

(1) of Gn. Firstly, let Ri(n) denote the expected weighted time for a walker in weighted networks Gn, originating from node i to return to the starting point i for the rst time, named mean weighted return time. By denition of R n

( )

an , we obtain

R n s F n

s F n F n F n

s s sF n F n

( ) 1 1 ( )

1 1 ( ) 1 ( ) 1 ( )

1 ( )

1 ( ), (9)

= +

= + + + + + +

= + = +

a

( )

n

j a

,

n

j

an

{ }

"

a a a a a a

a a

a a

( )

s

n n n n n

1

(1) , , ,

(2)

1

1

n

(1)

1

,

n n

n n

(1)

1

,

where an is the set of neighbors of the central node an and = = =

F n F n F n

(1) ( ) ( ) ( )

a a a a a a

, , ,

n n n n n

s

(2)

"

( ) . Using

1

Eq.(5) and Eq.(9) is solved as

=

+

1

1

n

R n T s

srs s

a

tot n n

( ) (0) 1 1

21 (10)

+

+

.

s sr s

Note that the degree of the node an = "

i s

( 1, 2, , ) is s, we obtain

(1) = + + + .

F n s

s

a ( ) 1 1 1 ( ) ( ) (11)

a a a a

, ,

n n n n n

1

s R n F n

(2)

(2)

(1)

1

1

1

Similarly,

F n ss rR n F n s F n s

s rR n s F n

1 (1) ( ) 1 ( ) ( )

(2) 1 = +

+ + +

, , ,

,

(2)

(2)

(1)

1 +

a a a a a a a

a a a

(1)

1

1

1

1 1 ( )

n n n n n n n

n n n

1

= + + +

1 + .

2 1 ( )

(2)

1 1 ( ) (12)

(1)

1

1

Inserting Eq.(12) into Eq.(11), we obtain

= +

=

2

F n r s R n s

r s T

s r s sr s r s s sr s

(1) ( ) ( 1) ( 1) 2 1

( 1) (0) ( 1)( 1) ( 1)( 2) 2 1

(13)

a a a

tot n

n n n

1

,

2 + + +

+ + + .

From the denition of Htot(n), Htot(n) is written by

H n F n N F n rH n

( ) ( ) ( ) ( 1)

(14)

tot

= = + .

(1)

i V

a i n a a tot

, 1 , n

n n n

1

(1) 1

Recalling Eq.(1) and Eq.(13), Eq.(14) is solved as

+

H n rH n r s T s

r s sr

s s s

( ) ( 1) ( 1) (0) ( 1)( 1)

1 ( ) (15)

tot n n

2 1

tot tot

+ + + +

.

+

The asymptotic behavior of Htot(n) in the limited of large n is as follows,

SCIENTIFIC REPORTS

4

www.nature.com/scientificreports/

H n r s T s s r

r s sr

s s r s

N

( ) ( 1) (0) ( )

( 1)( 1) 1( )

tot n

+ +

+ +

+

tot

2 2

2 2

2

n

.

(16)

We use the denition to obtain the asymptotic behavior of the EMWFPT in the limited of large n. Starting from the denition of the EMWFPT and the recursive construction, we can decompose the Ftot(n) into four terms:

=

= +

+ + .

F n F n

s F n s s F n

s F n s F n

( ) ( )

( ) ( 1) ( )

( ) ( )

(17)

tot

,

i j G

i j

,

n

,

,

i j G

i j

,

(1)

i G j G

i j

(1)

(2)

1

n n n

n

n

1

,

1

i a

, ,

a i

i G

(1)

(1)

n

1

i G

n

1

The rst term takes into account a walker starting from and arriving at nodes belonging to the same subgraph. The second term takes into account all the possible paths where the initial point and the nal one belong to two dierent subgraphs, and we can set them to

Gn 1

(1) and

Gn 1

(2) and multiply the contribution by a combinatorial factor s(s 1). Finally the last two terms takes into account all the possible paths between each of nodes of subgraph

"

G G

(1) , ,

n n

s

( ) and the central node an.

Using the scaling mechanism for the edges, the rst term in Eq.(17) can be easily identied with

= .

F n rT n

( ) ( 1)

1

1

i j G

i j tot ,

,

(1)

n 1

(18)

By construction, each pass connecting two nodes belonging to two dierent subgraphs, must pass through the central node an, hence using = +

F n F n F n

( ) ( ) ( )

i j i a a j

, , ,

n n , the second term of Eq.(17) can be split into two parts:

F n N F n N F n

( ) ( ) ( )

(19)

= + .

i a n

j G

a j

i G j G

i j n

i G

, 1 , 1 , n n n

n

(1)

(2)

(1)

n

1

,

1

(2)

1

n

1

Then, Eq.(17) can be simplied as

F n rsF n s s N s F n

s s N s F n

rsF n s Q n s H n

( ) ( 1) [ ( 1) ] ( )

[ ( 1) ] ( )

( 1) ( ) ( ) (20)

tot tot n

i G

= + +

+ +

= + + .

i a

1 ,

1 ,

2 2

n

n

(1)

1

n

a j

n

j G

(1)

n

1

n

+ +

n

tot

tot

tot

Inserting Eq.(8) and Eq.(16) into Eq.(20), the asymptotic behavior of Ftot(n) in the limited of large n is as follows,

.

^

F n N

( ) (21)

tot n

3

and

F F n

N N N

( )( 1)

= .

tot

n n

n

n

(22)

In this section, Method 2 is that the average weighted shortest path used to get the asymptotic behavior the EMWFPT. This method gives some signicantly new insights more straightforward than Method 1.

The resistance distance rij between two nodes i and j is dened as the eective (electrical) resistance between them when each weighted edge has been replaced by a resistor. It is known that the weighted rst-passage time between two nodes is related to their resistance distance by + =

F F E r

2

i j j i n ij

, ,

18,19 and, in which =

E N 1

n n is the total number of edges for weighted treelike network Gn and Fi,j=Fj,i. The EMWFPT of weighted treelike network is

F N N F

N N N r

N r

=

=

= .

n n n i j V i j

ij

1( 1)

1( 1) ( 1)

1

, ,

, :

n

n

n n i j V i j

n ij

n i j V i j

ij

, :

n

(23)

SCIENTIFIC REPORTS

5

www.nature.com/scientificreports/

Let ij as the weighted shortest path between two nodes i and j of the weighted networks Gn2. For any weighted treelike networks, the weighted shortest path ij of Gn is equal to the eective resistance rij between node i and j,i.e, rij=ij. By denition the average weighted shortest path n of the graph Gn is given by4

= .

, :

n

( 1) (24)

For a large system, i.e., Nn, we have already known that the n of the Gn is (see ref. 17).

^ .

2( 1)

n (1 )( ) (25)

Now we substitute Eq.(24) and Eq.(25) into Eq.(23) obtaining,

= 1

sr s r

, :

n

=

.

n n n

This result coincides with the asymptotic behavior Fn in Eq.(22). Therefore, we can draw the conclusion that the eective resistance mean exactly the weight between two adjacency nodes for the weighted treelike networks.

In this paper, we have proposed a family of weighted treelike networks formed by three parameters as a generalization of the un-weighted trees. We have calculated the entire mean weighted rst-passage time (EMWFPT) with random walks on a family of weighted treelike networks. We have used two methods to obtain the asymptotic behavior of the EMWFPT with regard to network parameters. Firstly, using the construction algorithm, we have calculated the receiving and sending times from the central nodes to the other nodes of

Gn 1

(1) to obtain the asymptotic behavior of the EMWFPT. Secondly, applying the relationship equation between EMWFPT and the average weighted shortest path, we also have obtained the asymptotic behavior of the EMWFPT. The dominating terms of the EMWFPT obtained by two methods are coincident, which shows that the eective resistance is equal to the weight between two adjacency nodes. Noticed that the dominating term of the EMWFPT scales linearly with network size Nn in large network. It is expected that the edge-weighted adjacency matrices can be used to compute the weighted Laplacian spectra to obtain the asymptotic behavior of the EMWFPT of weighted treelike networks.

1. R. Albert & A. L. Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics 74, 47100 (2002).2. S. Dorogovtsev & J. Mendes. Evolution of networks: from biological nets to the internet. WWW Oxford: Oxford University Press (2003).

3. M. Dai & J. Liu. Scaling of average sending time on weighted Koch networks. Journal of Mathematical Physics 53(10), 103501103511 (2012).

4. Y. Sun, M. Dai & L. Xi. Scaling of average weighted shortest path and average receiving time on weighted hierarchical networks. Physica A 407, 110118 (2014).

5. M. Dai, D. Chen, Y. Dong & J. Liu. Scaling of average receiving time and average weighted shortest path on weighted Koch networks. Physica A 391, 61656173 (2012).

6. M. Dai, X. Li & L. Xi. Random walks on non-homogenous weighted Koch networks. Chaos 23(3), 0331068 (2013).7. F. Zhu, M. Dai, Y. Dong & J. Liu. Random walk and rst passage time on a weighted hierarchical network. International Journal of Modern Physics C 25(9), 14500371450047 (2014).

8. L. Li, W. Sun, G. Wang & G. Xu. Mean Frst-passage time on a family of small-world treelike networks. International Journal of Modern Physics C 25(3), 135009713500107 (2014).

9. V. Tejedor, O. Benichou & R. Voituriez. Global mean rst-passage times of random walks on complex networks. Physical Review E 80, 065104(R) (2009).

10. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez & D. Hwang. Complex networks: Structure and dynamics. Physics Reports-review section of physics letters 424, 175308 (2006).

11. H. Liu & Z. Zhang. Laplacian spectra of recursive treelike small-world polymer networks: Analytical solutions and applications. The journal of chemical physics 138, 114904 (2013).

12. P. Xie, Y. Lin & Z. Zhang. Spectrum of walk matrix for Koch network and its application. the journal of chemical physics 142, 224106 (2015).

13. B. Dasgupta & L. Kaligounder. On Global Stability of Financial Networks. Journal of Complex Networks 2(3), 313354 (2014).14. H. Minsky, E. Altman & A. Sametz. A Theory of Systemic Fragility. In: Financial Crises: Institutions and Markets in a Fragile Environment (Eds.), Wiley (1977).

15. M. Dai, Y. Sun, S. Shao, L. Xi & W. Su. Modied box dimension and average weighted receiving time on the weighted fractal networks. Scientic Reports 74, 47 (2015).

16. M. Dai, D. Ye, J. Hou, L. Xi & W. Su. Average weighted trapping time of the node- and edge- weighted fractal networks. Commun Nonlinear Sci Numer Simulat 39, 209219 (2016).

17. T. Carletti & S. Righi. Weighted Fractal Networks. Physica A 389, 21342142 (2010).18. A. Chandra, P. Raghavan, W. Ruzzo, R. Smolensky & P. Tiwari. The electrical resistance of a graph captures its commute and cover times. Comput Complex 6, 312340 (1996).

19. D. Klein & M. Randic. Resistance distance. Journal of Mathematical Chemistry 12(1), 8195 (1993).

n

N N

i j V i j ij

n n

F N

N N N

N

n

n

n

ij

n i j V i j

1 ( 1)

SCIENTIFIC REPORTS

6

www.nature.com/scientificreports/

Authors are grateful to the reviewer for valuable comments and suggestions. Research is supported by the Humanistic and Social Science Foundation from Ministry of Education of China (Grants 14YJAZH012), National Natural Science Foundation of China (Nos 11371329, 11471124, 11501255), NSF of Zhejiang Province (No. LR13A010001).

M.D. and L.X. designed the research. Yu S. and Yanqiu S. collected the data. M.D. and Yanqiu S. wrote the manuscript, and Yanqiu S. and S.S. prepared Figure 1. All authors discussed the results and reviewed the manuscript.

Competing nancial interests: The authors declare no competing nancial interests.

How to cite this article: Dai, M. et al. The entire mean weighted rst-passage time on a family of weighted treelike networks. Sci. Rep. 6, 28733; doi: 10.1038/srep28733 (2016).

This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the articles Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

SCIENTIFIC REPORTS

7