#python #networkx #graph-theory #complex-networks
#питон #networkx #теория графов #комплекс-сети
Вопрос:
У меня есть программа, которая генерирует ориентированный график с Networkx каждый раз, когда происходит изменение целевого источника данных, динамической сети. Я использую эти графики, объединяя взаимодействия и анализируя вновь добавленные или удаленные ребра. Но я хотел бы также получить еще одну информацию:
Скажем, что при t = 0 у меня есть узел, который направлен к другому узлу:
N1 -gt; N2
При t = 1 между N2 и N3 появляется новое ребро:
N1 -gt; N2 -gt;gt; N3
При t = 2 новый узел появляется между N2 и N3:
N1 -gt; N2 -gt;gt; N4 -gt;gt;gt; N3
И так далее. Я не знаю правильного способа дать имя N1, но, может быть, семя? Потому что я хочу получить узлы, подобные N1, которые имеют растущий охват, например, распространение болезней. Но я хочу только иметь возможность возвращать эти узлы, а не имитировать распространение. Если этот узел получает доступ ко все большему и большему количеству узлов в каждый момент времени, как я могу назвать этот узел и какой алгоритм я могу использовать для его обнаружения? Я подумал, что, возможно, можно было бы измерить растущую центральную роль между ними, однако, если бы для этого существовал алгоритм, я бы предпочел полагаться на чье-то понимание, отличное от моего внутреннего ощущения.
Я думаю, что Networkx не поддерживает множество алгоритмов для временных графиков, но я видел библиотеки, которые это делают; pathpy, DyNetx.
Я буду признателен за любой ответ, заранее благодарю вас.
Ответ №1:
Я хочу, чтобы такие узлы, как N1, имели растущий охват
Я не совсем понимаю, что вы имеете в виду под этим.
Угадывание: Вам нужен список всех узлов, которые существовали в t, но которые могут достигать большего количества режимов при T 1?
Это кажется таким простым, я сомневаюсь, что это действительно то, что вы имели в виду.
Однако:
Get t graph Get t 1 graph LOOP N over nodes in t 1 IF N not in t CONTINUE to next node CALCULATE Kt number of nodes reachable from N ( Dijsktra will do this ) in t CALCULATE Kt 1 number of nodes reachable from N in t 1 IF Kt 1 gt; Kt Add N to output Мне приходит в голову другая возможность: график представляет собой «лес деревьев», и вам нужен список всех корневых узлов деревьев, которые выросли в размерах.
Get t graph Get t 1 graph LOOP N over nodes in t 1 IF N not in t CONTINUE to next node IF N is not root ( i.e. has out-edges but no in-edges ) CONTINUE to next node CALCULATE Kt number of nodes reachable from N ( Dijsktra will do this ) in t CALCULATE Kt 1 number of nodes reachable from N in t 1 IF Kt 1 gt; Kt Add N to output