For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2013/05/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Information Network
complex networks, small-world networks, random walks, search efficiency,
Full Text: PDF>>
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.