Recherche de réseaux bipartites individuels

Question

J'ai des données dans le formulaire ci-dessous, qui constitue un réseau bipartite.

A1 - B1 
A2 - B2 
A2 - B1 
A3 - B1 
A4 - B2 
A5 - B3 
A6 - B3 
A7 - B3 
A7 - B3 
A8 - B4 
A9 - B3 

Ce que je voudrais faire est d'écrire quelque chose (idéalement en python ou C) ou utiliser une bibliothèque existante pour identifier les communautés individuelles dans les données. Par exemple

A1, A2, A3, A4 font tous partie de la même communauté parce qu'ils se connectent à B1, B2 de manière similaire A5, A6, A7, A8, A9 tous reliés à B3 et B4.

Je suis un peu confus après avoir lu beaucoup de différents articles sur le flux de réseau et les graphiques pour savoir exactement où se situe mon problème. Est-ce juste une forme de recherche «Breadth-first» ou existe-t-il un moyen plus efficace de le faire?

Merci

Answer 1

@Eli a une bonne idée de trouver les composants connectés. Puisque vous connaissez les étiquettes (dans ce cas, de toute façon) commencer par « A », vous pouvez le faire comme ceci:

import networkx as nx 
edges = """A1 - B1 
A2 - B2 
A2 - B1 
A3 - B1 
A4 - B2 
A5 - B3 
A6 - B3 
A7 - B3 
A7 - B3 
A8 - B4 
A9 - B3""".split('\n') 
G = nx.parse_edgelist(edges,delimiter=' - ') 
for component in nx.connected_components(G): 
    print [n for n in component if n.startswith('A')] 

Answer 2

Si vous voulez utiliser Python, lisez la bibliothèque NetworkX. Il a beaucoup de modules et d'implémentations d'algorithmes pour les graphiques. En particulier, vous pouvez trouver le module Bipartite utile. Je ne suis pas sûr de ce que vous entendez par "communautés", mais la fonction bipartite_color de ce module peut vous aider.

Answer 3

Peut-être quelque chose comme:

import collections 

data = (("A1", "B1"), ("A2", "B2"), ("A2", "B1")) 
out = collections.defaultdict(list) 

for value, key in data: 
    out[key].append(value) 

print out 
-> defaultdict(<type 'list'>, {'B1': ['A1', 'A2'], 'B2': ['A2']}) 

Cela fonctionne à sens unique cependant. Vous pouvez bien sûr faire 2 dicts, l'un avec la clé A et l'autre avec la clé B. Il suppose que les clés sont immuables (chaînes, nombres).

Answer 4

En utilisant Python et le igraph library, vous pouvez effectuer les opérations suivantes:

import igraph 
graph = igraph.Graph.Formula("A1-B1, A2-B2, A2-B1, A3-B1, A4-B2, A5-B3, A6-B3, A7-B3, A8-B4, A9-B3") 
comms = graph.clusters() 
for comm in comms: 
    print ", ".join(graph.vs[comm]["name"]) 

Une brève explication: Graph.Formula construit un graphique sur une représentation de chaîne comme celle-ci, mais vous pouvez utiliser toute autre méthode prévue par igraph pour construire votre graphique. Un avantage d'utiliser Graph.Formula est qu'il crée automatiquement un attribut vertex name contenant les noms de vertex. graph.clusters() recherche les composants connectés du réseau et renvoie un objet VertexClustering. Cet objet peut être utilisé dans une boucle for pour parcourir les composants. Au cœur de la boucle for, la variable comm contiendra toujours les indices des nœuds de la communauté actuelle. Je sélectionne les sommets de la communauté en utilisant graph.vs[comm], demander leurs noms sous forme de liste (graph.vs[comm]["name"]), puis joindre les noms par des virgules.

Answer 5

Non! Veillez à utiliser la bibliothèque NetworkX car elle ne possède pas plus de 4 fonctions pour les graphiques bipartites. un pour vérifier s'il est bipartite, un pour colorier les nœuds, un pour créer un réseau bipartite simple sans poids et un autre pour créer une projection des réseaux bipartites Vous pouvez utiliser la dernière fonction.