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

在具有特定边界结点条件的有向图中寻找簇

我正在使用NetworkX库在Python语言中处理有向图(DiGraph).我的图表由几个 node 组成，这些 node 代表不同主题或类别(编号为1到6)的不同立场(标记为"与"和"反对").其中一些 node 有一个特殊的属性(special_attribute=True)，这在我的分析中起着至关重要的作用.

目的

在以下情况下，我需要开发一种算法来识别此图中的集群:

• 群集是一组强连接的 node .
• 这些集群中的border或peripheral nodes必须具有special_attribute=True属性.需要注意的是，这些边界 node 可以是多个集群的一部分.

示例图 struct

The graph has nodes like 1-WITH, 1-AGAINST, 2-WITH, etc., with some having the special_attribute attribute set. A small example graph is shown below, with the red nodes having the special attribute

问题

根据集群的边界 node 具有SPECIAL_ATTRIBUTE=True属性的条件，如何用Python语言实现在图中找到所有这类集群的算法？在上面的示例中，集群将是

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个

Note: The actual graph I am working on has around 40.000 vertices 和 70.000 edges.

用于创建上述图表的要复制粘贴的代码:

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