Какова размерность Платонова мира идей?

Если судить по Чертовым Куличкам, то около 7

Д. Манин

1. Постановка задачи

По работе мне понадобилось выяснить, каково может быть распределение HTML-страниц по частоте посещений (hit rate). Имея доступ к статистике посещений Чертовых Куличек, я отправился туда и взял данные за февраль 1998 года: количество попаданий для 300 самых популярных страниц. Кулички -- место крупное и хорошо посещаемое, за месяц набежало почти 13 миллионов попаданий, так что даже у последней страницы в списке набралось 1300 -- график получился гладкий. Вот он:

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

По оси X отложен порядковый номер страницы в списке, а по оси Y -- количество попаданий на нее за месяц. По обеим осям масштаб логарифмический, то есть, сдвиг на одно и то же расстояние вдоль оси соответствует изменению отложенной величины в одно и то же число раз. Иначе говоря, расстояние между отметками 10 и 100 такое же, как между 100 и 1000, или, скажем, между 0.37 и 3.7.

График, изображающий экспериментальные точки, прекрасно ложится на некую прямую. В логарифмическом масштабе прямая изображает степенную зависимость: когда X увеличивается в несколько (скажем, в a) раз, Y тоже увеличивается в несколько (скажем, в b) раз -- значит, Y = A Xc, где b = ac. Прямая, показанная на графике, -- наилучшее приближение экспериментальных данных степенной зависимостью. Ее показатель степени c = -0.85.

Естественно, возникает вопрос -- почему? Вряд ли мы сможем объяснить константу 0.85, да и вряд ли эта константа универсальна, но тот факт, что распределение именно степенное, бесспорен и требует объяснения. Надо сказать, что степенные распределения вообще встречаются нередко в естественных процессах, но это наблюдение еще не заменяет объяснения. Поэтому мы займемся черной магией физики -- изобретением модели, которая основывалась бы на "естественных" предпосылках, и из которой степенное распределение вытекало бы, как следствие.

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

2. Графы и размерности

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

По степени удаленности от точки входа страницы можно разделить на уровни: заглавная будет составлять нулевой уровень, все страницы, на которые можно попасть с нее непосредственно, составят первый уровень, и т.д. Очевидно, что со страницы n-го уровня можно попасть только на страницы (n-1)-го, n-го и (n+1)-го уровней. Действительно, если с нее можно попасть на страницы уровня n+2, то эта вторая страница должна принадлежать не выше, чем (n+1)-му уровню. Аналогично рассматривается движение вниз по уровням.

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

Допустим, граф Куличек изображался бы квадратной решеткой на плоскости. Тогда все страницы, в которые можно добраться за n шагов, поместились бы в квадрат со стороной 2n+1, и их было бы (2n+1)2, то есть для достаточно больших n, это число было бы пропорционально n2, а населенность уровня -- периметру квадрата, т.е. номеру уровня. Если бы граф изображался кубической решеткой в пространстве, населенность уровня была бы пропорциональна площади поверхности куба, т.е. квадрату номера уровня. Заметим, что населенность уровня связана с размерностью пространства, в котором располагаются вершины. Это очень простая связь, которая даже лежит в основе одного из возможных определений размерности: в пространстве размерности d, объем шара радиуса r пропорционален rd, а поверхность -- rd-1.

Разумеется, реальный граф Куличек -- не квадратная решетка и не кубическая. И населенность его уровней зависит не от того, как его нарисовать, а от того, как вершины связаны между собой. Поэтому отвлечемся вообще от того, что граф можно изобразить точками и стрелками, и останется суть дела: естественное предположение, что населенность уровня пропорциональна некоторой степени его номера. Это будет наша фундаментальная гипотеза, а показатель степени -- тот самый подгоночный параметр, который мы себе позволили. Точнее, как читатель, возможно, уже догадался, мы введем понятие размерности графа d, и населенность уровня n будет тогда соответствовать площади поверхности шара радиуса n, т.е. nd-1.

Напомним, что мы рассматриваем только уровни относительно фиксированной точки входа -- заглавной страницы Куличек. Однако велик соблазн распространить модель на всю Паутину и предположить, что взяв почти любую страницу и посмотрев, как растет число страниц, до которых с нее можно добраться за n шагов, мы всегда получим степенной закон с одним и тем же показателем. Иначе говоря, предположить, что Паутина имеет фиксированную размерность. Поскольку ссылки связывают между собой асоциативно близкие страницы, вне зависимости от физического местоположения серверов (вспомним переезд тех же Куличек на другую сторону Земли из Детройта в Москву), я ранее предложил для расстояния между страницами, измеряемого количеством шагов по ссылкам, термин "Платонова метрика", имея в виду Платонов мир идей. Теперь мы ввели в Платоновом мире и понятие размерности.

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

3. Модель

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

Итак, основные предположения:

Я не очень старался сделать эти предположения минимально необходимыми и достаточными -- все-таки, я не математик, а физик. Наверное, теория случайных блужданий по графам достаточно хорошо разработана, и изобретать велосипед не хочется. Меня здесь интересует в первую очередь результат.

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

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

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

Таким образом, показатель степени распределения страниц по частоте посещений оказывается связанным с платоновой размерностью графа. Именно, при размерности d число страниц на l-м уровне пропорционально ld-1, а ранг страницы (ее номер в порядке убывания посещаемости) -- n ~ ld, откуда сама посещаемость (обратно пропорциональная населенности уровня) выражается, как

fn ~ l1-d ~ n-(1-1/d)

Иначе говоря, искомый показатель степени равен 1-1/d = 0.85, откуда получаем размерность между 6 и 7.

4. Обсуждение

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

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

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

Конечно, модель, построенная в этой статье, отчасти игрушечная. Мне кажется, однако, что это занятие не было бессмысленным. Мне было интересно. А вам?