Peut-on définir le concept de communauté?

Toile de Confiance Ğ1
#1

A vrai dire, il s’avère que même les experts n’ont pas de définition exacte. Mais ce que tu dis est proche de ce qu’on admet généralement : une communauté serait un groupe de gens plus fortement connectés entre eux qu’avec les autres. Ce n’est pas une définition à proprement parler, mais une intuition, qui donne lieu à plusieurs interprétations.

Il y a une multitude d’algorithmes pour calculer des communautés dans un graphe, ne donnant pas les mêmes résultats même quand ils prennent la même définition de communautés. En effet, en général, calculer le résultat exact est hors de portée, donc on calcule des approximations. En plus, il peut y avoir plusieurs résultats exacts…

Bref, c’est un peu le bazar. La bonne nouvelle, c’est que les communautés données par la plupart des algorithmes se ressemblent quand même souvent, et ont généralement du sens.

1 J'aime
87 communautés
#2

Je parlais des communautés données par la wotmap. Dans ce sens-là, elles sont parfaitement définies par l’algo lui-même. Mais sinon oui tu as raison.

#3

C’est Label Propagation Algorithm qui est utilsé, c’est ça ? Il est déterministe ? Je ne le connais pas bien.

#4

Je ne sais plus, Label Propagation Algo c’est pas juste le nom générique de ce type d’algo ? On utilise la fonction de la bibli python igraph.

#5

On peut transformer cette proposition en définition exacte. Je n’ai pas encore lu d’article qui fasse ça, mais j’ai une idée de définition et d’algo associé qui vont m’être utiles pour la toile de confiance animée.

#6

Ce serait super d’avoir une définition exacte, en faisant attention toutefois au fait qu’elle doit être assez souple pour capturer l’intuition. C’est ce qu’essaient de faire la modularité et pas mal d’autres fonctions de qualité ; vois par exemple ce papier qui en répertorie pas mal.

Note aussi que, en vrai, les communautés ne sont pas disjointes, et qu’il n’existe pas un unique découpage. Mais les algos de détection de communautés avec recouvrement posent plein de nouveaux problèmes.

Dans cette direction, j’aime bien l’approche par coeurs de communautés, qui en gros itère plusieurs fois une détection de communautés classique non-déterministe, et regarde quel pourcentage du temps les noeuds sont placés ensemble. Vois cette thèse pour plus de détails.

1 J'aime
#7

Merci pour ces références que j’ajoute immédiatement à ma liste ! Pour l’instant je lis une review qui compare un peu tout ce qui se fait, je suis très content d’être tombé dessus : Community structure: A comparative evaluation of community detection methods.