Наименьший путь в теории графов (анализ социальных сетей)

Question

Это сценарий: существует неориентированный граф с n узлами и e ребрами, все узлы связаны.

Вопрос в сценарии: каждый узел в социальной сети может рассматриваться как человекделится или читает контент.Это означает, что если A подключен к B, C и D, если A совместно использует контент с сетью, он напрямую достигнет BCD.Это означает, что для достижения всех узлов в сети просто необходимо, чтобы они были смежными с узлом, который совместно использовал контент.

Q1: есть ли способ найти наилучшую отправную точку для достижения всей сети??Q2: есть ли способ найти наименьший путь из этой точки?

Я уже посмотрел на проблему продавца и prim'algorithm.

Спасибо!

Answer 1

Страница в Википедии о центральности описывает несколько различных форм центральности в графе и содержит ссылки на алгоритмы для некоторых из них.

Answer 2

Повышение матрицы смежности сети до n-й степени дает вам число переходов длины n между двумя вершинами i, j (представленными i-м элементом матрицы). Первое ненулевое значение x (i, j) скажет вам, насколько они далеко друг от друга относительно прогулок. Если вы ищете лучший узел для охвата всей сети, то вы можете просто найти первый экземпляр строки (или столбца) матрицы, который имеет все ненулевые значения при увеличении n.

Очевидно, что это не практично для огромных сетей ...

В противном случае вы можете применить алгоритм Дейкстры.

Answer 3

Центральность близости - это ранжирование каждого отдельного узла, и его можно рассматривать как меру того, насколько "близко узел находится к центру сети".Таким образом, узел с высоким значением центральности близости расположен в сети так, что этому узлу требуется меньшее количество надежд (в среднем), чтобы достичь всех других узлов в сети.Таким образом, для Q1, приведенного выше, узлы с наивысшей близостью могут быть интерпретированы как находящиеся в лучшем положении, чтобы достичь всех других узлов с минимальным количеством прыжков между узлами на пути.Для Q2 «наименьший путь» можно считать наименьшим средним путем ко всем узлам в сети.