Алгоритм Флажоле-Мартена как эффективный инструмент анализа социальных графов

Торопов Борис Андреевич кандидат технических наук доцент, Академия управления МВД России 125171, Россия, г. Москва, ул. З. и А. Космодемьянских, 8 Toropov Boris Andreevich PhD in Technical Science Associate Professor at the IT Department of the Academy of Management of the Ministry of Internal Affairs of the Russian Federation 125171, Russia, g. Moscow, ul. Z.i A. Kosmodem'yanskikh, 8 torbor@mail.ru Другие публикации этого автора

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

Самые простые метрики центральности, основаны на числе связей, они показывают со сколькими вершинами связана данная вершина. Если за основу берутся только прямые связи, то такая метрика называется степенью c^deg. О том, сколько вершин находятся от данной вершины на удалении не более k шагов, говорит метрика центральности, называемая k‒степенью c^k-deg. Эти метрики наиболее очевидны, они самые простые с точки зрения вычислительной сложности и скорости работы алгоритмов на больших сетях. Однако их ключевым недостатком является то, что они не учитывают, где именно находится анализируемая вершина – в центре социального графа или же на его периферии, важна ли она для данной сети как связующий элемент или без нее в структуре сети ничего существенно не изменится.

Другой класс метрик центральности основан на том, в какой мере кратчайшие пути, связывающие данную вершину с остальными вершинами, в действительности коротки. Близость c^cl – основная метрика, представляющая данный класс. Она рассчитывается как величина обратно пропорциональная сумме длин кратчайших путей от анализируемой вершины до каждой другой вершины графа. Обычно близость масштабируется по числу кратчайших путей N‒1 между i и j, где N – общее число вершин в графе:

где l_ij – длина кратчайшего пути от i к j.

В больших сетях минус единицей в числителе можно пренебречь и масштабировать близость по N:

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

С точки зрения практического применения близости в форме (1) или (1а) к большим сетям, основной ее недостаток – это время работы алгоритмов. Поиск кратчайшего пути между одной парой вершин при помощи BFS‒алгоритма (англ. breadth‒first search, поиск в ширину) в худшем случае имеет временную сложность O=(|N|+|M|), причем, M ‒ число ребер графа (связей между его вершинами), в зависимости от связности графа будет варьироваться от 1 до N². Для поиска кратчайших путей между всеми возможными парами вершин графа алгоритм необходимо применить N(N‒1)/2 раз. Таким образом, общая его сложность будет предположительно пропорциональна N³, а худший случай графа с большим числом ребер в наихудшем случае BFS-перебора сделает сложность пропорциональной N⁴.

Однако существуют способы оценки близости вершин графа, не предполагающие нахождения всех кратчайших путей. Рассмотрим метод определения так называемой эффективной близости ^[1] вершин.

Пусть N(r, ν) – число вершин графа, удаленных от вершины ν на расстояние не более r. Примем N_ν(r)за число вершин, находящихся от ν точно на расстоянии r. Тогда N_ν(r)= N(r, ν) ‒ N(r ‒ 1, ν). В этом случае стандартная близость (1) определяется следующим образом:

где d ‒ диаметр графа, т.е. длина самого длинного из всех кратчайших путей.

Теперь предположим, что имеется `hatN(r,v)` – оценочное значение N(r, ν), тогда `hatN_v(r)` – оценочное значение N_ν(r).Соответственно, аппроксимированное значение близости, или эффективная близость c^cl_eff, определяется как:

Вопросом остается то, каким образом определить `hatN(r,v)` так, чтобы не использовать методов и алгоритмов поиска кратчайших путей, влекущих чрезмерную вычислительную сложность при их применении на больших сетях.

` `

Одним из решений проблемы является алгоритм, предложенный Флажоле и Мартеном в ^[2] для аппроксимированного определения числа уникальных объектов во множестве. Данный алгоритм может быть легко адаптирован к определению `hatN(r,v)` в социальных графах. Алгоритм выполняется за O = (d|N|) операций для всех вершин, входящих в граф.

На этапе инициализации согласно алгоритму Флажоле-Мартена каждому объекту во множестве (вершине социального графа в нашем случае) присваивается кодовая последовательность M(0,v).

Кодовые последовательности M(0,v) формируются следующим образом. Для каждой вершины с вероятностью p=1/2 нулевому биту кодовой последовательности присваивается значение единица, с вероятностью p=1/4 – единичное значение присваивается первому биту, p=1/8 – второму, и т.д. Таким образом i-му биту кода каждого узла с вероятностью p = 2^-(i+1) присваивается единичное значение, а с вероятностью q=1‒p – присваивается нулевое.

Рис.1. Вероятности появления нулевых и единичных значений разрядов кодовой строки, формируемой по алгоритму Флажоле-Мартена

Как видно, эти кодовые последовательности неуникальны. Их длина задается не менее log₂N целых бит, что впоследствии позволит зафиксировать случай нахождения предельно возможного числа вершин на одинаковом удалении от ν. Действительно, бинарная строка длины log₂N позволяет закодировать ровно N‒1 десятичных чисел.

Далее алгоритм выполняется итеративно следующим образом:

1) Счетчик r увеличивается на 1 (начальное значение 0).

2) Кодовая строка каждой вершины M(r, v) задается равной логическому ИЛИ (`o+` ) между самой собой и кодовыми строками вершин ‒ непосредственных соседей.

3) Для каждой вершины определяется значение b ‒ порядок первого разряда в M(r, v), значение которого равно нулю.

Логика нахождения позиции первого нулевого разряда следующая: для того, чтобы получить в кодовой комбинации b единичных разрядов перед первым нулевым, необходимо при помощи логического ИЛИ «обойти» такое количество вершин графа, которое пропорционально 2^b. Это позволяет дать оценку тому количеству вершин графа, которое находится на расстоянии кратчайшего пути не более r от заданной вершины v.

4) Для каждой вершины определяется `hatN(r,v)` оценочное количество вершин находящихся от нее на длине кратчайшего пути не более r, где r ‒ это номер текущей итерации алгоритма. Как уже отмечалось, `hatN(r,v)` пропорционально 2^b и рассчитывается как:

где 0,77359 ‒ поправочный коэффициент, согласно ^[2].

5) Для каждой вершины определяется число вершин, удаленных от нее на расстояние r как:

6) На основе выражения (3) рассчитывается r-е слагаемое близости.

7) Если кодовые строки всех вершин графа равны, то расчет завершен, если хотя бы одна строка отличается от других, то выполняется следующая итерация алгоритма.

Формальное описание алгоритма приводится, например, в ^[3].

Расчет эффективной близости по Флажоле-Мартену рассмотрим на примере следующей сети, представленной графом из шести вершин и шести ребер.

Рис.2. Пример графа

Число вершин графа N = 6, то log₂N ≈2,6 и длина кодовой комбинации принимается равной 3. Поскольку граф невелик, для большей точности будем использовать для каждой вершины не одну, а четыре кодовых комбинации из трех разрядов каждая и при выполнении алгоритма опираться не на b, а на `barb` ‒ среднее положение первого разряда с нулевым значением.

Рисунок 3. показывает итеративное изменение кодовых последовательностей, соответствующих вершинам графа. Так на первой итерации алгоритма для вершины v₄ кодовая последовательность формируется как М(1,4) = М(0,4) `o+` М(0,3) `o+` М(0,5) = (010 001 000 011) `o+` ( 000 000 001 000) `o+` (000 000 101 000) = 010 001 101 011.

Рис.3. Расчет близости по Флажоле-Мартену, алгоритм завершен за три итерации

Значения `barb` для вершин графа на всех итерациях работы алгоритма приведены в таблице 2. Например, для вершины v₄ рассчитанная выше кодовая последовательность на первой итерации работы алгоритма следующая: 010 001 101 011, значит `barb = (0+1+1+2)/4=1`.

Таблица 1. Кодовые строки Флажоле-Мартена M(r, ν), соответствующие каждой вершине графа на каждой итерации работы алгоритма

Таблица 2. `barb` ‒ среднее положение первого нулевого разряда из четырех кодовых комбинаций. ‒ оценка числа соседей на расстоянии не более r, рассчитывается по (4)

Таблица 3. `hatN_v(r)` ‒ оценка числа соседей на расстоянии ровно r, рассчитанная по (5), эффективная близость по Флажоле-Мартену c^cl_eff , рассчитанная по (3) и стандартная близость c^cl , рассчитанная по (1)

Приведенные в таблице 3 значения эффективной близости вершин графа недалеки от реальных метрик близости, рассчитанных по BFS-алгоритму. Ниже приведем диаграмму разброса c^cl по c^cl_eff.

Рис.4. Диаграмма разброса c^cl по c^cl_eff

Как видно, между двумя рядами наблюдается существенная и значимая взаимозависимость. Таким образом, полученная по алгоритму Флажоле-Мартена эффективная близость является достаточно качественной аппроксимацией реальной близости, вычисляемой согласно (1).

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

В развитие рассмотренной идеи приведем пример другой метрики центральности, которая также может быть рассчитана по Флажоле-Мартену. В своем труде ^[4] М. Джексон вводит метрику, называемую decay centrality c^d. На русский можно попытаться перевести это наименование как центральность распада или центральность затухания, возможно, также подошло бы ‒ градиентная центральность. Рассчитывается данная метрика как:

`c^d = (sum_(j!=i)delta^(l(i,j)))/((n-1)delta)`

где δ ‒ коэффициент распада (затухания), δ`in` (0;1),

знаменатель дробинормирует полученное значение `sum_(j!=i)delta^(l(i,j))`по его наибольшему возможному значению в графе из n вершин (n-1)δ - тот случай, когда данная вершина напрямую связана со всеми остальными вершинами графа.

Метрика c^d будет прямо коррелировать с центральностью по степени c^deg вершины при значении коэффициента δ стремящемся к нулю, и с рассмотренной выше центральностью по близости c^cl при значении коэффициента δ стремящемся к единице.

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

Очевидно, что расчет c^d, будучи сопряжен с нахождением длин кратчайших путей между вершинами графа, предполагает те же самые вычислительные сложности, что и расчет близости. Применение алгоритма Флажоле-Мартена в свою очередь способно эти сложности преодолеть, что позволит осуществлять построение более сложных моделей. Например, таких моделей, где коэффициент распада δ будет задаваться индивидуально для каждой вершины, сообразно активности соответствующего пользователя в онлайновой социальной сети.