· 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)
· Масштабная инвариантность - неизменность процессов и характеристик при изменении длины временного интервала