Pull to refresh

Поиск наиболее влиятельных объектов подмножества социальной сети

Reading time 4 min
Views 4.3K
В современном мире отношения между людьми, кроме социального уровня, заняли еще один — цифровой. С распространением виртуальных социальных сетей появилась тенденция иметь собственную страницу с персональными данными, искать друзей по интересам, создавать группы и пр. На одной IT Talk встрече, проводимой DataArt, я познакомился с человеком, занимавшимся исследованием топологий социальных сетей. В этот день я полностью определился с темой магистерской диссертации, которая представлена заголовком статьи. Дело в том, что количество информации в соцсетях постоянно увеличивается, и бо́льшая часть этой информации представлена в сыром виде. Сама по себе она не представляет интереса. Возникла мысль обработать подобные данные и получить результаты, которые вполне могли бы послужить благому делу.

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

Введение


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

Рис. 1

Дадим интуитивное понятие влиятельности. Рассмотрим следующий рисунок.

Рис. 2

Тут объект в центре имеет 6 связей. Но влиятельность не сводится только к количеству связей. Мы должны учесть степень влияния объектов, с которыми связан целевой объект. Рассмотрим рис. 3.

Рис. 3

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

Матчасть


Толчком для исследования в этом направлении стала данная статья[1]. Я внес в предложенный алгоритм поправки, которые на мой взгляд кажутся целесообразными.
Граф будем представлять в виде матрицы смежности.



Введем понятие итерированной силы объекта i порядка k.



Заметим, что итерированная сила первого порядка объекта i есть количество связей данного объекта с другими. Она пока что еще не учитывает влиятельность других объектов. Начиная со второго порядка в данную сумму включается влиятельность иных объектов.

Вопрос: до какого порядка считать вектор итерированных сил?
Ответ: либо 2, либо 3.

Дело в том, что итерированная сила объекта i порядка k выражает степень влияния объекта i, учитывая, что он свое влияние может распространить не более чем в радиусе k. Так заложено в самой сумме. Вспомните когда вы просили своего друга, чтобы он попросил кого-то сделать что-то для вас? Это влиятельность в радиусе 2, и выражается она итерированной силой второго порядка. Если мы хотим учитывать цепи с еще одним промежуточным участником, то нужно считать вектор итерированных сил 3-го порядка. Считать итерированные силы бОльших порядком кажется нецелесообразным ввиду ничтожно малой вероятности возникновения столь длинных цепочек в реальной жизни.
Таким образом, если мы хотим посчитать влиятельность объектов в масштабе крупного города и выше, то считаем до 3-го порядка. Для меньших масштабов целесообразно использовать второй порядок.

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

Собираем информацию


Информация собиралась из социальной сети «Вконтакте». Было написано приложение, которое загружает 2 набора друзей: до 2-го и до 3-го уровней. Для большей ясности рассмотрим рисунок 4.
Рис. 4
Здесь красным обозначены друзья 1-го уровня, зеленым – второго, желтым – третьего. В силу того, что VK API не позволяет делать более 3 запросов в секунду, то для загрузки третьего уровня приходилось оставлять машину включенной на ночь.

Рис. 5

Заметим, что если загружать 4 уровня, то скорее всего мы скачаем 99 % пользователей сети. Существует теория шести рукопожатий [2], которая утверждает, что между любыми двумя людьми на Земле не более 5 уровней общих знакомых. В силу того, что VK распространена в основном в СНГ, то эта цифра должна быть меньшей.

Анализируем данные


Итак, у нас есть 2 набора данных:
  • Для 2 уровней друзей – примерно 40 тыс. пользователей.
  • Для 3 уровней друзей – примерно 4,2 млн. пользователей.

Я сам в соцсетях не сижу, поэтому в обоих случаях центром выборки был мой друг, студент Воронежского ГосУниверситета.

Начнем с анализа первого набора.

Рис. 6

Здесь центр выборки занял первое место по влиятельности. Объяснить это можно тем, как загружались данные. Дело в том, что весь последний уровень друзей содержит лишь по одной связи. Для этих объектов список друзей пуст. Поэтому влиятельность друзей 1-го уровня (которая в значительной степени базируется на друзьях 2-го уровня) оценивается низко. Из-за этого мы получаем не совсем объективные результаты. Тем не менее, можно наблюдать интересные данные: в первых 30 строках располагаются около половины активистов ВГУ.

Перейдем к исследованию второго набора данных. Здесь центр выборки по рейтингу занимает 3539 место.
Оно и понятно: тут уже влиятельность рассматривается в рамках города.

Рис. 7

В начале данной таблицы прослеживаются следующие записи:
  • Воронеж Афиша
  • Врн экскурсии
  • Воронеж nightparty.ru
  • Ручьев Сто
  • Арт-реальность Vrn

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

P.S. Если у кого есть мысли как можно улучшить данную модель, прошу отписаться в комментариях.

Источники:


  1. www.basegroup.ru/library/web_mining//information_flows_in_social_networks
  2. ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%88%D0%B5%D1%81%D1%82%D0%B8_%D1%80%D1%83%D0%BA%D0%BE%D0%BF%D0%BE%D0%B6%D0%B0%D1%82%D0%B8%D0%B9


Tags:
Hubs:
+4
Comments 3
Comments Comments 3

Articles