Network Evolution Model with Preferential Attachment at Triadic Formation Step

Abstract

It is recognized that most real systems and networks exhibit a much higher clustering with comparison to a random null model, which can be explained by a higher probability of the triad formation—a pair of nodes with a mutual neighbor have a greater possibility of having a link between them. To catch the more substantial clustering of real-world networks, the model based on the triadic closure mechanism was introduced by P. Holme and B. J. Kim in 2002. It includes a “triad formation step” in which a newly added node links both to a preferentially chosen node and to its randomly chosen neighbor, therefore forming a triad. In this study, we propose a new model of network evolution in which the triad formation mechanism is essentially changed in comparison to the model of P. Holme and B. J. Kim. In our proposed model, the second node is also chosen preferentially, i.e., the probability of its selection is proportional to its degree with respect to the sum of the degrees of the neighbors of the first selected node. The main goal of this paper is to study the properties of networks generated by this model. Using both analytical and empirical methods, we show that the networks are scale-free with power-law degree distributions, but their exponent γ is tunable which is distinguishable from the networks generated by the model of P. Holme and B. J. Kim. Moreover, we show that the degree dynamics of individual nodes are described by a power law.

Keywords

• triadic closure
• social networks
• preferential attachment
• complex networks
• high clustering
• growth model