0

我有一个程序，每次目标数据源（动态网络）发生变化时，都会使用 Networkx 生成有向图。我通过将交互组合在一起并分析新添加或删除的边来利用这些图表。但我还想提取另一个信息：

说，对于 t = 0，我有一个指向另一个节点的节点：

N1 -> N2

对于 t = 1，在 N2 和 N3 之间出现一条新边：

N1 -> N2 -> N3

对于 t = 2，在 N2 和 N3 之间出现一个新节点：

N1 -> N2 -> N4 -> N3

等等。我不知道给 N1 命名的正确方法，但也许是种子？因为我想获得像 N1 这样的节点，它们的影响范围越来越广，比如疾病传播。但我只想能够返回这些节点，而不是模拟传播。如果这个节点在每个 t 时刻都可以访问越来越多的节点，我可以称这个节点为什么，我可以使用什么算法来检测它？我认为也许可以衡量一个不断增长的中介中心性，但是如果有一个现有的算法，我宁愿依靠别人的洞察力，而不是我的菜鸟直觉。

我认为 Networkx 不支持很多时间图算法，但我见过支持的库；pathpy，DyNetx。

我将不胜感激，提前谢谢你。

4

1 回答 1

0

我想获得像 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 > 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 > Kt
       Add N to output
于 2021-12-08T18:04:55.160 回答