根据边界顶点属性将图划分为子图

Question

在有向图中寻找特定边界节点条件的聚类

我正在使用Python中的NetworkX库处理一个有向图（DiGraph）。这个图由多个节点组成，这些节点代表不同的立场（标记为“支持”和“反对”），涉及的主题或类别编号从1到6。其中一些节点有一个特殊的属性（special_attribute=True），这个属性在我的分析中非常重要。

目标

我需要开发一个算法，来识别这个图中的聚类，具体条件如下：

• 聚类是指一组强连接的节点。
• 这些聚类的边界或外围节点必须具有special_attribute=True属性。需要注意的是，这些边界节点可以属于多个聚类。

示例图结构

这个图中有像1-WITH、1-AGAINST、2-WITH等节点，其中一些节点设置了special_attribute属性。下面是一个小示例图，红色节点具有特殊属性：

问题

我该如何在Python中实现一个算法，找到图中所有符合条件的聚类，确保聚类的边界节点具有special_attribute=True属性？在上面的示例中，聚类将是：

4-AGAINST, 4-WITH, 6-WITH, 6-AGAINST, 5-WITH, 5-AGAINST, 2-WITH, 2-AGAINST

以及

5-WITH, 5-AGAINST, 2-WITH, 2-AGAINST, 3-WITH, 3-AGAINST, 1-WITH, 1-AGAINST

注意： 我正在处理的实际图大约有40,000个节点和70,000条边。

以下是创建上述图的代码：

digraph = nx.DiGraph()
digraph.add_node('1-WITH')
digraph.add_node('1-AGAINST')
digraph.add_node('2-WITH', specialAttribute=True)
digraph.add_node('2-AGAINST', specialAttribute=True)
digraph.add_node('3-WITH')
digraph.add_node('3-AGAINST')
digraph.add_node('4-WITH')
digraph.add_node('4-AGAINST')
digraph.add_node('5-WITH', specialAttribute=True)
digraph.add_node('5-AGAINST', specialAttribute=True)
digraph.add_node('6-WITH')
digraph.add_node('6-AGAINST')


# Add edges 
digraph.add_edges_from([('1-AGAINST', '1-WITH'),('1-WITH', '2-WITH'),('1-WITH', '3-WITH'), ('2-WITH','4-AGAINST'), ('4-AGAINST', '5-AGAINST'),  ('4-AGAINST', '6-AGAINST'),  ('6-AGAINST', '6-WITH'),
                        ('6-WITH', '5-AGAINST'),  ('6-WITH', '4-WITH'),  ('5-AGAINST', '3-AGAINST'), ('3-AGAINST', '2-WITH'), ('3-AGAINST', '1-AGAINST'), ('3-WITH', '5-WITH'), ('4-WITH','2-AGAINST'),
                        ('2-AGAINST','1-AGAINST'), ('2-AGAINST','3-WITH'), ('5-WITH','4-WITH'), ('5-WITH','6-AGAINST')
])```

Answer 1

这句话的意思是：“这个图会被分成不相连的小图，每个小图里有一个群体吗？”最终的目标是对这个图进行一个复杂的优化问题，其中带有特殊属性的节点可以看作是观察值，这样的逻辑会让每个群体变得独立，从而减少计算上的问题。

1. 生成一个不包含你“特殊”节点的小图。
2. 找出不相连的部分。

non_special_nodes = [node for node in digraph if "specialAttribute" not in digraph.nodes[node]]  
subgraph = nx.subgraph(digraph, non_special_nodes)
components = list(nx.connected_components(subgraph.to_undirected()))
print(components)
# [{'1-AGAINST', '1-WITH', '3-AGAINST', '3-WITH'},
#  {'4-AGAINST', '4-WITH', '6-AGAINST', '6-WITH'}]