Перколяционные сети

Коротко остановимся на еще одном типе сетей -перколяционных. В простейшем варианте перколяционная сеть строится из регулярной, например, квадратной решетки путем вырывания (разрушения) случайным образом выбранных связей. На рис. 1.2.7 оставшиеся связи обозначены жирной линией, вырванные тонкой. Пусть при создании перколяционной сети с вероятностью 1 - р вырываются связи (узлы), тогда она будет будет состоять из рN (N - целое число связей (узлов) ) так называемых черных связей (узлов).

Для каждой такой сети (квадратной, треугольной, шестиугольной, кубической, ...) существует такое значение

(порог протекания), что при

можно пройти по черным связям через всю сеть, а при нет.

На рис. 1.2.8 показана перколяционная сеть большого размера для двух случаев а - ниже порога протекания и б – выше

Рис. 1.2.7 - Квадратная решетка со случайно вырванными связями (тонкие линии)

Для разных решеток - треугольной, квадратной,

кубической и т.п. свой порог протекания численное значение которого можно (за редким исключением) только путем численного моделирования. В Таблице 1.2.1 приведены значения порога протекания для разных решеток.

Рис. 1.2.8 - Перколяционная сеть большого размера. Слева, случай, когда концентрация связей меньше пороговой, справа - больше

Таблица 1.2.1.

Численное значение порога протекания рс

Подчеркнуты значения рс, которые определены точно. Первый столбец - задача узлов, второй - задача связей.

При вычислении рс размер решетки выбирается достаточно большим (в теории - бесконечным), так что значение pc перестает зависеть от полного числа узлов - N или связей.

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

В этом отношении - бесконечный кластер аналогичен Giant Cluster в сложных сетях, например в сети ER. Существует как общее так и отличное в свойствах бесконечного кластера в теории протекания и в Giant Cluster в теории сложных сетей.

Обозначая для краткости Giant Cluster как GC и бесконечный кластер как PC отметим следующее.

Для перколяции на решетке Келли pc = 1/ (z — l), где z - координатное число, для GC ER сети координатное число из N связей равно N — 1, а для N >> 1 pc = 1/ N. Таким образом при увеличении N pc уменьшается, что аналогично увеличению пространственной размерности перколяционной сети. В этом случае теория сложных сетей ( ER ) в пределе N →∞ аналогично перколяции в бесконечно мерном пространстве.

Как в задаче о GC так и в задаче о PC при p < pc вероятность появления GC и PC равна нулю.

Выше порога протекания, при p> pc размер GC равен ( f (pcN) — f (pN)) N, где f - экспоненциально убывающая функция с f(l) = 1, в то время как размер PC равен (p — pc) N.

Еще одно отличие заключается в структуре, GC- это деревья, в то время как PC имеет фрактальную структуру.

Более подробно перколяционные сети описаны во второй части данного учебного пособия.

Примеры реальных сетей

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

• 1. World Wide Web: Количество веб-сайтов -919,533,715 (по состоянию на март 2014 года по данным службы Netcraft, рис. 1.3.1), охватывающих свыше триллиона ("1012 ) вебстраниц. Однонаправленные связи между отдельными веб-страницами реализуются в виде гиперссылок.
• 2. Internet - "Физическая сеть" (рис. 1.3.2, 1.3.3);
• 3. Протеиновые сети (рис. 1.3.4);
• 4. Сеть метаболизма;
• 5. Экологические сети;
• 6. Сеть телефонных звонков;
• 7. Сеть связей террористов;
• 8. Сеть цитирования (ациклическая);
• 9. Лингвистическая (сеть связанных слов);
• 10. Нейронные сети.

Рис. 1.3.1 - Динамика развития сети World Wide Web по данным службы Netcraft (netcraft.com)

Рис. 1.3.2 - Динамика роста количества Интернет-доменов по информации службы isc.org

Рис. 1.3.3 - Карта связей Интернет-серверов как сложная сеть (по данным wikipedia.org)

Рис. 1.3.4 - Протеиновая сеть (проект Protein Structure Initiative, сайт helixscript.com)