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
Projets de recherche autour de la G1
#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.

#8

Plus je lis de papiers sur le sujet, plus je me dis qu’on se trompe à chercher des communautés par les nœuds et qu’il faudrait plutôt chercher les communautés par les liens.

Par exemple, ça n’a pas tellement de sens de me mettre dans la communauté « chercheur » ou « musicien » ou « sportif » ou « habitant de paris », par contre, ça a du sens de catégoriser chacune de mes interactions comme « participe à des activités de recherche en biophysique avec… », « participe à l’orchestre symphonique avec… », « participe à telle compétition sportive avec… », « habite à paris ainsi que… ». Attribuer une communauté à chaque lien me paraît capturer bien mieux la réalité des interactions sociales.

Et de même que les individus ont une identité riche d’une multitude d’expérience, les interactions s’enrichissent avec le temps, au fur et à mesure qu’elles se renforcent. Et c’est là que le critère temporel devient intéressant. On peut dire « telles personnes ont interagi lors de tel événement » et distinguer un groupe de personnes qui se déplacent pour un hackathon national d’un groupe de personnes qui se réunissent pour une rencontre de ML locale.

Toute cette info, on la trouve en partie dans la topologie du réseau, mais aussi dans les interactions, que ce soit dans les transactions (pour l’instant il y en a trop peu comme l’a montré NicolasGensollen), les « like » sur le forum, les réseaux spécialisés… Bref, il y a de quoi faire pas mal de recherche :smiley:

1 J'aime
#9

Oui, des communautés de liens c’est intéressant, même si les liens aussi peuvent faire partie de plusieurs communautés (par exemple, nous on est collègues, potes, certificateurs l’un de l’autre, et on a fait des échanges en G1 :wink: ).

Le problème c’est que les gens éludent les spécificités des liens en passant au line graph pour ne travailler que sur des noeuds. Mais c’est tout pourri ; ce serait bien mieux (mais plus difficile) de bosser directement sur les liens.

Sur ce sujet là, tu peux regarder Expected Nodes: A Quality Function for the Detection of Link Communities #autopromo #désolé

Il y a aussi Discovering link communities in complex networks by exploiting link dynamics mais je n’ai pas lu. Et il y en a d’autres.

Sinon, ça a du sens d’aller vers des communautés qui se recouvrent partiellement. Dans cette direction, je suis particulièrement fan des coeurs de communautés, comme je disais plus haut.

Quant à la dimension temporelle, voilà comment je vois ce que tu dis : il y a des relations (stables dans le temps, même si elles peuvent évoluer) et des interactions (qui elles sont des événements ponctuels). Pour reprendre notre exemple : on a une relation, qui est matérialisée par de multiples interactions : au boulot, aux rencontres G1, sur le forum, etc. Il est plus facile de caractériser les interactions, car elles sont souvent (mais pas toujours) dédiées à un aspect de la relation, que de caractériser les relation elles-mêmes. Donc oui, je te rejoins, faire des clusters de liens temporels (interactions) a sans doute plus de sens que faire des clusters de liens classiques (relations).

1 J'aime
#10

Je vais tout lire :slight_smile: (je n’ai pas encore lu la thèse de Massoud Seifi, mais elle est dans ma liste de lecture Zotero)

J’avais complètement oublié les line graph, heureusement que tu me rafraîchis la mémoire :heart_eyes_cat:

C’est bien de distinguer « relations » et « interactions », j’avais tendance à utiliser l’un ou l’autre de manière interchangeable.