Блог

У меня есть ориентированный граф с 481 узлом и 6817 ребрами (вес — это количество раз, когда появляется ребро, иначе это было бы около 4 миллионов ребер). Здесь показан график:

Я хочу найти пути от большинства внешних узлов, которые чаще всего попадают в центр графика (возможно, пути с общим наибольшим весом?). Я вычислил центральность собственных векторов узлов и составил топ-20. Эти узлы отображаются в центре. Что я пробовал:

 d = g.successors(top20nodes[0])
h = g.subgraph(d)
  

Это способ получить только те узлы, которые в конечном итоге заканчиваются на узле с в данном случае наибольшей центральностью собственного вектора. Однако я не знаю, как получить n наиболее появляющихся (наиболее взвешенных) путей, ведущих к этому узлу.

В идеале мой конечный результат был бы таким: серые узлы предназначены только для того, чтобы дать понять, что меня интересуют только n наиболее часто появляющихся путей. В этом случае эти 4 красных пути к центру:

Я не обязательно ищу точный код, я просто не знаю, как действовать дальше. У кого-нибудь есть подсказки, как этого добиться?

Обратите внимание, что мое решение не является не полностью оптимальным, в некоторых случаях оно может возвращать не самые лучшие пути

Я придумал алгоритм для вас. В нем есть несколько допущений, поэтому он не является лучшим из лучших. Но это должно возвращать довольно хорошие результаты.

Во-первых, вы должны определить свой центр графика (я оставил его за пределами моего алгоритма). После того, как вы определили это, вам следует заменить все ваши центральные узлы только на один — Главный центральный узел (не забывайте о ребрах). После этого начинается мой алгоритм.

Он запускает дерево BFS с центрального узла с заданной глубиной. Вот основная несовершенная часть: если у вас будет два пути между двумя узлами — длинный-тяжелый и короткий-легкий, будет выбран короткий-легкий. Я не уверен, будет ли это критично для вашего графика, но, похоже, что это не так (картинка не очень информативна).

После построения дерева BFS оно суммирует все веса путей BFS и сортирует их. Затем вы можете просто выбрать первые X путей.

Я надеюсь, что это поможет вам решить вашу проблему 🙂

 import networkx as nx

# Create graph
G = nx.DiGraph()
G.add_nodes_from([1,6,7,8,9,10,11,12,13,14,15,16,17])
G.add_weighted_edges_from([
    (6,1,2),
    (7,1,5),
    (10,1,7),
    (12,1,1),
    (15,1,4),
    (17,1,6),
    (8,6,5),
    (8,7,8),
    (9,8,2),
    (11,10,1),
    (13,12,5),
    (14,13,6),
    (16,15,3),
    (16,14,4),
    (14,16,1),
])

# Get the BFS tree. 1 is the center, 100 is the BFS length. Note, that
# long lengths MAY waste a lot of computing time
B = nx.bfs_tree(G, 1, 100)
# Get our center
root = list(v for v, d in B.in_degree() if d == 0)[0]
# Get all leaves _in_BFS_tree
leaves = (v for v, d in B.out_degree() if d == 0)
# Get all paths
all_paths = [nx.shortest_path(B, root, l) for l in leaves]
# Get all sorted pairs [path, path_length]
result = sorted(
    [
        (
            path, sum((G.edges[path[i 1], path[i]]['weight'])
            for i in range(len(path) - 1))
        )
        for path in all_paths
    ],
    key=lambda x: x[1],
    reverse=True
)

result
[([1, 12, 13, 14], 12),
 ([1, 6, 8, 9], 9),
 ([1, 10, 11], 8),
 ([1, 15, 16], 7),
 ([1, 17], 6),
 ([1, 7], 5)]