как рассчитать среднюю длину кратчайшего пути в разнонаправленном графе с несколькими несвязанными узлами?

Я хотел бы вычислить average_shortest_path_length в моем разнонаправленном графе, но есть узел, не связанный с другими узлами

например, у меня есть сеть с узлами и ребрами, как показано ниже:

lst_nodes=[2782, 27118, 28931, 28936, 43162, 28770, 48325, 33783]

lst_edge = [(28931, 28936L), (28931, 27118L), (28931, 27118L), (28931, 33783L), (48325, 28936L), (28936, 43162L),
            (28936, 48325L), (27118, 28936L), (27118, 28936L), (27118, 48325L), (43162, 48325L), (2782, 28931L),
            (2782, 48325L), (2782, 48325L), (2782, 27118L), (2782, 33783L)]

MDG = nx.MultiDiGraph()
MDG.add_nodes_from(lst_nodes)
MDG.add_edges_from(lst_edge)

print 'avg shortest path length:', nx.average_shortest_path_length(MDG)

figure_1-1.png

это закончится исключением, например

networkx.exception.NetworkXError: Graph is not connected.

но в соответствии с примечаниями в NetworkX

Для несвязных графов вы можете вычислить среднюю длину кратчайшего пути для каждого компонента: >>> G = nx.Graph ([(1,2), (3,4)]) >>> для g в nx.connected_component_subgraphs (G) : ... print (nx.average_shortest_path_length (g)) 1.0 1.0

он должен работать с компонентами, поэтому я пробую код перед

for g in nx.connected_component_subgraphs(MDG):
    print nx.average_shortest_path_length(g)

но заканчивается исключением типа networkx.exception.NetworkXNotImplemented: not implemented for directed type, однако, если я удаляю один узел из сети, я могу вычислить среднюю длину кратчайшего пути для сети, поэтому мне интересно, как я могу вычислить среднюю длину кратчайшего пути в разнонаправленном графе с несколько узлов не подключены?


python networkx
person LancelotHolmes    schedule 07.03.2017    source источник
comment
Вы можете преобразовать каждый из компонентов в неориентированный граф: for g in nx.connected_component_subgraphs(G): F=nx.Graph(g); ...   -  person DYZ    schedule 07.03.2017
comment
@DYZ ну, это неверно, во-первых, средняя длина кратчайшего пути для ориентированного графа и неориентированного графа отличается, и я попробовал ваше решение, оно закончится новым исключением ZeroDivisionError: float division by zero, так как существует единственный узел в сети. Спасибо, в любом случае   -  person LancelotHolmes    schedule 07.03.2017
comment
Вы правы, средний кратчайший путь для орграфов и неориентированных графов различается. Но nx.average_shortest_path_length работает только с неориентированными графами (поэтому возникает исключение), поэтому я думаю, у вас нет выбора. Вы, конечно, можете вычислить nx.shortest_path_length и взять среднее значение.   -  person DYZ    schedule 07.03.2017

Ответы (1)


arrow_upward
0
arrow_downward

На самом деле, я думаю, что nx.shortest_path_length - наиболее разумное решение:

import statistics
from itertools import chain
# This includes the isolated node!
path_lengths = (x.values() for x in nx.shortest_path_length(MDG).values())
statistics.mean(chain.from_iterable(path_lengths))
# 1
person DYZ    schedule 07.03.2017
comment
спасибо @DYZ, но согласно Википедии, средняя длина кратчайшего пути не считается простое среднее значение, но я понятия не имею, следует ли мне делить на общее количество узлов (/8*(8-1)) или просто на количество узлов в компонентах (/7*(7-1)), в то время как последний получил результат 2/3, и я нахожу, рассматриваю ли я это как неориентированный граф, вычисление должно делиться на количество узлов в компонентах, которые получили результат около 1,47, аналогичный результату в Gephi - person LancelotHolmes; 09.03.2017