Ants: Agents on networks, trees, and subgraphs

Efficient exploration of large networks is a central issue in data mining a nd network maintenance applications. In most existing work there is a disti nction between the active 'searcher' which both executes the algorithm and holds the memory and the passive 'searched graph' over which the searcher h as no control at all. Large dynamic networks like the Internet, where the n odes are powerful computers and the links have narrow bandwidth and are hea vily-loaded, call for a different paradigm, in which a noncentralized group of one or more lightweight autonomous agents traverse the network in a com pletely distributed and parallelizable way. Potential advantages of such a paradigm would be fault tolerance against network and agent failures, and r educed load on the busy nodes due to the small amount of memory and computi ng resources required by the agent in each node. Algorithms for network cov ering based on this paradigm could be used in today's Internet as a support for data mining and network control algorithms. Recently, a vertex ant wal k (VAW) method has been suggested [I.A. Wagner, M. Lindenbaum, A.M. Bruckst ein, Ann. Math. Artificial Intelligence 24 (1998) 211-223] for searching an undirected, connected graph by an a(ge)nt that walks along the edges of th e graph, occasionally leaving 'pheromone' traces at nodes, and using those traces to guide its exploration. It was shown there that the ant can cover a static graph within time nd, where n is the number of vertices and d the diameter of the graph. In this work we further investigate the performance of the VAW method on dynamic graphs, where edges may appear or disappear du ring the search process. In particular we prove that (a) if a certain spann ing subgraph S is stable during the period of covering, then the VAW method is guaranteed to cover the graph within time nd,, where d, is the diameter of S, and (b) if a failure occurs on each edge with probability p, then th e expected cover time is bounded from above by nd((log Delta/log(1/p)) + (( 1 + p)/(1 - p))), where Delta is the maximum vertex degree in the graph. We also show that (c) if G is a static tree then it is covered within time 2n . (C) 2000 Elsevier Science B.V. All rights reserved.