Иерархическая сетевая модель
| Часть серии о | ||||
| Сетевая наука | ||||
|---|---|---|---|---|
| Типы сетей | ||||
| Графики | ||||
| ||||
| Модели | ||||
| ||||
| ||||
Иерархические сетевые модели представляют собой итерационные алгоритмы создания сетей способные воспроизводить уникальные свойства безмасштабной топологии и высокую кластеризацию узлов , одновременно . Эти характеристики широко наблюдаются в природе: от биологии до языка и некоторых социальных сетей .
Концепция [ править ]
Иерархическая сетевая модель является частью семейства безмасштабных моделей, их основным свойством является наличие пропорционально большего количества концентраторов среди узлов, чем при случайной генерации; однако она значительно отличается от других подобных моделей ( Барабаши-Альберта , Уоттса-Строгаца ) распределением коэффициентов кластеризации узлов: поскольку другие модели предсказывают постоянный коэффициент кластеризации как функцию степени узла , в иерархических Ожидается, что узлы моделей с большим количеством ссылок будут иметь более низкий коэффициент кластеризации. Более того, хотя модель Барабаши-Альберта предсказывает уменьшение среднего коэффициента кластеризации по мере увеличения числа узлов, в случае иерархических моделей нет никакой связи между размером сети и ее средним коэффициентом кластеризации.
Разработка иерархических сетевых моделей была главным образом мотивирована неспособностью других безмасштабных моделей объединить безмасштабную топологию и высокую кластеризацию в одну единственную модель. Поскольку несколько реальных сетей ( метаболические сети , сеть взаимодействия белков , Всемирная паутина или некоторые социальные сети ) обладают такими свойствами, для учета этих различных характеристик были введены различные иерархические топологии.
Алгоритм [ править ]
Иерархические сетевые модели обычно создаются итеративным путем путем репликации исходного кластера сети по определенному правилу. Например, рассмотрим исходную сеть из пяти полностью взаимосвязанных узлов (N=5). В качестве следующего шага создайте четыре реплики этого кластера и подключите периферийные узлы каждой реплики к центральному узлу исходного кластера (N=25). Этот шаг можно повторять бесконечно, при этом для любых k шагов количество узлов в системе можно определить как N=5. к+1 . [1]
Конечно, в литературе предлагалось несколько различных способов создания иерархических систем. Эти системы обычно различаются по структуре исходного кластера, а также по степени расширения, которую часто называют коэффициентом репликации модели. [2] [3]
Свойства [ править ]
Распределение степеней [ править ]
Являясь частью семейства безмасштабных моделей, распределение степеней иерархической сетевой модели подчиняется степенному закону, означающему, что случайно выбранный узел в сети имеет k ребер с вероятностью
где c — константа, а γ — показатель степени. В большинстве сетей реального мира, демонстрирующих безмасштабные свойства, γ лежит в интервале [2,3]. [4]
В качестве конкретного результата для иерархических моделей было показано, что показатель степени функции распределения может быть рассчитан как
где M представляет собой коэффициент репликации модели. [5]
Коэффициент кластеризации [ править ]
В отличие от других безмасштабных моделей ( Эрдёша–Реньи , Барабаши–Альберта, Уоттса–Строгаца), где коэффициент кластеризации не зависит от степени конкретного узла, в иерархических сетях коэффициент кластеризации может быть выражен как функция степень следующим образом:
Аналитически показано, что в детерминированных безмасштабных сетях показатель степени β принимает значение 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 ребер, распределение степеней которых соответствовало степенному закону с γ out =2,45 и γ in =2,1 для исходящих и входящих степеней соответственно. Доказательства распределения коэффициентов кластеризации по закону масштабирования значительно слабее, чем в предыдущих случаях, хотя в распределении C(k) четко заметна тенденция снижения , указывающая на то, что чем больше связей в домене, тем менее взаимосвязаны связанные/связывающие связи. веб-страницы есть. [1] [6]
Доменная сеть [ править ]
сеть Было обнаружено, что доменная , то есть Интернет на уровне автономной системы (AS), где административные домены считаются соединенными в случае наличия соединяющего их маршрутизатора, включает 65 520 узлов и 24 412 связей между ними и демонстрирует свойства безмасштабируемая сеть. Выборочное распределение коэффициентов кластеризации аппроксимировалось масштабирующей функцией C(k)~k −0.75 показатель степени которого (в абсолютном выражении) несколько меньше теоретического параметра для детерминированных безмасштабных сетей. [1] [7]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д и Равас, Е.Б.; Барабаши, БАС (2003). «Иерархическая организация в сложных сетях». Физический обзор E . 67 (2): 026112. arXiv : cond-mat/0206130 . Бибкод : 2003PhRvE..67b6112R . дои : 10.1103/PhysRevE.67.026112 . ПМИД 12636753 .
- ^ Jump up to: Перейти обратно: а б Дороговцев С.; Гольцев А.; Мендес, Дж. (2002). «Псевдофрактальная безмасштабная сеть». Физический обзор E . 65 (6): 066122. arXiv : cond-mat/0112143 . Бибкод : 2002PhRvE..65f6122D . дои : 10.1103/PhysRevE.65.066122 . ПМИД 12188798 .
- ^ Барабаши, БАС; Равас, Е.Б.; Вичек, Т.С. (2001). «Детерминированные безмасштабные сети». Физика А: Статистическая механика и ее приложения . 299 (3–4): 559. arXiv : cond-mat/0107419 . Бибкод : 2001PhyA..299..559B . дои : 10.1016/S0378-4371(01)00369-7 .
- ^ Барабаши, А.; Альберт, Р. (1999). «Появление масштабирования в случайных сетях». Наука . 286 (5439): 509–512. arXiv : cond-mat/9910332 . Бибкод : 1999Sci...286..509B . дои : 10.1126/science.286.5439.509 . ПМИД 10521342 .
- ^ Но, Дж. (2003). «Точные масштабирующие свойства иерархической сетевой модели». Физический обзор E . 67 (4). arXiv : cond-mat/0211399 . Бибкод : 2003PhRvE..67d5103N . дои : 10.1103/PhysRevE.67.045103 .
- ^ Барабаши, БАС; Альберт, РК; Чон, Х. (1999). «Интернет: диаметр Всемирной паутины». Природа . 401 (6749): 130. arXiv : cond-mat/9907038 . Бибкод : 1999Natur.401..130A . дои : 10.1038/43601 .
- ^ Васкес, А.; Пастор-Саторрас Р.; Веспиньяни, А. (2002). «Крупномасштабные топологические и динамические свойства Интернета». Физический обзор E . 65 (6): 066130. arXiv : cond-mat/0112400 . Бибкод : 2002PhRvE..65f6130V . дои : 10.1103/PhysRevE.65.066130 . ПМИД 12188806 .