0

我有以下形式的数据，它构成了一个二分网络。

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。

阅读了很多关于网络流和图表的各种文章，以了解我的问题究竟出在哪里，我有点困惑。这只是广度优先搜索的一种形式，还是有更有效的方法来做到这一点？

谢谢

4

5 回答 5

3

使用 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"])，然后用逗号连接名称。

于 2010-01-22T00:28:18.470 回答
1

如果您想使用 Python，请阅读NetworkX库。它有很多用于图的模块和算法实现。特别是，您可能会发现Bipartite模块很有用。我不确定您所说的“社区”是什么意思，但是该bipartite_color模块中的功能可能会对您有所帮助。

于 2010-01-09T10:36:02.283 回答
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']})

不过，这只适用于单向。您当然可以制作 2 个字典，一个将 A 设置为键，一个将 B 设置为键。它假定键是不可变的（字符串、数字）。

于 2010-01-09T10:36:42.663 回答
1

不！注意使用 NetworkX 库，因为它没有超过 4 个用于二分图的函数。一个用于验证它是否是二分的，一个用于为节点着色，一个用于创建没有权重的简单二分网络，另一个用于创建二分网络的投影您可以使用最后一个功能。

于 2011-05-02T22:08:09.677 回答
1

@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')]
于 2012-11-24T00:02:11.767 回答