Un algorithme rapide pour le calcul de la centralité

@elois
Dans un récent post :


j’expliquais l’intérêt de l’algorithme d’Ulrik Brandes (2001) pour un calcul rapide de la « betweenness centrality ».

Dans notre cas, un peu particulier, l’algorithme doit être légèrement modifié (j’y ai quand même passé plusieurs heures :grinning:) car les certifications peuvent survivre quelques temps aux membres qui les ont émises ou reçues. De ce fait, l’ensemble des nœuds du réseau considéré doit comprendre aussi bien les anciens membres (au moins ceux qui sont encore concernés par une certification valide) que les membres actifs. Par contre, les chemins considérés dans l’algorithme ne peuvent joindre que des membres actifs, les seuls concernés par cette notion de centralité. De ce fait, on est amené à définir un sous-ensemble V* de l’ensemble des nœuds V, correspondant aux membres actifs. Cela donne l’algorithme modifié suivant :

Modified Betweenness Centrality.pdf (268,1 Ko)

Comme indiqué dans l’article original (https://algo.uni-konstanz.de/publications/b-fabc-01.pdf), cet algorithme peut être adapté au calcul d’autres formes de centralité, comme la « stress centrality ». J’ai donc réécrit l’algorithme pour cette variante (modifié pour notre cas) :

Modified Stress Centrality.pdf (266,6 Ko)

Dans la prochaine version de WotWizard StandAlone, l’explorateur de toile de confiance affichera la « betweenness centrality ».

8 « J'aime »

Merci beaucoup @gerard94, c’est un excellent algo, je viens d’ouvrir un ticket pour qu’on l’implémente a duniter-wotb : https://git.duniter.org/nodes/rust/duniter-rs/issues/62

2 « J'aime »

@gerard94, il y a juste une seule ligne que je ne saisi pas précisement :

image

Qu’est ce que w ? Les certificateurs de v ? ou les nœuds certifiés par v ? ou autre chose ?

@gerard94 bon je suis parti du principe que w représente les certificateurs de v et j’ai implémenter un 1er jet :

Je ne sais pas si c’est cohérent ou pas, voici ce que je trouve en appliquant mon code a la wot initiale de bloc zéro de la Ğ1 :

148, 30, 184, 11, 60, 51, 40, 115, 24, 140, 47, 69, 16, 34, 94, 126, 151, 0, 34,
133, 20, 103, 38, 144, 73, 523, 124, 23, 47, 17, 9, 64, 77, 281, 6, 105, 54, 0,
111, 21, 6, 2, 0, 1, 47, 59, 28, 236, 0, 0, 0, 0, 60, 6, 0, 1, 8, 33, 169,

Sachant que les membres correspondants sont :

"cgeek"
"elois"
"jeanferreira"
"pafzedog"
"Galuel"
"vincentux"
"yannlefranco"
"mathieuBize"
"greyzlii"
"cuckooland"
"nicoleC"
"nay4"
"Mententon"
"William"
"Thatoo"
"CaroleFabre"
"Sybille"
"gege53"
"Tortue"
"vit"
"jytou"
"inso"
"SebasC"
"gpsqueeek"
"Paulart"
"BenoitLavenier"
"AnneAmbles"
"CatherineLeroy"
"Loda"
"JoelCaillerie"
"HubertGicqueau"
"moul"
"mimi"
"fbuland"
"bou2fil"
"EstienneDunord"
"Francisco"
"saintmerlin"
"Darunya"
"Gaelle"
"manu"
"Philippe26"
"YoanSallami"
"Fiatoux"
"candide"
"MarcelDoppagne"
"simonelion"
"MariPotter"
"DamienChretien"
"Ariane"
"LudovicPecquot"
"fluidlog"
"Audrey35"
"simons"
"BernardORSONI"
"CaizohanFerreira"
"smyds"
"Alfybe"
"gerard94"

Que trouve tu toi pour le bloc zéro ? Si tu me donne tes valeurs ça m’aidera a vérifier :slight_smile:

Tu peux prendre les flèches dans le sens que tu veux : certificateur -> certifié ou certifié -> certificateur. La grandeur calculée ne dépend pas du sens. L’important est de choisir un sens et de s’y tenir. Une fois le sens choisi, v -> w.

1 « J'aime »

Parfais ça m’arrange car wotb ne stocke les liens que dans le sens target -> source car c’est dans ce sens qu’on s’en sert pour le calcul de distance. Du coup mon implémentation de l’algo devrait etre juste, mais j’aimerais bien avoir tes valeurs pour pouvoir vérifier avec un test unitaire :slight_smile:

EDIT : Je ne dispose des données que pour le bloc zéro de la Ğ1, que j’ai obtenu grace a mon code rust qui empile un blocs mais je n’ai pas encore de quoi me synchroniser toute la blockchain donc je ne peut pas aller plus loin !

Tu as donc pris le sens certifié -> certificateur. OK.

1 « J'aime »

Tout à fait d’accord, mais je n’ai pas encore traité ce cas là. Je te demande un peu de temps.

1 « J'aime »

Une première remarque : tu trouves des valeurs entières, au lieu de valeurs réelles.
Je trouve pour le bloc 0, sauf erreur, ces valeurs-ci, qui, aux décimales près, semblent correspondre aux tiennes :

Alfybe    33.0823928763389
AnneAmbles    124.0487539081052
Ariane    0.0
Audrey35    60.30619872454911
BenoitLavenier    523.5920119318624
BernardORSONI    0.0
bou2fil    6.166175284983335
CaizohanFerreira    1.74005439005439
candide    47.06701540405572
CaroleFabre    126.967720433053
CatherineLeroy    23.75907413238935
cgeek    148.803011487112
cuckooland    140.3960326882652
DamienChretien    0.0
Darunya    111.3800227744466
elois    30.93729796269623
EstienneDunord    105.2072288541576
fbuland    281.0851992712537
Fiatoux    1.727306903622693
fluidlog    0.0
Francisco    54.61807666393725
Gaelle    21.09770435446906
Galuel    60.13047173200123
gege53    0.0
gerard94    169.3400629398197
gpsqueeek    144.2383340851316
greyzlii    24.60844758358556
HubertGicqueau    9.579874998190213
inso    103.532228279569
jeanferreira    184.2596490716823
JoelCaillerie    17.58852815688875
jytou    20.1048216489393
Loda    47.92305995890362
LudovicPecquot    0.0
manu    6.70458329068169
MarcelDoppagne    59.88137644519223
MariPotter    236.9376051285156
mathieuBize    115.4801742339327
Mententon    16.47015091390091
mimi    77.69702642283936
moul    64.81182050606199
nay4    69.85329445258978
nicoleC    47.53890660737562
pafzedog    11.47552851026047
Paulart    73.57263732635624
Philippe26    2.074156399156399
saintmerlin    0.0
SebasC    38.35903632342253
simonelion    28.81652874611646
simons    6.613578422146196
smyds    8.58293874168487
Sybille    151.8302607788342
Thatoo    94.86903851863352
Tortue    34.5451767842431
vincentux    51.52813750169754
vit    133.3049503160948
William    34.78091305867621
yannlefranco    40.98542407152468
YoanSallami    0.0

Cela me paraît un bon début et me rassure aussi sur mes calculs.

1 « J'aime »

En fait je trouve bien des valeurs réelles mais j’arrondis a l’entier (en fait pour l’instant je fait une simple troncature mais j’aimerais appliquer un arrondi a l’entier le plus proche).

Wouhou super je confirme ça correspond :slight_smile:

Voici mes valeurs pour la stress centrality (users toujours dans le même ordre) :

848, 240, 955, 80, 416, 203, 290, 645, 166, 908, 313, 231, 101, 202, 487, 769, 984,
0, 154, 534, 105, 697, 260, 700, 496, 1726, 711, 160, 217, 192, 89, 430, 636, 1276,
41, 420, 310, 0, 357, 125, 50, 15, 0, 12, 275, 170, 215, 1199, 0, 0, 0, 0, 201, 31,
0, 9, 55, 216, 865,

OK, c’est bon :smile:. Et là, c’est vraiment des entiers.

1 « J'aime »

@gerard94 du coup j’ai un problème de définition, pourquoi la betweenness centrality est décimale ?

Ça ne semble pas correspondre avec ce que j’appelle le degré de centralité : le nombre de couples orientés pour lesquels le membre est présent sur au moins l’un des plus court chemin reliant ce couple.

Il y a aussi une autre nuance qui me chiffonne : dans ma précédente façon de calculer je ne comptai que les chemins de longueur inférieure ou égale a step max, tu crois que c’est possible d’adapter l’algo pour faire ça ?

EDIT : en fait je me rend compte que ma définition correspond davantage a la stress centrality a une nuance près : si je suis présent sur plusieurs plus courts chemins entre A et B ça ne compte qu’une fois, alors que la stress centrality vas compter chaque chemin même s’il ont les mêmes extrémités !

Si c est la centralité calculée, je préfère afficher 100 * ln(1 + c) / max, où max est la plus grande valeur de ln(1 + c). C’est plus régulier et c’est de 0 à 100.

1 « J'aime »

Parce que c’est une somme de rapports entre deux entiers. Pour un nœud donné n, c’est la somme, sur tous les couples de nœuds orientés, du rapport entre “le nombre de chemins orientés joignant ce couple et passant par n” et “le nombre total de chemins orientés joignant ce couple”.

Ben, non, ce n’est pas pareil. Mais je n’ai pas trouvé de référence à ta définition. Par contre, la “betweenness centrality” semble être un indice très utilisé dans l’étude des réseaux sociaux et il répond à la question : “Quels sont les nœuds du réseau par lesquels on a le plus de chance de passer en allant d’un nœud à un autre en prenant l’un des chemins les plus courts ?”, ou, dit autrement, “Quels sont les nœuds les plus incontournables ?”.
La “stress centrality” correspond plus à ta définition, mais remplace le “nombre de couples orientés pour lesquels n est sur un des chemins les plus courts” par le “nombre de chemins orientés les plus courts contenant n”.
Est-ce que ta définition est déjà utilisée par d’autres ? Sinon, quel serait son intérêt ?

Oui, c’est tout à fait ça. Une fois que les valeurs ont été divisées par le maximum, il y a peu de différences entre les deux indices.

Ça ne me paraît pas trop dans l’esprit de cet algo. Mais quel serait l’intérêt de cette limitation ?

À la réflexion, oui, ça me paraît possible, mais pas forcément souhaitable.

Aucune idée.

J’ai remarquer qu’il existe parfois plus de 10 plus courts chemins différents entre deux membres. je considère que compter alors beaucoup de points de stress centrality a un membre pour le fait de relier un seul couple fausse sont “poids” sont “importance” dans la liaison entre les couples. Et plus la toile est grande et plus l’explosion combinatoire rendra ce biais significatif !

Mesurer le rôle d’un membre dans le respect de la règle de distance. Avec cette nouvelle définition la centralité obtenu rend directement compte du degré avec lequel ce membre permet a la règle de distance d’etre vérifiée.

Si l’on comptabilise aussi les très nombreux plus courts chemins supérieurs a step_max on aura des aberrations : certains membres a la stress centrality très élevée ne contribuerons en fait que très peu au respect de la règle de distance si la majorité des plus court chemins sur lesquels ils sont présents sont des chemins très longs.

2 « J'aime »

OK, tu as une vue tout à fait différente de la centralité par rapport à ce qui se fait couramment dans l’étude des réseaux sociaux. Tu l’envisages du point de vue de la règle de distance. Ça se tient et c’est intéressant. Cela me paraît même plus pertinent dans notre cas, où l’on parle de certifications et non pas de “qui parle à qui ?”. Je prends un peu de temps pour y réfléchir, mais, du point de vue algorithmique, on doit pouvoir s’adapter.
Si quelqu’un d’autre a des idées…

1 « J'aime »

@gerard94 oui ma définition viens de la. Je comprend bien que la plupart des travaux scientifiques sur le sujet sont motivés vers des finalités pour lesquelles il y a des financements en UNL, donc pour analyser les réseaux sociaux des gafams entre autre… mais comme tu le devine ce n’est pas ce qui m’intéresse :wink:

3 « J'aime »

A titre de comparaison, en premier (left) ma définition du degré de centralité, en deuxième (right) la stress centrality :

left: [540, 159, 544, 59, 235, 118, 214, 374, 103, 486, 179, 94, 82, 113, 222, 377, 248, 0, 129, 316, 88, 406, 198, 391, 230, 892, 297, 89, 134, 110, 51, 256, 237, 390, 38, 170, 178, 0, 164, 78, 43, 11, 0, 12, 123, 79, 113, 348, 0, 0, 0, 0, 88, 23, 0, 9, 50, 138, 489],
right: [848, 240, 955, 80, 416, 203, 290, 645, 166, 908, 313, 231, 101, 202, 487, 769, 984, 0, 154, 534, 105, 697, 260, 700, 496, 1726, 711, 160, 217, 192, 89, 430, 636, 1276, 41, 420, 310, 0, 357, 125, 50, 15, 0, 12, 275, 170, 215, 1199, 0, 0, 0, 0, 201, 31, 0, 9, 55, 216, 865]

On vois bien que dés la toile du bloc zéro la stress centrality est souvent baucoup plus élevée que le degré de centralité que je défini, pour rappel voici les 2 définitions :

Degré de Centralité d’un membre N (ma définition) : Nombre de couples orientés pour lesquels le membre N est présent sur au moins l’un des plus court chemin reliant le couple. Les plus courts chemin d’une longueur supérieure a step_max ne sont pas comptabilisés.

Stress Centrality d’un membre N : Nombre de plus courts chemins passants par N.

EDIT : Temps de calcul de mon code rust pour chaque définition (en millisecondes) :

Calcul du degré de centralité avec mon algo maison utilisant la fonction find_paths() de nano : 1267ms
Calcul de la Stress Centrality avec l’algo de @gerard94 : 40ms

C’est donc quand même 30 fois plus rapide rien que sur la wot du bloc zéro !!!
Ce facteur est a prendre avec des pincettes par le fait que les deux définitions ne sont pas les mêmes et que peut être l’une est fondamentalement plus complexe a calculée que l’autre…

1 « J'aime »

Je m’avance peut-être beaucoup, mais je pense pouvoir adapter l’algorithme à ce que tu veux calculer.
Pour la comparaison entre left et right, il faudrait d’abord normaliser les valeurs dans chaque cas, en les divisant par leurs valeurs maximales. Je pense qu’elles devraient alors être tout à fait comparables.

2 « J'aime »