Эволюция случайной сети - Evolution of a random network

Эволюция случайной сети - динамичный процесс, обычно приводящий к возникновению гигантский компонент сопровождается поразительными последствиями для топологии сети. Чтобы количественно оценить этот процесс, необходимо выяснить, как размер самого большого подключенного кластера в сети, ${\displaystyle {N_{G}}}$, варьируется в зависимости от среднего степень ${\displaystyle {\left\langle k\right\rangle }}$.^[1] Сети меняют свою топологию по мере развития, претерпевая фазовые переходы. Фазовые переходы обычно известны из физики, где они происходят, когда материя меняет состояние в соответствии с уровнем своей тепловой энергии, или когда в некоторых материалах проявляются ферромагнитные свойства при их остывании. Такие фазовые переходы происходят в материи, потому что это сеть частиц, и поэтому правила фазового перехода сети непосредственно применяются к ней. Фазовые переходы в сетях происходят по мере того, как ссылки добавляются к сети, что означает, что при наличии N узлов в каждом временном приращении связь устанавливается между случайно выбранной парой из них. Преобразование набора отключенных узлов в полностью подключенную сеть называется развитием сети.

Если мы начнем с сети, имеющей N полностью отключенных узлов (количество ссылок равно нулю), и начнем добавлять ссылки между случайно выбранными парами узлов, начнется эволюция сети. Некоторое время мы будем просто создавать пары узлов. Через некоторое время некоторые из этих пар соединятся, образуя маленькие деревья. По мере того, как мы продолжаем добавлять больше ссылок в сеть, наступает момент, когда в сети появляется гигантский компонент, поскольку некоторые из этих изолированных деревьев соединяются друг с другом. Это называется критической точкой. В нашем естественном примере эта точка соответствует температурам, при которых материалы меняют свое состояние. При дальнейшем добавлении узлов в систему гигантский компонент становится еще больше, поскольку все больше и больше узлов получают ссылку на другой узел, который уже является частью гигантского компонента. Другой особенный момент в этом переходе - это когда сеть становится полностью связанной, то есть когда все узлы принадлежат одному гигантскому компоненту, которым фактически является сама сеть в этой точке.^[1]

Условия появления гигантского компонента

в Модель Эрдеша – Реньи,^[2][3] среднее степень ${\displaystyle \langle k\rangle }$ графа с n вершинами и N ребрами задается формулой ${\displaystyle \langle k\rangle ={\frac {2N}{n}}}$Условием появления гигантского компонента является:

${\displaystyle {\left\langle k\right\rangle =1}}$.

Таким образом, одного звена достаточно для появления гигантской составляющей.^{[нужна цитата ]}.Если условие выражается через ${\displaystyle {p}}$, получается^{[нужна цитата ]}:
${\displaystyle {P_{c}={\frac {1}{N-1}}\approx {\frac {1}{N}}}}$ (1)
Где ${\displaystyle {N}}$ количество узлов, ${\displaystyle {P_{c}}}$ это вероятность кластеризация^{[нужна цитата ]}. Следовательно, чем больше сеть, тем меньше ${\displaystyle {p}}$ достаточно для гигантского компонента.

Режимы эволюции случайной сети

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

Субкритический режим

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

${\displaystyle {0<\left\langle k\right\rangle <1}}$, ${\displaystyle {\left(p<{\frac {1}{n}}\right)}}$

За ${\displaystyle {\left\langle k\right\rangle =0}}$ сеть состоит из ${\displaystyle {N}}$ изолированные узлы. Увеличение ${\displaystyle {\left\langle k\right\rangle }}$ означает добавление ${\displaystyle {N\left\langle k\right\rangle =pN(N-1)/2}}$ ссылки в сеть. Тем не менее, учитывая, что ${\displaystyle {\left\langle k\right\rangle <1}}$, в этом режиме есть только небольшое количество звеньев, поэтому можно наблюдать в основном крошечные кластеры. В любой момент самый крупный кластер можно обозначить как гигантский компонент. Однако в этом режиме относительный размер самого большого кластера${\displaystyle {\frac {N_{G}}{N}}}$, остается нулевым. Причина в том, что для ${\displaystyle {\left\langle k\right\rangle <1}}$ самый большой кластер - это дерево размером ${\displaystyle {N_{G}\sim lnN}}$, следовательно, его размер увеличивается намного медленнее, чем размер сети. ${\displaystyle {N_{G}/N=lnN/N\rightarrow 0}}$ в ${\displaystyle {N\rightarrow \infty }}$ Таким образом, в докритическом режиме сеть состоит из множества крошечных компонентов, размер которых следует экспоненциальному распределению. Следовательно, эти компоненты имеют сопоставимые размеры, и нет явного победителя, которого мы могли бы назвать гигантом.^[1]

Критическая точка

По мере того, как мы продолжаем соединять узлы, соединяющиеся пары образуют небольшие деревья, и если мы продолжаем соединять узлы, в критической точке = 1 появляется различимый гигантский компонент.

Это означает, что в тот момент, когда каждый компонент имеет в среднем 1 ссылку, появляется гигантский компонент. Эта точка соответствует вероятности p = 1 / (N-1), так как вероятность наличия связи между двумя узлами - это отношение одного случая, когда эта одна ссылка соединяет два случайно выбранных узла, деленное на все другие возможности, как это одно соединение может соединять один из узлов с другим узлом, которым является N-1, поскольку узел может подключаться ко всем другим узлам, кроме самого себя (исключая возможность петли в этой модели).

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

${\displaystyle {0<\left\langle k\right\rangle =1}}$, ${\displaystyle {\left(p={\frac {1}{n}}\right)}}$.

Критическая точка отделяет режим, в котором еще нет гигантской компоненты ( ${\displaystyle {0<\left\langle k\right\rangle <1}}$ ) от режима, в котором есть один ( ${\displaystyle {\left\langle k\right\rangle >1}}$ ). На этом этапе относительный размер самого большого компонента все еще равен нулю. Действительно, размер самого большого компонента равен ${\displaystyle {N_{G}\sim N^{\tfrac {2}{3}}}}$. Как следствие, ${\displaystyle {N_{G}}}$ растет намного медленнее, чем размер сети, поэтому ее относительный размер уменьшается по мере ${\displaystyle {{\frac {N_{G}}{N}}\sim N^{-{\tfrac {1}{3}}}}}$ в ${\displaystyle {N\rightarrow \infty }}$ Отметим, однако, что в абсолютном выражении наблюдается значительный скачок размера самого большого компонента при ${\displaystyle {\left\langle k\right\rangle =1}}$Например, для случайной сети с ${\displaystyle {N=7\ast 109}}$ узлов, сопоставимых с социальной сетью земного шара, для ${\displaystyle {0<\left\langle k\right\rangle <1}}$ самый большой кластер порядка ${\displaystyle {N_{G}\simeq lnN=ln(7\ast 109)\simeq 22.7}}$. В отличие от ${\displaystyle {\left\langle k\right\rangle =1}}$ мы ожидаем ${\displaystyle {N_{G}\simeq N^{\tfrac {2}{3}}=(7\ast 109){\tfrac {2}{3}}\sim 3\ast 106}}$, скачок примерно на пять порядков. Тем не менее, как в докритическом режиме, так и в критической точке самый большой компонент содержит только исчезающую часть от общего количества узлов в сети. Таким образом, в критической точке большинство узлов расположены в многочисленных небольших компонентах, распределение которых по размерам следует . Форма степенного закона показывает, что сосуществуют компоненты довольно разных размеров. Эти многочисленные небольшие компоненты в основном представляют собой деревья, тогда как гигантский компонент может содержать петли. Обратите внимание, что многие свойства сети в критической точке напоминают свойства физической системы, находящейся в фазе.^[1]

Сверхкритический режим

Как только гигантский компонент появится после прохождения критической точки, по мере добавления новых подключений сеть будет состоять из растущего гигантского компонента и все меньше и меньше изолированных кластеров и узлов. Большинство реальных сетей принадлежат этому режиму. Размер гигантского компонента описывается как Ng = (p - pc) N.

${\displaystyle {\left\langle k\right\rangle >1}}$, ${\displaystyle {\left(p>{\frac {1}{n}}\right)}}$.

Этот режим имеет наибольшее отношение к реальным системам, поскольку впервые у нас есть гигантский компонент, похожий на сеть. Вблизи критической точки размер гигантской компоненты изменяется как:
${\displaystyle {N_{G}/N\sim \left\langle k\right\rangle -1}}$
или же
${\displaystyle {N_{G}\sim (p-p_{c})N}}$ (2)
где pc определяется формулой (1). Другими словами, гигантский компонент содержит конечную долю узлов. Чем дальше мы продвинемся от критической точки, тем большая часть узлов будет ей принадлежать. Отметим, что (2) справедливо только в окрестности ${\displaystyle {\left\langle k\right\rangle =1}}$. Для больших ${\displaystyle {\left\langle k\right\rangle }}$ зависимость между ${\displaystyle {N_{G}}}$ и ${\displaystyle {\left\langle k\right\rangle }}$ Таким образом, в сверхкритическом режиме многочисленные изолированные компоненты сосуществуют с гигантским компонентом, причем их распределение по размерам следует экспоненциальному распределению. Эти маленькие компоненты представляют собой деревья, а гигантский компонент содержит циклы и циклы. Сверхкритический режим длится до тех пор, пока все узлы не будут поглощены гигантом.^[1]

Подключенный режим

По мере добавления подключений к сети наступает момент, когда = lnN, и гигантский компонент поглощает все узлы, поэтому не существует изолированных узлов или несвязанных компонентов.

${\displaystyle {\left\langle k\right\rangle >\ln N}}$, ${\displaystyle {\left(p>{\frac {\ln N}{N}}\right)}}$.

При достаточно большом p гигантская компонента поглощает все узлы и компоненты, следовательно, ${\displaystyle {N_{G}\simeq N}}$. При отсутствии изолированных узлов сеть становится связанной. Средняя степень, в которой это происходит, зависит от ${\displaystyle {N}}$ в качестве ${\displaystyle {\left({\frac {\ln N}{N}}\right)\rightarrow 0}}$. Обратите внимание, что когда мы входим в режим подключения, сеть все еще относительно разреженная, так как ${\displaystyle {\left({\frac {\ln N}{N}}\right)\rightarrow 0}}$ при больших N. Сеть превращается в полный граф только при ${\displaystyle {\left\langle k\right\rangle =N-1}}$Таким образом, случайная сетевая модель предсказывает, что возникновение сети не является плавным, постепенным процессом: изолированные узлы и крошечные компоненты, наблюдаемые для малого , коллапсируют в гигантский компонент через фазу.^[1]

Примеры явлений в природе

Переход вода-лед

Фазовые переходы происходят в материи, поскольку ее можно рассматривать как сеть частиц. Когда вода замороженный, при достижении 0 градусов (критическая точка) кристаллическая структура льда возникает в соответствии с фазовыми переходами случайных сетей: по мере охлаждения каждая молекула воды прочно связывается с четырьмя другими молекулами, образуя решетку льда, которая является возникающей сеткой.

Магнитный фазовый переход

Аналогично магнитный фазовый переход в ферромагнитный материалы также следуют схеме эволюции сети: выше определенной температуры, спины отдельных атомов могут указывать в двух разных направлениях. Однако после охлаждения материала по достижении определенной критической температуры спины начинают указывать в том же направлении, создавая магнитное поле. Возникновение магнитных свойств в структуре материала напоминает эволюцию случайной сети.^[1]

Приложения

Физика и химия

Как мы могли видеть в приведенных выше примерах, теория сетей применяется к структуре материалов, поэтому она также применяется в исследованиях, связанных с материалами и их свойствами в физике и химии.

Особо важными направлениями являются полимеры,^[4] гели,^[5] и другие материальные разработки, такие как целлюлоза с настраиваемыми свойствами.^[6]

Биология и медицина

Фазовые переходы используются в исследованиях, связанных с функционированием белков или возникновением диабета на клеточном уровне.^[7] Нейробиология также широко использует модель эволюции сетей, поскольку в нейронных сетях происходят фазовые переходы.^[8]

Сетевые науки, статистика и машинное обучение

Фазовый переход сети, естественно, также является строительным блоком для более продвинутых моделей в рамках ее собственной дисциплины. Он возвращается в исследованиях, посвященных кластеризации и перколяции в сетях,^[9] или предсказание свойств узла.^[10]

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

1. Альберт-Ласло Барабаши. Сетевые науки: Глава 3
2. Эрдеш, Пол и Альфред Реньи. «Об эволюции случайных графов». Publ. Математика. Inst. Подвешенный. Акад. Sci 5.1 (1960): 17-60. http://leonidzhukov.net/hse/2014/socialnetworks/papers/erdos-1960-10.pdf
3. Эрдеш П., Реньи А. «О случайных графах I.» Publ. математика. debrecen 6.290-297 (1959): 18. http://www.leonidzhukov.net/hse/2016/networks/papers/erdos-1959-11.pdf
4. Самулионис В., Свирскас Ш., Банис Й., Санчес-Феррер А., Химено Н. и Рос М. Б. (2015). Фазовые переходы в смектических изогнутых полимерных сетях основной цепи, обнаруженные диэлектрическими и ультразвуковыми методами. Сегнетоэлектрики, 479(1), 76-81. Дои:10.1080/00150193.2015.1012011
5. Habicht, A., Schmolke, W., Lange, F., Saalwachter, K., & Seiffert, S. (нет данных). Отсутствие влияния неоднородностей полимерной сети на фазовые переходы объема микрогеля: поддержка перспективы среднего поля. Макромолекулярная химия и физика, 215(11), 1116-1133.
6. Лю Ч., Чжун Г., Хуанг Х. и Ли З. (без даты). Индуцированный фазовой сборкой переход трехмерных нанофибрилл в листовые сети в пористой целлюлозе с регулируемыми свойствами. Целлюлоза, 21(1), 383-394.
7. Стампер И., Джексон Э. и Ван X. (без даты). Фазовые переходы в клеточных сетях островков поджелудочной железы и последствия для диабета 1 типа. Физический обзор E, 89(1),
8. Ли, К.Е. Лопес, М.А. Мендес, Дж. Ф.Ф. Гольцев, А.В. (2014). «Критические явления и индуцированные шумом фазовые переходы в нейронных сетях». Физический обзор E. 89: 012701. arXiv:1310.4232. Bibcode:2014PhRvE..89a2701L. Дои:10.1103 / PhysRevE.89.012701.
9. Коломер-де-Симон, П., и Богуна, М. (2014). Двойной перколяционный фазовый переход в кластерных сложных сетях.
10. Чжан П., Мур К. и Здеборова, Л. (2014). Фазовые переходы при полууправляемой кластеризации разреженных сетей.