Skip to Main content Skip to Navigation
Conference papers

On the Escape Probability Estimation in Large Graphs

Abstract : 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.
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-02413569
Contributor : Konstantin Avrachenkov Connect in order to contact the contributor
Submitted on : Monday, December 16, 2019 - 11:37:37 AM
Last modification on : Tuesday, November 17, 2020 - 12:10:13 PM
Long-term archiving on: : Tuesday, March 17, 2020 - 6:44:46 PM

File

EscapeProb2019paper.pdf
Files produced by the author(s)

Identifiers

Collections

`

Citation

Konstantin Avrachenkov, Alexandra Borodina. On the Escape Probability Estimation in Large Graphs. IEEE FRUCT 2019 - 24th Conference of Open Innovations Association FRUCT, Apr 2019, Moscow, Russia. ⟨10.23919/FRUCT.2019.8711919⟩. ⟨hal-02413569⟩

Share

Metrics

Record views

81

Files downloads

363