Использование взвешенных матриц смежности для вычисления глобальной эффективности упомянутой матрицы с использованием networkx - PullRequest
Новая
       22

Использование взвешенных матриц смежности для вычисления глобальной эффективности упомянутой матрицы с использованием networkx

0 голосов
/ 27 мая 2019

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

Для изучения этого я использовал метрику теории графов сети, глобальную эффективность.Но я понял, что код networkx игнорирует вес при расчете глобальной эффективности.Итак, я вошел и изменил исходный код и добавил вес в качестве метрики.Кажется, он работает и дает мне другие значения, чем невзвешенный подход, но исключительно медленный (около 20 раз).

Как я могу ускорить эти вычисления? 

##The code I am running

import networkx
import numpy as np
from networkx import algorithms 
from networkx.algorithms import efficiency 
from networkx.algorithms.efficiency import global_efficiency
import pandas



data=pandas.read_csv("ones.csv")
lol = data.values.tolist()
data=pandas.read_csv("twos.csv")
lol2 = data.values.tolist()

combo=[["10pp", "10d"]]
GE_list=[]


for row in combo:
    values = row
    datasafe=pandas.read_csv("b1.csv", index_col=0)
    datasafe.loc[values, :] = 0

    datasafe[values] = 0


    g=networkx.from_pandas_adjacency(datasafe)
    ge=global_efficiency(g)
    GE_list.append(ge)

extra=[""]
extra2=["full"]
combo.append(extra)
combo.append(extra2)
datasafe=pandas.read_csv("b1.csv", index_col=0) 
g=networkx.from_pandas_adjacency(datasafe)
ge=global_efficiency(g)
GE_list.append(ge)

values = ["s6-8","p9-46v","p47r","p10p","IFSp","IFSa",'IFJp','IFJa','i6-8','a9-46v','a47r','a10p','9p','9a','9-46d','8C','8BL','8AV','8AD','47s','47L','10pp','10d','46','45','44']
datasafe=pandas.read_csv("b1.csv", index_col=0)
datasafe.loc[values, :] = 0

datasafe[values] = 0


g=networkx.from_pandas_adjacency(datasafe)
ge=global_efficiency(g)
GE_list.append(ge)

output=pandas.DataFrame(list(zip(combo, GE_list)))
output.to_csv('delete 1.csv',index=None)


##The change I made to the original networkx code
    try:
        eff = 1 / nx.shortest_path_length(G, u, v)
## changed to
    try:
        eff = 1 / nx.shortest_path_length(G, u, v, weight='weight')

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

PS-я не очень хорошо понимаю Python, поэтому, пожалуйста, потерпите меня :))

1 Ответ

0 голосов
/ 28 мая 2019

Используя вес, вы обмениваетесь поиском в ширину с алгоритмом Дейкстры, который увеличивает время выполнения на log|V|, см. Второй комментарий https://stackoverflow.com/a/25449911

Если у вас есть проблемы со временем выполнения, вам лучше обменяться networkx, который реализован на python, с реализацией C, такой как graph-tool или igraph, см., Например. для (вероятно, предвзятого) сравнения производительности: https://graph -tool.skewed.de / performance

...