Diffusive capture processes for information search

Sungmin Lee; Soon Hyung Yook; Yup Kim

doi:10.1016/j.physa.2007.07.022

Diffusive capture processes for information search

Sungmin Lee, Soon Hyung Yook, Yup Kim

Research output: Contribution to journal › Article › peer-review

17 Citations (Scopus)

Abstract

We show how effectively the diffusive capture processes (DCP) on complex networks can be applied to information search in the networks. Numerical simulations show that our method generates only 2 % of traffic compared with the most popular flooding-based query-packet-forwarding (FB) algorithm. We find that the average searching time, 〈 T 〉, of the our model is more scalable than another well known n-random walker model and comparable to the FB algorithm both on real Gnutella network and scale-free networks with γ = 2.4. We also discuss the possible relationship between 〈 T 〉 and 〈 k² 〉, the second moment of the degree distribution of the networks.

Original language	English
Pages (from-to)	743-749
Number of pages	7
Journal	Physica A: Statistical Mechanics and its Applications
Volume	385
Issue number	2
DOIs	https://doi.org/10.1016/j.physa.2007.07.022
Publication status	Published - 15 Nov 2007

Bibliographical note

Funding Information:
We thank to Drs. Kwon and Yoon for useful discussions. This work is supported by Korea Research Foundation Grant no. KRF-2004-015-C00185 and Grants nos. R01-2006-000-10470-0 and F01-2006-000-10093-0 from the Basic Research Program of the Korea Science & Engineering Foundation.

Keywords

Complex networks
Internet
Random walks

Access to Document

10.1016/j.physa.2007.07.022

Cite this

@article{55daa49e19fb449fbebb55c5697cbe58,

title = "Diffusive capture processes for information search",

abstract = "We show how effectively the diffusive capture processes (DCP) on complex networks can be applied to information search in the networks. Numerical simulations show that our method generates only 2 % of traffic compared with the most popular flooding-based query-packet-forwarding (FB) algorithm. We find that the average searching time, 〈 T 〉, of the our model is more scalable than another well known n-random walker model and comparable to the FB algorithm both on real Gnutella network and scale-free networks with γ = 2.4. We also discuss the possible relationship between 〈 T 〉 and 〈 k2 〉, the second moment of the degree distribution of the networks.",

keywords = "Complex networks, Internet, Random walks",

author = "Sungmin Lee and Yook, {Soon Hyung} and Yup Kim",

note = "Funding Information: We thank to Drs. Kwon and Yoon for useful discussions. This work is supported by Korea Research Foundation Grant no. KRF-2004-015-C00185 and Grants nos. R01-2006-000-10470-0 and F01-2006-000-10093-0 from the Basic Research Program of the Korea Science & Engineering Foundation. ",

year = "2007",

month = nov,

day = "15",

doi = "10.1016/j.physa.2007.07.022",

language = "English",

volume = "385",

pages = "743--749",

journal = "Physica A: Statistical Mechanics and its Applications",

issn = "0378-4371",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Diffusive capture processes for information search

AU - Lee, Sungmin

AU - Yook, Soon Hyung

AU - Kim, Yup

N1 - Funding Information: We thank to Drs. Kwon and Yoon for useful discussions. This work is supported by Korea Research Foundation Grant no. KRF-2004-015-C00185 and Grants nos. R01-2006-000-10470-0 and F01-2006-000-10093-0 from the Basic Research Program of the Korea Science & Engineering Foundation.

PY - 2007/11/15

Y1 - 2007/11/15

N2 - We show how effectively the diffusive capture processes (DCP) on complex networks can be applied to information search in the networks. Numerical simulations show that our method generates only 2 % of traffic compared with the most popular flooding-based query-packet-forwarding (FB) algorithm. We find that the average searching time, 〈 T 〉, of the our model is more scalable than another well known n-random walker model and comparable to the FB algorithm both on real Gnutella network and scale-free networks with γ = 2.4. We also discuss the possible relationship between 〈 T 〉 and 〈 k2 〉, the second moment of the degree distribution of the networks.

AB - We show how effectively the diffusive capture processes (DCP) on complex networks can be applied to information search in the networks. Numerical simulations show that our method generates only 2 % of traffic compared with the most popular flooding-based query-packet-forwarding (FB) algorithm. We find that the average searching time, 〈 T 〉, of the our model is more scalable than another well known n-random walker model and comparable to the FB algorithm both on real Gnutella network and scale-free networks with γ = 2.4. We also discuss the possible relationship between 〈 T 〉 and 〈 k2 〉, the second moment of the degree distribution of the networks.

KW - Complex networks

KW - Internet

KW - Random walks

UR - http://www.scopus.com/inward/record.url?scp=34548729143&partnerID=8YFLogxK

U2 - 10.1016/j.physa.2007.07.022

DO - 10.1016/j.physa.2007.07.022

M3 - Article

AN - SCOPUS:34548729143

SN - 0378-4371

VL - 385

SP - 743

EP - 749

JO - Physica A: Statistical Mechanics and its Applications

JF - Physica A: Statistical Mechanics and its Applications

IS - 2

ER -

Diffusive capture processes for information search

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this