On the Escape Probability Estimation in Large Graphs
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
FRUCT
2019-04-01
|
| Series: | Proceedings of the XXth Conference of Open Innovations Association FRUCT |
| Subjects: | |
| Online Access: | https://fruct.org/publications/fruct24/files/Avr.pdf
|
| _version_ | 1819056639086428160 |
|---|---|
| author | Konstantin Avrachenkov Alexandra Borodina |
| author_facet | Konstantin Avrachenkov Alexandra Borodina |
| author_sort | Konstantin Avrachenkov |
| collection | DOAJ |
| 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 фЂ‚їrst 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. |
| first_indexed | 2024-12-21T13:26:36Z |
| format | Article |
| id | doaj.art-40be09f0d4854f068a3846735ca3b8cf |
| institution | Directory Open Access Journal |
| issn | 2305-7254 2343-0737 |
| language | English |
| last_indexed | 2024-12-21T13:26:36Z |
| publishDate | 2019-04-01 |
| publisher | FRUCT |
| record_format | Article |
| series | Proceedings of the XXth Conference of Open Innovations Association FRUCT |
| spelling | doaj.art-40be09f0d4854f068a3846735ca3b8cf2022-12-21T19:02:26ZengFRUCTProceedings of the XXth Conference of Open Innovations Association FRUCT2305-72542343-07372019-04-01854242430On the Escape Probability Estimation in Large GraphsKonstantin Avrachenkov0Alexandra Borodina1Inria, Sophia, Antipolis, FrancePetrozavodsk State University, Institute of Applied Mathematical Research of the Karelian Research Centre of RAS, Petrozavodsk, RussiaWe 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 фЂ‚їrst 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.https://fruct.org/publications/fruct24/files/Avr.pdf escape probabilitylarge graphsMonte Carlo methodregenerative simulationsplitting method |
| spellingShingle | Konstantin Avrachenkov Alexandra Borodina On the Escape Probability Estimation in Large Graphs Proceedings of the XXth Conference of Open Innovations Association FRUCT escape probability large graphs Monte Carlo method regenerative simulation splitting method |
| title | On the Escape Probability Estimation in Large Graphs |
| title_full | On the Escape Probability Estimation in Large Graphs |
| title_fullStr | On the Escape Probability Estimation in Large Graphs |
| title_full_unstemmed | On the Escape Probability Estimation in Large Graphs |
| title_short | On the Escape Probability Estimation in Large Graphs |
| title_sort | on the escape probability estimation in large graphs |
| topic | escape probability large graphs Monte Carlo method regenerative simulation splitting method |
| url | https://fruct.org/publications/fruct24/files/Avr.pdf
|
| work_keys_str_mv | AT konstantinavrachenkov ontheescapeprobabilityestimationinlargegraphs AT alexandraborodina ontheescapeprobabilityestimationinlargegraphs |