Accès chercheur

EEDIS Laboratory

Evolutionary Engineering

and

Distributed Information Systems

Réseaux et Communication

Sécurité et Multimédia

Ingénierie des Connaissances

Data Mining & Web Intelligent

Interopérabilité des Systèmes d’information
& Bases de données

Développement Orienté Service

Characterization of random walks on space of unordered trees using efficient metric simulation


Auteurs:	» BEN-NAOUM Farah » Christophe GODIN » Romain AZAIS
Type :	Revue Internationale
Nom du journal :	Discrete Applied Mathematics ISSN: 0166-218X
Volume : 341	Issue:	Pages: 290-307
Lien : » https://doi.org/10.1016/j.dam.2023.07.028
Publié le :	04-09-2023

The simple random walk on Zp shows two drastically different behaviors depending on

the value of p: it is recurrent when p ? {1, 2} while it escapes (with a rate increasing

with p) as soon as p ? 3. This classical example illustrates that the asymptotic properties

of a random walk provides some information on the structure of its state space. This

paper aims to explore analogous questions on space made up of combinatorial objects

with no algebraic structure. We take as a model for this problem the space of unordered

unlabeled rooted trees endowed with Zhang edit distance. To this end, it defines

the canonical unbiased random walk on the space of trees and provides an efficient

algorithm to evaluate its escape rate. Compared to Zhang algorithm, it is incremental

and computes the edit distance along the random walk approximately 100 times faster

on trees of size 500 on average. The escape rate of the random walk on trees is precisely

estimated using intensive numerical simulations, out of reasonable reach without the

incremental algorithm.