Centralite du second ordre : Calcul distribue de l'importance de noeuds

Anne-Marie Kermarrec 1 Erwan Le Merrer 1 Bruno Sericola 2 Gilles Tredan 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
2 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
Inria Rennes – Bretagne Atlantique , IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
Résumé : Dans le contexte de la théorie des graphes pour les réseaux sociaux, la notion de centralité a été introduite pour mesurer l'importance relative de noeuds dans une topologie donnée. Connaître cette importance est un enjeu majeur pour assurer la robustesse des systèmes distribués. De nombreuses formes de centralités ont déjà été définies; dans le contexte des systèmes distribués, elles sont cependant soit d'un intérêt limité (centralité des degrés), soit difficilement distribuables (centralité d'intermédiarité). Dans cet article, nous introduisons une nouvelle forme de centralité: la centralité du second ordre. Celle-ci est calculée de façon totalement distribuée, au moyen d'une marche aléatoire. Elle attribue à chaque noeud une valeur indicatrice de son importance dans le graphe. Pour cela, chaque noeud conserve les temps écoulés entre deux visites de la marche et calcule l'écart type de ces temps. Nous montrons que cet écart type est une mesure de centralité qui permet également de caractériser globalement la topologie d'un graphe donné.
Type de document :
Communication dans un congrès
Chaintreau, Augustin and Magnien, Clemence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00384426
Contributeur : Gilles Tredan <>
Soumis le : vendredi 15 mai 2009 - 10:56:40
Dernière modification le : mercredi 16 mai 2018 - 11:23:18
Document(s) archivé(s) le : jeudi 10 juin 2010 - 21:25:50

Fichier

algotel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00384426, version 1

Citation

Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Tredan. Centralite du second ordre : Calcul distribue de l'importance de noeuds. Chaintreau, Augustin and Magnien, Clemence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009. 〈inria-00384426〉

Partager

Métriques

Consultations de la notice

533

Téléchargements de fichiers

437