The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs

A. Davidson; A. Ganesh

doi:10.1007/978-3-030-25070-6_5

The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs

A. Davidson^*
, A. Ganesh

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

Abstract

Web crawlers are used by internet search engines to gather information about the web graph. In this paper we investigate a simple process which models such software by walking around the vertices of a graph. Once initial random vertex weights have been assigned, the robot crawler traverses the graph deterministically following a greedy algorithm, always visiting the neighbour of least weight and then updating this weight to be the highest overall. We consider the maximum, minimum and average number of steps taken by the crawler to visit every vertex of firstly, sparse Erdős-Rényi random graphs and secondly, complete k-partite graphs. Our work is closely related to a paper of Bonato et al. who introduced the model.

Original language	English
Title of host publication	Algorithms and Models for the Web Graph - 16th International Workshop, WAW 2019, Proceedings
Editors	Konstantin Avrachenkov, Paweł Prałat, Nan Ye
Publisher	Springer Verlag
Pages	57-70
Number of pages	14
ISBN (Print)	9783030250690
DOIs	https://doi.org/10.1007/978-3-030-25070-6_5
Publication status	Published - 4 Jul 2019
Event	16th International Workshop on Algorithms and Models for the Web Graph, WAW 2019 - Brisbane, Australia Duration: 6 Jul 2019 → 7 Jul 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11631 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Workshop on Algorithms and Models for the Web Graph, WAW 2019
Country/Territory	Australia
City	Brisbane
Period	6/07/19 → 7/07/19

Keywords

random graphs, web crawlers

Access to Document

10.1007/978-3-030-25070-6_5

Handle.net

Persistent link

Cite this

Davidson, A., & Ganesh, A. (2019). The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs. In K. Avrachenkov, P. Prałat, & N. Ye (Eds.), Algorithms and Models for the Web Graph - 16th International Workshop, WAW 2019, Proceedings (pp. 57-70). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11631 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-25070-6_5

Davidson, A. ; Ganesh, A. / The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs. Algorithms and Models for the Web Graph - 16th International Workshop, WAW 2019, Proceedings. editor / Konstantin Avrachenkov ; Paweł Prałat ; Nan Ye. Springer Verlag, 2019. pp. 57-70 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{46420398d35348009691cb557eb4df20,

title = "The Robot Crawler Model on Complete k-Partite and Erd{\H o}s-R{\'e}nyi Random Graphs",

abstract = "Web crawlers are used by internet search engines to gather information about the web graph. In this paper we investigate a simple process which models such software by walking around the vertices of a graph. Once initial random vertex weights have been assigned, the robot crawler traverses the graph deterministically following a greedy algorithm, always visiting the neighbour of least weight and then updating this weight to be the highest overall. We consider the maximum, minimum and average number of steps taken by the crawler to visit every vertex of firstly, sparse Erd{\H o}s-R{\'e}nyi random graphs and secondly, complete k-partite graphs. Our work is closely related to a paper of Bonato et al. who introduced the model.",

keywords = "random graphs, web crawlers",

author = "A. Davidson and A. Ganesh",

year = "2019",

month = jul,

day = "4",

doi = "10.1007/978-3-030-25070-6\_5",

language = "English",

isbn = "9783030250690",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "57--70",

editor = "Konstantin Avrachenkov and Pawe{\l} Pra{\l}at and Nan Ye",

booktitle = "Algorithms and Models for the Web Graph - 16th International Workshop, WAW 2019, Proceedings",

address = "Germany",

note = "16th International Workshop on Algorithms and Models for the Web Graph, WAW 2019 ; Conference date: 06-07-2019 Through 07-07-2019",

}

Davidson, A & Ganesh, A 2019, The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs. in K Avrachenkov, P Prałat & N Ye (eds), Algorithms and Models for the Web Graph - 16th International Workshop, WAW 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11631 LNCS, Springer Verlag, pp. 57-70, 16th International Workshop on Algorithms and Models for the Web Graph, WAW 2019, Brisbane, Australia, 6/07/19. https://doi.org/10.1007/978-3-030-25070-6_5

The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs. / Davidson, A.; Ganesh, A.
Algorithms and Models for the Web Graph - 16th International Workshop, WAW 2019, Proceedings. ed. / Konstantin Avrachenkov; Paweł Prałat; Nan Ye. Springer Verlag, 2019. p. 57-70 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11631 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs

AU - Davidson, A.

AU - Ganesh, A.

PY - 2019/7/4

Y1 - 2019/7/4

N2 - Web crawlers are used by internet search engines to gather information about the web graph. In this paper we investigate a simple process which models such software by walking around the vertices of a graph. Once initial random vertex weights have been assigned, the robot crawler traverses the graph deterministically following a greedy algorithm, always visiting the neighbour of least weight and then updating this weight to be the highest overall. We consider the maximum, minimum and average number of steps taken by the crawler to visit every vertex of firstly, sparse Erdős-Rényi random graphs and secondly, complete k-partite graphs. Our work is closely related to a paper of Bonato et al. who introduced the model.

AB - Web crawlers are used by internet search engines to gather information about the web graph. In this paper we investigate a simple process which models such software by walking around the vertices of a graph. Once initial random vertex weights have been assigned, the robot crawler traverses the graph deterministically following a greedy algorithm, always visiting the neighbour of least weight and then updating this weight to be the highest overall. We consider the maximum, minimum and average number of steps taken by the crawler to visit every vertex of firstly, sparse Erdős-Rényi random graphs and secondly, complete k-partite graphs. Our work is closely related to a paper of Bonato et al. who introduced the model.

KW - random graphs, web crawlers

UR - https://www.scopus.com/pages/publications/85069884972

U2 - 10.1007/978-3-030-25070-6_5

DO - 10.1007/978-3-030-25070-6_5

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85069884972

SN - 9783030250690

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 57

EP - 70

BT - Algorithms and Models for the Web Graph - 16th International Workshop, WAW 2019, Proceedings

A2 - Avrachenkov, Konstantin

A2 - Prałat, Paweł

A2 - Ye, Nan

PB - Springer Verlag

T2 - 16th International Workshop on Algorithms and Models for the Web Graph, WAW 2019

Y2 - 6 July 2019 through 7 July 2019

ER -

Davidson A, Ganesh A. The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs. In Avrachenkov K, Prałat P, Ye N, editors, Algorithms and Models for the Web Graph - 16th International Workshop, WAW 2019, Proceedings. Springer Verlag. 2019. p. 57-70. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-25070-6_5

The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this