Блог

Я задавал ранее аналогичный вопрос, но, как я думаю, это было неясно. У меня есть неориентированный и невзвешенный граф 10000 вершин и вокруг 5000000 ребер, которые я считываю в python как список ребер.

В моей работе я пытаюсь построить функцию из каждого ребра, которая зависит от расстояний между соседними вершинами на каждом ребре. Предположим, у нас есть две связанные вершины v1, v2 представляют собой ребро, для v1 есть n1 подключенных соседей, а также n2 соседей, подключенных к v2. Чтобы построить мою функцию, мне нужно получить расстояния между соседями n1 и n2. Для всех ребер в графе функция выглядит как:

 e_1*d_1  e_1*d_2  ... e_1*d_n ...e_m*d_1 ...e_m*d_n
  

где n — количество соседей для обеих вершин на каждом ребре, d_n — расстояние между этими вершинами, m — количество ребер в графе, а e_m — последнее ребро в этом графе.

Обычно, если мы хотим получить длину кратчайшего пути, мы думаем о обходе графа, таком как алгоритм Дейкстры или Bfs, особенно если мой график невзвешен. Я использовал много функций, уже написанных в пакетах, таких как networkx и igraph , но эти функции неэффективны и отнимают много времени для моего графика. Например shortest_paths_dijkstra() , для определения расстояния функции требуется около 6,9 часов, потому что мне нужно вызывать ее много-много раз. Кроме того, функция all_pairs_shortest_path _length занимает около 13 минут (фиксируя длину пути, известную как cutoff, равной 3) и еще 16 минут для вызова расстояния для каждой пары соседей на графике!

Как написано в вопросе, нам нужно получить расстояние между соседями v1, v2, чтобы максимальное расстояние было равно 3, поскольку v1, v2 соединены. Я чувствую, что есть более умное решение для уменьшения временной сложности, используя тот факт, что возможные расстояния для пути (в моем случае) таковы 0, 1, 2, 3 , что мне не нужно проходить весь график для каждого пути между источником и целью! просто я ищу умный способ получить расстояние между соседями (не любые две случайные вершины)!

Я написал этот код, но это занимает много времени, около 54 минут, поэтому он также неэффективен!

 neighbor1 = {}
neighbor2 = {}
distance = {}
for i in list(edges.values()):
  list_of_distances = []
  neighbor1 = tuple(graph.vs[graph.neighbors(i[0], mode="all")]["name"])
  neighbor2 = tuple(graph.vs[graph.neighbors(i[1], mode="all")]["name"])
  for n2 in neighbor2:
    for n1 in neighbor1:
       if n1 == n2:
            list_of_distances.append(0)
       elif (n1 != n2) and not graph.are_connected(n1,n2):
            if ( graph.are_connected(i[0],n2) ) or ( graph.are_connected(n1,i[1])  ): 
               list_of_distances.append(2)
            elif ( not graph.are_connected(i[0],n2)  ) or ( not graph.are_connected(n1,i[1]) ):
               list_of_distances.append(3)
       else:
            list_of_distances.append(1)
  distance[tuple(i)] = list_of_distances
  

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

У вас чрезвычайно сложная задача, поэтому нормально, что ваш скрипт работает часами. Вы можете попытаться распараллелить его с помощью CUDA или чего-то подобного, или вы можете попытаться создать большой кеш (GBs). Но если вы не можете или не хотите, я предлагаю вам не использовать функции networkx / igraph, потому что они очень медленные для вас. Вы можете решить свою проблему без 1000000 запусков DFS. Вот одно из возможных решений с использованием наборов Python (я думаю, это будет быстрее, чем у вас, может быть, не очень).

 import networkx as nx

# Create a graph like yours
G = nx.fast_gnp_random_graph(1000, 0.05)

# Create neighbours dict
G_adj = dict(G.adjacency())
nbrs_dict = {node: {n for n in G_adj[node]} for node in G_adj}

# Result dict
distances = {}

# For every edge:
for e in G.edges:

    # Start value
    dist_value = 0

    # Get N1 and N2 neighbours
    n1_nbrs = nbrs_dict[e[0]]
    n2_nbrs = nbrs_dict[e[1]]

    # Triangles - nodes that connected to both N1 and N2
    # Every triangle value = 0
    tri = n1_nbrs amp; n2_nbrs
    for t in tri:

        # Get neighbours to find nodes with distance length = 2
        t_nbrs = nbrs_dict[t]

        t_in_n1 = n1_nbrs amp; t_nbrs
        t_in_n2 = n2_nbrs amp; t_nbrs

        t_not_in_n1 = n1_nbrs - t_nbrs
        t_not_in_n2 = n2_nbrs - t_nbrs

        dist_value  = len(t_in_n1)   len(t_in_n2)
        dist_value  = (2 * len(t_not_in_n1))   (2 * len(t_not_in_n2))

    # Exclude all triangle nodes because we processed them all
    n1nt_nbrs = n1_nbrs - tri
    n2nt_nbrs = n2_nbrs - tri

    # Select squares - nodes with length = 1
    direct = set([])
    for n1 in n1nt_nbrs:
        nbrs = nbrs_dict[n1]
        d = nbrs amp; n2nt_nbrs
        for node in d:
            direct.add((n1, node))
    dist_value  = len(direct)

    # Exclude squares so we have only nodes with length = 3
    n1final = n1nt_nbrs - set(e[0] for e in direct)
    n2final = n2nt_nbrs - set(e[1] for e in direct)
    dist_value  = 3 * len(n1final) * len(n2final)

    # Distance for an edge
    distances[e] = dist_value
  

В любом случае, ваша проблема O(n^3) сложна, поэтому я настоятельно рекомендую вам попытаться разделить ваш график. Может быть, у вас есть мосты или просто несколько связанных компонентов. Если вы будете обрабатывать их по отдельности, вы невероятно увеличите свою скорость.