Иерархическая сетевая модель - Hierarchical network model

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

Концепция

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

Развитие иерархических сетевых моделей было главным образом мотивировано неудачей других безмасштабных моделей в объединении безмасштабной топологии и высокой кластеризации в одну единую модель. Поскольку несколько реальных сетей (метаболические сети, то сеть взаимодействия белков, то Всемирная паутина или несколько социальные сети ) демонстрируют такие свойства, были введены различные иерархические топологии для учета этих различных характеристик.

Алгоритм

Иерархические сетевые модели обычно получаются итеративным способом путем репликации исходного кластера сети в соответствии с определенным правилом. Например, рассмотрим начальную сеть из пяти полностью связанных узлов (N = 5). В качестве следующего шага создайте четыре реплики этого кластера и подключите периферийные узлы каждой реплики к центральному узлу исходного кластера (N = 25). Этот шаг может повторяться бесконечно, таким образом, для любых k шагов количество узлов в системе может быть получено следующим образом: N = 5^{к + 1}.^[1]

Конечно, в литературе было предложено несколько различных способов создания иерархических систем. Эти системы обычно различаются структурой исходного кластера, а также степенью расширения, которую часто называют фактор репликации модели.^[2]^[3]

Пример иерархической сетевой структуры.

Характеристики

Распределение степеней

Являясь частью семейства безмасштабных моделей, распределение степеней иерархической сетевой модели следует сила закона это означает, что случайно выбранный узел в сети имеет k ребер с вероятностью

{ Displaystyle P влево (к вправо) sim ck ^ {- gamma} ,}

куда c является константой и γ - показатель степени. В большинстве реальных сетей, демонстрирующих безмасштабные свойства γ лежит в интервале [2,3].^[4]

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

{ displaystyle gamma = 1 + { frac { ln M} { ln (M-1)}}}

куда M представляет фактор репликации модели.^[5]

Коэффициент кластеризации

В отличие от других безмасштабных моделей (Эрдеш – Реньи, Barabási – Albert, Watts – Strogatz), где коэффициент кластеризации не зависит от степени конкретного узла, в иерархических сетях коэффициент кластеризации может быть выражен как функция от степени следующим образом:

{ Displaystyle С влево (к вправо) сим к ^ {- бета} ,}

Аналитически показано, что в детерминированных безмасштабных сетях показатель степени β принимает значение 1.^[2]

Примеры

Актерская сеть

На основе базы данных актеров, доступной на www.IMDB.com, сеть определяется Голливуд актеры, которые связаны друг с другом, если они оба появились в одном фильме, что приводит к набору данных из 392 340 узлов и 15 347 957 ребер. Как показали более ранние исследования, эта сеть демонстрирует безмасштабные свойства, по крайней мере, для высоких значений k. Более того, коэффициенты кластеризации, похоже, подчиняются требуемому закону масштабирования с параметром -1, что свидетельствует об иерархической топологии сети. Интуитивно понятно, что у актеров с одним исполнением коэффициент кластеризации по определению равен единице, в то время как актеры, снявшиеся в нескольких фильмах, вряд ли будут работать с одной и той же командой, что в целом приводит к уменьшению коэффициента кластеризации по мере роста числа со-звезд.^[1]

Языковая сеть

Слова можно рассматривать как сеть, если указать критерии связи между ними. Определение ссылок как внешнего вида как синонима в Мерриам-Вебстер словаря была построена семантическая сеть из 182 853 узлов с 317 658 ребрами. Как оказалось, полученная сеть слов действительно следует степенному закону в распределении степеней, в то время как распределение коэффициента кластеризации указывает, что лежащая в основе сеть следует иерархической структуре с γ= 3,25 и β=1.^[1]

Сеть веб-страниц

Путем сопоставления домена www.nd.edu была получена сеть из 325 729 узлов и 1 497 135 ребер, распределение степеней которых следовало степенному закону с γ_из= 2,45 и γ_в= 2.1 для внешних и внутренних градусов соответственно. Свидетельства того, что распределение коэффициентов кластеризации по закону масштабирования значительно слабее, чем в предыдущих случаях, хотя есть четко видимый паттерн спада в распределении C (k) Это означает, что чем больше ссылок в домене, тем меньше взаимосвязаны между собой веб-страницы, на которые есть ссылки.^[1]^[6]

Доменная сеть

В домен сеть, то есть Интернет на уровне автономной системы (AS), где административные домены считаются подключенными в случае, если есть маршрутизатор, который их соединяет, было обнаружено, что она включает 65 520 узлов и 24 412 каналов между ними и демонстрирует свойства масштаба -бесплатная сеть. Выборочное распределение коэффициентов кластеризации было аппроксимировано масштабной функцией С (к) ~ к^−0.75 экспонента которого (в абсолютном выражении) несколько меньше теоретического параметра для детерминированных безмасштабных сетей.^[1]^[7]