A generic search strategy for large-scale real-world networks

ABSTRACT

We consider the following situation for a given large-scale network: Starting from an initial node we move to its neighbor node and repeat that until reaching a target node. How fast can we do this without any global topological information? This problem is considered "searching networks", and several approaches have been proposed. In this paper, we present a general framework of search strategies, under which all of these existing approaches can be formalized. Our framework characterizes random search strategies by the following three parameters: memory for previously-visited nodes, look-ahead property and transition probability. Through computational simulations for large-scale networks with small-worldness and scale-freeness, we investigate the relationship between the effect of parameters of the strategies and the coefficients of networks such as the clustering coefficient. The comparison result provides a guideline to obtain good parameters of the strategies according to the diameter and the clustering coefficients of networks.

REFERENCES

• 1: R. Albert, H. Jeong and A.-L. Barabási, "The diameter of the world-wide web," Nature, Vol. 401, 130--131, 1999.
• 2: D. J. Aldous, "On the time taken by random walks on finite groups to visit every state," Z. Wahrsch. verw. Gebiete 62, 361--393, 1983.
• 3: R. Albert and A.-L. Barabási, "Statistical Mechanics of Complex Networks," Reviews Of Modern Physics, Vol. 74, 47--97, 2002.
• 4: L. A. N. Amaral, A. Scala, M. Barthélé and H. E. Stanley, "Classes of small-world networks," Proceeding of The National Academy of Sciences, Vol. 97, 11149--11152, 2000.
• 5: A.-L. Barabási, R. Albert and H. Jeong, "Mean-field theory for scale-free random networks," Physica A, Vol. 272, 173--187, 1999.
• 6: G. Brightwell and P. Winkler, "Maximum Hitting Time for Random Walks on Graphs," J. Random Structures and Algorithms, Vol. 3, 263--276, 1990.
• 7: H. Ebel, L.-I. Mielsch and S. Bornhold, "Scale-free topology of e-mail networks," Pysical Review E, Vol. 66, 1--4, 2002.
• 8: P. Erdős and A. Rényi, "On random graphs," Publ. Math. Debrecen, 6:290--297, 1959.
• 9: P. Erdős and A. Rényi, "On the Evolution of random graphs," Publ. Math. Inst. Hung. Acad. Sci., Vol. 5, 17--61, 1960.
• 10: Uriel Feige, A tight upper bound on the cover time for random walks on graphs, Random Structures & Algorithms, v.6 n.1, p.51-54, Jan. 1995 [doi>10.1002/rsa.3240060106]
• 11: C. P. Herrero, "Self-avoiding walks on scale-free networks," Physical Review E, Vol. 71, 1--8, 2005.
• 12: S. Ikeda, I. Kubo and M. Yamashita, "Reducing the Hitting and the Cover Times of Random Walks on Finite Graphs by Local Topological Information," Proceedings of The 2003 International Conference on VLSI, 203--207, 2003.
• 13: H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai and A. L. Barabási, "The large-scale organization of metabolic networks," Nature, Vol. 407, 651--654, 2000.
• 14: B. I. Kim, C. N. Yoon, S. K. Han and H. Jeong, "Path finding strategies in scale-free networks," Physical Review E, Vol. 65, 1--4, 2002.
• 15: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 16: S. Render, "How popular is your paper? An emprical study of the citation distribution," Eur. Phys. J.B, Vol. 4, 131--134, 1998.
• 17: Toby Walsh, Search in a Small World, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1172-1177, July 31-August 06, 1999
• 18: D. J. Watts and S. H. Strogatz, "Collective dynamics of small-world networks," Nature, Vol. 393, 440--442, 1998.
• 19: S. Yang, "Exploring complex networks by walking on them," Physical Review E, Vol. 71, 1--5, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Design