Эффект «взрывной перколяции» в контентной сети

cnn-1.jpg

На проходившей в Киеве 14-15 мая 2014 года научной конференции "Интеллектуальный анализ информации" состоялся доклад А. Снарского и Д. Ландэ, посвященный эффекту "Взрывной перколяции" в контентных сетях.

В рамках доклада был описан метод построения контентной сети (CNC, Content Network Connections), являющийся развитием алгоритма «взрывной перколяции». Описано поведение данной растущей сети, а также фазовый переход первого рода, возникающий при построении такой сети.

Исследование динамики сложных сетей (Complex Networks) [1-2], изменения количества связей, уровней кластерности, других параметров, является актуальной научной и практической задачей, так как большинство реальных сетей (Интернет, WWW, социальные, биологические и др. сети) являются динамичными, растущими. Для таких сетей, в которых течением времени увеличивается число узлов и/или связей, очень важным является эффект возникновения так называемого гигантского кластера (GC,  Giant Cluster), при котором количество узлов самого большого кластера  в ней становится равным по порядку общему количеству узлов. Условия возникновения GC и его свойства хорошо изучены для перколяционных [3] и некоторых других сложных сетей, например, для сетей Эрдоша-Реньи. В частности, для таких сетей условие возникновения GC определяется степенями узлов и задается критерием Моллоя-Рида [4]:  , где  – степень узла, а –  означает усреднение по всем узлам.

На фазе возникновения и роста GC, как в перколяционных, так и в ER и в других сложных сетях, например, в безмасштабных  (SF, Scale Free Networks) [1], некоторые параметры этих сетей (например, размеры максимальных групп связанных узлов – кластеров), ведут себя аналогично  параметрам порядков в теории фазовых переходов второго рода [5] .

«Взрывная перколяция»

 В работе [6] был предложен алгоритм построения растущей сети, который приводит к так называемой взрывной перколяции (EP, Explosive Percolation). В отличие от алгоритма Эрдоша-Реньи, т.е. стандартного случайного порождения (путем «набрасывания») новых связей, этот алгоритм предполагает альтернативу. В соответствии с ним на каждом шагу случайным образом порождается не одна, а две связи, из которых только одна остается (реализуется), а вторая отбрасывается. Критерий отбора реализованной связи определяется сравнением произведений размеров кластеров (количества узлов), соединяемых связями. Из двух выбирается та связь, для которой это произведение наименьшее. Как оказалось, при реализации такого алгоритма, формирование и рост GC принципиально отличается, его размер изменяется скачкообразно, аналогом чего является фазовый переход первого рода, а не второго.

 

Модель контентной сети

 

Авторами предлагается следующая модель контентной сети. Предполагается, что сеть состоит из N узлов. Существует  M различных документов, отдельные экземпляры которых (копии) распределены в узлах контентной сети.  Пусть i-й узел сети содержит  различных документов, причем только по одному экземпляру каждого из них. Узлы можно интерпретировать как библиотеки, веб-сайты, файловые хранилища. Соответственно, документы можно интерпретировать как книги, веб-страницы, файлы, фрагменты файлов и т.п. Предполагается, что распределение количества документов по узлам соответствует закономерности Парето (аналогично распределению богатства в социальных системах), т.е. степенное.

В этом случае для построения растущей сети предложен новый алгоритм порождения связей в контентной сети (CNC, Content Network Connections), являющийся развитием алгоритма EP. В соответствии с ним на каждом шагу случайным образом из всего многообразия документов задаются два различных документа, а затем случайным образом выбираются две пары узлов, содержащих данные документы. В данном случае если хотя бы один выбранный узел не содержит необходимого документа, то происходит случайный выбор следующего узла. Эта процедура выполняется циклически до достижения цели, естественно, должны учитываться условия выхода из «зацикливания», например, путем перехода к выбору другой пары документов.

После этого между выбранными узлами, содержащими разные документы, также  как и в [6] устанавливаются две связи, из которых также остается (реализуется) только одна, а вторая отбрасывается. Критерий отбора реализованной связи в этом случае определялся сравнением общего количества документов, содержащихся в кластерах, узлы которых соединяются связями с выбранными узлами. Из двух связей выбирается та, для которой сумма документов в соответствующих кластерах оказывается наименьшей. Таким образом, документы являются основой построения связей между узлами-библиотеками. На рис.1 представлена абстрактная модель сети из 12 узлов-библиотек, содержащих документы, обозначенные различными фигурами  (закрашенными и не закрашенными треугольниками, квадратами, ромбами и т.д.).

 

 

Рис. 1 – Установление связи в модели контентной сети

 Здесь первое условие, задаваемое при построении новой связи, заключается в установлении связей между узлами, содержащими документы­-треугольники – закрашенный и не закрашенный. Случайным образом выбраны две пары узлов, содержащих требуемые документы: первая – 12 и 3, вторая – 6 и 9. Очевидно, кластер первой пары, содержащий документы из 12-го, 3-го и 2-го узлов (всего 7 документов), значительно меньше по количеству документов кластеру второй пары,  содержащей документы из 6-го, 9-го, 5-го и 8-го узлов (всего 18 документов). Таким образом остается только первая связь (между 12-м и 3-м узлами), а вторая отбрасывается.

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

 

Изменение размера гигантского кластера

 

Авторами были проведены эксперименты для различных и   с целью определения зависимости числа узлов (библиотек) наибольшего кластера от числа связей для предложенного алгоритма CNC. На рис. 2 показана типичная зависимость для эталонного примера, соответствующего алгоритму Эрдоша-Реньи, когда устанавливается связь между первыми выбранными узлами, содержащими требуемую пару  документов (рис 2а), и для CNC (рис 2b) при .

 

 

а

 

b

Рис. 2 – Зависимость размера наибольшего кластера от числа связей при

 

Оценка величины скачка

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

 

Рис. 3 – Зависимость величины скачка  

от размера контентной сети

Пусть  – размер самой большой компоненты связности,   – наибольшее количество связей в растущей контентной сети, при которых , а – наименьшее количество связей, при которых  . В случае непрерывных переходов, разность  линейно зависит от  , в частности,  для сетей Эрдоша-Реньи. В отличие от данного поведения, в случае CNC  зависимость  не является линейной, а может аппроксимироваться зависимостью , , что соответствует поведению, описанному в [6].

Выводы

 При реализации алгоритма CNC, образование и рост GC соответствует поведению, наблюдаемому при реализации алгоритма EP, его величина также изменяется скачкообразно, что также соответствует фазовому переходу первого рода, т. е. так называемой «взрывной перколяции». Как и в [6] небольшие изменения в правилах формирования связей приводит к принципиально новому характеру в протекании процесса формирования сети, что необходимо учитывать в процессе формирования и управления контентными сетями.

Рис. 4 – Зависимость величины  от размера контентной сети

 

Литература

 

1.      Albert R., Barabási A.-L. Statistical mechanics of complex networks // Rev. Mod. Phys., 2002 – 74. – P. 47-97.

2.      Dorogovtsev S.N., Mendes J.F.F. Evolution of Networks. From Biological Nets to the Internet and WWW. – Oxford: Oxford University Press, 2003. – 280 pp.

3.      Stauffer D., Aharony A. Introduction to Percolation Theory.  London: Taylor&Francis, 1992. – 180 pp.

4.      Dorogovtsev S.N., Goltsev A.V., Mendes J.F.F. Critical phenomena in complex networks // Rev. Mod. Phys., 2008. – 80. – P. 1275-1335.

5.      Ландау Л.Д., Лифшиц Е.М. Статистическая физика. Ч.1. – М.: Наука, 1976. – 584 с.

       6.      Achlioptas D., D’Souza R.H., Spenser J. Explosive Percolation in Random Networks // Science, 2009. – 323. – P. 1453-1455.

ВложениеРазмер
dwl-iai14.pdf1.53 МБ