muzyka_sfer (![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small} muzyka_sfer) wrote,@ 2005-05-07 22:35:00 |
|
Big Bang in a Small World - третья часть Портрета Русского ЖЖ
.
.
спекулятивные но практические рассуждения о геометрии русского ЖЖ
.
Рассмотрение русского ЖЖ методами естественных наук началось несколько сумбурной заметкой которая ввела проблему как я ее вижу и указала на методы рассмотрения - сбора информации и визуализации для получения оценок.
Через полторы недели после первой вторая показала на красивых построениях структуру графа ЖЖ (через движущиеся иллюстрации того, как в нем распространяется "идеальных слух"). Вторая (предыдущая) часть здесь
Рассмотрение возникло из представления, что необходимо создать способ хранить "непотопляемую" информацию на Интернете. Сводки новостей постоянно подхлестывают: сегодня CNN пугает обывателей рассказывая о специальном законе, принятом в США для запрещения Internet Hunting, настоящего отстрела настоящих зверей через интерфейс в Интернете (и, разумеется, по американской традиции, противники запрета выдвигали главный козырь культуры политкорректности - защиту меньшинств (ваш запрет нарушит права инвалидов-охотников)).
Для иллюстрации ужасов неотрегулированного Интернета очевидных педофилов уже не хватает после международной облавы и ареста последних - 15? 30? - и честно говоря приедаются они, если каждый день. Между тем, где-то в ЖЖ мелькнула ссылка о наборе на оксфордскую программу по обучению/исследованиям "Internet governance": еще одно из многих указание на то, что проблема управления и юридической регулировки Интернета давно поставлена, фонды выделены, и она решается.
Поэтому - и к тому же следующие полторы недели истекли - можно продолжить рассмотрение структуры русского ЖЖ.
1. СБОР ИНФОРМАЦИИ
1.1 Во второй части были перечислены способы сбора информации о русском ЖЖ.
Чтобы не допустить искажения картины и заведомой всеобщей связности nodes, следует избегать хождения по друзьям-друзей-друзей как единственном методе сбора.
Самым объективным остается мониторинг новых постингов написанных по-русски. В первый день (23-24 апреля) было собрано достаточно данных, но скрипты выделяющие только русские посты оказались недостаточно надежны. В результате я остановил сбор после 24 часов и в построениях для второй части использовал dataset, составленный из:
Полученный из примерно 2600 исходных имен/"родительких" файлов dataset в построениях дал граф с примерно 62.000 вершинами и 290.000 связями.
1.2 Через несколько дней, подправив скрипты, я сделал второй 24-часовой сбор информации. В этот раз он пришелся не на традиционно более медленные для русского ЖЖ выходные.
Во втором harvest я оцениваю засорение нерусскими ЖЖистами как единицы процентов, меньше 10 во всяком случае. Как отмечалось во второй части, (а) взаимные друзья культурно устойчивы да и барьер языка вряд ли преодолим (б) иностранные друзья русскоязычных ЖЖистов (из популярных на ум приходит, например, израильтянинavva) на графе выделены как оконечные "листья" без связей, и программа-визуализатор размещает заметным образом (в) попавшие в порождающее множество не связанные с остальным деревом, в основном иностранцы, алгоритмом построения дерева выносятся за пределы его русской кроны на красные трехступенчатые фальшивые ножки, "prop branches", и очень заметны и легко проверяемы (щеклкнуть мышкой, проверить имя в ЖЖ взяв неинтерактивно информационную страницу)
Самое большое построение по подмножеству полученных данных, которое вынес мой компьютер (недостаток RAM, extensive swapping as a result) представлено на графе с 245859 вершинами (людьми) и 979712 ребрами (взаимная дружба, почти на целый миллион дружбы).
Страница stats ЖЖ утверждает, что им известно порядка 160.000 плюс 18000 гарантированно русских; они скорее всего оценивали по информации на информационных/регистрационных записях:
( United States - 3498461 ... Canada - 243889 ... United Kingdom - 190848 ... Russian Federation - 160369 ... Australia - 85687 ... Ukraine - 17975 )
В таком случае, мои сборы имен, похоже, охватывают большую часть русскоязычной блогосферы ЖЖ.
2. СВЯЗНОСТЬ И РАСПРЕДЕЛЕНИЕ.
2.1 Из своих рассмотрений я могу сказать, что граф русского ЖЖ связен. Мне не удалось обнаружить сколько-нибудь значительных отдельных кусков. В наибольшем из построенных графов-миров, 245.859 nodes, "идеальный слух" от меня, например, доходит в самом большем построении до 207.627 nodes, покрывая примерно 85% графа. Это поведение типично, повторяемо для вычислений от других источников и годится для определения размеров наибольшей связной области. Вспомнив о некой загрязненности данных нерусскими ЖЖистами (не более 10% по моим прикидкам), мы можем видеть, что в русском ЖЖ все связаны со всеми.
Представление о русском ЖЖ как нескольких разных кусках неверно. Это один рой.
Мне кажется, что вряд ли также удастся представить ситуацию так, словно есть как бы "сгустки" пользователей, между которыми существуют более редкие "длинные" связи. Об этом ниже.
2.2
Во-вторых, для оценки наших сборов и свойств datasets следует посмотреть на распределения ЖЖузеров. На графике справа представлены распределения (гистограммы с шагом 10) числа количества ЖЖистов (y) от числа их взаимных друзей в интервале с шагом 10 (x). График нарисован линиями чтобы легче было читать. Шкалы логарифмические
Правая синяя линия показывает распределение по самому большому построению (245.000 ЖЖузеров) от порождающего списка из собранных через monitoring новых постов данным. Следующая влево красная - по подмножеству приблизительно 58300 из тех, на которых производились эксперименты этой части; это подмножество практически совпадает с использовавшимся в части 2 (с одним исключением).
Можно отметить, что:
(а) такие распределения принято приблизительно считать "степенными" (power-law); утверждается, что порождаемые ими случайные графы принадлежат к одному типичному классу (power-law (random) graphs).
(б) Все кривые похожи: малое число ЖЖузеров с большим числом взаимных друзей (группа справа-внизу, порядка 500-1000; ЖЖ стал с 2005 года обрезать число наксимальных друзей, и, следовательно, взаимных науровне 750) -- больше, но мало средних -- огромное число ЖЖузеров (которые впервые выяснил harvesting новых постов) с малым числом связей.
Такие кривые иногда называют распределениями с тяжелым хвостом.
Рост, прибавка новых имен произошла в первую очередь за счет средних и еще более малосвязанных никому не известных (шкалы логарифмические): кривая отодвинула тулово и хвост вправо, практически не ворочая пришпиленной справа головой. Кстати, в крайнее лево должен был попасть и весь случайный и несвязанный с русскоязычными блогами мусор, который на этом графике показан
(в) Две прямые показывают для сравнения степенные функции с показателями (-1.6), сиреневая, и (-2.5), зеленая.
(г) Если после второго дня сборов мы смотрим на более чем 200.000 ЖЖистов, то в отсутствие маловероятных сюрпризов, правая кривая скорее всего верно отражает распределение всего возможного русского ЖЖ.
(г) Подобие кривых означает, что подмножество, которое мы рассматривали в [часть 2] и продолжаем применять здесь верно отражает целое (красная и синяя кривые практически параллельны). На самом деле одна из фундаментальных особенностей графа ЖЖ в том, что в очень гибких пределах части ведут себя точно как целое. Об этом ниже.
(д) Похожее распределение было получено по результатам мониторинга Gnutell'ы ( вот и вся "скрытость" этих систем ;)) - я все же нашел статью тех, кто пытался описать граф P2P, правда цифры и графики там не дают общего представления как это делает визуализация, из-за чего в этой и других статьях о P2P и графах им на мой взгляд приписываются несуществующие свойства, ниже).
Результат для Гнутеллы косвенно подтверждает наш результат.
О таких графах принято считать, что они хорошо устойчивы к случайным помехам и слабоустойчивы к атакам на самые сильные связи. Что мы и рассмотрим.
3. УСТОЙЧИВОСТЬ К РАЗРУШЕНИЮ.
3.1 Еще раз об идее подхода
Мы оцениваем жизнеспособность распределенного ЖЖ. Напомню, гениальная моя идея была в том, что распределенные блоги нужны как слой для создания системы социальных связей, первая основная и абсолютно открытая функция, и делать их нужно распределенными, а не централизованными чтобы создать достаточные потоки обмена на стандартных HTTP, HTTPS. Это позволит существовать (отдельной от самих блогов) сетке для неубиваемой информации, плохо обнаружимой, т.к. она неотличима от открытого traffic'а и его patterns, и интегрированной в служебную структуру services и протоколов Интернета (точнее, в моем примере Веба), который отделить от законного и необходимого чтобы запретить или отменить легко не удастся.
Дело в том, что современные модели P2P наивны, могут быть обнаружены любым школьником за несколько минут, и как показывает практика, они дешевы для шантажа угрозой суда со стороны больших компаний (список имен им стоит что-то около 200 долларов). Озаботившись раздумиями как можно сделать, я не нашел возможностей для анонимных скрытых сеток которые при том были бы общедоступны и обеспечивали обзор и поиск информации, оставаясь притом защищеными от разрушения. Максимум достигнутого - анонимность и "deniability", т.е. ответ в суде, что человек не знает что автоматически вытворяет его компьютер, жалкая защита, когда судом в США рассматривается вопрос о запрещении "file-swapping services" как класса программ, т.е. полное введение наказания за сам факт использования. И на ежа сесть, и зад не уколоть не удается.
Об этом в четвертой части.
Для рассмотрения я решил, что ЖЖ - пример идеальной сетки социальных связей, которые возникли сами собой. Условно говоря, если принять, что взаимные друзья - это основа для обмена "непотопляемой" информацией (подробнее об этом допущении потом), то следует наше рассмотрение русского ЖЖ квалифицировать как идеальную модель, случай общения без помех.
"Идеальные слухи", которые мы пускали во второй заметке, описывают структуру графа и показывают предельно благоприятный случай. В реальности на описанную структуру, если бы она отражала устройство гипотетической распреденной блогосферы или P2P, накладываются ограничения. Например, пользователи, которые немогут оставить компьютер on-line 24 часа в сутки.
Как промоделировать такие ограничения? Что случится, если часть сетки, подлежащей физической Интернет-структуры, станет недоступна? При намеренных атаках, из хулиганства или в случае официально открытого сезона охоты на блоггеров?
Эти эффекты можно описать моделируя разрушение идеального графа общения.
3.2 Разрушение можно проводить по-разному
Во-первых, можно выбивать только связи - или вершины, с которыми уйдут все их связи. Я делаю второе, более жесткое разрушение. Во-вторых, можно разрушать:
- выбивая ЖЖузеров и все принадлежащие им связи случайно.
- Нападая на ЖЖузеров с определенными характеристиками
- По расстрельным спискам составленным по каким угодно критериям.
Ниже я покажу поведение сетки при (а) случайных выбиваниях и (б) при методическом убийстве верших с самым большим числом связей, что интересно в свете предсказаний в литературе о плохой устойчивости таких графов.
Правда, авторы статей делали simulations на искусственно сгенерированных случайных степенных графах. Мы посмотрим на реально сложившуюся сетку.
Чтобы наблюдать эффект воздействия, я буду использовать в дополнение к animation два вида графиков: количество охваченных ЖЖузеров при распространении "идеального слуха" от номера шага и размер предельно достижимого связного компонента от степени разрушения.
Наш dataset для третьей части (который совпадает с тем, что был принят во второй части с одним небольшим отличием; как мы согласились выше, он "типичен" в смысле распределения и верно представляет картину для полного русского ЖЖ) состоит из приблизительно 58000 вершин (и 265000 связей). Из них достижимы примерно 54700, т.е. более 90%. Как изменится соотношение при устранении вершин графа?
3.2.1 Для прикидки я посмотрел как поведет себя граф при случайном изъятии 20, 50, 80 и 90% вершин и их связей.
Первый график показывает как происходит "поджог" графа. Данные для случайных разрушений нормализованы, т.е. для сравнения на одном графике мы представляем, что полные размеры графов как бы остаются неизменными. По оси X отложены шаги распространения (поколения взаимных друзей, расстояния от порождающей вершины), по Y - количество вершин, которых достиг "идеальный слух".
Вспомните движущиеся визуализации из второй части (или см. ниже): вселенная русского ЖЖ резко "вспыхивает" на 3м и 4м шагах, заполняясь почти целиком.
Три почти вертикальных плотно лежащих кривых показывают этот процесс для полного графа (т.е. описывает процесс визуализаций из 2й заметки).
Поразительно, что после случайных разрушений характер процесса - резкие скачки и резкий "поджог" всей доступной части вселенной - совершенно не меняется. После 4-го шага охвачено 85-90% ЖЖузеров из доступной связной компоненты, и после 5го шага кривые становятся практически параллельными оси x, гореть больше нечему.
Высота "стола" показывает уменьшение относительного (графики нормализованы) размера доступной части.
Здесь (случайная серия отмечена зеленым цветом) верхняя линия показывает полный размер графа после изъятий, нижняя - ту его часть, которая остается достижимой для "идеального слуха", т.е. размер его связной (наибольшей связной) компоненты.
Они практически параллельны, наша вселенная усыхает, но связная компонента присутствует, только видимая ей часть графа занимает меньшую и меньшую его долю.
Другими словами совершенно замечательно то, что граф с точки зрения распространения в нем информации продолжает вести себя качественно "почти" по-прежнему. Случайная атака не приводит к мгновенному распаду на отдельные куски и/или не приводит к ситуации, когда вместо мгновенного "воспламенения", распространение стало бы более медленным.
Это совершенно замечательный результат. Структура графа социальных связей такова, что в очень больших пределах поведение части графа подобно поведению целого.
Визуализации [вставить сюда] по-прежнему показывают характерное поведение, показанное на движущихся картинках во второй части.
Отличия тоже есть и я о них расскажу ниже.
3.2.2 Как изменится ситуация если уничтожать ЖЖузеров с наибольшими связями?
Я сделал серию (см. картинку с распределением для понятности) с уничтожением ЖЖузеров с более чем 500, 300, 100, 70, 50 Взаимных Друзей, которых оказалось соответственно 74, 236, 910, 1302 и 1800.
Это - красные линии на графике выше. Видно, что убийство 1800 самых мощных вершин в нашем 58000 мире сужает пространство примерно так же, как выбивание 50% случайным образом.
На графике слева: верхняя линия показывает кривую для целого 58к построения без выбываний. Для строгости надо было бы строить распределение по всем ЖЖузерам, мы берем типичный пример хорошо соединенной вершины. Мы видим, что при атаках на самых больших, видимая часть графа для оставшихся резко уменьшается.
Однако и здесь поведение графа до уровня примерно 100 ВД качественно остается все тем же "поджогом", пока не остались самые малосвязанные (граф 70-50ВД и ниже) и самы многочисленные, тот самый "тяжелый хвост" распределения. Для них "взрыв" на 3-4 шагах превращается в более долгое "горение со вспышками" [здесь вставить более наглядную анимацию].
Сценарий, когда исчезают все большие возможен при преднамеренной атаке на сетку - в нашем примере достаточно убить 1800 чтобы резко сузить доступную часть и замедлить максимальную скорость распространения информации (повысить диаметр оставшейся доступной части графа) вместо сравнимых по воздейсвию 50-60% при случайном выбывании.
Сетки с малой интенсивностью -- как, возможно, американская часть ЖЖ, в которой я сильно не копался, но которая по сравнению с русской (а) демографически представлена 17-20летними (б) их миллионы (см. страницу статистики) (в) у них очень мало друзей, и еще меньше взаимных друзей по сравнению с русским роем -- возможно будут проявлять характеристики графа с выбитыми сильными вершинами. (конечно, полное ограничение на число общих друзей более 50 нереалистично, будет некая разношерстность, но характер по-видимому будет таким - резко сузившаяся видимая связная часть, больший диаметр, т.е. распространение информации требует большего числа шагов).
Понастроив этих графиков и анимаций, я решил, что с одной стороны они подтверждают те описания поведения "power-law random graphs", которые я смутно помнил, и с другой стороны когда остаются только nodes с 50ВД и меньше, изменения носят качественный характер.
Почему? Тут я пошел читать про "Малые Миры".
4. THIS IS A SMALL WORLD
4.1 История идеи "малого мира" широко известна и из популярной литературы и много раз пересказывалась в научных статьях.
Идее много лет. В 67м чтобы ее обосновать, социолог Милграм рассылал письма пытаясь прикинуть сколько шагов друзей друзей отделяют людей друг от друга и решил, что среднее значение 6 ( http://en.wikipedia.org/wiki/Small_worl
Следующий шаг в понимании как образуется "малый мир" связывают с математиком Watts'ом. Математика не менее других видов интеллектуальной деятельности завязана на образы и метафоры, и Ваттс начал построения от картинки как бы клубков связанных более длинными редкими связями. При этом подспудно и психологически он нормой считал крайнюю регулярность - для него "нормальный" граф есть решетка вроде кристалла, отклонения от которой он ищет в своей модели для порождения графа со свойствами "малого мира". Построение он начинает с одномерного случая и рисует кольцо на котором расположены точки - распространение информации идет от соседа к соседу, и занимает много шагов. Он считает расстояния по решетке как бы естественными и объективными. Но если мы будем бросать случайно связи-спицы вдобавок к решеточному движению строго по окружности, то возникнет случайный граф со свойствами "малого мира".
Визуальный образ клубков соединенных длинными редкими или более редкими связями также постоянно возникает в его математике в виде введенного в качестве основного "коэффициента кластеризации".
Ваттс ведет обсуждение в терминах вероятностей, что, добавлю от себя возражение, на самом деле отражает не столько свойства малых миров, они могут быть порождены как угодно, хоть по своду строжайших правил в соответствии с указом китайского императора (об этом ниже), сколько (а) традицию относить рассмотрение к теории случайных графов (б) методику создания графов Ваттсом. Первое отчасти просто несет какую-то "гарантию" потому что вероятность здесь имеет по большей части смысл усреднения, средних значений, верных для множества конкретных исполнений.
Duncan J. Watts & Steven H. Strogatz развили эти представления, обнаружили что их правила генерирования порождают виды графов, которые встречаются в реальной жизни, и стали чрезвычайно популярны и цитируемы. Буквально каждая статья по Computer Science на предмет P2P начинает с повторения мантры о кольце и перекидываемых добавочных случайных связях и перечисления тех примеров графов "малых миров", которые дали W&S (граф нервной системы червя, цитируемости научных статей, электросистемы США, распространения эпидемий, директоров корпораций, с членством в более чем одном директорате); практически все в своих исследованиях пользуются сгенерированными на регулярных решетках со введенной случайностью построениями для опробования предлагаемых протоколов и т.д.
Одна мной обнаруженная статья, рассматривает реальный граф Гнутеллы, сравнивая его с результами Watts'а.
Второй чаще всего встречаемый мной в цитатах из Computer Science по вопросам P2P человек - Kleinberg. Он принимает без рассуждений модель Watts'а (иногда говорят Watts'а и Strogatz'а), но переформулирует проблему так: Milgram, Watts и т.д исследуя малые миры открыли не одну а две удивительные вещи. Первое, что мир так мал (6 шагов в эксперименте с письмами) Второе, что неочевидно - то, что в этом малом мире с короткими путями (от группы к группе) "через задворки" люди могут находить эти короткие пути. Далее он пишет работы (на языке математики) о том, какие алгоритмические системы поиска "коротких путей" можно придумать в "малых мирах".
Другими словами, Кляйнберг принимает безоговорочно "клубки" или "clusters" с подразумевается, но не говорится вслух, регулярной решеточной структурой, впрочем и весь мир имеет регулярную решеточную структуру с "естественными" для нее расстояниями по решетке - и более редкими "длинными связями" или "путями через задворки", которые вводят более быстрое распространение информации. Кляйнберг принимает безоговорочно необходимость случайности для порождения графов.
Кляйнберг утверждает, что общего алгоритма поиска для степенных графов нет, за исключением случая распределения второй степени ( число вершин L, и число их связей N [вставить формулу]).
Watts также занимается вопросом "просачивания" информации в подобных графах - т.е. исследует в точности тот процесс, идеальное без помех течение которого мы наблюдали в движущихся визуализациях. Продолжая держать в уме образ "клубков" соединенных длинными более редкими связями, которые превращают мир из "решеточного" с линейным ростом расстояний в "малый", он в статье о просачивании тратит немало усилий на введение неинтуитивных определений для вычисления размеров таких скученностей, а затем представляет распространение в графе как что-то вроде расходящихся сфер, которые могут расширяясь натыкаться на другие "соседства" и тем запускать их.
Вся его математика корчась обслуживает простой мысленный образ, который абсолютно не похож на то, что дает визуализация реального мира социальных связей.
4.2 Сомнения and speculations.
Польза этих теорий несомненна. Однако они основаны на ряде предположений и невысказанных психологических предпосылках, которые не обязательно верны. Поскольку сформулировав теорию, эти авторы генерируют для проверки случайные графы на компьютере по своим же правилам, изредка сравнивая интегральные характеристики с параметрами графов реальных малых миров, они в каком-то смысле ходят по логическому кругу, или варятся в своем собственном соку:
Одна из невысказанных предпосылок в том, что сгенерированный граф ведет вебя как бесконечный, и полученные для расползания параметры учитывают только первую фазу процесса, его нарастание (В. с небрежением говорит о "насыщении" когда что-то распространится достаточно сильно). В реальном мире любые сетки конечны.
Статью о распространении в степенных графах Watts называет "о просачивании в модели малого мира" (percolation, слово применяют в быту о процессе процеживания горячей воды через молотый кофе во время его заварки). Это придуманное представление завязано на традиции одного из подходов в математике (theory of percolation), но в той статье вне ее, в прямом смысле распространения информации по графу. Как я уже отметил, это совершенно не отвечает тому, что мы наблюдали на картинах расползания "идеального слуха".
(Note: "Идеальный слух" есть характеристика геометрия графа; иное поведение во времени будут показывать процессы например моделирующие заражение с задержками, вероятностью заражения, не все "соседи" подхватывают заразу, ограниченном периоде заразности (TTL) - но эти процессы на сети не есть, как "идеальный слух", характеристика самой сети. "Идеальный слух" - предельно достижимый максимум).
5.BIG BANG IN A SMALL WORLD.
Визуализация - сильнейшее средство, потому что, с одной стороны менее точная чем цифра, она более точна в том, что показывает больше всякого разного сразу и дает "целостную" картину.
Мы с вами находимся в лучшем положении - мы "это видели" - и виденное может нас натолкнуть на иную трактовку.
Во-первых, никакого "просачивания" в нашем р е а л ь н о м, а не сгенерированном мире нет за исключением серии с выбиванием самых сильных nodes, когда были оставлены только те, у кого меньше 50 взаимных друзей, которые демонстрируют качественно иное поведение. Переход к нему был постепенным, не резким, но оно к этому уровню уже меняется качественно.
В остальных случаях есть - как мы видим своими глазами - в з р ы в : шаг-два поджога, взрыв (2-3, иногда 4), выгорание мелких остатков.
Картина совершенно одинакова для сильно и слабо связанных вершин: для сильных взрыв начинается сразу, для слабых - после шага-двух "ползучего горения". Почему?
(а) Последний кадр на первой анимации - красные вершины недостигнуты (больше. чем при 50% случайном разрушении); части дерева и вершины, устраненные при изъятии вершин не показаны
(б) Вторая анимация - Покрывающее дерево убрано для наглядности, (в отличие от случая (а), где на первых кадрах видны зеленые звездочки - реальные остатки дерева). Отдельно дерево не приведено, т.к. оно практически полностью покрывается (все становится зеленым, красные точко практически отсутствуют - см. часть 2 для уточнений)
[На графике - сравнение фронтов "горения" для построений из 245к вершин и 58к вершин; построение и распространение от одного и того же ЖЖузера. Можно получить одну из оценок (не обязательно нижнюю) диаметра наибольшего построения и величину (наибольшей) связной компоненты по отношению к размерам всей вселенной.
Несколько групп кривых для малого мира (58000 вершин) показывают: слева - nodes с большим числом связей, в которых взрыв происходит почти сразу, правее - те, которым нужен дополнительный шаг или два чтобы добраться "с окраин". Как только это происходит, развивается точно такой же взрыв. ЖЖузер "поликаров" оказался вне связной части и его размазало по оси X, видно много красного.
Очевидно, что несмотря на высокие скорости распространения, полное выгорание "большого мира" происходит за большее число шагов (диаметр очевидно есть функция числа вершин).
Качественно поведение 58к и 200к миров, однако, одинаково. Поведение графа остается таким же, как мы висели выше, и при очень больших случайных воздействиях, и при выбивании самых сильносвязанных вершин до некоего порога. Это - самый замечательный результат.]
Простое естественное и сразу приходящее на ум объяснение (имея в виду, что у нас ненаправленный граф): потому что правильную математическую модель можно построить учитывая не количества входящих и исходящих вершин - процесс полностью описывается количеством "новых" вершин, т.е. ведущих к еще не "зараженным".
Количества связей сами по себе представляют лишь верхний предел возможного числа путей к незараженным, и в самом начале процесса они все и используются (заметьте, что на последнем графике поджог 200к несколько шагов распространяется практически одинаковыми по величине скачками, т.е. скорее всего используя все доступные новые связи), но затем по мере взрыва-выгорания распределение как бы динамически модифицирует само себя: процесс надо рассматривать не на бесконечном машинно сконструированном графе, а в ограниченном пространстве (как все small world networks в реальной жизни), как горение/взрыв ограниченного количества вещества.
На самом деле, я думаю, что правильной и точной математикой для нашего графа (и класса подобных "малых миров" из реальности) будут дискретизированные уравнения взрыва или горения веществ вроде пороха (физика горения, а не детонации).
Я пока что нашел одну случайную русскую технологическую статью с описанием определения параметров взрыва/горения для какой-то их хрени, и графики изменения давления в камере очень похожи на наши пошаговые построения выше, с подобным режимом взрыва (они называют это "экспоненциальным режимом") и горения (они аппроксимируют пологое поднятие до разрыва мембраны линейной функцией).
Возможно, случайность не имеет отношения к природе "малого мира", т.е для порождения самоподобия и геометрии взрыва. Можно представить себе алгоритмический набор формальных правил создающий граф "малого мира" и избежать вызывающих раздражение порождений введением случайных возмущений в регулярную решетку. [Интересно, что уже написав это я увидел ссылку на автора, который именно так и поступил, тем мое интуитивное представление впрямую доказав - пойду найду его статью и почитаю - добавлю отзыв ниже]
Я не могу представлять этот граф как куски "регулярных" решеточных скученностей, clusters (или просто clusters соседей), соединенные более редкими "длинными" связями, т.к. мне не кажется, что в наблюдаемом мире в принципе удастся выделить однородные и "регулярные" области по каким-то разумным непротиворечивым критериям - решеточные структуры не норма, как показалось математику (хотя концептуально разделение представлений полезно).
Впрочем, можно было бы заменить тянущееся по традиции слово "решетка" на "структура графа обеспечивающая при распространении по нему сигнала минимальное число новых связей".
То есть:
Вне математических представлений все три сформулированные особенности поведения нашего мира в смысле скорости распространения информации и достижимом за 3-4 шага охвате чрезвычайно полезны для создания системы распределенных блогов и наводят на мысль, что простой раутинг "by rumour" с коротким TTL и другими методами предотвращения flooding может быть достаточным для построения помехоустойчивой работоспособной системы.
О конкретных соображениях о построении ее возможно в части 4.
На этом автор останавливается и делает заключение, что
* Random graphs with arbitrary degree distributions and their applications -- M. E. J. Newman1,2 , S. H. Strogatz2,3 , and D. J. Watts1,4
* Collective dynamics of `small-world' networks -- Duncan J. Watts* & Steven H. Strogatz
* Exploring complex networks -- Steven H. Strogatz
* Scaling and percolation in the small-world network model -- M. E. J. Newman and D. J. Watts
*Random graph models of social networks -- M. E. J. Newman D. J. Watts S. H. Strogatz
* The Small-World Phenomenon: An Algorithmic Perspective -- Jon Kleinberg
* Small-World Phenomena and the Dynamics of Information -- Jon Kleinberg
* The Small-World Phenomenon and Decentralized Search -- Jon Kleinberg
* The Small World Web -- Lada A Adamic
* Peer-to-Peer Architecture Case Study: Gnutella Network -- Matei Ripeanu
* Mapping the Gnutella Network: Macroscopic Properties of Large-Scale Peer-to-Peer Systems Matei Ripeanu, Ian Foster
P.S. Математическую интерпретацию этих результатов - обзор области и изложение иной порождающей модели, предложенной автором, которая интуитивно кажется верной и не вызывает такого отторжения, как Watts - можно найти здесь:
Statistical Mechanics of Complex Networks
Reka Albert, and Albert-Laszlo Barabasi ( arXiv:cond-mat/0106096 v1 6 Jun 2001 )
Barabasi (иногда используется оригинальное (венгерское?) написание с диакрическим знаком над вторым а, учтите при поиске), кажется, одно из центральных имен в теории случайных графов.
У него есть статья, рассматривающая percolation (для направленных графов) с картинкой фазовых переходов и оценкой величины показателя степени распределения для попадания в области разных режимов распространения:
Percolation in Directed Scale-Free Networks
N. Schwartz, R. Cohen , D. ben-Avraham , A.-L. Barabasi and S. Havlin
arXiv:cond-mat/0204523 v2 6 Aug 2002
.
.
Big Bang in a Small World
спекулятивные но практические рассуждения о геометрии русского ЖЖ
.
Рассмотрение русского ЖЖ методами естественных наук началось несколько сумбурной заметкой которая ввела проблему как я ее вижу и указала на методы рассмотрения - сбора информации и визуализации для получения оценок.
Через полторы недели после первой вторая показала на красивых построениях структуру графа ЖЖ (через движущиеся иллюстрации того, как в нем распространяется "идеальных слух"). Вторая (предыдущая) часть здесь
Рассмотрение возникло из представления, что необходимо создать способ хранить "непотопляемую" информацию на Интернете. Сводки новостей постоянно подхлестывают: сегодня CNN пугает обывателей рассказывая о специальном законе, принятом в США для запрещения Internet Hunting, настоящего отстрела настоящих зверей через интерфейс в Интернете (и, разумеется, по американской традиции, противники запрета выдвигали главный козырь культуры политкорректности - защиту меньшинств (ваш запрет нарушит права инвалидов-охотников)).
Для иллюстрации ужасов неотрегулированного Интернета очевидных педофилов уже не хватает после международной облавы и ареста последних - 15? 30? - и честно говоря приедаются они, если каждый день. Между тем, где-то в ЖЖ мелькнула ссылка о наборе на оксфордскую программу по обучению/исследованиям "Internet governance": еще одно из многих указание на то, что проблема управления и юридической регулировки Интернета давно поставлена, фонды выделены, и она решается.
Поэтому - и к тому же следующие полторы недели истекли - можно продолжить рассмотрение структуры русского ЖЖ.
1. СБОР ИНФОРМАЦИИ
1.1 Во второй части были перечислены способы сбора информации о русском ЖЖ.
Чтобы не допустить искажения картины и заведомой всеобщей связности nodes, следует избегать хождения по друзьям-друзей-друзей как единственном методе сбора.
Самым объективным остается мониторинг новых постингов написанных по-русски. В первый день (23-24 апреля) было собрано достаточно данных, но скрипты выделяющие только русские посты оказались недостаточно надежны. В результате я остановил сбор после 24 часов и в построениях для второй части использовал dataset, составленный из:
- первых 12 часов "ловли" новых постов на русском (2112 порождающих имен, списки друзей которых, принесли больше); я наблюдал за поступлением информации и она во многом очищена "руками". Загрязнение ее постами на английском (и еще реже - на других языках, как испанский, немецкий, японский) - единицы процентов.
- внешнего списка из заметки какой-то журналистки об "известный людях (России) в ЖЖ"
- списка 100 самых популярных ЖЖистов из ljplus.ru
- друзей друзей двух ЖЖистов (идеей было использовать их как корневую и monitoring точки и хотелось иметь полную структуру их непосредственного окружения)
Полученный из примерно 2600 исходных имен/"родительких" файлов dataset в построениях дал граф с примерно 62.000 вершинами и 290.000 связями.
1.2 Через несколько дней, подправив скрипты, я сделал второй 24-часовой сбор информации. В этот раз он пришелся не на традиционно более медленные для русского ЖЖ выходные.
Во втором harvest я оцениваю засорение нерусскими ЖЖистами как единицы процентов, меньше 10 во всяком случае. Как отмечалось во второй части, (а) взаимные друзья культурно устойчивы да и барьер языка вряд ли преодолим (б) иностранные друзья русскоязычных ЖЖистов (из популярных на ум приходит, например, израильтянин
avva) на графе выделены как оконечные "листья" без связей, и программа-визуализатор размещает заметным образом (в) попавшие в порождающее множество не связанные с остальным деревом, в основном иностранцы, алгоритмом построения дерева выносятся за пределы его русской кроны на красные трехступенчатые фальшивые ножки, "prop branches", и очень заметны и легко проверяемы (щеклкнуть мышкой, проверить имя в ЖЖ взяв неинтерактивно информационную страницу)Самое большое построение по подмножеству полученных данных, которое вынес мой компьютер (недостаток RAM, extensive swapping as a result) представлено на графе с 245859 вершинами (людьми) и 979712 ребрами (взаимная дружба, почти на целый миллион дружбы).
Страница stats ЖЖ утверждает, что им известно порядка 160.000 плюс 18000 гарантированно русских; они скорее всего оценивали по информации на информационных/регистрационных записях:
( United States - 3498461 ... Canada - 243889 ... United Kingdom - 190848 ... Russian Federation - 160369 ... Australia - 85687 ... Ukraine - 17975 )
В таком случае, мои сборы имен, похоже, охватывают большую часть русскоязычной блогосферы ЖЖ.
2. СВЯЗНОСТЬ И РАСПРЕДЕЛЕНИЕ.
2.1 Из своих рассмотрений я могу сказать, что граф русского ЖЖ связен. Мне не удалось обнаружить сколько-нибудь значительных отдельных кусков. В наибольшем из построенных графов-миров, 245.859 nodes, "идеальный слух" от меня, например, доходит в самом большем построении до 207.627 nodes, покрывая примерно 85% графа. Это поведение типично, повторяемо для вычислений от других источников и годится для определения размеров наибольшей связной области. Вспомнив о некой загрязненности данных нерусскими ЖЖистами (не более 10% по моим прикидкам), мы можем видеть, что в русском ЖЖ все связаны со всеми.
Представление о русском ЖЖ как нескольких разных кусках неверно. Это один рой.
Мне кажется, что вряд ли также удастся представить ситуацию так, словно есть как бы "сгустки" пользователей, между которыми существуют более редкие "длинные" связи. Об этом ниже.
2.2
Во-вторых, для оценки наших сборов и свойств datasets следует посмотреть на распределения ЖЖузеров. На графике справа представлены распределения (гистограммы с шагом 10) числа количества ЖЖистов (y) от числа их взаимных друзей в интервале с шагом 10 (x). График нарисован линиями чтобы легче было читать. Шкалы логарифмическиеПравая синяя линия показывает распределение по самому большому построению (245.000 ЖЖузеров) от порождающего списка из собранных через monitoring новых постов данным. Следующая влево красная - по подмножеству приблизительно 58300 из тех, на которых производились эксперименты этой части; это подмножество практически совпадает с использовавшимся в части 2 (с одним исключением).
Можно отметить, что:
(а) такие распределения принято приблизительно считать "степенными" (power-law); утверждается, что порождаемые ими случайные графы принадлежат к одному типичному классу (power-law (random) graphs).
(б) Все кривые похожи: малое число ЖЖузеров с большим числом взаимных друзей (группа справа-внизу, порядка 500-1000; ЖЖ стал с 2005 года обрезать число наксимальных друзей, и, следовательно, взаимных науровне 750) -- больше, но мало средних -- огромное число ЖЖузеров (которые впервые выяснил harvesting новых постов) с малым числом связей.
Такие кривые иногда называют распределениями с тяжелым хвостом.
Рост, прибавка новых имен произошла в первую очередь за счет средних и еще более малосвязанных никому не известных (шкалы логарифмические): кривая отодвинула тулово и хвост вправо, практически не ворочая пришпиленной справа головой. Кстати, в крайнее лево должен был попасть и весь случайный и несвязанный с русскоязычными блогами мусор, который на этом графике показан
(в) Две прямые показывают для сравнения степенные функции с показателями (-1.6), сиреневая, и (-2.5), зеленая.
(г) Если после второго дня сборов мы смотрим на более чем 200.000 ЖЖистов, то в отсутствие маловероятных сюрпризов, правая кривая скорее всего верно отражает распределение всего возможного русского ЖЖ.
(г) Подобие кривых означает, что подмножество, которое мы рассматривали в [часть 2] и продолжаем применять здесь верно отражает целое (красная и синяя кривые практически параллельны). На самом деле одна из фундаментальных особенностей графа ЖЖ в том, что в очень гибких пределах части ведут себя точно как целое. Об этом ниже.
(д) Похожее распределение было получено по результатам мониторинга Gnutell'ы ( вот и вся "скрытость" этих систем ;)) - я все же нашел статью тех, кто пытался описать граф P2P, правда цифры и графики там не дают общего представления как это делает визуализация, из-за чего в этой и других статьях о P2P и графах им на мой взгляд приписываются несуществующие свойства, ниже).
Результат для Гнутеллы косвенно подтверждает наш результат.
О таких графах принято считать, что они хорошо устойчивы к случайным помехам и слабоустойчивы к атакам на самые сильные связи. Что мы и рассмотрим.
3. УСТОЙЧИВОСТЬ К РАЗРУШЕНИЮ.
3.1 Еще раз об идее подхода
Мы оцениваем жизнеспособность распределенного ЖЖ. Напомню, гениальная моя идея была в том, что распределенные блоги нужны как слой для создания системы социальных связей, первая основная и абсолютно открытая функция, и делать их нужно распределенными, а не централизованными чтобы создать достаточные потоки обмена на стандартных HTTP, HTTPS. Это позволит существовать (отдельной от самих блогов) сетке для неубиваемой информации, плохо обнаружимой, т.к. она неотличима от открытого traffic'а и его patterns, и интегрированной в служебную структуру services и протоколов Интернета (точнее, в моем примере Веба), который отделить от законного и необходимого чтобы запретить или отменить легко не удастся.
Дело в том, что современные модели P2P наивны, могут быть обнаружены любым школьником за несколько минут, и как показывает практика, они дешевы для шантажа угрозой суда со стороны больших компаний (список имен им стоит что-то около 200 долларов). Озаботившись раздумиями как можно сделать, я не нашел возможностей для анонимных скрытых сеток которые при том были бы общедоступны и обеспечивали обзор и поиск информации, оставаясь притом защищеными от разрушения. Максимум достигнутого - анонимность и "deniability", т.е. ответ в суде, что человек не знает что автоматически вытворяет его компьютер, жалкая защита, когда судом в США рассматривается вопрос о запрещении "file-swapping services" как класса программ, т.е. полное введение наказания за сам факт использования. И на ежа сесть, и зад не уколоть не удается.
Об этом в четвертой части.
Для рассмотрения я решил, что ЖЖ - пример идеальной сетки социальных связей, которые возникли сами собой. Условно говоря, если принять, что взаимные друзья - это основа для обмена "непотопляемой" информацией (подробнее об этом допущении потом), то следует наше рассмотрение русского ЖЖ квалифицировать как идеальную модель, случай общения без помех.
"Идеальные слухи", которые мы пускали во второй заметке, описывают структуру графа и показывают предельно благоприятный случай. В реальности на описанную структуру, если бы она отражала устройство гипотетической распреденной блогосферы или P2P, накладываются ограничения. Например, пользователи, которые немогут оставить компьютер on-line 24 часа в сутки.
Как промоделировать такие ограничения? Что случится, если часть сетки, подлежащей физической Интернет-структуры, станет недоступна? При намеренных атаках, из хулиганства или в случае официально открытого сезона охоты на блоггеров?
Эти эффекты можно описать моделируя разрушение идеального графа общения.
3.2 Разрушение можно проводить по-разному
Во-первых, можно выбивать только связи - или вершины, с которыми уйдут все их связи. Я делаю второе, более жесткое разрушение. Во-вторых, можно разрушать:
- выбивая ЖЖузеров и все принадлежащие им связи случайно.
- Нападая на ЖЖузеров с определенными характеристиками
- По расстрельным спискам составленным по каким угодно критериям.
Ниже я покажу поведение сетки при (а) случайных выбиваниях и (б) при методическом убийстве верших с самым большим числом связей, что интересно в свете предсказаний в литературе о плохой устойчивости таких графов.
Правда, авторы статей делали simulations на искусственно сгенерированных случайных степенных графах. Мы посмотрим на реально сложившуюся сетку.
Чтобы наблюдать эффект воздействия, я буду использовать в дополнение к animation два вида графиков: количество охваченных ЖЖузеров при распространении "идеального слуха" от номера шага и размер предельно достижимого связного компонента от степени разрушения.
Наш dataset для третьей части (который совпадает с тем, что был принят во второй части с одним небольшим отличием; как мы согласились выше, он "типичен" в смысле распределения и верно представляет картину для полного русского ЖЖ) состоит из приблизительно 58000 вершин (и 265000 связей). Из них достижимы примерно 54700, т.е. более 90%. Как изменится соотношение при устранении вершин графа?
3.2.1 Для прикидки я посмотрел как поведет себя граф при случайном изъятии 20, 50, 80 и 90% вершин и их связей.
Первый график показывает как происходит "поджог" графа. Данные для случайных разрушений нормализованы, т.е. для сравнения на одном графике мы представляем, что полные размеры графов как бы остаются неизменными. По оси X отложены шаги распространения (поколения взаимных друзей, расстояния от порождающей вершины), по Y - количество вершин, которых достиг "идеальный слух".Вспомните движущиеся визуализации из второй части (или см. ниже): вселенная русского ЖЖ резко "вспыхивает" на 3м и 4м шагах, заполняясь почти целиком.
Три почти вертикальных плотно лежащих кривых показывают этот процесс для полного графа (т.е. описывает процесс визуализаций из 2й заметки).
Поразительно, что после случайных разрушений характер процесса - резкие скачки и резкий "поджог" всей доступной части вселенной - совершенно не меняется. После 4-го шага охвачено 85-90% ЖЖузеров из доступной связной компоненты, и после 5го шага кривые становятся практически параллельными оси x, гореть больше нечему.
Высота "стола" показывает уменьшение относительного (графики нормализованы) размера доступной части.
Здесь (случайная серия отмечена зеленым цветом) верхняя линия показывает полный размер графа после изъятий, нижняя - ту его часть, которая остается достижимой для "идеального слуха", т.е. размер его связной (наибольшей связной) компоненты.Они практически параллельны, наша вселенная усыхает, но связная компонента присутствует, только видимая ей часть графа занимает меньшую и меньшую его долю.
Другими словами совершенно замечательно то, что граф с точки зрения распространения в нем информации продолжает вести себя качественно "почти" по-прежнему. Случайная атака не приводит к мгновенному распаду на отдельные куски и/или не приводит к ситуации, когда вместо мгновенного "воспламенения", распространение стало бы более медленным.
Это совершенно замечательный результат. Структура графа социальных связей такова, что в очень больших пределах поведение части графа подобно поведению целого.
Визуализации [вставить сюда] по-прежнему показывают характерное поведение, показанное на движущихся картинках во второй части.
Отличия тоже есть и я о них расскажу ниже.
3.2.2 Как изменится ситуация если уничтожать ЖЖузеров с наибольшими связями?
Я сделал серию (см. картинку с распределением для понятности) с уничтожением ЖЖузеров с более чем 500, 300, 100, 70, 50 Взаимных Друзей, которых оказалось соответственно 74, 236, 910, 1302 и 1800.Это - красные линии на графике выше. Видно, что убийство 1800 самых мощных вершин в нашем 58000 мире сужает пространство примерно так же, как выбивание 50% случайным образом.
На графике слева: верхняя линия показывает кривую для целого 58к построения без выбываний. Для строгости надо было бы строить распределение по всем ЖЖузерам, мы берем типичный пример хорошо соединенной вершины. Мы видим, что при атаках на самых больших, видимая часть графа для оставшихся резко уменьшается.
Однако и здесь поведение графа до уровня примерно 100 ВД качественно остается все тем же "поджогом", пока не остались самые малосвязанные (граф 70-50ВД и ниже) и самы многочисленные, тот самый "тяжелый хвост" распределения. Для них "взрыв" на 3-4 шагах превращается в более долгое "горение со вспышками" [здесь вставить более наглядную анимацию].
Сценарий, когда исчезают все большие возможен при преднамеренной атаке на сетку - в нашем примере достаточно убить 1800 чтобы резко сузить доступную часть и замедлить максимальную скорость распространения информации (повысить диаметр оставшейся доступной части графа) вместо сравнимых по воздейсвию 50-60% при случайном выбывании.
Сетки с малой интенсивностью -- как, возможно, американская часть ЖЖ, в которой я сильно не копался, но которая по сравнению с русской (а) демографически представлена 17-20летними (б) их миллионы (см. страницу статистики) (в) у них очень мало друзей, и еще меньше взаимных друзей по сравнению с русским роем -- возможно будут проявлять характеристики графа с выбитыми сильными вершинами. (конечно, полное ограничение на число общих друзей более 50 нереалистично, будет некая разношерстность, но характер по-видимому будет таким - резко сузившаяся видимая связная часть, больший диаметр, т.е. распространение информации требует большего числа шагов).
Понастроив этих графиков и анимаций, я решил, что с одной стороны они подтверждают те описания поведения "power-law random graphs", которые я смутно помнил, и с другой стороны когда остаются только nodes с 50ВД и меньше, изменения носят качественный характер.
Почему? Тут я пошел читать про "Малые Миры".
4. THIS IS A SMALL WORLD
4.1 История идеи "малого мира" широко известна и из популярной литературы и много раз пересказывалась в научных статьях.
Идее много лет. В 67м чтобы ее обосновать, социолог Милграм рассылал письма пытаясь прикинуть сколько шагов друзей друзей отделяют людей друг от друга и решил, что среднее значение 6 ( http://en.wikipedia.org/wiki/Small_worl
Следующий шаг в понимании как образуется "малый мир" связывают с математиком Watts'ом. Математика не менее других видов интеллектуальной деятельности завязана на образы и метафоры, и Ваттс начал построения от картинки как бы клубков связанных более длинными редкими связями. При этом подспудно и психологически он нормой считал крайнюю регулярность - для него "нормальный" граф есть решетка вроде кристалла, отклонения от которой он ищет в своей модели для порождения графа со свойствами "малого мира". Построение он начинает с одномерного случая и рисует кольцо на котором расположены точки - распространение информации идет от соседа к соседу, и занимает много шагов. Он считает расстояния по решетке как бы естественными и объективными. Но если мы будем бросать случайно связи-спицы вдобавок к решеточному движению строго по окружности, то возникнет случайный граф со свойствами "малого мира".
Визуальный образ клубков соединенных длинными редкими или более редкими связями также постоянно возникает в его математике в виде введенного в качестве основного "коэффициента кластеризации".
Ваттс ведет обсуждение в терминах вероятностей, что, добавлю от себя возражение, на самом деле отражает не столько свойства малых миров, они могут быть порождены как угодно, хоть по своду строжайших правил в соответствии с указом китайского императора (об этом ниже), сколько (а) традицию относить рассмотрение к теории случайных графов (б) методику создания графов Ваттсом. Первое отчасти просто несет какую-то "гарантию" потому что вероятность здесь имеет по большей части смысл усреднения, средних значений, верных для множества конкретных исполнений.
Duncan J. Watts & Steven H. Strogatz развили эти представления, обнаружили что их правила генерирования порождают виды графов, которые встречаются в реальной жизни, и стали чрезвычайно популярны и цитируемы. Буквально каждая статья по Computer Science на предмет P2P начинает с повторения мантры о кольце и перекидываемых добавочных случайных связях и перечисления тех примеров графов "малых миров", которые дали W&S (граф нервной системы червя, цитируемости научных статей, электросистемы США, распространения эпидемий, директоров корпораций, с членством в более чем одном директорате); практически все в своих исследованиях пользуются сгенерированными на регулярных решетках со введенной случайностью построениями для опробования предлагаемых протоколов и т.д.
Одна мной обнаруженная статья, рассматривает реальный граф Гнутеллы, сравнивая его с результами Watts'а.
Второй чаще всего встречаемый мной в цитатах из Computer Science по вопросам P2P человек - Kleinberg. Он принимает без рассуждений модель Watts'а (иногда говорят Watts'а и Strogatz'а), но переформулирует проблему так: Milgram, Watts и т.д исследуя малые миры открыли не одну а две удивительные вещи. Первое, что мир так мал (6 шагов в эксперименте с письмами) Второе, что неочевидно - то, что в этом малом мире с короткими путями (от группы к группе) "через задворки" люди могут находить эти короткие пути. Далее он пишет работы (на языке математики) о том, какие алгоритмические системы поиска "коротких путей" можно придумать в "малых мирах".
Другими словами, Кляйнберг принимает безоговорочно "клубки" или "clusters" с подразумевается, но не говорится вслух, регулярной решеточной структурой, впрочем и весь мир имеет регулярную решеточную структуру с "естественными" для нее расстояниями по решетке - и более редкими "длинными связями" или "путями через задворки", которые вводят более быстрое распространение информации. Кляйнберг принимает безоговорочно необходимость случайности для порождения графов.
Кляйнберг утверждает, что общего алгоритма поиска для степенных графов нет, за исключением случая распределения второй степени ( число вершин L, и число их связей N [вставить формулу]).
Watts также занимается вопросом "просачивания" информации в подобных графах - т.е. исследует в точности тот процесс, идеальное без помех течение которого мы наблюдали в движущихся визуализациях. Продолжая держать в уме образ "клубков" соединенных длинными более редкими связями, которые превращают мир из "решеточного" с линейным ростом расстояний в "малый", он в статье о просачивании тратит немало усилий на введение неинтуитивных определений для вычисления размеров таких скученностей, а затем представляет распространение в графе как что-то вроде расходящихся сфер, которые могут расширяясь натыкаться на другие "соседства" и тем запускать их.
Вся его математика корчась обслуживает простой мысленный образ, который абсолютно не похож на то, что дает визуализация реального мира социальных связей.
4.2 Сомнения and speculations.
Польза этих теорий несомненна. Однако они основаны на ряде предположений и невысказанных психологических предпосылках, которые не обязательно верны. Поскольку сформулировав теорию, эти авторы генерируют для проверки случайные графы на компьютере по своим же правилам, изредка сравнивая интегральные характеристики с параметрами графов реальных малых миров, они в каком-то смысле ходят по логическому кругу, или варятся в своем собственном соку:
Random graphs with arbitrary degree distributions and their applications
M. E. J. Newman1,2 , S. H. Strogatz2,3 , and D. J. Watts1,4
arXiv:cond-mat/0007235 v2 7 May 2001
[...]In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. [...] We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors.
We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the b ehavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
Одна из невысказанных предпосылок в том, что сгенерированный граф ведет вебя как бесконечный, и полученные для расползания параметры учитывают только первую фазу процесса, его нарастание (В. с небрежением говорит о "насыщении" когда что-то распространится достаточно сильно). В реальном мире любые сетки конечны.
Статью о распространении в степенных графах Watts называет "о просачивании в модели малого мира" (percolation, слово применяют в быту о процессе процеживания горячей воды через молотый кофе во время его заварки). Это придуманное представление завязано на традиции одного из подходов в математике (theory of percolation), но в той статье вне ее, в прямом смысле распространения информации по графу. Как я уже отметил, это совершенно не отвечает тому, что мы наблюдали на картинах расползания "идеального слуха".
(Note: "Идеальный слух" есть характеристика геометрия графа; иное поведение во времени будут показывать процессы например моделирующие заражение с задержками, вероятностью заражения, не все "соседи" подхватывают заразу, ограниченном периоде заразности (TTL) - но эти процессы на сети не есть, как "идеальный слух", характеристика самой сети. "Идеальный слух" - предельно достижимый максимум).
5.BIG BANG IN A SMALL WORLD.
Визуализация - сильнейшее средство, потому что, с одной стороны менее точная чем цифра, она более точна в том, что показывает больше всякого разного сразу и дает "целостную" картину.
Мы с вами находимся в лучшем положении - мы "это видели" - и виденное может нас натолкнуть на иную трактовку.
Во-первых, никакого "просачивания" в нашем р е а л ь н о м, а не сгенерированном мире нет за исключением серии с выбиванием самых сильных nodes, когда были оставлены только те, у кого меньше 50 взаимных друзей, которые демонстрируют качественно иное поведение. Переход к нему был постепенным, не резким, но оно к этому уровню уже меняется качественно.
В остальных случаях есть - как мы видим своими глазами - в з р ы в : шаг-два поджога, взрыв (2-3, иногда 4), выгорание мелких остатков.
Картина совершенно одинакова для сильно и слабо связанных вершин: для сильных взрыв начинается сразу, для слабых - после шага-двух "ползучего горения". Почему?
Выгорание: все nodes с > 50 ВД убраны;  Здесь картинка большего размера | Взрыв - полный граф;  Здесь картинка большего размера |
(а) Последний кадр на первой анимации - красные вершины недостигнуты (больше. чем при 50% случайном разрушении); части дерева и вершины, устраненные при изъятии вершин не показаны
(б) Вторая анимация - Покрывающее дерево убрано для наглядности, (в отличие от случая (а), где на первых кадрах видны зеленые звездочки - реальные остатки дерева). Отдельно дерево не приведено, т.к. оно практически полностью покрывается (все становится зеленым, красные точко практически отсутствуют - см. часть 2 для уточнений)
[На графике - сравнение фронтов "горения" для построений из 245к вершин и 58к вершин; построение и распространение от одного и того же ЖЖузера. Можно получить одну из оценок (не обязательно нижнюю) диаметра наибольшего построения и величину (наибольшей) связной компоненты по отношению к размерам всей вселенной.
Несколько групп кривых для малого мира (58000 вершин) показывают: слева - nodes с большим числом связей, в которых взрыв происходит почти сразу, правее - те, которым нужен дополнительный шаг или два чтобы добраться "с окраин". Как только это происходит, развивается точно такой же взрыв. ЖЖузер "поликаров" оказался вне связной части и его размазало по оси X, видно много красного.Очевидно, что несмотря на высокие скорости распространения, полное выгорание "большого мира" происходит за большее число шагов (диаметр очевидно есть функция числа вершин).
Качественно поведение 58к и 200к миров, однако, одинаково. Поведение графа остается таким же, как мы висели выше, и при очень больших случайных воздействиях, и при выбивании самых сильносвязанных вершин до некоего порога. Это - самый замечательный результат.]
Простое естественное и сразу приходящее на ум объяснение (имея в виду, что у нас ненаправленный граф): потому что правильную математическую модель можно построить учитывая не количества входящих и исходящих вершин - процесс полностью описывается количеством "новых" вершин, т.е. ведущих к еще не "зараженным".
Количества связей сами по себе представляют лишь верхний предел возможного числа путей к незараженным, и в самом начале процесса они все и используются (заметьте, что на последнем графике поджог 200к несколько шагов распространяется практически одинаковыми по величине скачками, т.е. скорее всего используя все доступные новые связи), но затем по мере взрыва-выгорания распределение как бы динамически модифицирует само себя: процесс надо рассматривать не на бесконечном машинно сконструированном графе, а в ограниченном пространстве (как все small world networks в реальной жизни), как горение/взрыв ограниченного количества вещества.
На самом деле, я думаю, что правильной и точной математикой для нашего графа (и класса подобных "малых миров" из реальности) будут дискретизированные уравнения взрыва или горения веществ вроде пороха (физика горения, а не детонации).
Я пока что нашел одну случайную русскую технологическую статью с описанием определения параметров взрыва/горения для какой-то их хрени, и графики изменения давления в камере очень похожи на наши пошаговые построения выше, с подобным режимом взрыва (они называют это "экспоненциальным режимом") и горения (они аппроксимируют пологое поднятие до разрыва мембраны линейной функцией).
Возможно, случайность не имеет отношения к природе "малого мира", т.е для порождения самоподобия и геометрии взрыва. Можно представить себе алгоритмический набор формальных правил создающий граф "малого мира" и избежать вызывающих раздражение порождений введением случайных возмущений в регулярную решетку. [Интересно, что уже написав это я увидел ссылку на автора, который именно так и поступил, тем мое интуитивное представление впрямую доказав - пойду найду его статью и почитаю - добавлю отзыв ниже]
Я не могу представлять этот граф как куски "регулярных" решеточных скученностей, clusters (или просто clusters соседей), соединенные более редкими "длинными" связями, т.к. мне не кажется, что в наблюдаемом мире в принципе удастся выделить однородные и "регулярные" области по каким-то разумным непротиворечивым критериям - решеточные структуры не норма, как показалось математику (хотя концептуально разделение представлений полезно).
Впрочем, можно было бы заменить тянущееся по традиции слово "решетка" на "структура графа обеспечивающая при распространении по нему сигнала минимальное число новых связей".
То есть:
1. Как я отмечал выше, первая главная особенность "малого мира" вроде русского ЖЖ, насколько я ее понял, в том, что граф устроен так, что его части подобны целому в очень широком диапазоне делений и недружелюбных воздействий. Это совершенно замечательное наблюдение с практической точки зрения.
2. Геометрия связей обеспечивающая "взрыв" есть его вторая главная особенность. При обеднении связей в какой-то момент взрыв заменяется горением, затем спорадическим "бегущим огнем" со вспышками там, где горючего больше, как подожженная сухая осенняя трава.
3. В-третьих, он представляет из себя одну гигантскую связную компоненту, покрывающую подавляющее число вершин.
Вне математических представлений все три сформулированные особенности поведения нашего мира в смысле скорости распространения информации и достижимом за 3-4 шага охвате чрезвычайно полезны для создания системы распределенных блогов и наводят на мысль, что простой раутинг "by rumour" с коротким TTL и другими методами предотвращения flooding может быть достаточным для построения помехоустойчивой работоспособной системы.
О конкретных соображениях о построении ее возможно в части 4.
На этом автор останавливается и делает заключение, что
Russian LJ, in a sense, is a real bomb. ;))
* Random graphs with arbitrary degree distributions and their applications -- M. E. J. Newman1,2 , S. H. Strogatz2,3 , and D. J. Watts1,4
* Collective dynamics of `small-world' networks -- Duncan J. Watts* & Steven H. Strogatz
* Exploring complex networks -- Steven H. Strogatz
* Scaling and percolation in the small-world network model -- M. E. J. Newman and D. J. Watts
*Random graph models of social networks -- M. E. J. Newman D. J. Watts S. H. Strogatz
* The Small-World Phenomenon: An Algorithmic Perspective -- Jon Kleinberg
* Small-World Phenomena and the Dynamics of Information -- Jon Kleinberg
* The Small-World Phenomenon and Decentralized Search -- Jon Kleinberg
* The Small World Web -- Lada A Adamic
* Peer-to-Peer Architecture Case Study: Gnutella Network -- Matei Ripeanu
* Mapping the Gnutella Network: Macroscopic Properties of Large-Scale Peer-to-Peer Systems Matei Ripeanu, Ian Foster
P.S. Математическую интерпретацию этих результатов - обзор области и изложение иной порождающей модели, предложенной автором, которая интуитивно кажется верной и не вызывает такого отторжения, как Watts - можно найти здесь:
Statistical Mechanics of Complex Networks
Reka Albert, and Albert-Laszlo Barabasi ( arXiv:cond-mat/0106096 v1 6 Jun 2001 )
Barabasi (иногда используется оригинальное (венгерское?) написание с диакрическим знаком над вторым а, учтите при поиске), кажется, одно из центральных имен в теории случайных графов.
У него есть статья, рассматривающая percolation (для направленных графов) с картинкой фазовых переходов и оценкой величины показателя степени распределения для попадания в области разных режимов распространения:
Percolation in Directed Scale-Free Networks
N. Schwartz, R. Cohen , D. ben-Avraham , A.-L. Barabasi and S. Havlin
arXiv:cond-mat/0204523 v2 6 Aug 2002
