Портрет русского ЖЖ (2): six apart?

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

Под cut'ом будет картинок килобайт на 600-700. Они маленькие но дюже тяжелые потому что красивые портреты ЖЖ в этой заметке - animated GIFs, они движутся.

( Первая часть здесь: http://www.livejournal.com/users/muzyka_sfer/514.html )

---

1. МЕТОД

 

1.1 Сбор данных и задача

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

Во-вторых, легче всего "ползать" (crawl) по друзьям друзей. Условно можно сказать, что ЖЖисты по степени присутствия бывают маленькие (до 100-200 друзей - не общих, просто друзей в одну или другую сторону), средние (200-600), и большие (свыше 600).
Второе поколение от пользователя проведшего на ЖЖ примерно год и находящегося на среднем уровне (около 400 друзей, около 90-100 взаимных), т.е. взаимных друзей взаимных друзей, дало больше 7000 имен русского ЖЖ., граф, обрывающийся на друзьях друзей друзей составлял около 67000 имен и 366000 связей.
По моим оценкам, такой граф практически не покидает пространства русского ЖЖ
Взаимные связи культурно устойчивы, что каждый раз подтверждается моими результатами.

Однако выявляя имена, такие построения не решают вопрос о существовании или несуществовании отдельных несвязанных или малосвязанных "галактик" в пределах русской ЖЖ-вселенной. Граф ДДДрузей ( = друзей-друзей-друзей ) преувеличивает степень связности: для накопанного дерева из 2 поколений потомков одного корня (и 3его в виде его листьев) путь от любой вершины до любоой другой тривиально не превышает (2n), т.е. 5, т.е. в самом худшем случае двух точек, не имеющих никаких иных связей, кратчайшим путем будет спуск из А до корня и подъем до следующей вершины Б

Так что для обнаружения новых имен и отдельных групп (в существование которых верится все меньше) надо собирать информацию иначе.

Один способ - из длинных скандальных заметок, в которых могут отмечаться случайные люди, от которых затем можно разрабатывать друзей друзей и сопоставлять их с известной частью вселенной.
Другой - использование внешних списков (например, 100 известных общественных деятелей в русском ЖЖ)
Третий, пожалуй, самый объективный - harvesting новых постингов в ЖЖ.

В эти выходные я запустил скрипты, которые раз в 2 минуты собирали имена и одну-две строчки всех новых постеров, писавших по-русски. На самом деле это слишком большой промежуток: имена в соседних списках не перекрывались.

Я собирал данные 24 часа в субботу-воскресенье. Обычно для русского ЖЖ любой уикенд медленный, однако 24 часа дали 14170 уникальных имен; вся информация еще не до конца обработана.

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

1.1 Двенадцать часов постингов

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

Apr [[info]]dark_angelika: 23 А я - подобие слабой улитки, 19: прячусь за рифмы, бегу за улыбки.	Apr [[info]]gizmo_unholy: 23 15 причин, почему взлом софта круче секса 19: 15 причин, почему взлом софта круче секса	Apr [[info]]_elchik_: 19: Я девочка с сгоревшими коленями.
Apr [[info]]slivo4naya: 23 дапошловсе. дерьмо какое-то. Сидим с Машкой и грузим дру г друга в аське. Жизньдерьмо. Да не знаю я, че писать!!! Еще ч итаешь? ну и зря.	Apr [[info]]ebanutaya: 23 Поехали	Apr_23_19:26 [[info]]estet69: пидары , везде одни пидары...
Apr_23_19:26 [[info]]asol1: А интересно, это правда?	Apr [[info]]wertykiss: 24 Способы Сразить девочку наповал 05: Способ № 0 09 Вырезано цензурой.	Apr [[info]]sopet: 24 бля суки ну напишети что нибудь во фрнендленте!

(цитировать можно ровно 2112 раз, чтение суточного запаса первых строчек сдвинуло мое представление о соотечественниках ;) )
Собрав имена, я построил граф этого мира.

Более точно "построить граф" означает:

(а) собрать информацию-имена, создать уникальные списки
(б) взять информацию о друзьях каждого имени в ЖЖ.
(в) найти взаимных друзей, ВД (MF, mutual friends - почему только общих объясню потом)
(г) а-б дают parent lists, которые обрабатываются скриптами - построить покрывающее дерево графа, без которого программа-показыватель не сможет построить мир
(д) запустить алгоритмы, производящие смысловые вычисления
(е) записать их в виде атрибутов вершин (которые все сидят в графе на spanning tree, покрывающем дереве, как мы помним) и ребер графа
(ж) собрать файл данных в формате программы
(з) запустить программу, "полетать" по построенной визуализации, включая и выключая разные разности (расцветку, показ или исчезновение частей и т.д.)
Сохранить нужные картинки
(и) собрать их в gif-animations, resize и т.д. - привести в вид, пригодный для показа
(к) написать нудный сопроводительный текст и послать красивые картинки в ЖЖ для удовольствия публики ;))

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

1.2 Про деревья

У графа нет какой-то канонической формы, и внешний вид зависит от корневой вершины, порядка обхода вершин при конструировании дерева, и прихотей программы-визуализатора, которая внутри себя решает задачу layout'а, т.е. как разумно разместить дерево в сферическом пространстве.

--[Дерево справа относится к построению, для которых приводятся картинки ниже. Если кликнуть на картинку, вы извлечете еще 200кб траффика]--

--[Гораздо более красивое дерево (185кб) можно увидеть здесь]--.

Это дерево было построено для 214897 ЖЖузеров образовавших 434367 связи; оно включает русский ЖЖ, но dataset кажется был сильно засорен. Похоже на какой-то традиционный японский вид керамики.

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

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

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

Такое конструирование дерева разделяет изолированные группы если те существуют и уже поэтому не бессмысленно.

2 В терминах задачи о распределенном ЖЖ дерево обхода представляет некий как скажут компьютерщики "routing algorithm", один из возможных для распространения информации в сетке социальных связей. Разные способы конструирования деревьев таким образом будут моделировать разные алгоритмы.

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

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

2. РЕЗУЛЬТАТЫ

2.1 Связность

Итак, получив первые 12 часов данных, я построил граф и удивился.
(а) Выходные - медленный день для русского ЖЖ. Многие, включая самых известных ЖЖ-истов не были в это время on-line. Однако список вершин графа включал (через первые поколение друзей) большую часть имен, входящих в сильно населенную и известную мне часть ЖЖ.
Другими словами, случайные постеры связаны по крайней мере с известными. Для известных (100 самых популярных в ЖЖ по списку ljplus) я строил графы раньше. Их миры очень сильно связаны между собой, это я уже видел (даже если один популярный писатель, другой больше пишет про рецепты). Более того, в графе, например, стоящего вверху таблицы по количеству запоминаемых постов krylov'а его друзья очень сильно заносят в друзья друг друга, впрочем , общая тенденция в тусовках вокруг популярных ЖЖистов и вообще русского ЖЖ.
(Копаясь в американской части, я видел какой-то жалкий писк в сообществе об изучении самого LJ: мои LJ friends занесли в друзья друг друга.Хорошо ли это? Не думаю, что все такие, но иной, менее интенсивной структуры там естественно ожидать. Возможно, одним из определяющих факторов оказывается демография: американские ЖЖисты в подавляющей массе 17-21 лет от роду, см http://www.livejournal.com/stats )

Вид графа показал, что 2112 вокресных сильно и типично связаны и друг с другом.
Тогда я перешел к главной задаче:

2.2 SIX DEGREES APART: первое построение

Как оценить - визуализовать, инженерно прикинуть - сколько поколений друзей друзей связывают русских ЖЖ-истов друг с другом?

Подобной задаче много лет. Чаще всего ее цитируют связывая в именем Мильграма социологa-активистa, "six degrees of separation".

Математики играют в свой вариант под названием "число Эрдеша". Вообще, тема вызывает миллион гаданий. Сейчас, например, в Computer Science, только ленивый не говорит о том, что Веб представляет из себя "явление малого мира", результат оценки не более, абсолютно не более серьезной, чем этот текст, выполненной сотрудницей Xerox Ладой Адамич (Lada Adamic) "The Small World Web".
Это как бы дает им право постулировать поведение разного рода сетей на поле как тетрадка в клеточку, в которую "вносятся случайные возмущения", что делает ее свойства "похожими на small-world model".
Мало кому пришло в голову подумать, где найти реальные сети социальных свюзей и выяснять, как дело обстоит в них на самом деле. По таким ученым надо ездить паровыми катками.

По поводу нашего рассмотрения можно сказать следующее:

1. ЖЖ представляет идеальную модель социальных связей, это предел, к которому бы стремилось общение, если бы были сняты все помехи.
ЖЖ - дистиллированная система социальных связей, которая сложилась стихийно без центральных справочных ресурсов и ограничений на то, кто с кем может разговаривать.
В этом новизна, ЖЖ - гость из будущего. Раньше общению в чистом виде мешала необходимость физически придти куда-то, быть вхожим в круг и т.д.
Впервые в истории на примере Net-сообществ мы можем так ясно понять так многое о таком числе людей.
2. Современные оценки - первые возможные точные оценки. Все предыдущее (читайте ссылку в Википедии), в общем, гадания. Сейчас впервые любой энтузиаст вроде меня может за выходные получить ответ на гипотезу "six apart" - и почему-то никто, насколько я знаю, не озаботился его получить, после стольких лет ажиотажа.
Возможно я плохо знаю
3. Эта оценка центральна для жизнеспособности идеи распределенного ЖЖ и сохранения нецензурированной информации, т.к. от параметра зависит выбор возможного решения.

Я взял очень слабосвязаную даму (всего 7 общих друзей) и перестроив граф он нее как корня стал смотреть, когда я (не музыка сфер, созданная для этого проекта, а ЖЖист из средней группы имеющий примерно 400 друзей и 90-100 общих друзей) смогу до нее добраться через друзей-друзей-друзей, запустив алгоритм, красящий вершины.
Можно представить себе задачу, как распространение идеального слуха: каждый передает его всем взаимным друзьям; попав в вершину, он ее навсегда переводит в состояние "знаю" и идет дальше.

Ответ: из ее 7 связей 4 оказались окрашены через 4 шага.

Гораздо замечательнее другое, я этого совершенно не ожидал и был поражен:
на картине 4го шага видно, что окрасилось большинство вершин - чтобы быть точным, из прибл. 40900 вершин графа на 4м шаге достигнуто 30800, т.е. 3/4 всего населения построенного подмножества.

На самом деле результат даже может быть чуть выше, т.к. наша вселенная несколько загрязнена ЖЖистами нерусского мира: мои скрипты иногда обманывались на особые знаки юникода (например, сердечки, которые американские девушки ставят гроздьями, или другими неанглийскими шрифтами - испанскими,немецкими. Я не совсем понял, где происходит заражение и постараюсь дочистить скрипты.
Их, однако, хорошо видно именно потому что они остаются изолированными - как я не очень понятно объяснил в разделе об алгоритме построения дерева: такие ЖЖисты выглядят висящими на красных ножках-веточках над кроной одного связного огромного баобаба русского ЖЖ и не имеющими связей с русской частью мира. Никаких общих взаимных друзей у них нет.

Отсюда вытекает общий результат первого подсчета (и красивой визуализации):
я могу гарантировать, что среди 75% покрытых вершин все могут достичь друг друга по крайней мере через 8 шагов.
Однако визуализация в каком-то смысле сильнее подсчетов вслепую: я могу рассматривать и "на глаз" оценивать характер графа, и быть почти уверенным, что реально полученный результат должен быть типичным. Скорее всего подавляющее число русских ЖЖистов примерно в 3-4, реже в 5 шагах друг от друга.

2.3 SIX DEGREES APART: второе построение.

Однако наше исходное подмножество 2112 случайных постеров должно дать заниженный результат.
Замечательно, что известные появились в их графе, т.е. они присоеденены к основному облаку русского ЖЖ. Однако поскольку я не вставлял второе поколение друзей этих 2112ти, нет гарантии, что появившиеся имена присутствуют всеми своими связями.
Поэтому первая оценка может занижать результат. (Если я не учитываю еще полмиллиона прячущихся одиноких волков, однако, все мои результаты завышены, но на то по результатам долгих копаний совсем не похоже --- [см. часть 3 с распределением и уточнениями - m_s ]).

Сначала я хотел строить вторые 12 часов субботы-воскресенья. Однако решил что должен чистить сырые данные: мой скрипт набрал сколько-то (не слишком много, но ) американцев. Работать не хотелось, нужен был легкий результат.
(б) Я добавил к 2112 случайных ЖЖистов список 100 известных деятелей, чрисутствующих в ЖЖ (обычно писатели, журналисты и т.д.) с их ВД, список ВД самых популярных ЖЖистов с ljplus.ru, и свой ВД.
Получилось 3683 parent lists которые содержали 61966 ЖЖузеров, имеющих 292259 связей (коэффициент 1:4.7, но это, как пишут в газетах, очень средняя температура по больнице).
Как показало построение, они почти полностью принадлежат русскому ЖЖ.
Количество случайных американцев как показали полеты, клики по вершинам на красных веточках и чтук 20 отдельных случайных проверок вручную, действительно невелико и они действительно вынесены из облака вон.


Что на картинках?

1. Дерево мира можно видеть на первой картинке в заметке, выше.

--[Сразу щелкнув на картинку, начинайте думать, стоило ли вам ждать 500кб чтобы рассматривать то же самое большего размера]-- 2. Это построение по показывает часть дерева сбоку-сверху близко к корню. (весь граф получился поножим на баобаб, относительные величины колец друзей из файлов "родителей", следуя по которым граф строился, не важны. Изображение натянуто на сферу, искажено как в объективе "рыбий глаз", велико то, что близко; большая часть графа скрыта передними ветвями либо "закатилась за горизонт" сферы. Не ставшие "родительскими" вершины все равно присутствуют множеством связей, это неважно, у графа как у джинна вообще нет одного лица или образа. Зеленые точки - друзья друзей исходящие от корневой вершины (меня самого ЖЖиста с 87 ВД). Можно было строить "распространение слуха" от любой точки, не обязательно корневой, но у меня была идея сравнения с распространением информации по дереву (потом). Всего было просчитано 5 шагов. Арифметика такая: ЖЖузеров 61966; связей 292259; шаг 1 (друзья, Д): покрывают 87 имен - 0.14% от 61966 шаг 2 (ДД): 6967 имен, 6880 новых - 11.24% шаг 3 (ДДД): 34531 имен, 27564 новых - 55.73% шаг 4 (ДДДД): 53760 имен, 19229 новых - 86.76% шаг 5 (ДДДДД): 56712 имен, 2952 новых - 91.52% Последнее, по-видимому (визуализация дает гораздо, чем слепые цифры) покрывает практически всех в русском ЖЖ. Повторяясь, я полетал вокруг облака и пощелкал на иставшиеся красные точки и гроздья. Их мало, они дают нерусские nicks, выборочные проверки подтверждают представление (на самом деле я знаю как легко проверить строго, но (а) уверен в правоте (б) их мало, и результат они не изменят) == лень.)

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

[*animated*] На третьем построении все наоборот: находясь где-то там же сверху и глядя на крону вниз (корень в общем скрыт, но где-то справа-внизу) мы наблюдаем что остается от полного дерева, какая его часть еще не затронута ползущей заразой. Шаг 5 выпущен (потому что бесполезен, уже на 4м дотлевает красными улями когда-то зеленое дерево). Шаг один (первые 87 друзей) еще совершенно не видны; шаг 2 убирает некоторые связи и гасит зеленые вершины; дальше полная разруха и запустение.

[*animated*] Еще один вид на то же самое но без цветовой кодировки вершин. Они доберутся до вас, и очень скоро. По-моему, вышло удачно.

Здесь мы смотрим на то же дерево снизу. ТТакая маленькая плошка ближе к левому нижнему углу - это я и мои взаимные друзья. Я в центре, конечно, и на этом графе у меня самый первый номер в ЖЖ. Шаг 4 пропущен (картинка была некрасивая, а разницы снизу между шагами 4 и 5 нет никакой - к этому моменту щупальца дорастают до самых отдаленных вершин, здесь бои давно отшумели. Еще две (статические) картинки если хотите: --[ Красивая картинка шага 1 здесь (дерево снизу зеленые еще не пришли, около 200кб, ну да вы сами знаете ]-- --[ Все красивое, и зеленое. Шаг 4, к этому моменту щупальца зеленых тянутся к самым отдаленным вершинам, здесь внизу под сенью дерева все давно проросло. 200кб, ага. ]--

3. ВЫВОД, kind of

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

Расстояние - диаметр русского ЖЖ - по-видимому,
не более 4 шагов для покрытия более 80% nodes и не более 5 для практически 100% покрытия. В силуэтого можно гарантировать, что любой достигнет любого за максимум 10 шагов, или 8 если он попадает в 86% большинство. На самом деле типичными должны быть указанные цифры - 4 или 5 - потому что визуализация "точнее" слепых цифр и показывает характер графа значительно лучше, чем вычисленные коэффициенты.

Визуализация - отличный инструмент, который в чем-то точнее подсчетов. То, что я здесь делаю является (инженерной прикидкой, конечно, но) для традиций какой-нибудь computer science полной ересью: мы смотрим на реальные данные и извлекаем из них соображения вместо того, чтобы постулировать модель и ее обсчитывать.
Вот пример из смеси математики и computer science:

...our approach consists of 3 basic parts: (1) embed resources as points in a metric space, (2) construct random graph by appropriately linking these points, and (3) efficiently locate resources by routing greedily along the edges of the graph
Наш подход состоит из 3 основных частей: (а) расположим ресурсы как точки в метрическом пространстве (б) сконструируем случайный граф соединяя их соответственно и (в) эффективно обнаружим ресурсы используя такой-то раутинг вдоль ребер графа

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

Интересно, что введение всех связей больших из ЖЖ, не уменьшило диаметр значительно (однако я буду рассматривать это точнее в следующем построении об устойчивости к разрушению связей и выбиванию членов.. мм.. то есть выбыванию участников. Там кстати появится и первое построение как subset без самых сильных связей.)

В целом это прекрасный результат для жизнеспособности нашей инженерной идеи.

---

ПРОДОЛЖЕНИЕ СЛЕДУЕТ.
В следующий раз ( в эти выходные?) попробуетм оценить устойчивость ЖЖ к нарушению связей
( Первая часть здесь: http://www.livejournal.com/users/muzyka_sfer/514.html )