Твиттер как нелинейная динамическая система

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет бизнеса и менеджмента

Школа бизнес-информатики

Выпускная квалификационная работа - БАКАЛАВРСКАЯ РАБОТА

по направлению подготовки Бизнес-Информатики студента группы ББИ144

образовательная программа «Бизнес-Информатика»

ТВИТТЕР КАК НЕЛИНЕЙНАЯ ДИНАМИЧЕСКАЯ СИСТЕМА

Сомов Александр Евгеньевич

Научный руководитель

д-р. физ.-мат. наук., проф.

Дмитриев А.В.

Москва 2018



Оглавление

Введение

Актуальность

Методологические предпосылки исследования

Цель исследования

Задачи исследования

Объект исследования

Предмет исследования

Методы исследования

Практическая значимость результатов

Краткое описание структуры работы

Обзор литературы

Обоснование выбора литературы

Литература

Предметная область

Ключевые термины и определения

Данные

Способ получения

Описание полученной выборки

Принадлежность сети к классу сложных и наличие фрактальности с точки зрения структуры

Сложность сети

Фрактальность

Наличие у системы фрактальности с точки зрения временного ряда

Признаки фрактальности временного ряда

Вычисление основных индикаторов фрактальности временного ряда

Выводы

Моделирование процесса работы системы

Использование модели как инструмента политической борьбы

Заключение

Список использованной литературы



Введение

Актуальность

За последнее десятилетие социальные сети превратились из средств коммуникации в огромные СМИ, которые оказывают значительное влияние на население в целом. В частности, политические стратеги заинтересовались этим явлением как одним из инструментов в гонке за голоса избирателей (McClurg, Scott, 2003). Широко известно, что ряд современных лидеров демократических стран добился победы через социальные сети. Недавним сенсационным примером является избрание президента США Дональда Трампа. Это не случайно, потому что в Twitter люди делятся своими мнениями и формируют свои взгляды на основе информации, которую они используют из разных источников. Это можно использовать, создавая точки воздействия информацией, которые будут влиять на приверженность определенных социальных групп тому или иному политическому лидеру. Доказательством способности точно определять факторы и силу, которая влияет на данное значение с определенной вероятностью, является необходимой основой для практической реализации такого информационного воздействия как политическими стратегами, так и маркетологами, исследователями и другими.

Моделирование процессов, происходящих в социальных сетях, является сложной, но в то же время теоретически и практически важной научной проблемой. Результаты и выводы, которые могут быть сделаны с использованием моделей социальных сетей, позволяют определять, сможет ли социальная сеть оставаться стабильной при внутреннем и внешнем информационном воздействие, выявлять различные способы формирования сообществ и выяснять практические способы управление социальной сетью. Моделирование социальных сетей может иметь широкий масштаб применений: может быть полезно для процессов принятия решений при разработке краткосрочных и долгосрочных маркетинговых стратегий, разработке систем рекомендаций, прогнозировании спроса, а также задачах, связанных с национальной безопасностью (Dmitriev, Dmitriev, Tsukanova, Maltseva, 2017).



Методологические предпосылки исследования

Структура функционирования Twitter по своей системе напоминает другие системы, которые неоднократно были изучены другими областями науки. Что позволяет предположить, что используя различные уже изученные в других областях научные методы можно рассмотреть, как практически использовать социальную сеть, для воздействие на массовое сознание. Например, устройство Twitter хорошо ложится на теорию сложности, теорию хаоса и нелинейную динамика. Эти направления изучения могут с большой эффективностью моделировать и прогнозировать поведение современного общества в контексте соц. сети. Сложной в математике считается система, которая одновременно обладает пятью-шестью признаками. Предыдущие исследователи (Dmitriev, Dmitriev, Tsukanova, Maltseva, 2017) о проблеме сложности Twitter доказали одновременное присутствие максимум трех из пяти-шести особенностей сложности, что потенциально дает основания для дальнейшего исследования данной проблемы. В частности, одним из разделов теории сложности является теория сложных сетей. В данной работе в качестве дальнейшего изучения проблемы сложности Twitter будет проведен анализ структуры Twitter на предмет того, является ли она сложной сетью.

Цель исследования

Цель данного исследования заключается в построение динамической модели Twitter и определения значений ключевых факторов, при которых состояние сети радикально меняется. Для доказательства такой потенциальной возможности изменения нужно доказать наличие определенных свойств в социальной сети.



Задачи исследования

Ключевыми задачами для достижения поставленной цели являются:

1. Рассмотреть социальную сеть Twitter с точки зрения двух направлений: сложность сети Twitter и анализ изменения количественных показателей

o Сложность сети Twitter

§ Анализ структуры сети Twitter и определение является ли Twitter по структуре сложной сетью через доказательство наличия пяти-шести признаков сложности

§ Определение типа сложной сети, к которому принадлежит Twitter

o Доказать наличие признаков сложности у временного ряда количественных показателей Twitter

2. Построить динамическую модель сети Twitter

3. Определить ключевые факторы и их начальные значения, которые приводят к радикальным изменениям в топологической и временной структуре Twitter

Объект исследования

twitter динамический сеть временный

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



Предмет исследования

Автором данного исследования, в качестве предмета исследования, будут рассмотрены два направления признаков социальной сети. С одной стороны для понимания возможности применения практических научных методов воздействия на социальную сеть нужно доказать является ли Twitter сложной фрактальной сетью. С другой стороны для понимания возможности применения практических научных методов к данной сети будет необходимо рассмотреть количественные показатели соц. сети в процессе их изменения, для этих целей будут использован методы анализа мультифрактальных временных рядов. На основе полученных данных от двух направлений признаков будет возможным смоделировать процессы функционирования соц. сети.

Методы исследования

Для изучения поставленной проблемы, автору исследования необходимо изучить существующие подходы к сложным сетям и их моделирование. Таким образом, в работе будут применены следующие исследовательские методы:

· анализ литературы

· изучение существующих сложных систем

· изучение существующих моделей сложных систем

· практические расчеты и моделирование

· теоретический анализ и синтез



Практическая значимость результатов

Предыдущими исследователями данной проблемы был описан ряд вопросов по продолжению и улучшению исследования (Dmitriev, Dmitriev, Tsukanova, Maltseva, 2017). В рамках данного исследования автор собирается расширить и уточнить предыдущий опыт, тем самым создав исследование с более расширенной научной обоснованностью.

Краткое описание структуры работы

Во введении описана актуальность работы и методологические предпосылки исследования, поставлена цель и задачи, раскрыты объект, предмет, методы исследования, а также практическая значимость работы.

В первой главе раскрыта предметная область и заданы ключевые термины и определения данной области, приведен литературный обзор.

Во второй главе будет проведено изучение структуры Twitter на предмет сложности и мультифрактальности. Также в этой главе будут построены временные ряды по данным из сети.

Третья глава посвящена моделированию сети Twitter и экспериментам относительно влияния на модель.

В заключении представлены результаты исследования, а также описаны возможные пути развития и дополнения.

Обзор литературы

Обоснование выбора литературы

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

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

Литература

В статье «A Nonlinear Dynamical Approach to the Interpretation of Microblogging Network Complexity» Андрея Дмитриева, Виктора Дмитриева, Ольги Цукановой и Светланы Мальцевой (2017 г.) была рассмотрена сложность Twitter в терминах временных рядов, представляющих изменения характеристик социальной сети. Это доказало существование основных показателей сложности системы: масштабную инвариантность, тенденцию к катастрофам и неравновесное состояние. В результате было получено, что временные ряды Twitter имеют распределение вероятностей энтропии Tsalis (q-экспоненциальной), что также позволяет говорить о социальной сети Twitter как о классе сложных систем. Они были дополнительно смоделированы по уравнению Каулакиса, которое хорошо подходит для описания сигналов и, следовательно, временных рядов (Дмитриев, Дмитриев, Цуканова, Мальцева, 2017).

В статье «Investigation into the Regular and Chaotic States of Microblogging Networks as Applied to Social Media Monitoring» Андрея Дмитриева, Виктора Дмитриева, Ольги Цукановой и Светланы Мальцевой (2016 г.) более подробно рассмотрены вопросы, которые описаны в статье выше, а также приведен подробный анализ моделирования микроблогов. Работа посвящена исследованию эволюционной динамики социального микроблога. Рассмотрены различные состояния сети: регулярные и хаотические. В статье предложена и обоснована новая модель социальной сети микроблогов: точечная диссипативная система. Представлены динамические переменные такой системы по вариациям числа твитов / ретвитов вокруг равновесного значения. Указывается, что система находится в условиях асимптотически устойчивого равновесия, когда значения интенсивности внешней информации малы (количество твитов в конечном итоге стремится к его равновесному значению). Когда значения интенсивности внешней информации не превышают критическое значение, в системе микроблога наблюдается стабильность (почти гармоническая), происходят колебания твитов. Если интенсивность значения внешней информации превышают критическое значение, тогда следует наблюдать хаотические колебания твитов.

В статье «Multifractal analysis of complex networks» Wang Dan-Ling, Yu Zu-Guo и Anh V (2012) предлагается новый алгоритм построения полей для вычисления фрактальной размерности связанного графа, что позволяет принять или отклонить гипотезу мультифрактальности сети. Этот алгоритм был протестирован на четырех разных типах сетей: искусственных сетях без малейших сетей, сетях малого масштаба и случайных сетях, а также сети взаимодействия белка и белка на основе реальных данных. В результате исследования была продемонстрирована мультифрактальность в сетях artificial scale-free, small world, random и на сети protein-protein interaction (Dan-Ling, Zu- Guo, V, 2012).

В статье «Fractal Characterization of Complex Networks» (2015) Roland Molontay («Фрактальная характеристика сложных сетей») рассмотрел теорию фрактальных сетей, он не продвигает одну цель: пересмотреть основные достижения в этой области, наоборот, он продвинул исследование и обработал недостаток математического строгости соответствующих статей и предлагал различные подходы к уточнению понятий. В начальных главах рассматривались основные понятия теории сложности: фрактальность и автомодельность, и было доказано, что эти характеристики присущи любой сложной сети. Проведен обзор предыдущих работ, посвященных изучению этих характеристик, а также их точная математическая формализация и устранение дефектов, сделанных предыдущими исследователями. Кроме того, был исследован базовый алгоритм покрытия полей, чтобы доказать существование фрактальности и автомодельности, модификации которых могут быть успешно использованы для доказательства сложности реальных систем и сетей. Далее в статье автор рассмотрел дальнейшие размеры сети в дополнение к фрактальной размерности: метрическую размерность, фрактальную размерность кластера и т. д. Это дало возможность более глубокого понимания природы сложных сетей с использованием этих новых характеристик. Основным результатом этой работы стала формализация понятий фрактальности и самоподобия и исчерпывающий список методов и характеристик, которые помогают анализировать и описывать сложные сети (Molontay, 2015).

В статье «Possible generalization of Boltzmann-Gibbs statistics» Constantino Tsallis (Constantino Tsallis, 1987) предлагается обобщение энтропии Больцмана, устраняя обязательное условие экстенсивности переменных системы. Это предположение позволяет моделировать поведение сложных систем с выраженной мультифрактальностью и heavy-tailored распределением, что, в частности, указывает на наличие дальних взаимодействий в замкнутой системе. Выводы Constantino Tsallis позволяют доказать существование одной из необходимых особенностей сложности системы, которая до появления этой работы была невозможна, путем сравнения энтропии системы рассмотрения с энтропией Tsallis и проверки гипотезы их распределения подобия (Tsallis, 1987).

Отдельно можно отметить ряд статей посвящённых физическому моделированию социальных сетей.

Работа «Statistical mechanics of complex networks» Reka Albert and Albert-Laszlo Barabasi (2002) посвящена исследованию физической природы любых организационных структур с точки зрения их математического анализа. В статье отмечается, что сложные сети описывают широкий спектр систем в природе и обществе. Например сложными системами часто называют: устройство клетки, сеть химических веществ, связанных химическими реакциями, и др. Но ведь и интернет это есть сеть маршрутизаторов и компьютеров, соединенных физическими связями. Хотя традиционно все эти системы были смоделированы как случайные графы, все чаще отмечается, что топология и эволюция реальных сетей регулируются надежными организационными принципами. В этой статье актуальные исследования сложных сетей, однако, основное внимание уделяется статистической механике и топологии и динамики сети. Авторы исследования обсуждают основные модели и аналитические инструменты, охватывающие случайные графики, сети малого масштаба, возникающую теорию эволюционирующих сетей и взаимодействие между топологией и устойчивость сети к отказам и атакам.

Работа «Phase of Ising spins on modular networks analogous to social polarization» (2009) Subinay Dasgupta, Raj Kumar Pan, and Sitabhra Sinha посвящена исследованию модели Изинга. Модель Изинга описывает процессы упорядочивания в сложных сетях. Так процессы координации в сложных системах могут быть связаны с проблемой коллективного упорядочения в сетях, многие из которых имеют модульную организацию. Авторы исследования отмечают, что исследуя переход порядка и беспорядка на модульные случайные сети, они наблюдали различные формы формирования консенсуса в обществе. На основе наблюдений они выделили две различные фазы: упорядочение внутри каждого модуля при критической температуре, за которым следует глобальное упорядочение при более низкой температуре. Это указывает на поляризацию общества на группы, имеющие противоположные мнения, которые могут сохраняться бесконечно, даже когда взаимное взаимодействие между агентами способствует достижению консенсуса.

Работа «Bose-Einstein Condensation in Complex Networks» Ginestra Bianconi (2001) посвящена исследованию природы различных социальных сетей на предмет их рассмотрения с точки зрения природы равновесных квантовых газов. Эволюция многих сложных систем, в том числе сетей интернет, социальный сетей и др., кодируется в динамической сети, описывающей взаимодействия между составляющими системы. Несмотря на их необратимый и неравновесный характер, эти сети следуют за статистикой Бозе и могут подвергаться конденсации Бозе-Эйнштейна. Рассмотрение динамических свойств этих неравновесных систем в рамках равновесных квантовых газов предсказывает, что наблюдаемые в конкурентных системах явления «первопроходца», «пригодности-обогащения» и «победителя-все-все» являются термодинамически-отличными фазами основных эволюционирующих сетей.

Еще одна модель физического моделирования посвящена модели квантового пробега. Работа «Degree Distribution in Quantum Walks on Complex Networks» (2013) Faccin M, Johnson T, Biamonte J, Kais S посвящена анализу квантового блуждания по сложным сетям, которое моделируют сетевые процессы, от квантовых вычислений до биологии и даже социологии. В частности, в статье аналитически относят среднее распределение вероятности долгого времени для местоположения унитарного квантового ходока по сравнению с соответствующим классическим ходоком.

В работе «Statistical mechanics of community detection» (2006) Reichardt J, Bornholdt S., рассматриваются методы нахождения сообществ и первоначальных состояний. В данной работе структура сообщества сети интерпретируется как spin configuration, это минимизирует энергию spin glass, причем такие состояния являются индексами сообщества. Авторы выясняют свойства конфигурации основного состояния, чтобы дать краткое определение сообществ как сплоченных подгрупп в сетях, которые адаптированы к конкретному классу исследуемой сети. Кроме того, авторы работы показывают, как иерархии и совпадения в структуре сообщества могут быть обнаружены.

Предметная область

В последние годы наука о сетях становится отдельной новой дисциплиной, имеющей большое значение. Началом данной науки можно отметить 2005 год, когда Национальный исследовательский совет Соединенных Штатов определил науку о сетях как новое поле фундаментальных исследований (National Research Council Committee on Network Science for Future Army Applications, 2005). Самые выдающиеся академические издательские компании объявляют о запуске новых журналов, посвященных сложным сетям, один за другим:

· Журнал Journal of Complex Network by Oxford University Press

· Журнал Network Science by Cambridge University Press

Ведущие университеты также постоянно создают исследовательские центры для исследования сложных сетей, такие как: Йельский университет, Университет Дьюка, Северо-восточный университет, Центрально-Европейский университет, последние два из них запустили программы PhD в этой области. Значение теории сети также отражено в большом количестве публикаций о сложных сетях и в огромном числе цитирования пионерских работ Барабаша и Альберта (Barabasi, Albert, 1999) и Ватса и Строгаца (Watts, Strogatz, 1998), которые первыми обратили внимание на сложные сетей. Некоторые ученые интерпретируют сетевую науку как новый сдвиг парадигмы (Kocarev, Visarath, 2010). Сложные сети влияют на исследовательское сообщество, но они даже появлялись в популярной литературе (Watts, 2003) и средствах массовой информации (Bollobas, Riordan, 2004).

Сложные сети исследуют несколько разрозненных дисциплин математики, в первую очередь, с точки зрения, теории графов и вероятностей. Математики иногда испытывают трудности с науками о сети, поскольку в основном исследования ведутся с эмпирической точки зрения без математической строгости, но с понятиями, основанными на симуляциях. Также важно упомянуть некоторые критические высказывания в области сложных сетей. Некоторые статьи ставят под сомнение вездесущность безмасштабного свойства, но допускают предположение о том, что биологические сети или сеть Интернет свободны от масштаба (Lima-Mendez, Helden, 2009), (Tanaka, 2005), (Willinger, Alderson, Doyle, 2009). В этих документах утверждается, что в большинстве случаев, в публикациях недостаточно данных, а измерения не имеют удовлетворительного качества для не удовлетворяют цели, для которой они предназначены, кроме того, нет тщательных статистических испытаний (Stumpf, Porter, 2012). Критики теории науки о сетях также отмечают недостаточность дифференциации методов применяемых в исследованиях: при изучении сетей обычно нет статистически чистого разделения данных, используемые модели, зачастую применяются на этапах и выборки и проверки. Из недостатков исследовательских методов, также отмечается, что множество утверждений получается путем подстроения и подгонки, например, создание логарифмических графиков степени по частоте и установке прямой линии. Неточность подчеркивается тем, что обычно используемые методы, такие как подгонка наименьших квадратов, могут давать достаточно неточные оценки параметров (Clauset, Shalizi, Newman, 2009). Стоить отметить, что важность изучения сложных сетей и наук о сетях в целом, не ставит под сомнение не один из исследователей. В первую очередь среди тех, кто критикует существующие теории, вызывают озабоченность именно методов и заявления существующих исследователей сложных сетей.

Теория сетей обладает большим потенциалом для изучения математики с несколькими выдающимися математическими вызовами. Чтобы устранить существующую двусмысленность в математической формулировке и методах исследования. Многие выдающиеся математики пытаются построить математически прочную основу данной проблемы: развивая теорию беспорядочных случайных графов (Bollobas, Riordan, 2003, 2004), развивая теорию графовых последовательностей и границ графа (Lovasz, 2012), (Borgs, Chayes, Lovasz, Sos, Szegedy, Vesztergombi, 2006), вырабатывая точные концепции теории графов без шкалы (Li, Alderson, Doyle, Willinger, 2005), создавая определения математических основ случайных сетевых моделей (Hofstad, 2009). Тем не менее можно утверждать, что математически строгие концепции и теории иногда не отвечают реальным интересам исследователей данной проблемы. Пример: большинство теорий разработаны для графиков, стремящихся к бесконечности, но для практических целей больше интересны сети реального мира (которые, безусловно, имеют конечные узлы). Важно также отметить, что как и в научной литературе, так и в этой работе в большинстве случаев понятие network (сеть) и graph (граф) являются взаимозаменяемыми понятиями. Обычно мы используем понятие сеть, если хотим подчеркнуть его реальный характер, и понятие граф, если хотим подчеркнуть его математические свойства.

Одним из ключевых направлений данной работы является изучение сложных сетей. Сложные сети широко изучаются, так как они описывают, широкий спектр систем, охватывающих множество различных дисциплин, таких как биология (например, сети взаимодействия с белками), информационные технологии (например, всемирная паутина, Интернет), социальные науки (например, социальные сети, сетей связей человека) и т. д. Соответственно, сети появляются в науке повсеместно, поскольку они могут представлять различные системы в разумной форме. Характеристика топологии сетей очень важна для широкого спектра статических и динамических свойств (например, топология социальных сетей влияет на распространение информации и вирусов). Одно из самых важных открытий состоит в том, что, несмотря на разнообразие сетей, большинство сетей реального мира имеют особые свойства, которые во многом отличаются от случайных сетей (например, случайный граф Erdos-Renyi random graph (Erdos, Renyi, 1960)). Основными типами графов сложных сетей привлекающих внимание в последнее время являются: small-world и scale-free графы. Small-world - это такой тип графа, в котором среднее расстояние между вершинами логарифмически масштабируется с количеством узлов (Watts, Strogatz, 1998). Scale-free - это такой тип графа, в котором распределение степени следует степенному закону (Barabasi, Albert, 1999).

Другими фундаментальными основами, которые находятся в центре внимания этой работы, являются самоподобие и фрактальность. Фрактальность, иными словами, исследует выглядит ли вся сеть так же, как и ее подразделение. Несмотря на то, что нет разницы между фрактальностью и самоподобием по отношению к регулярным фрактальным объектам, в теории сетей принято различать эти два термина: фрактальность означает степенное соотношение между минимальным количеством делений, необходимых для покрытия всей сети, и размером этих делений, тогда как самоподобная сеть определяется как сеть, распределение степени которой инвариантно относительно перенормировки (Song, Havlin, Makse, 2005).



Ключевые термины и определения

В этом разделе автор исследования вводит наиболее важные определения теории сетей и фиксирует обозначения, используемые в данной работе. Отмечая тот факт, что сеть означает систему, которая может быть смоделирована графиком (в большинстве случаев неориентированным одиночным графом), многие понятия в данной работе исходят из теории графов. Тем не менее, тема исследуемая в данной работе очень новая, поэтому она исследуется в основном эмпирически: с более практической точки зрения учеными из нескольких дисциплин, в связи с этим, определения не всегда точны в математическом смысле, а иногда терминология не является следствием математики указанной в статьях. В качестве источников для создания определений терминов автор исследования опирался на ряд источников (Bornholdt, Schuster, 2002), (Wang, 2011), (Rozenfeld, Gallos, Song, Makse, 2009).

· Граф (graph) - упорядоченная пара G = (V; E), где V - множество вершин или узлов, E множество ребер или связей, которые являются двухэлементными подмножествами V. Это определение неориентированного и простого графа, поскольку оно не допускает ни петель (саморебер), ни кратных ребер между элементами V. Заметим, что иногда множество вершин (узлов) обозначается через N.

· Путь (path) представляет собой последовательность ребер, окончание предыдущего края является источником следующего ребра. Длина пути - это число его ребер.

· Путь является геодезическим (geodesic path), если его конечные точки не могут быть связаны более коротким путем.

· Геодезическая длина (length of a geodesic) между вершинами u и v равна расстоянию d (u; v) этих вершин.

· l-neighborhood (окрестность) вершины u - это множество вершин v, расстояние от которых не больше l.

· Diam (G) (диаметр) графа - это максимальное расстояние в графе G между любыми двумя вершинами внутри компонента связности. Diam(G) -1

· Характеристическая длина пути (characteristic path length) определяется как число ребер в кратчайшем пути между двумя вершинами, усредненное по всем парам вершин (среднее из геодезической длины):

· Учитывая две переменные x и y, y прямо пропорциональна x, если существует ненулевая константа C такая, что y = Cx.

· Сеть называется small-world (малым миром), если характеристическая длина пути растет пропорционально логарифму числа узлов в сети:

· Распределение степени P (k) - вероятность того, что степень случайной (равномерно) выбранной вершины равна k

· Scale-free network (сеть не имеет масштаба), если ее распределение по степеням следует степенному закону, т. е. P (k) пропорционально степени k, для некоторого числа

При этом во многих случаях степенное распределение характерно для хвостов графоф, то есть Для реальных сетей показатель степени обычно удовлетворяет

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

Большой объем данных.

Современные вычислительные мощности едва ли могут обработать объемы данных, исчисляемые сотнями петабайт (Савкин, 2017).

Невозможность получения всего объема данных.

Согласно правилам сервиса Twitter API (Twitter Developer Policy, 2017) данные для выгрузки предоставляются в ограниченном объеме (например, 100 последних ретвитов пользователя). Это правило можно обойти с помощью ряда способов (например, выгружая твиты по заранее известному списку id), однако их использование также не гарантирует целостности датасета (Rodriguez, 2015).

Низкая скорость получения данных.

Скорость загрузки данных при помощи Twitter API позволяет загрузить дневной объем поступающих данных за несколько дней, что говорит о невозможности загрузки данных, которые были собраны Twitter за все время его существования. Ограничения Twitter API можно частично снять, приобретя доступ к платной версии API, однако и она имеет ограничения на объемы загруженных данных. Система Twitter ставит ограничение на 900 обращений к API по загрузке 100 твитов за 15 минут. Таким образом на загрузку всего датасета из ~3,5 млн id у автора исследования ушло бы около 10 часов. Для ускорения процесса загрузки автор данного исследования производил загрузку одновременно с 10 аккаунтов.

Невозможность передачи полной информации об объектах другим лицам.

Данные, получаемые из Twitter API, представлены в форме JSON-объектов с множеством полей, содержащих различную информацию про объект (например, в случае объекта твита, полученные данные будут содержать в том числе информацию о количестве ретвитов, идентификаторах упомянутых пользователей и т.д.). Согласно правилам сервиса Twitter API (Twitter Developer Policy, 2017), пользователи не вправе каким-либо образом распространять информацию о твитах и других объектах, за исключением уникальных идентификаторов твитов. Это ограничение существенно затрудняет коллективный анализа большого объема полученных данных

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

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

Данные

Первый этап исследования посвящен сбору данных и созданию датасета. В качестве данных была загружена выборка, содержащая более 3 млн. твитов, относящихся к первым дебатам в ходе предвыборной гонки Президентских Выборов 2016 года в США. Эта выборка интересна по двум причинам:

· Большой объем.

Выборка содержит более 3 млн. твитов, сделанных более чем 1 млн. пользователей в период с 13:45 26 сентября 2016 г. По 11.00 27 сентября 2016 г. Данная кампания имела широкий общественный резонанс и её данные по количеству претендуют на репрезентативную выборку. Критериями для попадания в выборку, которая будет формировать датасет, были соответствие твита/ретвита одному или нескольким хэштегам: #debate, #debates, #debatenight, #debate2016, #debates2016, - и наличие автора твита/ретвита в списке фолловеров одного или нескольких из пользователей: CPD (@debates), Hillary Clinton (@HillaryClinton) и Donald J. Trump (@realDonaldTrump).

· Практическая значимость.

Данная выборка представляет собой пример данных, которые могут быть успешно использованы в сфере политологии для предсказания исхода выборов или оказания влияния на них

Способ получения

Данные были получены путем гидрирования (hydrating) списка из 3183202 идентификаторов твитов, взятых в свою очередь из распространяемого Гарвардским Университетом набора из 12 списков идентификаторов, относящихся к Президентским Выборам 2016 года в США: «2016 United States Presidential Election Tweet Ids» (2016) список создан Littman, Justin; Wrubel, Laura; Kerchner, Daniel, в этом исследование авторы используя сервис SocialFeed собирали данные сразу после первых дебатов, таким образом в выборку не попали твиты относящиеся к последующим дебатам.

Технология гидрирования - это процесс загрузки JSON-объектов твитов по имеющимся идентификаторам. Может производиться как путем непосредственного взаимодействия с Twitter API, так и с помощью сторонних приложений (например, Hydrator).



Описание полученной выборки

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

· Первым критерием для попадания в выборку, которая будет формировать датасет, будет соответствие твита/ретвита одному или нескольким хэштегам: #debate, #debates, #debatenight, #debate2016, #debates2016

· Второй кретерий попадания в выборку: наличие автора твита/ретвита в списке фолловеров одного или нескольких из пользователей: CPD (@debates), Hillary Clinton (@HillaryClinton) и Donald J. Trump (@realDonaldTrump).

· Количество твитов (включая ретвиты и упоминания): 2290855 твитов

· Количество пользователей: 934656

· Количество временных интервалов: 76458

· Длина временных интервалов: 1 секунда

· После получения списка твитов из них была выделена информация в формате id:original_id, где id - уникальный идентификатор пользователя, сделавшего данный ретвит и original_id - уникальный идентификатор пользователя, который создал оригинальный твит. В случае если твит не является ретвитом, id и original_id совпадают.

По полученным данным можно построить структуру взаимодействия пользователей друг с другом и временные ряды количества твитов (включая ретвиты и упоминания).

Принадлежность сети к классу сложных и наличие фрактальности с точки зрения структуры

Сложность сети

В рамках данного исследования необходимо доказать принадлежность рассматриваемой системы к классу сложных сетей.

В более ранних (Barabasi, Albert, 1999), (Watts, Strogatz, 1998) был приведен набор топологических характеристик, которыми должна обладать сложная сеть, а также выделены несколько специфических классов сложных сетей, такие как безмасштабные (scale-free) сети и сети тесного мира (small-world).

Для доказательства принадлежности рассматриваемой системы к классу сложных сетей необходимо проверить наличие у нее следующих ключевых характеристик:

1) Степенной закон распределения степеней вершин (распределение с «тяжелыми хвостами»)

2) Высокий коэффициент кластеризации

3) Диаметр сети где N - число узлов в сети

Необходимо проверить истинность утверждения для наблюдаемой выборки: для степеней вершин k = 0,1,2, …, n вероятность того, что случайная вершина имеет k связей равна

Согласно (Фамилия, год) лишь малая часть эмпирических распределений совпадает в точности с каким-либо теоретическим распределением ввиду наличия шумов в данных. Также, используемый для получения значения p-value для гипотезы о соответствии наблюдаемого распределения теоретическому метод бутстрэпа с расчетом статистики Колмогорова-Смирнова вычислительно более сложный чем попарные тесты отношения правдоподобия для разных теоретических распределений. Таким образом, вычисление вероятности соответствия наблюдаемого распределения теоретическому не имеет практического смысла как в случае со статистически значимым p-value: такой результат может получиться для нескольких теоретических распределений, - так и в случае со статистически незначимым p-value: такой результат типичен для большинства эмпирических выборок. Поэтому для поиска теоретического распределения, наиболее хорошо описывающего наблюдаемые данные, был использован метод попарного сравнения соответствия эмпирических данных нескольким теоретическим распределениям. Ввиду специфики рассматриваемого объекта, сравнение будет проведено между наиболее подходящими с точки зрения теории для описания данных с «тяжелыми хвостами» распределениями, список которых были предложен в (Alstott, Bullmore, Plenz, 2014): степенное, экспоненциально усеченное степенное, логнормальное, логнормальное положительное, экспоненциальное, растянутое экспоненциальное (распределение Вейбулла).

В ходе попарного сравнения применимости различных теоретических распределений для объяснения эмпирических данных были получены следующие нормализованные значения статистики отношения правдоподобия и соответствующие p-value:

Степенное vs Логнормальное: R = 7.79 p-value = 0.00

Степенное vs Экспоненциальное: R = 65.20 p-value = 0.00

Степенное vs Экспоненциально

усеченное степенное: R = -0.13. p-value = 0.88

Степенное vs Растянутое экспоненциальное: R = 8.15 p-value = 0.00

Степенное vs Логнормальное положительное: R = 134.74 p-value = 0.00

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

Получившийся результат соответствует теории сложных сетей (Barabasi, Albert, 1999), а также недавним исследованиям (Mathews, Mitchell, Nguyen, Bean, 2017) в которых была подтверждена возможность соответствия распределения степеней узлов сложных сетей помимо простого степенного закона экспоненциально усеченному степенному закону.

Помимо степенного закона распределения вершин у сети присутствует высокий коэффициент кластеризации, сравнимый с показателями других социальных графов (Edunov, Logothetis, Wang, Ching, Kabiljo, 2016):

Рис. 1 Среднее значение коэффициента кластеризации в традиционных социальных графах

Сеть также характеризуется низким диаметром - 2,7



Фрактальность

Структура графа является фрактальной, если имеет конечную фрактальную размерность (Molontay, 2015).

Автором (Molontay, 2015) предлагается уточнить определение размерности Хаусдорфа для случая последовательности графов

где - количество квадратов со стороной в алгоритме box-covering, необходимых для того, чтобы покрыть граф

В случае конечных последовательностей графов данная формула превращается в следующую:

Методы определения наличия фрактальности в структуре сетей аналогичны (Molontay, 2015) тем, что используются для определения фрактальности в структуре регулярных фракталов, а именно алгоритм box-counting (Molontay, 2015). Отличие состоит в том, что в случае регулярных фракталов в этом алгоритме используется евклидово расстояние, которое не существует для графа. В качестве расстояния для случая графа (Molontay, 2015) предлагается использовать кратчайшее расстояние между двумя вершинами.

В результате применения метода box-counting с последующей ренормализацией сети было получено значение фрактального измерения для графа: 1,28. Это подтверждает предположение о наличии фрактальности в сети.

Наличие у системы фрактальности с точки зрения временного ряда

Признаки фрактальности временного ряда

Фрактальные временные ряды обладают следующим набором свойств (Подлазов, 2005)

· Масштабная инвариантность - неизменность процессов и характеристик при изменении длины временного интервала

· Целостность - наличие в системе дальних корреляций (индекс Хёрста (H) не равен 0,5)

· Склонность к катастрофам - вероятность катастрофических событий в системе превышает порог уровня значимости

О наличии этих свойств говорят несколько статистических индикаторов:

· Фрактальные сигналы - размерность Хаусдорфа ,

· Степенной закон распределения приращений

· Спектральная плотность ряда аналогична - шуму

· Автокорреляционная функция следует степенному закону

Вычисление основных индикаторов фрактальности временного ряда

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

Для доказательства фрактальной природы сигнала и получения полезной информации относительно закономерностей ряда был вычислен индекс Хёрста (H) и фрактальная размерность .

Индекс Хёрста может принимать значение в диапазоне от 0 до 1 и в зависимости от него ряд обладает следующими свойствами:

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

· - у ряда отсутствует память, т.е. он является стохастическим

· - ряд обладает персистентностью, т.е. свойством сохранять изначальный тренд. Чем ближе это значение к 1, тем более устойчив ряд и тем меньше в нем шумов

А

Б

Рис. 2 А. Временной ряд прироста количества твитов, ретвитов и упоминаний; Б. Временной ряд изменения скорости прироста количества твитов, ретвитов и упоминаний

Значения для рассматриваемой выборки оценивались при помощи метода R/S-анализа (Гарольда Хёрста) по следующему алгоритму:

1. Исходный временной ряд преобразуется в ряд логарифмических отношений

2. Преобразованный ряд разбивается на A смежных сегментов

3. Для каждого сегмента рассчитывается локальное выборочное среднее (Рис.3) и суммарное отклонение от среднего (Рис.4):

4. Далее в пределах каждого сегмента нужно рассчитать размах

5. Рассчитываем стандартное отклонение (Рис.5) и стандартное значение (Рис.6)

6. Для получения результатов нужно многократно повторить шаги описанные выше, начиная со второго, при это каждый раз увеличивая n: длину сегмента A, пока соблюдается условие

7. После проделанных операций мы можем оценить показатель R/S-анализа

В результате применения алгоритма были получены следующие значения: , где - топологическая размерность кривой на плоскости. Таким образом автор данного исследования может сделать вывод о том, что данный ряд является фрактальным (фрактальная размерность больше топологической) и является персистентным, то есть имеет свойство сохранять тренд (H > 0,5).

Необходимо также проверить распределение приращений ряда твитов-ретвитов на наличие «тяжелых хвостов», которые говорят о склонности ряда к катастрофам. На графике функции распределения (Рис. 6) видно, что эмпирические данные выходят за пределы функции плотности нормального распределения в промежутках , что является индикатором наличия «тяжелых хвостов».



Рис. 7 Нормированное распределение скорости прироста твитов

Обобщенный тест Д'Агостино-Пирсона также говорит о возможности отвергнуть нулевую гипотезу о нормальности распределения на пороге значимости a = 0,01 при значении статистики k2 = 6419,89

Еще одним подтверждением предположения о наличии «тяжелых хвостов» является их соответствие степенному закону (Рис. 7).



Рис. 8 Функция плотности распределения и кумулятивная функция распределения достаточно хорошо аппроксимируются прямой

Далее автору исследования необходимо определить тип шума, который присутствует в ряде. Для этих целей обычно применяется метод DFA (Detrended Fluctuation Analysis), который заключается в следующем:

1) Исходный ряд разбивается на N сегментов

2) Для каждого сегмента определяется уравнение прямой, аппроксимирующей ряд внутри этого сегмента (эта прямая является локальным трендом)

3) Вычисляется среднеквадратичная ошибка всех прямых по сравнению с исходными фрагментами ряда

4) Определяется скейлинговая экспонента которая является показателем степенного распределения, аппроксимирующего среднеквадратичную ошибку.

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

Такое значение из всех видов шума наиболее близко к фликкер-шуму , что говорит о наличии медленных процессов, оказывающих влияние на систему. Полученный с помощью алгоритма результат также совпадает с результатом, полученным в ходе аппроксимации функции спектральной плотности ряда прямой (Рис. 8) и соответствует значению индекса Хёрста для функции спектральной плотности , которое говорит о наличии отрицательной памяти в функции спектральной плотности и склонности к сменам знаков приращений. Спектральная плотность была получена путем применения к исходному ряду быстрого преобразования Фурье (FFT - Fast Fourier Transform).

Рис. 9 Аппроксимация графика спектральной плотности ряда прироста твитов с помощью прямой

Еще одной характеристикой временного ряда является соответствие автокорреляционной функции степенному закону (Рис.9).

Рис. 10 Автокорреляционная функция ряда прироста твитов, аппроксимированная прямой

Соответствие автокорреляционной функции степенному закону говорит о наличии в ряде «длинной памяти».

Помимо фрактальности сигнала, наличия «тяжелых хвостов» и фликкер-шума, представляет интерес корреляционная размерность и размерность фазового пространства системы. Значения этих компонент позволят утверждать, является ли система хаотической и если да, то системой из какого числа дифференциальных уравнений ее можно описать. Для определения значений этих компонент используется метод временной задержки координат Флоренса-Такенса совместно с алгоритмом Грассбергера-Прокаччиа.

Значения корреляционной размерности говорят о хаотической природе наблюдаемого временного ряда и о том, что для моделирования поведения системы необходимо не более 10 переменных.



Выводы

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

Хаотическая природа Twitter позволяет описать его функционирование с помощью системы нелинейных динамических уравнений. Это имеет практическую значимость для задач предсказания взрывов / угасаний информационной активности Твиттер или контролируемого управления поведением системы в целом с помощью регуляции ряда параметров. Предыдущими исследователями (Dmitriev, Dmitriev, Tsukanova, Maltseva, 2017) в работе «Investigation into the Regular and Chaotic States of Microblogging Networks as Applied to Social Media Monitoring» была предложена модель системы, основанная на аттракторе Лоренца-Хакена:

В этой системе линейных уравнений - количество твитов и ретвитов в момент времени t, - количество твитов и ретвитов в состоянии равновесия;, где - количество информации внутри системы в момент времени t, - количество информации внутри системы в состоянии равновесия; , где - количество пользователей, которые имеют достаточно информации, для того чтобы отправить твит или ретвит, а - количество пользователей, у которых недостаточно информации для отправки твита или ретвита. - количество информации, поступающей в единицу времени извне системы.

После упрощения система принимает следующий вид (Dmitriev A., Dmitriev V., Tsukanova O., Maltseva S., 2016):

Как можно видеть, количество информации, поступающей извне системы предлагается принять за постоянную величину, что, строго говоря, необязательно совпадает с реальной величиной. В рамках текущего исследования предлагается расширить понятие количества информации, поступающей извне до случайной величины I с q-гауссовым распределением (это распределение является обобщением гауссова нормального распределения с возможностью наличия «тяжелых хвостов», что позволяет более точно объяснить значения случайного потока внешней информации):



Моделирование процесса работы системы

Для выполнения задачи моделирования системы необходимо определить:

1) Значения коэффициентов. Для моделирования были выбраны стандартные значения (Dmitriev A., Dmitriev V., Tsukanova O., Maltseva S., 2016):

·

·

2) Стартовые значения переменных модели

·

· y = 1

· z = 1

3) Параметры q-гауссова распределения

·

·

В результате моделирования был получен временной ряд (Рис. 11), по основным характеристикам:

H = 0.87

DFA = 1,13

D_F = 1.13

D_C=4.59

размерность фазового пространства n?10

близкий к исходному ряду, что говорит о высокой объясняющей силе модели. Ввиду специфики



Рис. 11 Модельный ряд

Использование модели как инструмента политической борьбы

Построенная модель успешно описала социальную сеть Twitter и может быть использована, как инструмент политической борьбы. Данная практическая модель не может точно предсказывать временные ряды Twitter, так как это не соответствует специфике хаотических моделей, зато при помощи данной модели возможно тестировать влияние тех или иных исходных факторов на состояние системы Twitter. Тщательное определение стартовых значений параметров модели может позволить спроектировать такое состояние, при котором населению не будет интересна тема выборов, что может сыграть на руку авторитарным правителям. Или например, при изменении исходного параметра количества твитов система при определенных настройках внутренних параметров может менять свое состояние с полицентрического на эгоцентрическое или наоборот. В текущей выборке, а именно, в модели предвыборной гонки в США пользователи проявляли крайне эгоцентрическое состояние, и массово концентрировались около темы выборов, причем в основном возле двух главных кандидатов. В данном случае политтехнологи предвыборных штабов менее популярных кандидатов вроде Берни Сандерса могут воздействовать на Twitter таким образом, чтобы система перешла в состояние полицентричности, когда внимание избирателей будет равномерно распределено по разным кандидатам. Таким образом, независимо от успешности дебатов, ключевые кандидаты не смогут донести свою повестку до массового избирателя, а периферийные кандидаты смогут воспользоваться ситуацией для агрегации избирателя вокруг себя, без необходимости затрачивать серьезные суммы на маркетинговую кампанию по продвижению себя как будущего президента. Полученный в данном исследовании результат открывает новую страницу в сфере политических технологий и при должном развитии в перспективе может изменить принцип работы демократии, породив вызовы, на которые придется отвечать всему обществу.