Naturality of Network Creation Games, Measurement and Analysis

Modeling is one of the major research areas in social network analysis whose goal is to study networks structure and its evolution. Motivated by the intuition that members in social networks behave selfishly, network creation games have been introduced for modeling social networks. In this paper, our aim is to measure how much the output graphs of a given network creation game are compatible with a social network. We first show that the precise measurement is not possible in polynomial time. Then we propose a method for its approximation; finally, we show the usability of our method by conducting experiments on real network data.