Random Walks on Stochastic and Deterministic Small-World Networks

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

doi:10.1587/transinf.E96.D.1215

Random Walks on Stochastic and Deterministic Small-World Networks

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

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.5 pp.1215-1218

Publication Date: 2013/05/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.1215

Type of Manuscript: LETTER

Category: Information Network

Cite this

Copy

Zi-Yi WANG, Shi-Ze GUO, Zhe-Ming LU, Guang-Hua SONG, Hui LI, "Random Walks on Stochastic and Deterministic Small-World Networks" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 5, pp. 1215-1218, May 2013, doi: 10.1587/transinf.E96.D.1215.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.1215/_p

Copy

@ARTICLE{e96-d_5_1215,
author={Zi-Yi WANG, Shi-Ze GUO, Zhe-Ming LU, Guang-Hua SONG, Hui LI, },
journal={IEICE TRANSACTIONS on Information},
title={Random Walks on Stochastic and Deterministic Small-World Networks},
year={2013},
volume={E96-D},
number={5},
pages={1215-1218},
abstract={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.},
keywords={},
doi={10.1587/transinf.E96.D.1215},
ISSN={1745-1361},
month={May},}

Copy

TY - JOUR
TI - Random Walks on Stochastic and Deterministic Small-World Networks
T2 - IEICE TRANSACTIONS on Information
SP - 1215
EP - 1218
AU - Zi-Yi WANG
AU - Shi-Ze GUO
AU - Zhe-Ming LU
AU - Guang-Hua SONG
AU - Hui LI
PY - 2013
DO - 10.1587/transinf.E96.D.1215
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2013
AB - 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.
ER -