Procurando redes bipartidas individuais

Question

Eu tenho dados no formulário abaixo, que compõe uma rede bipartido.

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

O que eu gostaria de fazer é escrever algo (idealmente em Python ou C) ou usar uma biblioteca existente para identificar comunidades individuais dentro dos dados. Por exemplo

A1, A2, A3, A4 são todos parte da mesma comunidade, porque eles se conectam a B1, B2 semelhante A5, A6, A7, A8, A9 todos ligados a B3 e B4.

Estou um pouco confuso com lotes ler vários artigos sobre fluxo de rede e gráficos como para exatamente onde o meu problema se senta. Isto é apenas uma forma de Amplitude-primeira pesquisa ou há um meio mais eficiente de fazer isso?

Graças

Answer 1

@Eli tem uma boa idéia para encontrar os componentes ligados. Desde que você sabe os rótulos (neste caso, de qualquer maneira) começa com "A" você pode fazê-lo como este:

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

Usando Python eo IGRAPH biblioteca , você pode fazer o seguinte:

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"])

Uma breve explicação: Graph.Formula constrói um gráfico a partir de uma representação de cadeia como o descrito acima, mas você pode usar qualquer outro método fornecido pelo IGRAPH para construir seu gráfico. Uma vantagem de usar Graph.Formula é que ele cria automaticamente um atributo name vértice contendo os nomes de vértice. Pesquisas graph.clusters() para os componentes conectados da rede e retorna um objeto VertexClustering. Este objecto pode ser utilizado num ciclo for para repetir os componentes. No núcleo do circuito for, a variável comm sempre conterá os índices dos nós na comunidade atual. Eu selecione os vértices da comunidade usando graph.vs[comm], solicitar seus nomes em uma lista (graph.vs[comm]["name"]) e depois juntar os nomes por vírgulas.

Answer 3

Se você quiser usar Python, leia sobre o NetworkX biblioteca . Ela tem muitos módulos e algoritmo implementações para gráficos. Em particular, você pode encontrar a Bipartite módulo útil. Eu não tenho certeza que você entende por "comunidades", mas a função bipartite_color daquele módulo pode ajudá-lo.

Answer 4

Talvez algo como:

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']})

Isso só funciona de uma maneira embora. Você poderia naturalmente fazer 2 dicts, um com o Um conjunto de chave e um com o conjunto B como chave. Assume-se que as teclas são imutáveis ??(cordas, números).

Answer 5

Não! Tome cuidado para usar a biblioteca NetworkX porque isso não tem mais de 4 função para grafos bipartidos. um para verificar se ele é bipartido, uma para colorir os nós, uma para criar um simples redes bipartidos sem pesos e outra para criar uma projecção das redes bipartidos Você pode pode ser usar a última função um.