Comment pouvons-nous savoir à quelle communauté un sommet appartient à l'algorithme Girvan-Newman?

Question

Je l'ai fait un peu de lecture sur la détection de la communauté dans les graphiques que je prévois de travailler sur ma thèse pour elle. Je l'ai passé en revue les articles portant sur le même et suis tombé sur l'algorithme Girvan-Newman . J'ai lu le papier et un doute que je ne pouvais pas vraiment comprendre.

L'algorithme fonctionne en supprimant le bord qui a la valeur la plus élevée de « bord intermédiarité » à chaque itération. Supposons que j'ai un graphe $ G (V, E) $ tel que $ V = \ {v_ {1}, v_2, \ cdots, v_n \} $. Maintenant, supposons que ce graphique est tel qu'il a 2 communautés distinctes (quelque chose que nous savons déjà, mais c'est ce que l'algorithme doit détecter). Après la première itération, il supprimerait le bord qui a la valeur la plus élevée du bord intermédiarité. Maintenant, ma question est, après cela se fait (ou même après quelques itérations), dire que j'ai un sommet $ v_i $, comment pouvons-nous savoir quelle communauté ce sommet appartiennent à? Suis-je manque quelque chose ici?

Answer 1

Ceci est la méthode de classification hiérarchique. Comme vous enlevez les bords, à un moment donné le graphique déboîtement: les composants connectés sont vos communautés de haut niveau. Comme vous gardez les bords suppression, les communautés de niveau supérieur sont déconnectés trop, et vous pouvez penser des nouveaux composants connectés plus petits que les sous-communautés. Ainsi, vous pouvez penser à l'algorithme comme la construction d'un arbre des communautés plus en plus fins, où les feuilles sont des sommets individuels.