Brief Announcement: Network Formation Games Can Give Rise to Realistic Networks

摘要

The purpose of network formation games is to give a game-theoretical tool which can effectively explain the topoiogicsl properties (clustering, degree distribution, small world property) and the emergence of Internet-like complex networks in an incentive centered economical fashion. In the influential book of the subject , the development of an incentive-oriented and endogenous model of network formation, that would generate more heterogeneous and realistic networks, is still attributed as an exciting open challenge. Although more recently several studies recovered realistic clustering and degree distribution by encoding these properties into the cost functions of the players, these still qualify as exogeneous models. In this paper, we define a network formation game in which realistic topologies naturally emerge as equilibrium networks, without enforcing topological concerns in the cost functions. Inspired by the wealth of studies concerning greedy search processes in networks, we define a modified game where players are placed in a metric space and, instead of the usual shortest path metric, we use the length of greedy paths as the measure of communication cost between players. We also present some preliminary results.