Modeling of Complex Networks Formation by Game Theoretical Model and Establishing a Methodology for Forecast and Control of Complex Networks

In recent studies, it is revealed that some of social and technological networks have the properties of scale-free and/or small world, and these are called as "Complex Networks". The AS(Autonomous System)-level Internet topology (network) is considered as one of these complex networks. Although the inter-AS topology is decentrally and selfishly constructed by many administrators with capable of rational decision making, it seems that previous models for topology formation do not sufficiently represents such decentral and selfish topology formation. I consider that these complex networks can be represented by one of outcomes of rational behaviors by decentral and selfish multiple agents, therefore it is valid to model them by the frame of network formation game in game theory. Because results of game theory are valid for forecasting outcomes obtained by multiple and rational behaviors and for controlling them to more desirable things. On the other hand, traditional studies of the network formation game are not sufficient to represent large scale networks which have grown under various conditions like the inter-AS topology.

I presently study the relationship between the game theory and complex network formation. Based on the frame of network formation game in game theory, I especially focus on the inter-AS topology and I study following problems:

  • Modeling of the inter-AS topology by the frame of network formation game
  • Establishing a methodology for forecast and control of complex networks from a viewpoint of network formation game

I have already proposed with a coresearcher the dynamic network formation model based on the network formation game[Imai,2010]. The following figure represents an example of network formation generated by our topology formation model.

Example

It represents time series of link formation constructed by consensus formation among multiple and selfish agents. Our model can generate various topologies by some variation of settings and it is observed that some of topologies have scale-free properties which is typical properties of complex networks.
I consider that our model can be one of valid models to generate complex networks because it represents decentrally network design by multiple selfish agents(in the microscopic sense), and because it can generate scale-free networks observed in various real networks(in the macroscopic sense).

In RIKEN AICS, I study about social simulation using supercomputer K. I also belong to JST Basic Research Programs: CREST as research member, and now I am trying massive parallelization of traffic flow simulator using K computer.
Massive parallel computing technique is needed also for our network formation model to simulate network formation of comparable scale to actual social and technological network formation. I am now preparing for massive parallel simulation of large scale network formation.

Related/Interesting fields

  • Graph Theory
  • Game Theory
  • Theory of Complex Systems
  • Machine Learning
  • Optimization Theory
  • Technology about Communication Protocols
  • Theory of Probability
  • etc.

[Imai,2010] Tetsuo IMAI and Atsushi TANAKA, "A Game Theoretic Model for AS Topology Formation with the Scale-Free Property," IEICE TRANSACTIONS on Information and Systems, Vol.E93-D, No.11, pp.3051-3058, 2010.