Правильно ли это вычисление промежуточности?

Question

На этом простом графике я пытаюсь вычислить промежуточность для всех узлов для пути от 2 до 6.

G=nx.Graph()
edge=[(1,5),(2,5),(3,5),(4,5),(4,6),(5,7),(7,6)]
G.add_edges_from(edge)
btw=nx.betweenness_centrality_subset(G,[2],[6])

Однако результат таков:

{1: 0.0, 5: 0.5, 2: 0.0, 3: 0.0, 4: 0.25, 6: 0.0, 7: 0.25}

Мне было интересно, почемупромежуточность для узла 5 равна 0,5, в то время как она должна быть равна 1, поскольку число всего кратчайшего пути равно 2, и оба они включают 5, а узлы 4 и 7 должны быть 0,5

Answer 1

Похоже, ошибка.

Вот мой угадай . Кажется, ошибка связана с функцией _rescale . Здесь, если график ориентирован, вычисленные значения умножаются на 0,5.

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

Пример:

nx.betweenness_centrality_subset(G,[2,6],[2,6])
# {1: 0.0, 5: 1.0, 2: 0.0, 3: 0.0, 4: 0.5, 6: 0.0, 7: 0.5}

Итак, если мое предположение верно, вам просто нужно умножить на 2 вычисленный результат.

Answer 2

Я считаю, что это не ошибка.

Прежде всего, будьте осторожны с нормализацией результатов.Если не нормализовано, вы получите количество путей через каждый узел.При нормализации вы получаете долю путей.По умолчанию nx.betweenness_centrality (G) нормализуется.По умолчанию nx.betweenness_centrality_subset (G, [2], [6]) НЕ нормализовано.

Во-вторых, для неориентированных графов ненормализованные значения междуness_centrality подсчитывают неориентированные пути.Это означает, что каждый направленный путь считается одной половиной ненаправленного пути.Вот почему ваш исходный пост имеет значения 0,5 и 0,25, а не 1,0 и 0,5.Пути подсчитываются таким образом, чтобы убедиться, что вы никогда не получите больше путей, чем общее количество ненаправленных путей в сети.Когда вы нормализуетесь, это не проблема.