Skip to Main content Skip to Navigation
Conference papers

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
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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é.
Document type :
Conference papers
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/inria-00384426
Contributor : Gilles Tredan <>
Submitted on : Friday, May 15, 2009 - 10:56:40 AM
Last modification on : Tuesday, June 15, 2021 - 4:13:24 PM
Long-term archiving on: : Thursday, June 10, 2010 - 9:25:50 PM

File

algotel.pdf
Files produced by the author(s)

Identifiers

  • 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. AlgoTel, 2009, Carry-Le-Rouet, France. ⟨inria-00384426⟩

Share

Metrics

Record views

592

Files downloads

580