关于使用 networkx 进行 modularity-based 分区的问题

Question

给定边列表，如下面的代码所示：

import networkx as nx
from networkx.algorithms.community import greedy_modularity_communities
from networkx.algorithms.cuts import conductance

# Create a networkx graph object
my_graph = nx.Graph() 

# Add edges to to the graph object
# Each tuple represents an edge between two nodes
my_graph.add_edges_from([
                        (1,2), 
                        (1,3), 
                        (3,4), 
                        (1,5), 
                        (3,5),
                        (4,2),
                        (2,3),
                        (3,0)])

# Draw the resulting graph
nx.draw(my_graph, with_labels=True, font_weight='bold')

# Modularity
c = list(greedy_modularity_communities(my_graph))

我们得到作为切入点：

[frozenset({0, 2, 3, 4}), frozenset({1, 5})]

如果我们看一下它对应的图表：

为什么这里的节点 1 和 5 被删除或被认为是一个很好的拆分，而不是从图中的其余部分删除节点 0？

提前感谢您的任何提示最好的问候

Answer 1

仅从名称 greedy_modularity_communities 和 documentation 算法将始终 return 最佳分区的近似值。

对于您建议的分区，您可以简单地检查值：

from networkx.algorithms.community.quality import modularity

print(modularity(my_graph, [frozenset({0, 2, 3, 4}), frozenset({1, 5})]))
# 0.0546875
print(modularity(my_graph, [frozenset({1, 2, 3, 4, 5}), frozenset({0})]))
# -0.0078125

关于使用 networkx 进行 modularity-based 分区的问题

Questions on a modularity-based partitioning using networkx

modularity

networkx