WikiDer > Иерархическая сетевая модель

Hierarchical network model
Сетевая наука
Internet_map_1024.jpg
Типы сетей
Графики
Функции
Типы
Модели
Топология
Динамика
  • Списки
  • Категории

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

Концепция

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

Аналитически показано, что в детерминированных безмасштабных сетях показатель степени β принимает значение 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]

Рекомендации

  1. ^ а б c d е Ravasz, E.B .; Барабаши, А. Л. С. (2003). «Иерархическая организация в сложных сетях». Физический обзор E. 67 (2): 026112. arXiv:cond-mat / 0206130. Bibcode:2003PhRvE..67b6112R. Дои:10.1103 / PhysRevE.67.026112. PMID 12636753.
  2. ^ а б Дороговцев, С .; Гольцев, А .; Мендес, Дж. (2002). «Псевдофрактальная безмасштабная паутина». Физический обзор E. 65 (6): 066122. arXiv:cond-mat / 0112143. Bibcode:2002PhRvE..65f6122D. Дои:10.1103 / PhysRevE.65.066122. PMID 12188798.
  3. ^ Barabási, A. L. S .; Ravasz, E.B .; Вичек, Т. С. (2001). «Детерминированные безмасштабные сети». Physica A: Статистическая механика и ее приложения. 299 (3–4): 559. arXiv:cond-mat / 0107419. Bibcode:2001PhyA..299..559B. Дои:10.1016 / S0378-4371 (01) 00369-7.
  4. ^ Barabási, A .; Альберт, Р. (1999). «Появление масштабирования в случайных сетях». Наука. 286 (5439): 509–512. arXiv:cond-mat / 9910332. Bibcode:1999Научный ... 286..509Б. Дои:10.1126 / science.286.5439.509. PMID 10521342.
  5. ^ Но, Дж. (2003). «Точные масштабируемые свойства иерархической сетевой модели». Физический обзор E. 67 (4). arXiv:cond-mat / 0211399. Bibcode:2003PhRvE..67d5103N. Дои:10.1103 / PhysRevE.67.045103.
  6. ^ Barabási, A. L. S .; Альберт, Р. К .; Чон, Х. (1999). «Интернет: диаметр всемирной паутины». Природа. 401 (6749): 130. arXiv:cond-mat / 9907038. Bibcode:1999Натура 401..130А. Дои:10.1038/43601.
  7. ^ Васкес, А .; Pastor-Satorras, R .; Веспиньяни, А. (2002). «Масштабные топологические и динамические свойства Интернета». Физический обзор E. 65 (6): 066130. arXiv:cond-mat / 0112400. Bibcode:2002ПхРвЭ..65ф6130В. Дои:10.1103 / PhysRevE.65.066130. PMID 12188806.