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.
Type de document :
Rapport
[Research Report] RR-8581, Inria. 2015, pp.15
Liste complète des métadonnées

https://hal.inria.fr/hal-01055893
Contributeur : Konstantin Avrachenkov <>
Soumis le : jeudi 9 mars 2017 - 19:33:57
Dernière modification le : jeudi 20 avril 2017 - 14:17:50

Fichiers

RR8581/RR-8581.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

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. 2015, pp.15. <hal-01055893v3>

Partager

Métriques

Consultations de
la notice

177

Téléchargements du document

16