Andrey Raigorodskii

Yandex and Moscow State University, Moscow

Small Subgraphs in Preferential Attachment Networks

Abstract. Real-world networks such as web-graphs, social networks, biological networks, etc. have many important characteristics including the degree distribution (which usually follows a power law), the degree correlations, the diameter (which is usually small), the robustness to random attacks on vertices and the vulnerability to attacks on hubs, and so on. Also, a source of very important properties is given by counting small subgraphs in the networks: the most well-known such property is "high clustering", but there are many others. In our talk, we shall mainly concentrate on such properties.

On the other hand, many good and simple models of complex networks are provided by the now classical principle of preferential attachment. So in the talk, we shall define some of them and discuss the corresponding distributions of small subgraphs. We shall give a survey of results including the most recent ones.