The robot crawler graph process
| Autor: | Anthony Bonato, Rita María del Río-Chanona, Xavier Pérez-Giménez, Paweł Prałat, Kirill Ternovsky, Jake Nicolaidis, Calum MacRury |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Random graph
Theoretical computer science Computer Science::Information Retrieval Applied Mathematics 0102 computer and information sciences 02 engineering and technology Complex network Crawling Preferential attachment Computer Science::Digital Libraries 01 natural sciences Graph 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Robot 020201 artificial intelligence & image processing Web crawler MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Applied Mathematics. 247:23-36 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2018.01.018 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect