ECAI 2004 Conference Paper

[full paper]

Complex Networks Emergence through Local Optimisation

Josep M. Pujol, Andreas Flache, Ramon Sanguesa, Jordi Delgado

The emergence of complex network structures, such as the celebrated power-law and small-world networks reflecting relationships between autonomous agents emerge in a wide range of distributed systems. Many researchers have proposed models to explain and reproduce this striking phenomenon. However, most of their assumptions are non-realistic and are motivated by their interest of reproducing, rather than explaining, the emergence of such structures. One example of this is the need for agents to have knowledge about all other agents interactions in order to carry on preferential attachment, the most used mechanisms for generation power-laws. A more realistic point of departure is based on the agents having access only to local knowledge and not to the global properties of the system and the corresponding network. We propose a general model based on a set agents with dissimilar attractiveness level, who are seeking the best set of agents to interact with in terms of the outcome received from the payoff matrix of the cooperative game they are engaged in. Thus, agents perform an local optimisation process bounded by realistic and plausible assumptions: local and imperfect information. Furthermore, our model is able to generate several kinds of complex networks: from power-law to small-world including central-periphery networks. This diverstiy depends on a new parameter that we have identified: system's harshness.

Keywords: complex networks, power-law networks, scale-free networks, small-world networks, social simulation, multi-agent systems, distributed AI, game-theory

Citation: Josep M. Pujol, Andreas Flache, Ramon Sanguesa, Jordi Delgado: Complex Networks Emergence through Local Optimisation . In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.43-47.