Published April 8, 2019
| Version v1
Conference paper
On the Escape Probability Estimation in Large Graphs
- Others:
- Network Engineering and Operations (NEO ) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
- Institute of Applied Mathematical Research [Petrozavodsk] ; Russian Academy of Sciences [Moscow] (RAS)-Petrozavodsk State University [Petrozavodsk]
Description
We consider the large graphs as the object of study and deal with the problem of escape probability estimation. Generally, the required characteristic cannot be calculated analytically and even numerically due to the complexity and large size of the investigation object. The purpose of this paper is to offer the effective method for estimating the probability that the random walk on graph first enters a node b before returning into starting node a. Regenerative properties of the random walk allow using an accelerated method for the cycles simulation based on the splitting technique. The results of numerical experiments confirm the advantages of the proposed method.
Abstract
International audience
Additional details
- URL
- https://hal.inria.fr/hal-02413569
- URN
- urn:oai:HAL:hal-02413569v1
- Origin repository
- UNICA