Есть ли у графического инструмента способ проецирования двудольных графов?

Я пытаюсь спроецировать двудольный граф на два одномодовых графа.

Я хочу проанализировать двудольный граф, используя подход с двойной проекцией. Я использую NetworkX, но я хотел попробовать инструмент graph-tool, так как он утверждает, что он более эффективен. Есть вероятность, что мой график очень быстро станет очень большим, поэтому я хочу использовать наиболее эффективный метод/пакет. Пакет graph-tool утверждает, что он более эффективен, и я хотел бы попробовать его, но не могу найти способ спроецировать двудольный граф с его помощью. Кто-нибудь знает, возможно ли это с помощью графического инструмента? Единственная информация, которую я нашел, заключалась в том, что создатель просил кого-то, кто задал аналогичный вопрос, создать заявку, чтобы он / они могли начать над ней работать, но это с 2014 года.


python projection graph-theory graph-tool bipartite
person Jean    schedule 12.09.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

У меня была такая же проблема, и я нашел решение. У меня он работает на графиках до 5 миллионов узлов.

Он следует трем основным шагам:

  1. используйте функцию is_bipartite для создания логического массива, к которому принадлежит каждая вершина.
  2. перебрать удаляемый набор, добавляя ребра между всеми комбинациями соседей.
  3. используйте GraphView для создания нового графика, сохраняя только узлы интересующего набора.
g = gt.lattice([5,5])
is_biparitite, part = gt.is_bipartite(g, partition=True)
gt.graph_draw(g, vertex_fill_color=part)  # to view the full graph coloured by set

from itertools import combinations

g_temp = g.copy()  # this is a deepcopy

for v, bipartite_label in enumerate(part):
    if bipartite_label == 0:
        neighbours = list(g.vertex(v).all_neighbours())

        for s, t in combinations(neighbours, 2):
            g_temp.add_edge(s, t)

g_projected = gt.Graph(gt.GraphView(g_temp, vfilt=part.a==1), prune=True)

gt.graph_draw(g_projected)
person wem    schedule 02.12.2019