@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 ) 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”.