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 - http://www.scopus.com/inward/record.url?scp=85069884972&partnerID=8YFLogxK

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 -