Как я могу оценить связность моих узлов?

Question

У меня есть пространство, в котором есть все взаимосвязанные узлы, основанные на «показателе сходства».Я хотел бы определить, насколько «связан» узел с остальными.

Моя цель - найти узлы, которые плохо связаны, чтобы убедиться, что обратная ссылка с другого узла имеет приоритет.

Возможно, поможет пример.

У меня есть веб-страница, которая ссылается на другие мои страницы на основе оценки сходства.Предположим, у меня есть страницы: A, B, C, ...

A имеет обратную ссылку со всех других страниц, так что она очень хорошо связана.Он также имеет ссылки на все мои другие страницы (каждая строка на графике по существу двунаправленная).B имеет только одну обратную ссылку от A. C имеет ссылку от A и D.

Я хотел бы убедиться, что ссылка A-> B имеет приоритет над ссылкой A-> C (даже еслиоценка сходства между C и A выше, чем у B и A).

Короче говоря, я хотел бы оценить, какие узлы являются наименее и лучше всего связаны, чтобы я мог сопоставить результаты со своими средствами.

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

Answer 1

Центральность является мерой "... относительной важности вершины в графе (например, насколько важен человек в социальной сети или, в теории синтаксиса пространства насколько важна комната в здании или насколько хорошо используется дорога в городской сети). "

(из Википедии, конечно).

В качестве интересного (и практического) применения этой концепции кто-то нанес на карту наиболее связанный artcile в Википедии . Оказывается, 2007 . На этой же странице обсуждается основной алгоритм и даже пример кода.

Некоторые другие потенциально полезные метрики можно найти здесь .