La modularité du réseau de Newman fonctionne-t-elle pour les graphiques signés et pondérés?

11

La modularité d'un graphe est définie sur sa page Wikipédia . Dans un autre article , quelqu'un a expliqué que la modularité peut facilement être calculée (et maximisée) pour les réseaux pondérés car la matrice d'adjacence peut également contenir des liens de valeur. Cependant, je voudrais savoir si cela fonctionnerait également avec des arêtes signées et valorisées, allant, par exemple, de -10 à +10. Pouvez-vous fournir une intuition, une preuve ou une référence sur cette question?Aij

Philip Leifeld
la source

Réponses:

13

La généralisation directe de la modularité pour les réseaux pondérés ne fonctionne pas si ces pondérations sont signées. Par simple, je veux dire: utiliser simplement la matrice de poids au lieu de celle d'adjacence, comme Newman le fait, par exemple, dans (Newman 2004) . Vous avez besoin d'une version spécifique, telle que celle citée par BenjaminLind, ou celle de (Gomez et al. 2009) .

ijpipj=wiwj/(2w)2wiwjijw[0,1]pjepj

Pour résoudre ce problème, Gomez et al . considérer les liens positifs et négatifs séparément. Ils obtiennent deux valeurs de modularité distinctes: une pour les liaisons positives, une pour les liaisons négatives. Ils soustraient ce dernier de l'ancien pour obtenir la modularité globale.

Vincent Labatut
la source
Merci, cela semble prometteur. Je vais jeter un œil à Gomez et al. article. Y a-t-il une implémentation?
Philip Leifeld
1
Oui, je pense que vous trouverez le code source ici: deim.urv.cat/~sgomez/radatools.php
Vincent Labatut
le code semble dans une boîte noire aux fichiers EXE, mais si tout ce dont vous avez besoin est de la modularité pour les poids positifs et négatifs, pourquoi ne pas simplement (1) convertir votre matrice en une liste de bord pondérée, (2) diviser la liste entre des poids signés positivement et négativement, et (3) calculer la modularité en igraphutilisant des poids absolus dans chaque partition?
Fr.
C'est une bonne idée, mais la modularité traitée pour les poids négatifs doit être minimisée, et les méthodes en igraph ne font que la maximisation (pour autant que je sache). Quant au code source, je pense que vous avez raison. Peut-être pouvez-vous contacter directement l'un des auteurs?
Vincent Labatut
6

Oui il peut. Les modèles en verre rotatif pour la détection communautaire peuvent calculer la modularité à partir de graphiques signés pondérés. Vous aurez besoin de Traag et Bruggeman "Détection de communauté dans les réseaux avec des liens positifs et négatifs" comme référence. La fonction "spinglass.community ()" dans igraph peut trouver les communautés et retourner la modularité du graphe.

BenjaminLind
la source
Je vous remercie. Je ne m'intéresse pas vraiment aux communautés mais plutôt à la tendance du réseau signé à se polariser / se fragmenter en communautés. Mais pour autant que je puisse voir, la modularité peut être récupérée de l' communitiesobjet résultant en utilisant la modularityfonction. Je vais certainement jeter un œil à l'article de Traag et Bruggeman. Puisque l'implémentation semble être basée sur un recuit simulé: quelle est sa performance? Puis-je réellement m'assurer que l'algorithme retourne vraiment la modularité optimale (puisque je veux mesurer la polarisation / fragmentation)?
Philip Leifeld
3

Nous avons souligné le problème des fonctions de modularité [-égal] avec les réseaux signés dans cet article . Ils ont tendance à ignorer davantage la densité positive des communautés à mesure que le nombre absolu de liens négatifs dans le réseau augmente.

En outre, voici notre projet Java open source pour les réseaux signés pondérés, qui est basé sur le modèle de Constant Potts (similaire à la modularité), l' algorithme de Louvain rapide et l'évaluation de la communauté basée sur une extension de Map Equation .

Esmailian, P. et Jalili, M., 2015. Détection communautaire dans les réseaux signés: le rôle des liens négatifs à différentes échelles. Rapports scientifiques, 5, p.14339

Esmailian
la source