Volume 92, Number 5, December 2010
|Number of page(s)||6|
|Published online||23 December 2010|
Network discovery by generalized random walks
Department of Physics and Interdisciplinary Center for Network Science and Applications (iCeNSA), University of Notre Dame - Notre Dame, IN 46556, USA
2 Department of Computer Science and Department of Physics, Rensselaer Polytechnic Polytechnic Institute 110 8 th Street, Troy, NY 12180-3590, USA
Accepted: 17 November 2010
We investigate network exploration by random walks defined via stationary and adaptive transition probabilities on large graphs. We derive an exact formula valid for arbitrary graphs and arbitrary walks with stationary transition probabilities (STP), for the average number of discovered edges as a function of time. We show that for STP walks site and edge exploration obey the same scaling ∼nλ as a function of time n. Therefore, edge exploration on graphs with many loops is always lagging compared to site exploration, the revealed graph being sparse until almost all nodes have been discovered. We then introduce the edge explorer model (EEM), which presents a novel class of adaptive walks, that perform faithful network discovery even on dense networks.
PACS: 05.40.-a – Fluctuation phenomena, random processes, noise, and Brownian motion / 89.75.-k – Complex systems / 89.75.Hc – Networks and genealogical trees
© EPLA, 2010
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.