учитывая список ребер, как показано в коде ниже:
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 удален из остальной части графа?
Заранее спасибо за любые подсказки С наилучшими пожеланиями
Только из имени greedy_modularity_communities
и из документация алгоритм всегда будет возвращать приближение оптимального раздела.
Для предложенного вами раздела вы можете просто проверить значения:
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