Vue d’ensemble

La centralité de l'intermédiarité mesure la probabilité qu'un node se trouve dans les plus courts paths entre deux autres nodes quelconques. Proposée par Linton C. Freeman en 1977, cet algorithme détecte efficacement les nodes 'pont' ou 'médiateur' entre plusieurs parties du graph.

La centralité de l'intermédiarité prend des valeurs comprises entre 0 et 1, les nodes ayant des scores plus élevés ayant un impact plus fort sur le flux ou la connectivité du réseau.

Les matériaux connexes sont les suivants :

• L.C. Freeman, A Set of Measures of Centrality Based on Betweenness (1977)
• L.C. Freeman, Centrality in Social Networks Conceptual Clarification (1978)

Concepts

Shortest Path

Pour chaque paire de nodes dans un graph connecté, il existe au moins un plus court path entre les deux nodes de telle sorte que le nombre d'edges que le path traverse (pour les graphs non pondérés) ou la somme des poids des edges (pour les graphs pondérés) soit minimisé.

Dans le graph non pondéré ci-dessus, nous pouvons trouver trois plus courts paths entre les nodes rouges et verts, et deux d'entre eux contiennent le node jaune, donc la probabilité que le node jaune se trouve dans les plus courts paths de la paire de nodes rouge-vert est 2 / 3 = 0.6667.

Centralité de l’Intermédiarité

Le score de centralité de l'intermédiarité d'un node est défini par cette formule :

où x est le node cible, i et j sont deux nodes distincts dans le graph (x lui-même est exclu), σ est le nombre de plus courts paths de la paire ij, σ(x) est le nombre de plus courts paths de la paire ij qui passent par x, σ(x)/σ est la probabilité que x se trouve dans les plus courts paths de la paire ij (qui est 0 si i et j ne sont pas connectés), k est le nombre de nodes dans le graph, (k-1)(k-2)/2 est le nombre de paires de nodes ij.

Calculez la centralité de l'intermédiarité du node rouge dans ce graph. Il y a 5 nodes en tout, donc (5-1)*(5-2)/2 = 6 paires de nodes sauf le node rouge, les probabilités que le node rouge se trouve dans les plus courts paths entre toutes les paires de nodes sont 0, 1/2, 2/2, 0, 2/3 et 0 respectivement, donc son score de centralité de l'intermédiarité est (0 + 1/2 + 2/2 + 0 + 2/3 + 0) / 6 = 0.3611.

L'algorithme de Centralité de l'Intermédiarité consomme beaucoup de ressources informatiques. Pour un graph avec V nodes, il est recommandé d'effectuer un échantillonnage (uniforme) lorsque V > 10,000, et le nombre d'échantillons suggéré est le logarithme de base 10 du nombre de nodes (log(V)).

Pour chaque exécution de l'algorithme, le prélèvement d'échantillons n'est effectué qu'une seule fois, les scores de centralité de tous les nodes sont calculés en fonction des plus courts paths entre tous les nodes échantillonnés.

Considérations

• Le score de centralité de l'intermédiarité des nodes isolés est de 0.
• L'algorithme de Centralité de l'Intermédiarité ignore la direction des edges mais les calcule comme des edges non dirigés. Dans un graph non dirigé de k nodes, il y a (k-1)(k-2)/2 paires de nodes pour chaque node cible.

Syntaxe

• Commande : algo(betweenness_centrality)
• Paramètres :

Exemples

Le graph d'exemple est un petit réseau social, les nodes représentent les utilisateurs et les edges représentent la relation de connaissance :

File Writeback

algo(betweenness_centrality).params().write({
  file:{ 
    filename: 'centrality'
  }
})

Résultats : Fichier centrality

Billy,0
Jay,0.0666667
May,0.0666667
Mark,0.133333
Ann,0.133333
Dave,0.333333
Sue,0

Property Writeback

algo(betweenness_centrality).params().write({
  db:{ 
    property: 'bc'
  }
})

Résultats : Le score de centralité pour chaque node est écrit dans une nouvelle property nommée bc

Direct Return

algo(betweenness_centrality).params({
  order: 'desc',
  limit: 3
}) as bc
return bc

Résultats : bc

Stream Return

algo(betweenness_centrality).params().stream() as bc
where bc.centrality == 0
return count(bc)

Résultats : 2