Московский международный Синергетический форум
Наука

Безмасштабные сети: как прямая линия на графике расколола сетевую науку

11 минут чтения

В 1999 году Барабаши и Альберт объявили, что большие сети самоорганизуются в безмасштабное состояние. В 2018-м Броидо и Клаузет проверили 928 сетей и нашли строгие признаки этого лишь у 4%. Разбираем спор по текстам сторон: что показали данные, что зависит от определения и где вопрос стоит сейчас.

9 января 2018 года на arXiv появился препринт с вызывающим названием «Безмасштабные сети редки» (Scale-free networks are rare). Его авторы, Анна Броидо (Anna Broido) и Аарон Клаузет (Aaron Clauset) из Университета Колорадо, проверили почти тысячу реальных сетей и пришли к выводу, что одно из главных утверждений сетевой науки двадцатилетней давности не подтверждается данными. Через два месяца, 6 марта, Альберт-Ласло Барабаши (Albert-László Barabási), автор этого утверждения, ответил в блоге своей лаборатории. Текст назывался «Love is all you need», а подзаголовок звучал как диагноз: «бесплодные поиски безмасштабных сетей у Клаузета» [8].

Со стороны спор выглядит узкостатистическим: ложатся ли точки на графике в прямую линию. На деле от ответа зависит многое. Если почти все большие сети устроены одинаково, у эпидемий, отказов интернета и распространения слухов есть общая теория. Если нет, эту теорию придется применять с оговорками. Для синергетики вопрос особенно чувствителен: Барабаши в 1999 году прямо писал, что большие сети «самоорганизуются» в безмасштабное состояние.

Откуда взялась прямая линия

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

В 1999 году Барабаши вместе с Рекой Альберт (Réka Albert) посмотрели на большие реальные сети и увидели другое [1]. В сети киноактеров, где двое связаны, если снимались в одном фильме, доля актеров с k связями убывала как степенная функция P(k) ~ k−γ с показателем γ ≈ 2,3. Для ссылок между веб-страницами получилось γ ≈ 2,1, для энергосистемы запада США около 4, для цитирований научных статей (по данным Сидни Реднера) около 3. В двойном логарифмическом масштабе степенной закон выглядит прямой линией, и эту прямую авторы увидели во всех четырех случаях. Вывод они сформулировали широко: «независимо от системы и природы ее составляющих вероятность P(k) того, что узел сети взаимодействует с k другими узлами, убывает по степенному закону» (пер. ред.) [1].

Степенной закон отличается от пуассоновского тем, что у него нет характерного масштаба. Петтер Хольме (Petter Holme) поясняет это так: утверждение «узлов со степенью две тысячи вдвое больше, чем со степенью три тысячи» останется верным, если заменить тысячи на сотни или миллионы [6]. Отсюда название «безмасштабная сеть» (scale-free network). На практике это означает хабы: немногие узлы с огромным числом связей, которых в сети Эрдеша — Реньи просто не бывает.

Главным в статье было объяснение. Барабаши и Альберт предложили модель с двумя составляющими. Сеть растет: на каждом шаге приходит новый узел с m связями. Связи распределяются не равномерно: вероятность присоединиться к узлу i пропорциональна его текущей степени, Π(ki) = ki/Σjkj. Это предпочтительное присоединение (preferential attachment), по-бытовому «богатый богатеет». Расчет дает P(k) = 2m2/k3, то есть γ = 3 при любом m. Авторы проверили и обратное: без роста или без предпочтения степенной закон не возникает. В аннотации они написали, что развитие больших сетей управляется «устойчивыми явлениями самоорганизации, которые выходят за пределы частностей отдельных систем» [1].

Сам механизм был не нов, и критики это быстро напомнили [6]. Герберт Саймон (Herbert Simon) в 1955 году вывел похожие распределения из процесса, в котором новое чаще достается тому, у кого уже много [2]. Дерек де Солла Прайс (Derek de Solla Price) в 1965 году описал степенной хвост у числа цитирований, а в 1976-м предложил для него модель «накопленного преимущества» [3, 4]. Новым было другое: перенос этой схемы на любые растущие сети и утверждение, что безмасштабность у них общая.

Модель сразу начали обобщать. В 2000 году С. Н. Дороговцев и А. Н. Самухин из Физико-технического института им. А. Ф. Иоффе в Санкт-Петербурге вместе с Ж. Мендесом (J. F. F. Mendes) из Университета Порту точно решили модель с «начальной привлекательностью» узлов. Показатель γ в ней принимает любые значения от 2 до бесконечности [9]. Почти одновременно П. Крапивский, С. Реднер и Ф. Лейвра (P. L. Krapivsky, S. Redner, F. Leyvraz) решили модель через кинетические уравнения [10]. Сам Барабаши в 2018 году назвал именно эти работы основой, которая объяснила разброс показателей в реальных сетях [8]. Петербургская линия теории сетей заслуживает отдельной статьи.

Зачем всем был нужен хвост

Из безмасштабности следовали сильные выводы. Альберт, Чон и Барабаши в 2000 году показали, что такие сети устойчивы к случайным отказам и уязвимы для прицельной атаки на хабы [11]. Ромуальдо Пастор-Саторрас и Алессандро Веспиньяни (Pastor-Satorras, Vespignani) в 2001 году нашли, что в безмасштабной сети у эпидемии может не быть порога: инфекция охватывает заметную долю узлов при сколь угодно малой заразности [12]. Хольме пересказывает этот знаменитый результат так: при показателе γ меньше трех порога нет. И тут же оговаривается, что строго это верно только для бесконечной сети [6]. Через несколько лет «безмасштабными» объявили белковые сети, сети знакомств, интернет на уровне автономных систем и многое другое.

Проверяли это по большей части на глаз. Строили гистограмму в двойном логарифмическом масштабе, проводили прямую, по наклону считали γ. Хольме называет этот прием неточным и подверженным «мотивационным искажениям» [6]. Исследователь, который ждет прямую линию, ее и найдет. Логнормальное распределение или степенной закон с экспоненциальным обрезанием на конечной выборке выглядят почти так же.

Строгая проверка: 928 сетей

Инструмент для честной проверки появился в 2009 году. Клаузет, Косма Шализи (Cosma Shalizi) и Марк Ньюман (Mark Newman) предложили процедуру в три шага [5]. Сначала методом максимального правдоподобия оценить показатель и нижнюю границу хвоста, с которой начинается степенной закон. Потом получить p-значение: правдоподобно ли вообще, что данные взяты из степенного распределения. И наконец сравнить степенной закон с соперниками (экспонентой, растянутой экспонентой, логнормальным законом, степенным законом с обрезанием) по отношению правдоподобий.

Броидо и Клаузет применили эту процедуру к сетям из каталога ICON (Index of Complex Networks). В журнальной версии 2019 года их 928, в препринте 927 [7]. Примерно половина сетей биологические, треть социальные и технологические, шестая часть информационные и транспортные. Сложные сети (ориентированные, взвешенные, многослойные) авторы раскладывали на несколько простых графов. Например, у ориентированной сети отдельно проверяются входящие степени, исходящие и общие. Чтобы учесть разные определения безмасштабности в литературе, они ввели шкалу из пяти уровней доказательности: от «сверхслабого» (степенной закон хотя бы не хуже альтернатив) до «сильнейшего» (почти все простые графы сети проходят все тесты, а показатель лежит между 2 и 3).

Результат по всему корпусу такой. У 49% сетей нет никаких признаков безмасштабности. К «сильным» относятся 10%, к «сильнейшим» 4%. Логнормальное распределение описывает данные не хуже степенного или лучше в 88% случаев. Социальные сети оказались «в лучшем случае слабо безмасштабными»: ни одна не попала в сильные категории. Сильнейшие признаки нашлись лишь у горстки технологических и биологических сетей; среди биологических это в основном метаболические. Авторы оговорили, что 28% корпуса составляют сети грибных мицелиев, которые все оказались небезмасштабными. Без них доля «сильнейших» растет с 4 до 5%, и картина в целом не меняется [7].

Вывод в статье осторожнее заголовка. Броидо и Клаузет пишут, что безмасштабные сети «не повсеместны» и что брать их за исходную точку моделирования реальных сетей эмпирически не обосновано (пер. ред.). Тут же они признают, что для некоторых сетей, например цитирований, предпочтительное присоединение доказано. И делают оговорку, с которой потом согласится и другая сторона: по одному распределению степеней механизм образования сети не определить [7].

Ответ Барабаши: проверяли не то

Ответ Барабаши строится на двух доводах [8]. Первый касается теории. Модель 1999 года механистическая: она объясняет, откуда берется хвост, но не претендует быть моделью интернета или клетки. Уже к 2001 году было понятно, что в реальной сети к росту и предпочтению добавляются старение узлов, новые связи между старыми узлами, разная «приспособленность» (fitness). Все это искажает чистый степенной закон предсказуемым образом: насыщение при малых степенях, обрезание при больших, логарифмические поправки. Значит, подгонять под все сети чистую степень бессмысленно, нужно подгонять ту форму, которую предсказывает теория для конкретной системы. Барабаши обращает внимание на таблицу из препринта: по его подсчету, в 51% сетей данные лучше описываются степенным законом с экспоненциальным обрезанием. По его мнению, это подтверждает теорию, а не опровергает ее.

Второй довод касается методики. Разбиение сети на простые графы дает голос каждому из них, хотя по сути важен обычно один. У сети цитирований степенной закон давно известен для входящих связей, то есть для числа ссылок на статью. Число ссылок в самой статье зависит от правил журнала и подчиняется другому распределению. Но при голосовании оно весит столько же. Эту логику Барабаши изобразил притчей: если разбить слово «Love» на все подстроки и требовать, чтобы с ним совпала хотя бы половина, придется заключить, что «в Love нет Love». Еще он утверждает, что даже сеть, построенная точно по его модели, в критериях Броидо и Клаузета не дотягивает до высшей категории. Это его довод, мы его не проверяли.

Третья сторона: что считать степенным законом

Самый содержательный ответ пришел от математиков. Иван Войталов, Пим ван дер Хорн, Ремко ван дер Хофстад и Дмитрий Крюков (Voitalov, van der Hoorn, van der Hofstad, Krioukov) в статье «Безмасштабные сети, сделанные как следует» (Scale-free networks well done) предложили другое определение [13]. Распределение называется степенным, если оно правильно меняется на бесконечности (regularly varying): это степенная функция, умноженная на медленно меняющуюся. Такое определение допускает сколь угодно сильные отклонения от чистой степени при малых k и не трогает показатель хвоста. Для его оценки авторы взяли три состоятельные оценки из теории экстремальных значений (оценки Хилла, моментов и ядерную).

На 115 сетях из базы KONECT получилась другая картина. Интернет на уровне автономных систем, ссылки между веб-страницами, белковые взаимодействия человека, цитирования, рекомендации товаров классифицируются как степенные. Дорожная сеть Калифорнии и исходящие степени в рекомендациях Amazon классифицируются как нестепенные. Итог работы: безмасштабные сети «не редки». Одна их оговорка звучит неудобно для обеих сторон. Вопрос о механизме, породившем конкретное распределение степеней, они называют некорректно поставленным, потому что совсем разные модели дают одно и то же распределение. Еще одно ограничение они признают сами: строгого статистического теста на правильное изменение не существует, p-значение к такому выводу не приложишь.

В 2021 году Маттео Серафино с соавторами (Serafino et al.) зашел с третьей стороны [14]. Если отклонение от степенного закона вызвано конечным размером выборки, обрезание должно сдвигаться с ростом сети по законам конечномерного скейлинга. Около двухсот сетей проверили на это свойство. Белковые, компьютерные, гиперссылочные и вообще информационные сети ему следуют. Инфраструктурные, транспортные и социальные заметно отклоняются.

Где вопрос стоит сейчас

Лучший итог спора, по-нашему, подвел Хольме, в 2019 году сотрудник Токийского технологического института. Он написал комментарий к журнальной версии статьи Броидо и Клаузета [6]. По его словам, в сетевой науке теперь две школы. Одна считает безмасштабную сеть идеальным объектом, который существует в пределе бесконечного роста. Другая видит в ней свойство конкретных конечных данных. Первой нужны пороги эпидемий и другие понятия, которые строго определены только на бесконечности. Второй нужны методы, которые работают с реальными выборками. Хольме предлагает не мирить школы, а различать «статистические» и «эмерджентные» безмасштабные сети. Он добавляет, что спор, похоже, вышел за пределы науки: поле сползает от науки о сложности к науке о данных, и в спорах о безмасштабности есть что-то от «коллективного поиска себя» (пер. ред.).

Несколько вещей после 2019 года бесспорны. Тяжелые хвосты и хабы в больших сетях реальны, это признают все стороны. Утверждение о всеобщей безмасштабности в сильной форме не выдержало проверки, особенно для социальных сетей. Наконец, вывод о механизме по форме одного распределения ненадежен: на этом сошлись Броидо и Клаузет, Войталов с соавторами и Хольме.

Для синергетики здесь урок о слове «самоорганизация». В 1999 году оно стояло в аннотации как объяснение, а через двадцать лет спор шел уже о том, что именно в данных этой самоорганизации соответствует. В архиве Форума есть статья В. И. Аршинова, Ю. А. Данилова и В. В. Тарасенко «Методология сетевого мышления: феномен самоорганизации». Ее авторы начинают с вопроса, что такое интернет как целое. Именно на измерениях веба Барабаши и Альберт увидели в 1999 году свою прямую линию.

Если вам попадется фраза «сеть X безмасштабна», ее можно проверить тремя вопросами. По какому определению? Каким тестом? Сравнивали ли с логнормальным законом и законом с обрезанием? Если ответ сводится к прямой на логарифмическом графике, перед вами пока гипотеза, а не результат.

Источники
1. Barabási A.-L., Albert R. Emergence of scaling in random networks // Science. 1999. Vol. 286, № 5439. P. 509–512. doi:10.1126/science.286.5439.509. Препринт: arXiv:cond-mat/9910332.
2. Simon H. A. On a class of skew distribution functions // Biometrika. 1955. Vol. 42, № 3–4. P. 425–440. doi:10.1093/biomet/42.3-4.425.
3. Price D. J. de S. Networks of scientific papers // Science. 1965. Vol. 149, № 3683. P. 510–515. doi:10.1126/science.149.3683.510.
4. Price D. de S. A general theory of bibliometric and other cumulative advantage processes // Journal of the American Society for Information Science. 1976. Vol. 27, № 5. P. 292–306. doi:10.1002/asi.4630270505.
5. Clauset A., Shalizi C. R., Newman M. E. J. Power-law distributions in empirical data // SIAM Review. 2009. Vol. 51, № 4. P. 661–703. doi:10.1137/070710111. Препринт: arXiv:0706.1062.
6. Holme P. Rare and everywhere: Perspectives on scale-free networks // Nature Communications. 2019. Vol. 10. Art. 1016. doi:10.1038/s41467-019-09038-8. Открытый доступ.
7. Broido A. D., Clauset A. Scale-free networks are rare // Nature Communications. 2019. Vol. 10. Art. 1017. doi:10.1038/s41467-019-08746-5. Открытый доступ; препринт: arXiv:1801.03400.
8. Barabási A.-L. Love is all you need: Clauset’s fruitless search for scale-free networks. Блог лаборатории Барабаши, 6 марта 2018. Архивная копия: web.archive.org.
9. Dorogovtsev S. N., Mendes J. F. F., Samukhin A. N. Structure of growing networks with preferential linking // Physical Review Letters. 2000. Vol. 85, № 21. P. 4633–4636. doi:10.1103/PhysRevLett.85.4633. Препринт: arXiv:cond-mat/0004434.
10. Krapivsky P. L., Redner S., Leyvraz F. Connectivity of growing random networks // Physical Review Letters. 2000. Vol. 85, № 21. P. 4629–4632. doi:10.1103/PhysRevLett.85.4629.
11. Albert R., Jeong H., Barabási A.-L. Error and attack tolerance of complex networks // Nature. 2000. Vol. 406. P. 378–382. doi:10.1038/35019019.
12. Pastor-Satorras R., Vespignani A. Epidemic spreading in scale-free networks // Physical Review Letters. 2001. Vol. 86, № 14. P. 3200–3203. doi:10.1103/PhysRevLett.86.3200.
13. Voitalov I., van der Hoorn P., van der Hofstad R., Krioukov D. Scale-free networks well done // Physical Review Research. 2019. Vol. 1. Art. 033034. doi:10.1103/PhysRevResearch.1.033034. Открытый доступ; препринт: arXiv:1811.02071.
14. Serafino M., Cimini G., Maritan A., Rinaldo A., Suweis S., Banavar J. R., Caldarelli G. True scale-free networks hidden by finite size effects // PNAS. 2021. Vol. 118, № 2. Art. e2013825118. doi:10.1073/pnas.2013825118.