Skip to Main content Skip to Navigation
Reports

Hitting Times in Markov Chains with Restart and their Application to Network Centrality

Konstantin Avrachenkov 1 Alexey Piunovskiy 2 Yi Zhang 3
1 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
3 imagine - Extraction de Caractéristiques et Identification
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Résumé : Motivé par diverses applications provenant de télécommunications, informatique et de la physique, nous considérons un processus générale de Markov dans l'espace de Borel avec une possibilité de redémarrage. A chaque étape, avec une probabilité le processus redémarre a partir d'une distribution donnée et avec la probabilité complémentaire le processus continue l'évolution selon une noyau de Markov. Nous étudions l'espérance du temps de premier passage à l'ensemble donné. Nous obtenons une formule explicite pour l'espérance du temps de premier passage et démontrons que le processus avec redémarrage est Harris positif récurrent. Ensuite, nous établissons que les assertions suivantes sont équivalentes : (a) le fait d'être limité (par rapport à l'état initiale) de l'espérance du temps de premier passage; (b) la finitude de l'espérance du temps de premier passage pour presque tous les états initiaux par rapport à la probabilité invariante unique; et, (c) l'ensemble cible est de mesure positive par rapport à la probabilité invariante. Enfin, nous illustrons nos résultats théoriques avec deux exemples dans les espaces dénombrables et non dénombrables et avec l'application à la mesure de centralité de réseau.
Complete list of metadatas

https://hal.inria.fr/hal-01055893
Contributor : Konstantin Avrachenkov <>
Submitted on : Thursday, March 9, 2017 - 7:33:57 PM
Last modification on : Wednesday, July 8, 2020 - 12:43:36 PM
Document(s) archivé(s) le : Saturday, June 10, 2017 - 3:31:30 PM

Files

RR8581/RR-8581.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01055893, version 3
  • ARXIV : 1503.08548

Citation

Konstantin Avrachenkov, Alexey Piunovskiy, Yi Zhang. Hitting Times in Markov Chains with Restart and their Application to Network Centrality. [Research Report] RR-8581, Inria. 2017, pp.15. ⟨hal-01055893v3⟩

Share

Metrics

Record views

504

Files downloads

604