Теоретико-игровая центральность вершин в графах на основе вектора Шепли

Торопов Борис Андреевич кандидат технических наук доцент, Академия управления МВД России 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 Другие публикации этого автора

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

Центральность вершины ^[1] в графе ‒ это модель значимости соответствующего участника социальной сети. В зависимости от природы этой сети и задач анализа, могут применяться различные метрики центральности, отражающие различные особенности самого графа и составляющих его вершин и ребер. К настоящему времени исследователями в данной области предложена масса метрик центральности, таких как, центральность по степени (степень), центральность по близости (близость), центральность по промежуточности (промежуточность) и многие другие, каждая из которых позволяет оценить важность определенной вершины в графе по сравнению с другими вершинами. Какая из метрик применима к решению той или иной аналитической задачи, зависит от природы исследуемого графа, от того какие именно социальные объекты, процессы и явления принимаются за его вершины и ребра. Будучи рассчитанной для каждой вершины социального графа, любая метрика центральности, например, из числа упомянутых выше, позволяет определить k наиболее влиятельных вершин.

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

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

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

Идея расширения концепции индивидуальной центральности вершин до групповой центральности принадлежит Эверетту и Боргатти, в чьей работе ^[2] введено соответствующее понятие (group centrality). Там же проиллюстрирован расчет метрик групповой центральности по степени и групповой центральности по близости для двух учебных графов.

Эверетт и Боргатти определяют групповую центральность по степени (group degree centrality) для группы вершин как количество вершин ‒ не членов группы, которые непосредственно связаны с вершинами ‒ членами группы:

где c^deg(S) ‒ групповая центральность по степени для группы вершин S, а V и E ‒ множества вершин и ребер графа Gсоответственно.

Отсюда, ценность вершины v графа как элемента группы S будет определяться как разность центральностей данной группы до и после включения в нее v:

Формула носит общий характер, в ней не имеет значения, какие характеристики вершины или группы вершин важны для вычисления центральности. Если принять в расчет центральность группы по степени c^deg(S), то ценность каждой вершины для группы определяется тем, со сколькими новыми внешними вершинами она создает связи. Такая формулировка предполагает и наличие вершин с отрицательной ценностью для определенных групп. Например, на рис.1 вершина, обозначенная как «1», при включении в группу S лишь уменьшит c^deg(S) на единицу ‒ у группыS пропадет внешняя связь с самой«1». А вот вершина «2» добавит 3 новые связи, тем самым увеличивc^deg(S) на 2.

Рис.1. Группа вершин S и ее центральность по степени c^deg(S)

Так определяется ценность вершины v при включении ее в конкретную группу S. Однако, что если требуется определить потенциальную ценность φ_v вершины v при ее вхождении в произвольную группу вершин из множества V? В этом случае необходимо рассмотреть |V|! перестановок множества V, каждая из которых является полной группой S=V, при этом порядок v в каждой перестановке из |V|! следует рассматривать как очередность вхождения данной вершины в полную группу.

Средний вклад, рассчитанный для каждой вершины графа при ее вхождении во все возможные перестановки полной коалиции, образует вектор Шепли ^[3] для данного графа. Его формальное представление следующее:

|S|! – перестановки тех вершин, которые уже вошли в группу перед вершиной v;

(|V|-|S|-1)! – перестановки тех вершин, которые вошли после v;

и наконец, 1/|V|! – деление результата на общее число перестановок позволяет вычислить средний вклад вершины v во все возможные группы.

Применению вектора Шепли для анализа значимости вершин в социальных графах посвящен ряд работ, в частности, Т. Михалака и его коллег ^{[4, 5, 6]}. Ниже рассмотрим некоторые возможности использования вектора Шепли при различных подходах к оценке значимости вершин, образующих группу или коалицию (в терминологии теории игр).

Очевидно, что рассчитать для каждой v из V в каждой из |V|! перестановок ее вклад в группу предшествующих вершин, с точки зрения вычислительной сложности, весьма трудоемкая задача. Однако также очевидно, что рассматривать все возможные перестановки в случае оценки групповой центральности по степени и не потребуется. Для решения задачи необходимо задаться вопросом: какова вероятность для вершины v при ее вхождении в группу S в случайной перестановке из |V|! обогатить эту группу связью со своим соседом ‒ вершиной u? Обозначим множество вершин-соседей вершины u как {z} такое, что: (u, z)`in` E. Тогда v при ее вхождении в группу добавит связь с u лишь в том случае, если ни сама вершина u, ни одна из вершин {z} на момент вхождения v в группу в этой группе еще не находится: u`!in` S`^^` {z}`!in` S. То есть вероятность для v добавить в формируемую группу связь с u обратно пропорциональна числу соседей вершины u:

Вероятность для v привнести в группу любую новую связь и будет составлять значение вектора Шепли для данной вершины:

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

Такой способ определения значения Шепли для всех вершин графа экономичен с точки зрения вычислительной сложности и требует число операций O=(V+E). В то же время, решение задачи методом Монте-Карло, предложенное в ^[7] требует O=(V+E) операций на каждой итерации алгоритма, при том, что метод дает аппроксимированное значение, тем более точное, чем большее число итераций выполнено.

Рис.2. Псевдокод алгоритма расчета значений Шепли на основе центральности по степени

Полученные согласно (5) или (6) и рассчитанные по алгоритму (рис.2) значения имеют интуитивно понятное объяснение. Чем больше соседей у вершины, тем больше слагаемых будет в расчетной формуле, однако величина каждого из этих слагаемых тем меньше, чем больше соседей у соответствующей вершины. Таким образом, наиболее значима не та вершина, у которой просто много соседей, но та, у чьих соседей связей меньше, чем у самой данной вершины. Power comes from being connected to those who are powerless (Влияние проистекает из связей с теми, кто невлиятелен. (англ.)) ‒ феномен, известный в литературе по вопросам центральности ^[8] и в различных прикладных областях, где важна центральность исследуемых объектов, например ^[9]. Также можно вспомнить здесь хорошо известный пример с флорентийскими марьяжами ^[11], где рост политического и экономического влияния семьи Медичи может быть объяснен заключением ряда чрезвычайно выгодных брачных союзов.

На рис.3 вершины графа ‒ олигархические семьи средневековой Флоренции, ребра ‒ брачные союзы между членами семей.

Рис.3. Граф флорентийских марьяжей

В ^[11] Джексон рассматривает значения центральности вершин данного графа, а именно центральности по степени, центральности по близости и центральности по промежуточности. Ниже приведены расчетные значения этих метрик центральности плюс значение Шепли на основе степени для каждой семьи, рассчитанное вышеописанным методом.

Таблица 1. Центральность флорентийских семей, c^deg- центральность по степени, c^SV-deg- значение Шепли на основе центральности по степени, c^btw- центральность по промежуточности, c^cl- центральность по близости.

Как видно, значения Шепли по степени отличаются ото всех трех «традиционных» метрик центральности, во многом повторяя значения обычной центральности по степени (коэффициент корреляции между ними составляет 0,89), но уточняя их и придавая несколько большую значимость семьям с малым числом уникальных соседей. В наибольшей мере значения Шепли коррелируют для данного графа со значениями центральности по промежуточности (коэффициент корреляции 0,92) поскольку граф невелик, и в наименьшей со значениями центральности по близости (коэффициент корреляции 0,65).

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

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

На примере флорентийских марьяжей рассмотрим следующую задачу. Пусть 5 семей выбранных случайным образом обладают неким важным ресурсом, это может быть наличие голоса в совете, редких товаров и производств, контактов с иностранным государством, флота или т.п., обозначим это свойство для данных семей как R=1, а для остальных как R=0. Пусть также для достижения некой коллективной цели важно будет наличие в формируемой коалиции (группе вершин на графе) как минимум двух семей с этим ресурсом. При этом число внешних связей группы также как и ранее останется важным свойством.

Что изменится в этом случае при расчете значения Шепли для каждой семьи? Она будет давать отличный от нуля вклад в формируемую группу только в том случае, если как минимум две из пяти обладающих свойством R=1 семьи в группу уже вошли, либо если эта семья сама обладает заданным свойством и в группе уже имеется как минимум одна такая же.

Чтобы выяснить, как изменится значение Шепли для семьи v с R=0, рассмотрим 15! возможных перестановок на имеющемся графе. Очевидно, что в каждой конкретной перестановке важно будет положение семьи v и пяти семей с R=1. Всего эти шесть семей можно разместить в 15! перестановках `((15),(6))` способами, что составляет `(15!)/(6!(15-6)!)` возможных вариантов.

Причем только в тех перестановках, где 2, 3, 4 либо 5 семей с R=1 уже находятся перед v, семьяv будет давать в центральность формируемой группы отличный от нуля вклад сообразно числу и качеству своих соседей. То есть в 4X5! случаях в каждом из `(15!)/(6!(15-6)!)` вариантов размещения семья v будет находиться в «правильном» положении относительно пяти семей с R=1. При этом остальные семьи могут разместиться еще (15-6)! способами. Таким образом, всего можно насчитать `(15!)/(6!(15-6)!)xx4xx5!xx(15-6)!` случаев из 15!, когда семья v даст формируемой группе пользу.

где вклад семьи с R=0 отличен от нуля.

То есть значение Шепли для каждой семьи с R=0 составит 2/3 от ранее рассчитанного. Несложно убедиться, что у семей с R=1 значение Шепли составит 5/6 от исходного, или на 1/5 станет больше по сравнению с семьями, не обладающими ресурсом R (прим.: Это касается тех семей, которые не граничат с владеющими введенной качественной характеристикой. Для семей же, имеющих соседей с R при заданных условиях значение Шепли уменьшится сильнее, так как у них будет меньше шансов привнести в коалицию новые связи при том, что 2 семьи с R уже стали ее участниками).

` `

Рассмотренный теоретико-игровой метод анализа социальных графов на основе значения Шепли является весьма гибким инструментом. Он позволяет вводить сколь угодно много качественных характеристик и использовать любые топологические свойства в любых пропорциях, которыми обладают вершины исследуемого графа для расчета их значимости.

В развитие положений работы ^[4] ранее нами был рассмотрен пример анализа сети террористов, совершивших теракт 11 сентября 2001 г. в США с учетом специальных навыков, которыми они обладали и с учетом требования о связности формируемых на сети групп ^[12]. Однако прикладное значение рассмотренного метода в правоохранительной сфере может быть расширено. В частности, метод подходит для анализа экстремистских сообществ в Интернете, где основная ценность участников коалиции будет заключаться в увеличении охвата целевой аудитории. Данное направление сегодня чрезвычайно актуально как с научной, так и с практической точек зрения, существуют и правовые предпосылки к организации такой работы ^[13]. На основе значения Шепли можно также осуществлять и анализ традиционных организованных преступных сообществ, относительно участников которых имеются оперативные сведения. Возможно также использование рассмотренного метода при анализе маршрутов движения транспорта и планировании связанных между собой профилактических мероприятий в деятельности ГИБДД ^[14], информационное обеспечение которой сегодня уже автоматизировано, то есть исходные данные для применения теоретико-игровых моделей имеются.

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