Statistical model of graph structure based on "VKontakte" social network

Alexey Kislitsyn, Yurii Orlov
The paper presents a study of the graph network structure formed by the friendly connections of the "VKontakte" social network between the cities of Russia. It turned out that the graph node degree distribution is close to uniform. The consequence of this is the existence of a high-dimensional fully connected region and thin periphery. Also, the probability of fully connected structures was estimated for dense and sparse areas of the graph.