Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Robustness of Spatial Preferential Attachment Networks Read chapter Read first chapter

2015 | OriginalPaper | Chapter

The Robot Crawler Number of a Graph

Authors : Anthony Bonato, Rita M. del Río-Chanona, Calum MacRury, Jake Nicolaidis, Xavier Pérez-Giménez, Paweł Prałat, Kirill Ternovsky

Published in: Algorithms and Models for the Web Graph

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Information gathering by crawlers on the web is of practical interest. We consider a simplified model for crawling complex networks such as the web graph, which is a variation of the robot vacuum edge-cleaning process of Messinger and Nowakowski. In our model, a crawler visits nodes via a deterministic walk determined by their weightings which change during the process deterministically. The minimum, maximum, and average time for the robot crawler to visit all the nodes of a graph is considered on various graph classes such as trees, multi-partite graphs, binomial random graphs, and graphs generated by the preferential attachment model.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Note on Modeling Retweet Cascades on Twitter
next chapter PageRank in Undirected Random Graphs
Literature
1.
Aiello, W., Bonato, A., Cooper, C., Janssen, J., Prałat, P.: A spatial web graph model with local influence regions. Internet Math. 5, 175–196 (2009)CrossRef
2.
3.
Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem. Princeton University Press, Princeton (2007)
4.
5.
6.
Bollobás, B., Riordan, O., Spencer, J., Tusnády, G.: The degree sequence of a scale-free random graph process. Random Struct. Algorithms 18, 279–290 (2001)CrossRefMATH
7.
8.
Bonato, A., Nowakowski, R.J.: The Game of Cops and Robbers on Graphs. American Mathematical Society, Providence (2011)CrossRefMATH
9.
Bradonjić, M., Hagberg, A., Percus, A.: The structure of geographical threshold graphs. Internet Math. 5, 113–140 (2008)CrossRefMathSciNet
10.
Brin, S., Page, L.: Anatomy of a large-scale hypertextual web search engine. In: Proceedings of the 7th International World Wide Web Conference (1998)
11.
Chung, F., Lu, L.: Complex Graphs and Networks. American Mathematical Society, Boston (2006)CrossRefMATH
12.
Cooper, C., Frieze, A., Prałat, P.: Some typical properties of the spatial preferred attachment model. Internet Math. 10, 27–47 (2014)
13.
Cooper, C., Ilcinkas, D., Klasing, R., Kosowski, A.: Derandomizing random walks in undirected graphs using locally fair exploration strategies. Distributed Comput. 24, 91–99 (2011)CrossRefMATH
14.
Cooper, C., Prałat, P.: Scale free graphs of increasing degree. Random Struct. Algorithms 38, 396–421 (2011)CrossRefMATH
15.
16.
17.
18.
Koenig, S., Szymanski, B., Liu, Y.: Efficient and inefficient ant coverage methods. Ann. Math. Artif. Intell. 31, 41–76 (2001)CrossRef
19.
Komlós, J., Szemerédi, E.: Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete Math. 43(1), 55–63 (1983)CrossRefMathSciNetMATH
20.
Li, Z., Vetta, A.: Bounds on the cleaning times of robot vacuums. Oper. Res. Lett. 38(1), 69–71 (2010)CrossRefMATH
21.
Malpani, N., Chen, Y., Vaidya, N.H., Welch, J.L.: Distributed token circulation in mobile ad hoc networks. IEEE Trans. Mob. Comput. 4, 154–165 (2005)CrossRef
22.
Manning, C.D., Raghavan, P., Schütze, H.: Introduction to Information Retrieval. Cambridge University Press, New York (2008)CrossRefMATH
23.
24.
Messinger, M.E., Nowakowski, R.J., Prałat, P.: Cleaning a network with brushes. Theor. Comput. Sci. 399, 191–205 (2008)CrossRefMATH
25.
Olston, C., Najork, M.: Web crawling. Found. Trends Inform. Retrieval 4(3), 175–246 (2010)CrossRefMATH
26.
Pittel, B.: Note on the heights of random recursive trees and random \(m\)-ary search trees. Random Struct. Algorithms 5, 337–347 (1994)CrossRefMathSciNetMATH
27.
Wagner, I.A., Lindenbaum, M., Bruckstein, A.M.: Efficiently searching a graph by a smell-oriented vertex process. Ann. Math. Artif. Intell. 24, 211–223 (1998)CrossRefMathSciNetMATH
28.
West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)
29.
Yanovski, V., Wagner, I.A., Bruckstein, A.M.: A distributed ant algorithm for efficiently patrolling a network. Algorithmica 37, 165–186 (2003)CrossRefMathSciNetMATH
Metadata
Title
The Robot Crawler Number of a Graph
Authors
Anthony Bonato
Rita M. del Río-Chanona
Calum MacRury
Jake Nicolaidis
Xavier Pérez-Giménez
Paweł Prałat
Kirill Ternovsky
Copyright Year
2015
Book
Algorithms and Models for the Web Graph

Print ISBN: 978-3-319-26783-8

Electronic ISBN: 978-3-319-26784-5

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26784-5_11

Premium Partner

    Image Credits