Game-theoretic Analysis of Structure of Communication Networks
- Prof. Vladimir V. Mazalov, Institute of Applied Mathematical Research KarRC RAS
- Time: 2018-11-15 14:00
- Host: Prof. Xiaotie Deng
- Venue: Room 102, Courtyard No.5, Jingyuan
Abstract
The betweenness centrality is one of the basic concepts in the analysis of the communication and social networks. Initial definition for the betweenness of a node in the graph is based on the fraction of the number of geodesics (shortest paths) between any two nodes that given node lies on, to the total number of the shortest paths connecting these nodes. This method has polynomial complexity. We propose a new concept of the betweenness centrality for weighted graphs using the methods of cooperative game theory. The characteristic function is determined by special way for different coalitions (subsets of the graph). We use the approach in which the characteristic function is determined via the number of direct and indirect weighted connecting paths in the coalition. After that the betweenness centrality is determined as the Myerson value. The results of computer simulations for some examples of networks, in particular, for the popular social network “VKontakte and portal of mathematical publications MathNet.ru are presented. Then we apply game-theoretic methods for community detection in networks. The traditional methods for detecting community structure are based on selecting dense subgraphs inside the network. Here we propose to use the methods of cooperative game theory that highlight not only the link density but also the mechanisms of cluster formation. Specifically, we suggest two approaches from cooperative game theory: the first approach is based on the Myerson value, whereas the second approach is based on hedonic games. Both approaches allow to detect clusters with various resolution. The tuning of the resolution parameter in the hedonic games approach is based on the Maximum likelihood method. Finally, for approaches based on potential hedonic games we suggest a very efficient computational scheme using Gibbs sampling.
Biography
Vladimir V. Mazalov is the Director of the Institute of Applied Mathematical Research KarRC RAS and he is also the President of International Society on Dynamic Games(ISDG). Mazalov’s research focuses on optimal stopping theory, game theory, decision analysis and applications of dynamic programming in behavioral ecology. His research has been recognized with Laureate of the Young Scientist Contest in basic science of the RAS Siberian Branch; Zabaikalsky Komsomol Prize Winner.