Networkx - найти наиболее появляющиеся пути в взвешенной сети - PullRequest
Новая
       12

Networkx - найти наиболее появляющиеся пути в взвешенной сети

2 голосов
/ 10 марта 2019

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

enter image description here

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

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

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

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

enter image description here

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

1 Ответ

1 голос
/ 29 марта 2019

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

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

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

Запускает дерево 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)]
...