寻找单个二分图网络

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

也许可以这样做：

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

不过，这种方法只能单向使用。你当然可以创建两个字典，一个用A集合作为键，另一个用B集合作为键。这种方法假设键是不可变的，也就是说，像字符串和数字这样的类型。

Answer 2

使用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 3

@Eli 提出了一个很好的主意来找到连接的部分。因为你知道这些标签（在这种情况下）都是以 "A" 开头的，所以你可以这样做：

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