Безмасштабные сети: статистическая аберрация или природная тенденция

Частичный перевод статьи “Rare and everywhere: Perspectives on scale-free networks” Petter Holme с дополнениями

В 1999 году Барабаши и Альберт опубликовали свою работу “Emergence of scaling in random networks” [1], которая заложила основы междисциплинарных сетевых исследований. Они описали в этой работе для трёх эмпирических сетей следующий факт: “вероятность P(k) того факта, что вершина имеет степень k описывается степенным законом в эмпирических сетях”. Они объяснили это спецификой механизмов роста сети, когда новые вершины присоединяются ребрами к уже существующим вершинам с вероятностью пропорциональной степени существующих вершин. В последующие годы вышло большое количество статей, в которых описывались другие эмпирические сети, распределение степеней вершин в которых отвечало данному степенному закону. Такие сети в итоге и стали называть безмасштабными сетями (англ. skale-free networks).

Одна из наиболее часто встречающихся формул в современной сетевой науке

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

Паттерны безмасштабности возникают во многих системах (общность организации в разных масштабах, например, пространственных): от береговых линий, стволов деревьев и брокколи до степенного распределения степеней вершин в сетях. Распределение степеней вершин может быть безмасштабным в том смысле, что утверждения по типу «вершин степени 2000 вдвое больше, чем со степенью 3000», верны, даже если изменить масштаб в 10 раз или в 10³ [2].

Ещё одна концепция теории о сложных системах, важная для понимания интереса к безмасштабным сетям, — это универсальность. Типы эмерджентных свойств систем часто являются следствием базовых симметрий и правил поведения отдельных элементов систем. Так, например, стаи птиц разных видов могут иметь схожие паттерны стайного поведения. Это означает, что довольно разные системы могут иметь общие эмерджентные свойства — Барабаши и Альберт утверждали, что безмасштабность сетей является таким универсальным эмерджентным явлением, которое присуще многим сложным системам.

Однако уверенность Барабаши и Альберта в повсеместной представленности безмасштабных сетей разделяют далеко не все. Критики отмечают, что распределение степеней вершин не зависит от масштаба, реальные сети далеко не всегда обладают этим свойством [2]. А также, что степенной закон распределения степеней вершин уже был описан ранее [3]. Звучали и утверждения о том, что распределение степеней вершин далеко не всегда или почти никогда не подчиняется степенному закону.

Первая статья, в которой использовались статистические тесты для опровержения заявленной универсальности свойства безмасштабности в естественных сетях — работа Джонса и Хэндкока [4]. Однако более влиятельной и показательной оказалась статья Клаузета, Шализи и Ньюмана [5], в которой они предложили статистический метод оценки безмасштабности сети (важно, что их критерий работает только на конечных сетях не больше некоторого размера). До этого исследователи обычно строили гистограммы распределения степеней вершин в двойном логарифмическом масштабе и если такие графики были достаточно “прямыми”, они называли это степенным законом. Замена этого метода — неточного и подверженного субъективным искажениям с позиции интерпретатора на формальный критерий проверки — важная веха в сетевой науке.

В статье “Scale-free networks are rare”, опубликованной в Nature Communications [6], Бройдо и Клаузет исследуют структуру 927 эмпирических сетей (по сравнению с 7 в [5]) и используют тот факт, что богатые информацией сетевые данные могут быть сведены к анализу множества простых сетей. Исследую степень близости взятых в анализе сетей к безмасштабным, Бройдо и Клаузет выделяют 5 классов среди них (по степени близости к безмасштабным — от «сверхслабых» до «очень сильных». Они обнаружили, что 57% сетей из выборки относятся по крайней мере к какому-то безмасштабному классу из выделенных пяти, в то время как только 4% относятся к категории «очень сильных». Более того, в то время как биологические и искусственные технологические сети (как интернет) могут достигать «очень сильного» уровня, социальные сети могут быть в лучшем случае относится к классу «слабых» безмасштабных сетей.

Когда статья “Scale-free networks are rare” появились в виде препринта в январе 2018 года, то тут же вызвала бурную онлайн-активность вокруг себя, в том числе появление статьи в блоге Барабаши и длительные обсуждения в социальных сетях. Наиболее распространенные аргументы против утверждения о том, что безмасштабные сети встречаются редко, связаны с истоками теории сложных систем — с тем фактом, что безмасштабность четко определена только в пределе бесконечного размера сети. Согласно этой точке зрения, сеть является безмасштабной, если распределение её степеней приближается к степенному закону, поскольку сеть продолжает расти, следуя одним и тем же механизмам. Таким образом, флуктуации, из-за которых сеть не проходит статистические тесты, не имеют значения, потому что, если позволить сети свободно развиваться, то она сможет вскоре пройти тест, что описано в статье того же года “Scale-free networks well done” [7].

На текущий момент в сетевой науке есть два лагеря ученых: первые считают, что безмасштабные сети обладают свойством универсальности и просто существуют как идеальные объекты в платоновском мире, а мы сталкиваемся лишь с различными этапами их развития в природе, где в пределе они бы сошлись к одной модели; вторые же видят их только как частные конкретные примеры и не признают права на универсальность за свойством безмасштабности сетей. Ученые часто насмехаются над гуманитарными науками с их школами мысли и отсутствием единого парадигмального консенсуса или даже явно выделенного предмета исследования [8], но подобные проблемы встречаются не только там…

Основное направление современных исследований должно быть направлено на выявление универсальных механизмов роста эмпирических сетей [9].

1. Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999).
2. 2. Tanaka, R. Scale-rich metabolic networks. Phys. Rev. Lett. 94, 168101 (2005).
3. Newman, M. E. J. The structure and function of complex networks. SIAM Rev. 45, 167–256 (2003).
4. Jones, J. H. & Handcock, M. S. Sexual contacts and epidemic thresholds. Nature 423, 605–606 (2003).
5. Clauset, A., Shalizi, C. R. & Newman, M. E. J. Power-law distributions in empirical data. SIAM Rev. 51, 661–703 (2009).
6. Broido, A. D. & Clauset, A. Scale-free networks are rare. Nat. Commun. https://doi.org/10.1038/10.1038/s41467-019-08746-5 (2019).
7. Voitalov, I., van der Hoorn, P., van der Hofstad, R. & Krioukov, D. Scalefree networks well done. arXiv preprint at: https://arxiv.org/abs/1811.02071 (2018).
8. Hagstrom, W. O. The Scientific Community, 276–279 (Basic Books, NY, 1965).
9. Overgoor, J., Benson, A. R. & Ugander, J. Choosing to grow a graph: modeling network formation as discrete choice. arXiv preprint at: https://arxiv.org/abs/ 1811.05008 (2018)