Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Программные системы и вычислительные методы
Правильная ссылка на статью:

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

Торопов Борис Андреевич

кандидат технических наук

доцент, Академия управления МВД России

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
Другие публикации этого автора
 

 

DOI:

10.7256/2454-0714.2017.2.22647

Дата направления статьи в редакцию:

10-04-2017


Дата публикации:

19-06-2017


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


Ключевые слова:

граф, социальный граф, социальная сеть, центральность вершины, центральность по степени, групповая центральность, коалиционные игры, вектор Шепли, перестановки, алгоритм

Abstract: The object of studies concerns the methods for evaluation of the graph nodes. The author pays attention to the fact that the existing centrality metrics, such as level centrality, closeness centrality, interval centrality, own vector, etc., are sometimes not suitable for modeling the situations, when graph nodes are social object models, and therefore, they are capable of cooperation in order to achieve social goals.  In this case game-theoretic centrality models (such as coalition games models) are better suited to reflect the modeling object.  The methodology of the study involves the elements of graph theory, probability theory, as well as the apparatus for the analysis of social networks as a new independent scientific sphere. The key result of the stuy is that game-theoretic centrality based upon the Shapley vector is a flexible and mostly universal instrument for the social graph analysis.  It allows to consider an unlimited set of quality characteristics of the graph nodes, as well as their topological qualities in any combination in order to evaluate the nodes.


Keywords:

algorithm, permutation, Shapley vector, coalition games, group centrality, level centrality, node centrality, social network, social graph, graph

Введение

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

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

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

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

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

Групповая центральность и ценность вершины графа как элемента группы

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

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

`c^(deg)(S) = |{u:(v,u)inE ^^v in S^^u!inS}|, SsubeV,` `(1)`

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

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

`phi_v(S) = c(S)-c(S{v})` (2)

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

deg_1

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

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

Ценность вершины графа как потенциального элемента произвольной группы вершин на основе вектора Шепли

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

`phi_(v)=1/V!sum_(SsubeV)|S|!(|V|-|S|-1)![c(S)-c(S{v})]` (3)
где: `sum_(SsubeV)|S|!(|V|-|S|-1)!` – это общее число возможных перестановок вершин в полной группе из V;

|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:

`p_u=1/(1+|{z:(u,z)inE}|)` (4)

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

`phi_v=sum_(uin{u:(v,u)inE}uu{v})1/(1+|{z:(u,z)inE}|) ` (5)

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

`phi_v=` 1/(1+ число соседей v) + `sum` 1/(1+число соседей u) (6)
u`in`

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

gdeg1

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

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

Расчетный пример на графе флорентийских марьяжей

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

medici

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

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

Таблица 1. Центральность флорентийских семей, cdeg- центральность по степени, cSV-deg- значение Шепли на основе центральности по степени, cbtw- центральность по промежуточности, ccl- центральность по близости.

Семья

Метрика центральности:

Место по центральности:

cdeg

cSV-deg

cbtw

ccl

cdeg

cSV-deg

cbtw

ccl

Medici

6

2,06

0,52

0,56

1

1

1

1

Guadagni

4

1,45

0,25

0,47

2

2

2

5

Strozzi

4

1,20

0,10

0,44

2

3

7

6

Albizzi

3

1,09

0,21

0,48

4

4

3

3

Castellan

3

1,03

0,05

0,39

4

5

10

9

Saviati

2

0,98

0,14

0,39

10

6

4

9

Peruzzi

3

0,95

0,02

0,37

4

7

11

11

Bischeri

3

0,90

0,10

0,40

4

8

6

8

Ridolfi

3

0,84

0,11

0,50

4

9

5

2

Tornabuon

3

0,84

0,09

0,48

4

9

9

3

Pazzi

1

0,83

0,00

0,29

12

11

12

15

Ginori

1

0,75

0,00

0,33

12

12

12

13

Barbadori

2

0,73

0,09

0,44

10

13

8

6

Lambertes

1

0,70

0,00

0,33

12

14

12

14

Acciaiuol

1

0,64

0,00

0,37

12

15

12

11

Как видно, значения Шепли по степени отличаются ото всех трех «традиционных» метрик центральности, во многом повторяя значения обычной центральности по степени (коэффициент корреляции между ними составляет 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 даст формируемой группе пользу.

`1/(15!)xx(15!)/(6!(15-6)!)xx4xx5!xx(15-6)! = (4xx5!)/(6!) = 4/6 = 2/3` ‒ доля перестановок,

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

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

` `

Заключение

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

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

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

Библиография
1. Freeman L.C. Centrality in social networks: Conceptual clarification // Social Networks. 1978. №1. P. 215-239.
2. Everett M.G., Borgatti S.P. The centrality of groups and classes // Journal of Mathematical Sociology 1999. №3. P.181-201.
3. Shapley, Lloyd S. A Value for n-person Games. In Kuhn, H. W.; Tucker, A. W. Contributions to the Theory of Games // Annals of Mathematical Studies. Princeton University Press. V.28. 1953. P. 307–317.
4. Michalak T.P., Rahwan T., Skibski O., Wooldridge M. Defeating Terrorist Networks with Game Theory // IEEE Intelligent Systems. 2015. V. 30. № 1. P. 53-61.
5. Aadithyaa K.V., Ravindran B., Michalak T.P., Jennings N.R. Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality // Journal of Artificial Intelligence Research. 2013. V.46. P. 607–650.
6. Michalak T.P., Marciniak D., Samotulski M., Rahwan T., McBurney P., Wooldridge M., JenningsN. A logic-based representation for coalitional games with externalities // Proceedings of the Ninth International Joint Conference on Autonomous Agents and Multi-Agent Systems. 2010 P.125–132.
7. Suri N.R., Narahari Y. Determining the top-k nodes in social networks using the Shapley Value // Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multi-Agent Systems. 2008. P. 1509–1512.
8. Bonacich P. Power and centrality: A family of measures // American Journal of Sociology. 1987. №5 P.1170–1182.
9. Karlsson C., Andersson M., Norman T. Handbook of research methods and applications in economic geography. Cheltenham : Edward Elgar Publishing, 2015. 648 p.
10. Padgett J. F., Ansell C.K. Robust Actin and the Rise of the Medici, 1400-1434 // American Journal of Sociology. 1993. V.98, P.1259-1319.
11. Jackson M.O. Social and Economic Networks. Princeton University Press, 2008. 520 p.
12. Торопов Б.А., Тагиров З.И. Модели террористических сетей и теоретико-игровой подход к оценке центральности их участников // Вопросы безопасности. — 2016.-№ 6.-С.77-89. DOI: 10.7256/2409-7543.2016.6.21436. URL: http://e-notabene.ru/nb/article_21436.html
13. Баранов В.В. Совершенствование правового обеспечения деятельности органов внутренних дел по противодействию проявлениям экстремизма в глобальной компьютерной сети // Труды Академии управления МВД России. 2016. № 4. С.27-30.
14. Кузнецов А.С., Машурова О.Ю. Применение геоинформационных систем в деятельности Госавтоинспекции МВД россии // Информационные технологии в деятельности правоохранительных органов: проблемы использования и пути повышения эффективности. Сборник научных статей.. Орел. 2016. С. 62-65.
References
1. Freeman L.C. Centrality in social networks: Conceptual clarification // Social Networks. 1978. №1. P. 215-239.
2. Everett M.G., Borgatti S.P. The centrality of groups and classes // Journal of Mathematical Sociology 1999. №3. P.181-201.
3. Shapley, Lloyd S. A Value for n-person Games. In Kuhn, H. W.; Tucker, A. W. Contributions to the Theory of Games // Annals of Mathematical Studies. Princeton University Press. V.28. 1953. P. 307–317.
4. Michalak T.P., Rahwan T., Skibski O., Wooldridge M. Defeating Terrorist Networks with Game Theory // IEEE Intelligent Systems. 2015. V. 30. № 1. P. 53-61.
5. Aadithyaa K.V., Ravindran B., Michalak T.P., Jennings N.R. Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality // Journal of Artificial Intelligence Research. 2013. V.46. P. 607–650.
6. Michalak T.P., Marciniak D., Samotulski M., Rahwan T., McBurney P., Wooldridge M., JenningsN. A logic-based representation for coalitional games with externalities // Proceedings of the Ninth International Joint Conference on Autonomous Agents and Multi-Agent Systems. 2010 P.125–132.
7. Suri N.R., Narahari Y. Determining the top-k nodes in social networks using the Shapley Value // Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multi-Agent Systems. 2008. P. 1509–1512.
8. Bonacich P. Power and centrality: A family of measures // American Journal of Sociology. 1987. №5 P.1170–1182.
9. Karlsson C., Andersson M., Norman T. Handbook of research methods and applications in economic geography. Cheltenham : Edward Elgar Publishing, 2015. 648 p.
10. Padgett J. F., Ansell C.K. Robust Actin and the Rise of the Medici, 1400-1434 // American Journal of Sociology. 1993. V.98, P.1259-1319.
11. Jackson M.O. Social and Economic Networks. Princeton University Press, 2008. 520 p.
12. Toropov B.A., Tagirov Z.I. Modeli terroristicheskikh setei i teoretiko-igrovoi podkhod k otsenke tsentral'nosti ikh uchastnikov // Voprosy bezopasnosti. — 2016.-№ 6.-S.77-89. DOI: 10.7256/2409-7543.2016.6.21436. URL: http://e-notabene.ru/nb/article_21436.html
13. Baranov V.V. Sovershenstvovanie pravovogo obespecheniya deyatel'nosti organov vnutrennikh del po protivodeistviyu proyavleniyam ekstremizma v global'noi komp'yuternoi seti // Trudy Akademii upravleniya MVD Rossii. 2016. № 4. S.27-30.
14. Kuznetsov A.S., Mashurova O.Yu. Primenenie geoinformatsionnykh sistem v deyatel'nosti Gosavtoinspektsii MVD rossii // Informatsionnye tekhnologii v deyatel'nosti pravookhranitel'nykh organov: problemy ispol'zovaniya i puti povysheniya effektivnosti. Sbornik nauchnykh statei.. Orel. 2016. S. 62-65.