Как проверить статистически, является ли моя сеть (график) сетью «маленького мира» или нет?

10

Малой мировая сеть представляет собой тип математического графа , в котором большинство узлов не являются соседями друга с другом, но большинство узлов могут быть достигнуты с любым другим небольшим числом прыжков или шагов. В частности, сеть малого мира определяется как сеть, в которой типичное расстояние L между двумя случайно выбранными узлами (требуемое количество шагов) растет пропорционально логарифму числа узлов N в сети, то есть

Llog(N)

Эта связь между L и N является «правилом большого пальца». Я ищу более профессиональное определение графиков маленького мира для моего исследования. Как я могу проверить, является ли мой граф графом маленького мира или нет?

Мир тесен состоял из нескольких экспериментов , проведенных Стэнли Милгрэмом и другими исследователями , исследующих среднюю длину пути для социальных сетей людей в Соединенных Штатах. Исследование было новаторским в том смысле, что оно предполагало, что человеческое общество представляет собой сеть маленького мирового типа, характеризующуюся короткими путями. Эксперименты часто ассоциируются с фразой «шесть степеней разделения», хотя Милграм сам не использовал этот термин.

Заранее спасибо.

Юбель Йилдмар
источник
2
Я не знаю, какова цель вашего папы или вашего происхождения. У вас есть реальный график, который вы хотите проверить? Вы можете принять основные описательные меры вашего графа, что подойдет любая библиотека графов (например, networkx в python или igraph в R). Просто проверьте, подключена ли ваша сеть, каков ее диаметр, средний кратчайший путь и т. Д. Если вы генерируете график или ваш контекст отличается, я бы сказал, что для ответа на ваш вопрос требуется больше информации.
lrnzcig
2
Чтобы оценить наличие этих логарифмических отношений, я думаю, вам понадобится ряд значений. Например, последовательность снимков вашего графика, эволюционирующая во времени. Или набор различных графиков, соответствующих сходным (сопоставимым) системам (например, компьютерные сети нескольких фирм различных размеров).
Винсент Лабатут

Ответы:

7

TL; DR:

Ты не можешь

Что обычно делается

Текущее «современное состояние» при определении того, является ли сеть маленьким миром, использует следующий подход:

  1. LC

  2. Сформировать соответствующий ансамбль нуль-модель сетей, такие как Эрдеш-Рение случайных графов , или Маслов-Sneppen случайных графов .

  3. LрСр

  4. λзнак равноL/Lрγзнак равноС/Ср

  5. λγλ1γ>1

Идея этого заключается в том, что:

  • Сети малого мира должны иметь некоторую пространственную структуру, что отражается в высоком коэффициенте кластеризации. Напротив, случайные сети не имеют такой структуры и низкого коэффициента кластеризации.

  • Сети малого мира эффективны в общении и похожи, и поэтому имеют небольшую кратчайшую длину пути, сравнимую с таковой в случайных сетях. Напротив, чисто пространственные сети имеют высокую длину кратчайшего пути.

Где проблемы

  • Это ничего не говорит о том, как средний кратчайший путь масштабируется с размером сети. На самом деле, для реальных сетей все приведенное вами определение не может быть применено, поскольку не существует такой вещи, как одна и та же сеть с разным количеством узлов.

  • λγ

    Сеть малого мира - это пространственная сеть с добавленными дальними связями.

    λγ

  • Вышеуказанный метод не устойчив к ошибкам измерения. Небольших ошибок при создании сети из измерений достаточно, чтобы, например, решетка выглядела как сеть малого мира, см., Например, Bialonski et al., Chaos (2010) и Papo et al., Front. Hum. Neurosci. (2016) . На самом деле, я не знаю ни одного исследования, в котором утверждается, что какая-то эмпирическая сеть не является сетью маленького мира.

Sidenote: Что бы вы получили?

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

Полный отказ от ответственности: одна из вышеупомянутых работ принадлежит моей непосредственной академической близости.

Wrzlprmft
источник
Кроме того, знаете ли вы какой-либо документ, в котором приведена методика, упомянутая вами в этом ответе. Создание ансамбля сетей, вычисление его среднего и т. Д.
Последнее слово
@TheLastWord: Кроме того, знаете ли вы какой-либо документ, в котором приведена методология, упомянутая вами в этом ответе. - В документе Bialonski et al. Обобщен этот подход, и он должен содержать соответствующие ссылки. Также см. Этот документ мой .
Wrzlprmft
2

Индекс малости мира можно вычислить в «R» с помощью функции smallworldness в пакете qgraph .

Это основано на: Humphries, MD, & Gurney, K. (2008). Сеть " маломирность": количественный метод определения эквивалентности канонической сети . PLoS One, 3 (4), e0002051

Из бумаги:

«Сеть теперь считается« маленьким миром », если S> 1 - утверждение, которое может быть проверено статистически».

Скотт Баттон
источник