Algorithmes de détection de communauté pour les graphes bipartites?

Existe-t-il des algorithmes de détection de communauté pour les graphes bipartites (réseaux à 2 modes) implémentés dans igraph, networkX, R ou Python etc.? En particulier, existe-t-il une telle mise en œuvre dans laquelle on pourrait restreindre la détection des communautés uniquement sur l'un des deux modes?

python graph-theory adamo
la source

Comment "restreindre la détection des communautés sur un seul des deux modes" sans savoir à l'avance quels nœuds composent les modes? Cela semble circulaire.

hardmath

Dans un réseau bipartite , vous connaissez déjà les deux modes. Ainsi, par exemple, si la moitié des nœuds appartenant au mode "A" sont liés à un nœud appartenant au mode "B", vous avez une communauté là-bas.

adamo

Si vous savez à l'avance quels nœuds appartiennent à chaque mode, cela répond à ma question sur la façon de restreindre la détection. Cependant, votre exemple et sa notion implicite de «communauté» ne sont pas clairs. Si un sommet dans un graphe bipartite n'est lié à aucun sommet du mode opposé, il n'est lié à aucun sommet (il serait isolé). Dans un graphe biparti connecté, chaque sommet de mode "A" est lié à un sommet de mode "B" et vice versa. "Communauté" signifie généralement quelque chose de plus qu'un sous-graphe connecté.

hardmath

À la réflexion, je soupçonne votre "lien avec un nœud" destiné à se lier à un seul nœud commun, donnant une clique dans le graphique projeté (voir la réponse), et donc "une communauté là-bas". Toutes mes excuses pour ne pas avoir saisi votre point en première lecture.

hardmath

Aucune excuse nécessaire. Mon anglais n'était pas si clair de toute façon.

adamo

Réponses:

L'expression "détection de communauté" est vaguement définie comme partitionnant les sommets d'un graphique en "communautés" de telle sorte que chacune a des membres plus densément liés les uns aux autres qu'aux membres d'autres "communautés".

Notre première tâche est de déterminer ce que cela devrait signifier dans le cas d'un graphe bipartite, qui par définition se compose de deux "modes" de telle sorte que les membres d'un mode ne sont liés qu'aux membres de l'autre mode. Elle peut être exprimée, au moins pour les graphiques simples, comme ayant une matrice d'adjacence de structure de bloc spéciale:

A = (\begin{matrix} 0 & B \\ B^{T} & 0 \end{matrix})

$A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$

Il me semble que l'interprétation la plus pertinente de "restreindre la détection des communautés uniquement sur l'un des deux modes" appliquerait lesdits algorithmes aux graphes "projetés" correspondant aux blocs de , c'est-à-dire le premier mode à matrice d'adjacence et le deuxième mode avec matrice d'adjacence . Notez que même si le graphe bipartite d'origine est simple (de sorte que est binaire), les graphes projetés seront généralement multi-graphes. Heureusement, igraph a une méthode pour les construire pour nous. $A^2$ $BB^T$ $B^TB$ $A$

Nous avons également la chance que les algorithmes de détection de la communauté igraph et connexes aient été "mis à jour pour gérer les graphiques pondérés" (tels que les graphiques multiples).

S. Fortunato (2010) étudie les critères de détection communautaire ( détection communautaire dans les graphiques ) et leur utilisation avec les réseaux bipartites et multipartites. L'interprétation que je suggère ci-dessus est articulée à la page 8:

Les graphiques multipartites sont généralement réduits à des projections unipartites de chaque classe de sommets. Par exemple, à partir du réseau bipartite de scientifiques et d'articles, on ne peut extraire qu'un réseau de scientifiques liés par coauteurs.

hardmath
la source