Eng During last 365 days Approved articles: 1911,   Articles in work: 308 Declined articles: 809 
Articles and journals | Tariffs | Payments | Your profile

Back to contents

Game-theoretic centrality in the graph nodes based upon the Shapley vector.
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





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



Article was received:


Review date:


Publish date:


This article written in Russian. You can find full text of article in Russian here .

Freeman L.C. Centrality in social networks: Conceptual clarification // Social Networks. 1978. 1. P. 215-239.
Everett M.G., Borgatti S.P. The centrality of groups and classes // Journal of Mathematical Sociology 1999. 3. P.181-201.
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. 307317.
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.
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. 607650.
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.125132.
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. 15091512.
Bonacich P. Power and centrality: A family of measures // American Journal of Sociology. 1987. 5 P.11701182.
Karlsson C., Andersson M., Norman T. Handbook of research methods and applications in economic geography. Cheltenham : Edward Elgar Publishing, 2015. 648 p.
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.
Jackson M.O. Social and Economic Networks. Princeton University Press, 2008. 520 p.
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
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.
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.