Abstract
Scale-free networks naturally model wide area networks like the WWW. We consider the problem of fast exploration of huge scale-free networks using small memory space. Although there are many search algorithms for exploring an unknown graph, they require much space or time. For example, the depth first search requires some memory for all the nodes in the worst case, and the average number of steps in the random walk is O(n 3), where n is the size of the graph. Under assumptions reflecting WWW applications, we propose a new exploration paradigm called forest search particularly designed for scale-free networks, and theoretically evaluate its space complexity. We also demonstrate its superiority over random walk based search algorithms by conducting simulations.
This research partly received financial support from Scientific research fund of ministry of Education, Culture, Sports, Science and Technology.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albert, R., Barabási, A.-L.: Statistical Mechanics of Complex Networks. Reviews Of Modern Physics 74, 47–97 (2002)
Amaral, L.A.N., Scala, A., Barthélé, M., Stanley, H.E.: Classes of small-world networks. Proceeding of The National Academy of Sciences 97, 11149–11152 (2000)
Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Applied Mathematics 65, 21–46 (1996)
Barabási, A.-L., Albert, R., Jeong, H.: Mean-field theory for scale-free random networks. Physica A 272, 173–187 (1999)
Bollobás, B., Riordan, O.: The degree sequence of a scale-free random graph process. Random Structure and Algorithms 18, 279–290 (2001)
Bollobas, B., Riordan, O.: The diameter of a scale-free random graph. Combinatorica 24, 5–34 (2004)
Brightwell, G., Winkler, P.: Maximum Hitting Time for Random Walks on Graphs. J. Random Structures and Algorithms 3, 263–276 (1990)
Ebel, H., Mielsch, L.-I., Bornholdt, S.: Scale-free topology of e-mail networks. Pysical Review E 66, 1–4 (2002)
Erdős, P., Rényi, A.: On random graphs. Publ. Math. Debrecen 6, 290–297 (1959)
Feige, U.: A tight upper bound on the cover time for random walks on graphs. J. Random Structures and Algorithms 6, 51–54 (1995)
Flocchini, P., Mans, B., Santoro, N.: On the Impact of Sense of Direction on Message Complexity. Inf. Process. Lett. 63(1), 23–31 (1997)
Fraigniaud, P., Gavoille, C., Mans, B.: Interval routing schemes allow broadcasting with linear message-complexity. Distributed Computing 14(4), 217–229 (2001)
Ikeda, S., Kubo, I., Yamashita, M.: Reducing the Hitting and the Cover Times of Random Walks on Finite Graphs by Local Topological Information. In: Proceedings of The 2003 International Conference on VLSI, pp. 203–207 (2003)
Kurumida, Y., Ogata, T., Ono, H., Sadakane, K., Yamashita, M.: A Generic Search Strategy for Large Scale Real World Networks. In: Proc. of the 1st International Conference on Scalable Information Systems. ACM, Digital Library (2006)
Panaite, P., Pelc, A.: Impact of topographic information on graph exploration efficiency. Networks 36(2), 96–103 (2000)
Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393, 440–442 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kurumida, Y., Ono, H., Sadakane, K., Yamashita, M. (2006). Forest Search: A Paradigm for Faster Exploration of Scale-Free Networks. In: Guo, M., Yang, L.T., Di Martino, B., Zima, H.P., Dongarra, J., Tang, F. (eds) Parallel and Distributed Processing and Applications. ISPA 2006. Lecture Notes in Computer Science, vol 4330. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11946441_9
Download citation
DOI: https://doi.org/10.1007/11946441_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68067-3
Online ISBN: 978-3-540-68070-3
eBook Packages: Computer ScienceComputer Science (R0)