摘要A comparative study is carried out on the efficiency of five different random walk strategies searching on directed networks constructed based on several typical complex networks. Due to the difference in search efficiency of the strategies rooted in network clustering, the clustering coefficient in a random walker's eye on directed networks is defined and computed to be half of the corresponding undirected networks. The search processes are performed on the directed networks based on Erdös–Rényi model, Watts–Strogatz model, Barabási–Albert model and clustered scale-free network model. It is found that self-avoiding random walk strategy is the best search strategy for such directed networks. Compared to unrestricted random walk strategy, path-iteration-avoiding random walks can also make the search process much more efficient. However, no-triangle-loop and no-quadrangle-loop random walks do not improve the search efficiency as expected, which is different from those on undirected networks since the clustering coefficient of directed networks are smaller than that of undirected networks.
Abstract：A comparative study is carried out on the efficiency of five different random walk strategies searching on directed networks constructed based on several typical complex networks. Due to the difference in search efficiency of the strategies rooted in network clustering, the clustering coefficient in a random walker's eye on directed networks is defined and computed to be half of the corresponding undirected networks. The search processes are performed on the directed networks based on Erdös–Rényi model, Watts–Strogatz model, Barabási–Albert model and clustered scale-free network model. It is found that self-avoiding random walk strategy is the best search strategy for such directed networks. Compared to unrestricted random walk strategy, path-iteration-avoiding random walks can also make the search process much more efficient. However, no-triangle-loop and no-quadrangle-loop random walks do not improve the search efficiency as expected, which is different from those on undirected networks since the clustering coefficient of directed networks are smaller than that of undirected networks.
ZHU Zi-Qi, JIN Xiao-Ling**, HUANG Zhi-Long. Search for Directed Networks by Different Random Walk Strategies[J]. 中国物理快报, 2012, 29(3): 38901-038901.
ZHU Zi-Qi, JIN Xiao-Ling, HUANG Zhi-Long. Search for Directed Networks by Different Random Walk Strategies. Chin. Phys. Lett., 2012, 29(3): 38901-038901.
[1] Watts D J and Strogatz S H 1998 Nature 393 440
[2] Barabási A L and Albert R 1999 Science 286 509
[3] Wang B H and Zhou T 2007 J. Korean Phys. Soc. 50 134
[4] Tadic B, Rodgers G J and Thurner S 2007 Int. J. Bifurcation & Chaos 17 2363
[5] Zhou T, Fu Z Q and Wang B H 2006 Prog. Nat. Sci. 16 452
[6] Pandit S A and Amritkar R E 2001 Phys. Rev. E 63 041104
[7] Huang Z G, Xu X J, Wu Z X and Wang Y H 2006 Eur. Phys. J. B 51 549
[8] Yang H X, Wang B H, Liu J G, Han X P and Zhou T 2008 Chin. Phys. Lett. 25 2718
[9] Yang S J 2005 Phys. Rev. E 71 016107
[10] Yin C Y, Wang B H, Wang W X, Zhou T and Yang H J 2006 Phys. Lett. A 351 220
[11] Wang W X, Wang B H, Yin C Y, Xie Y B and Zhou T 2006 Phys. Rev. E 73 026111
[12] Newman M E J, Strogatz S H and Watts D J 2001 Phys. Rev. E 64 026118
[13] Erdos P and Renyi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17
[14] Barrat A and Weigt M 2000 Eur. Phys. J. B 13 547
[15] Klemm K and Eguıluz V M 2002 Phys. Rev. E 65 057102
[16] Barabasi A L, Albert R and Jeong H 1999 Physica A 272 173
[17] Fronczak A, Fronczak P and Holyst J A 2003 Phys. Rev. E 68 046126
[18] Noh J D and Rieger H 2004 Phys. Rev. Lett. 92 11
[19] Zhou T, Zhao M and Zhou C S 2010 New J. Phys. 12 043030
2012, Vol. 29 
