On November 14^th, 2018, Professor Vladimir V. Mazalov from Russian Academy of Sciences and Professor Elena Parilina from the St. Petersburg State University visited the Center on Frontiers of Computing Studies of PKU. Professor Vladimir V. Mazalov gave a talk titled "Game-theoretic methods for analysis of the structure of communication networks" and Professor Elena Parilina gave a talk titled "Stochastic Game of Data Transmission in the Presence of Buffers of Finite Capacities". Professor Xiaotie Deng from CFCS hosted the lecture.

Professor Vladimir V. Mazalov

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.

Professor Elena Parilina

Abstract:

The game-theoretic model of data transmission in a network of a given topology is presented. Two players (network nodes) tend to send as many random data packages as possible to the final nodes through one common node. Each player has a finite capacity buffer for storing data packages. A system of costs for sending and storing data packages and rewards for the successful package delivery is introduced. A dynamic conflict-controlled process is modeled as a stochastic game with a finite set of states. Existence of the Nash equilibrium and a cooperative solution is proved. The cooperative solution is a strategy profile which maximizes the total expected payoff. The price of anarchy in the network is calculated. The price compares the players’ payoffs in the Nash equilibrium and cooperative solution.

Biography:

Elena Parilina is the PH.D., Associate Professor of Faculty of Applied Mathematics and Control Processes, Department of Mathematical Game Theory and Statistical Decisions, Saint Petersburg State University, Russia. Parilina's research focuses on Cooperative games and applications, stochastic games and applications, statistical data analysis, modeling of social and economic systems.