Поиск индивидуальных двусторонних сетей

Question

У меня есть данные в форме ниже, которая составляет двудольную сеть.

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

Что я хотел бы сделать - это написать что-нибудь (в идеале на python или C) или использовать существующую библиотеку для идентификации отдельных сообществ в данных. Например

A1, A2, A3, A4 являются частью одного сообщества, поскольку они подключаются к B1, B2, аналогично A5, A6, A7, A8, A9, все подключены к B3 и B4.

Я немного сбит с толку, прочитав множество различных статей о сетевом потоке и графиках относительно того, где именно находится моя проблема. Это просто форма поиска в ширину или есть более эффективные способы сделать это?

Спасибо

Answer 1

Используя Python и библиотеку igraph , вы можете сделать следующее:

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

Краткое объяснение: Graph.Formula создает график из строкового представления, подобного приведенному выше, но вы можете использовать любой другой метод, предоставленный igraph, для построения вашего графика. Преимущество использования Graph.Formula состоит в том, что он автоматически создает атрибут вершины name, содержащий имена вершин. graph.clusters() ищет подключенные компоненты сети и возвращает объект VertexClustering. Этот объект можно использовать в цикле for для перебора компонентов. В ядре цикла for переменная comm всегда будет содержать индексы узлов в текущем сообществе. Я выбираю вершины сообщества, используя graph.vs[comm], запрашиваю их имена в виде списка (graph.vs[comm]["name"]) и затем соединяю имена запятыми.

Answer 2

@ У Эли хорошая идея найти подключенные компоненты. Поскольку вы знаете, что метки (в данном случае в любом случае) начинаются с буквы «А», вы можете сделать это так:

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 3

Нет! Позаботьтесь об использовании библиотеки NetworkX, поскольку в ней не более 4 функций для двудольных графов. один для проверки, является ли он двудольным, один для окраски узлов, один для создания простых двудольных сетей без весов и другой для создания проекции двудольных сетей Вы можете использовать последнюю функцию.

Answer 4

Может быть что-то вроде:

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

Это работает только в одну сторону. Конечно, вы могли бы сделать 2 дикта, один с ключом A, установленным в качестве ключа, и один с ключом B, установленным в качестве ключа. Предполагается, что ключи являются неизменяемыми (строки, числа).

Answer 5

Если вы хотите использовать Python, прочитайте о библиотеке NetworkX . Он имеет множество модулей и реализации алгоритмов для графов. В частности, вам может пригодиться модуль Bipartite . Я не уверен, что вы подразумеваете под "сообществами", но функция bipartite_color из этого модуля может вам помочь.