Просмотр исходного текста страницы Комплексные сети

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

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

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

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

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

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

1.	Модель случайного графа. Простейшим примером является сеть, в которой фиксировано число вершин n и ребер m. Из всего множества пар вершин равномерно и случайно выбирается m пар, и между ними проводится ребро. Для случайного графа распределение степеней вершин является пуассоновским.

2.	Конфигурационная модель , в отличие от случайного графа, позволяет построить сеть с заданным законом распределения степеней. 

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

4.	Модель предпочтительного добавления позволяет строить сети со степенным распределением; при этом его характеристики зависят от степени роста сети.
Перечисленные модели позволяют формировать только срезы состояний сети в фиксированные моменты времени. 

Более подробная информация о комплексных сетях размещена в разделе «Учебные материалы».

Литература:
1.	A. Fronczak, P. Fronczak and J. A. Holyst. Self-organized criticality  and coevolution of network structure and dynamics // Phys. Rev. E. 2006. Vol. 73. 

2.	Bollob´as B. Random Graphs. Cambridge: Cambridge Univ. Press, 2001

3.	Broder A., Kumar R., Maghoul F. et al. Graph structure in the web // Computer Networks. 2000. Vol. 33. P. 309—320.

4.	D. Garlaschelli an M. I. Loffredo. Maximum likelihood: Extracting unbiased information from complex networks // Phys. Rev. E. 2008. Vol. 78. 

5.	I. Farkas, I. Derényi, G. Palla and T. Vicsek. Equilibrium statistical mechanics of network structures // Lect. Notes Phys. A, 650 (2004) 163-187

6.	J. Berg and M. Lassig. Correlated Random Networks // Phys. Rev. E. Vol. 89. 2002. 

7.	J. Park and M.E.J. Newman. Statistical mechanics of networks // Phys. Rev. E. 2004. Vol 70. 

8.	Lodge D., 1985, Small World. An Academic Romance, London: Penguin Books

9.	P. M.A. Sloot, S. V. Ivanov, A. V. Boukhanovsky, D. A.M.C. van de Vijver & C. A.B. Boucher, Stochastic simulation of HIV population dynamics through complex network modeling // International Journal of Computer Mathematics. 2008. Vol. 85. P. 1175-1187.

10.	Price D. J. de S. A general theory of bibliometric and other cumulative advantage processes // Journal of the American Society for Information Science. 1976. Vol. 27. P. 292—306.

11.	Redner S. How popular is your paper? An empirical study of the citation distribution // European Physical Journal B. 1998. Vol. 4. P. 131—134.

12.	Wasserman S., Faust K. Social Network Analysis // Cambridge University Press, Cambridge. 1994.

13.	Wooldridge M. An Introduction to Multi-Agent Systems.  –  John Wiley and Sons. – 2002. – 376 p.

14.	Z. Burda, J. Jurkiewicz  and A. Krzywicki. Network transitivity and matrix models // Phys. Rev. E. Vol. 69. 2004.

15.	Болгова Е. В., Иванов С. В., Гринина Е. А., Слоот П. М. А., Бухановский А. В. Параллельные алгоритмы моделирования динамических процессов на комплексных сетях // Известия высших учебных заведений. Приборостроение. 2011. Вып. 10. С. 72—79.

16.	Кормен Т. М.и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS — 2-е изд. — М.: «Вильямс», 2006. — С. 1296.

17.	Ризниченко Г.Ю., Рубин А.Б. Математические модели биологических продукционных процессов. М.: Изд. МГУ, 1993.