Random Walks on Stochastic and Deterministic Small-World Networks

Zi-Yi WANG  Shi-Ze GUO  Zhe-Ming LU  Guang-Hua SONG  Hui LI  

IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.5   pp.1215-1218
Publication Date: 2013/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.1215
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Information Network
complex networks,  small-world networks,  random walks,  search efficiency,  

Full Text: PDF>>
Buy this Article

Many deterministic small-world network models have been proposed so far, and they have been proven useful in describing some real-life networks which have fixed interconnections. Search efficiency is an important property to characterize small-world networks. This paper tries to clarify how the search procedure behaves when random walks are performed on small-world networks, including the classic WS small-world network and three deterministic small-world network models: the deterministic small-world network created by edge iterations, the tree-structured deterministic small-world network, and the small-world network derived from the deterministic uniform recursive tree. Detailed experiments are carried out to test the search efficiency of various small-world networks with regard to three different types of random walks. From the results, we conclude that the stochastic model outperforms the deterministic ones in terms of average search steps.