#graph #networkx #graph-theory #social-networking
#График #networkx #теория графов #социальные сети
Вопрос:
Я читал, что центральность между значениями определяется как количество раз, когда вершина лежит на кратчайшем пути других пар узлов.
Однако, в случае, если веса имеют положительное значение (т. Е. Чем Больше вес ребра, тем лучше), тогда как определить центральность между значениями?
В этом случае есть ли другой способ вычислить центральность между значениями? Или это просто интерпретируется по-другому?
Комментарии:
1. Диким предположением было бы использовать отрицательные веса
2. @willcrack Разве это не вызовет проблем, если, например, используется алгоритм Дейкстры? Будут ли работать взаимные веса?
3. Из документации NetworkX по центральности между значениями (см. Примечания ), вы не можете использовать отрицательные веса ребер…
4. Вы пытаетесь вычислить центральность, когда вы отслеживаете, сколько раз узел находится на пути с наибольшим весом, независимо от длины пути (количества ребер)? Если это так, чтобы обойти отсутствие отрицательных ребер в Дейкстре, вы могли бы создать новые веса как
new_weight(i,j) = max(all_weights) - old_weight(i,j).5. @cookesd На самом деле, я просто пытаюсь понять, как вычисляется / определяется центральность между значениями, когда все веса графика выше 0, а более высокие веса «лучше», чем низкие веса (например, ребро — это значение экспорта), и я не могу понять идею «кратчайшего пути» вэтот случай. Я все же рассмотрю вашу реализацию!
Ответ №1:
Вычисление центральности промежуточности вершины v зависит от следующей дроби для любых u и w: s (u, w, v) / s (u, w) где s (u, w, v) — количество кратчайших путей между u и w, которые включают v и s(u, w) — общее количество кратчайших путей между u и w.
При положительных весах ребер я бы посоветовал вам считать каждый кратчайший путь с его собственным весом: замените s (u, w, v) на сумму весов кратчайших путей между u и w, которые включают v; и s (u, w) на сумму весов всех кратчайших путеймежду u и w.
Затем вам нужно определить вес путей, и это зависит от того, что вы имеете в виду. Вы можете, например, рассмотреть сумму весов ребер, их произведение, их минимальное или максимальное значение и т. Д.
Предупреждение: это определение по-прежнему основывается на кратчайших невзвешенных путях; если существуют более длинные пути с более высокими весами, они будут проигнорированы, что означает, что структура графа преобладает. Это может быть неудовлетворительным.
Примечание: этот подход в некоторой степени эквивалентен, если ребра имеют целочисленный вес, а вес пути равен его произведению на вес ребра, чтобы использовать классическое определение для мультиграфа (невзвешенный граф, в котором между двумя одинаковыми вершинами может существовать несколько ребер).