New Deterministic Model of Evolving Trinomial Networks

摘要

We provide a new model of attributed networks where label of each vertex is a partition of integer n into at most m integer parts and all labels are different. The metric in the space of (n, m)-partitions is introduced. First, we investigate special class of the trinomial (m~2, m)-partitions as a base for synthesis of networks G(m). It turns out that algorithmic complexity (the shortest computer program that produces G(m) upon halting) of these networks grows with m as log m only. Numerical simulations of simple graphs for trinomial (m~2,m)-partition families (m = 3,4,..., 9) allows to estimate topological parameters of the graphs-clustering coefficients, cliques distribution, vertex degree distribution-and to show existence of such effects as scale-free and self-similarity for evolving networks. Since the model under consideration is completely deterministic, these results put forward new mode of thought about mechanisms of similarity, preferential attachment and popularity of complex networks. In addition, we obtained some numerical results relating robust behavior of the networks to disturbances like deleting nodes or cliques.