The problem of modeling dynamics of complex networks is considered. The network model with non-unit elasticity controlled by mediation-driven attachment rule is studied. According to that rule, new nodes do not need a direct access to node statistics of the network: this data affects the links of new nodes, but is used implicitly. The assortative property of the considered model of complex networks is studied. It was shown that the proposed model generates networks with non-zero assortativity coefficient that is an important feature of this model. The dependence of the assortativity coefficient on the network size and copy-factor is obtained by numerical simulation. power law Assortativity, complex network, scale-free network, mediation-driven attachment, elasticity, ORCID: 0000-0002-4388-8180 (A. 1); 0000-0002-9890-4790 (A. 2); 0000-0001-5945-8647 (A. 3); 0000-0001-7778-231X (A. 4)
The theory of complex networks is a modern science area. As is known, the most of such networks demonstrate the power law distribution of nodes by degree [1-4]. Networks with the above property are called "scale-free". For instance, most of social networks, collaboration networks, communication networks, and citations of scientific papers, neural and protein networks [5] (but not all of them [6]) are scale-free.
At the heart of most of today's scale-free network models is the model proposed by Barabási and Albert in 1999 (BA-model) [7]. It is based on two powerful but simple concepts: concept of growth and concept of preferential attachment (or preferential linking). According to the latter, the probability for a new vertex to attach with some existing one is proportional to its degree. Although at present there exists many specifications and generalizations for the preferential attachment rule [1-4, 8-10], the proposed network models has some common features inherited from the parental BA-model. In particular, all these models inherit such a drawback of the BA-model as the explicit use of network's node statistic. The concept of implicit use of node degree information has been proposed in the mediation-driven anchor (MDA) model by Hassan [11]. Later the elastic variant of this model (EMDA model [12]) has been also developed.
Apart from the nodes degree distribution, the assortativity property of networks is also very important. It is known [2, 13-15] that the real world networks are essentially assortative (social networks), or disassortative (biological and technical ones), while artificial dynamic network models (such as BA) generate networks that are neutral in assortativity of nodes degree. This fact is a significant drawback of existing models of complex networks. Studying the assortativity properties of the EMDA-model forms the main subject of current interest.
2020 Copyright for this paper by its authors.
All models describing the networks topology can be classified into dynamic and static, depending on whether they are based on the concept of growth, i.e. increasing the number of nodes and links over time, or not. Static are models "inherited" from graph theory (for instance, the Erdős-Rényi (ER) model), as well as a well-known "small world" model by Watts-Strogatz [15].
In dynamic models, new nodes and links are added to the network step by step. Usually, but not always, the addition occurs one node at a each step. In this case, the size of the network (n) is a measure of time, and the number of the node (i) is the time of its birth.
The growth of the network and its properties are determined by the presence or absence of dying off nodes and links, the source of links and the linking rule. The simplest and most popular class of dynamic models of complex networks is formed by models in which only a new node can be a source of a new edge, and there is no dying off of nodes and links. In such models, the linking rule is the dependence of the probability i of connecting a new node with an existing node i on its individual properties (Prop(i)) , the network size n , and on the general (control) parameters of the network (Net_Prop) :
The most famous dynamic network model is the Barabási-Albert (BA) model [7], for which rule
(
i
ki .
ki
According to (
The control parameter of the BA-network is the number of links m const incident to each incoming node.
The BA-model generates a scale-free network (SFN). It means, that the distribution of nodes by degree (i.e. the number of links p(k) ) follows the Yule-Simon (YS) distribution. This distribution is a discrete analogue of a power law and asymptotically tends to it degree tends to infinity: p(k ) C
(k ) (k ) k , k k0 .
The parameter 2 is called the scaling factor. For BA-network 3 .
Currently, there are many different extensions and generalizations of the BA model, which
nevertheless fit into the general form (
One of such modifications of the BA-model is the elastic network model [12, 16, 17]. This model assumes that the relative growth rates of the number of links and nodes are different. Their ratio is called the elasticity index:
L(t) nL((tt)) Ln((tt)) n n(t)
L(n 1) L(n)
L(n) .
(
If const (1 2 ), then the total number of links in the network L(n) and, accordingly, the average degree of nodes k (n) grow asymptotically according to a Yule-Simon law with exponents and 1 respectively. Thus, using the concept of elasticity make us possible to generalize the original BA-model and allows dense networks to be modeled.
For 1 , each new node brings more links than their current average: L(n) L(n 1) L(n) k (n) . (5)
For example, the more scientific papers have been written, the more references the author of the new paper should revise.
The most important classifying factor of network growth models is the availability of information
about the nodes and / or links of the existing network. In BA-model and its numerous generalizations,
this information (for example, the values ki of the degrees of nodes in (
Obviously, for many networks in the real world, the hypothesis of the availability and explicit use of information is unrealistic. Both because of the closed nature of this information, and because of its huge volumes. Thus, a more natural class of complex network models is mediation-driven attachment (MDA) models. In the original model [11], a new node chooses one of the existing ones as an intermediary (equiprobably) and then connects (also equiprobably) with m of the neighbors of this mediator. The probability of joining i will depend on the degree of this node ki , but this degree value is used implicitly. In the elastic MDA-model (EMDA, [12]), not m is fixed, but the probability ( q ) of forming a link with an intermediary's neighbor. Parameter q is also called the copy-factor. This model is relatively new, its description and analysis is the first task of the current study.
An important property of networks is assortativity, i.e. the tendency of nodes to connect with similar ones by some property, or with opposite ones. Any node parameter can be used as such a property; in the simplest case, the node degree. It is known [13-15] that the real world networks are essentially assortative (social networks), or disassortative (biological and technical ones), while artificial dynamic network models (BA, ER, and others) generate networks that are neutral in assortativity of nodes degree. This property should be considered as a significant drawback of existing models of complex networks. Studying the assortativity properties of the EMDA-model is the second and main problem of current research.
In the EMDA model [12], the control parameter is the copy-factor (q) - the probability with which a new node binds to an mediator's neighbor node. In addition, it is assumed that the intermediary node itself is always linked with a new node (Figure 1).
Thus, the number of links incident with the new node is not a constant (as in the MDA rule, or in the BA-model), but equal to m 1 q kmed (where kmed is the degree of the intermediary node). Then the equation for the dynamics of the number of links in the network has the form (6) (7) (8) E{L(n)} 2(1 q E{kmed }) 2 2q k (n) .
2q . k (n) 2 (n 2q)
2q 1 (n 1)(1 2q)
1 .
Comparing (5) and (6), it is easy to see that the EMDA model is elastic with the elasticity index The average degree of nodes k (n) L(n) / n depends on the network size and on the copy-factor: 1 3 1 3
1 1 new new new p = 1/3 1
The dependence of the average degree of nodes on the network size and the copy factor (both theoretical (8)-(9) and numerical) is shown in Fig. 2.
It was shown [12] that the rank distribution of the nodes of the EMDA network asymptotically follows to a power law with the scaling factor (10) (11) min{q, 1 q} .
1 1 / 1 1 / min{q, 1 q} .
The power law of the rank distribution with exponent (10) corresponds to the power law of
frequency distribution (
Thus, the EMDA model generates networks that are elastic with the elasticity exponent (7) and scale-free with the scaling factor (11).
We can compare this fact with the properties of non-elastic (MDA) model. In such models factor m (instead of q ) used as a control parameter. Because of m is not scale-free, thus the generated MDA – networks should be not. Hassan [11] called MDA models "superpreferencial" in the sense of the attachment rule. Rank distributions of nodes degree for cases m 1 , m 5 and m 100 (obtained in [12]) are shown on Fig. 2 – Fig.4.
As one can see, this distributions are not power-law, thus MDA-model is not scale-free. Conversely, the analyzed class of models (EMDA) produces networks, which are scale-free. where
S1S3 S2 n Sk dik , i1
n n N3 d T Ad Aijdid j , i1 j1 A is adjacency matrix of the network, di is node degrees.
In general case assortativity coefficient (12) lies in the range 1 r 1; r 0 for random networks, such as BA-model or ER-graph. In boundary cases r 1 , the network has [14] a special structure (shown in Fig. 6), which are far from the structure of real networks.
An assortativity coefficient is defined as correlation coefficient of the nodes by their degrees [13,
15], or by the adjacency matrix:
The power law of the nodes degree distribution (
(14)
It is known [15] that the real-world networks are not neutral on its assortativity: social networks
are positively assortative while technical and biological ones are disassortative. Based on the
correlation nature of the assortativity coefficient, the numerical values given in Table 1 (less than 0.3
in absolute value) do not seem to be very significant. But supposing these networks as follows to
BAmodel, we can conclude that the assortative property should be considered as strongly significant
(Fig. 7). In fact, the networks shown in this example are SFN (
Asymptotic bounds of the assortativity index for the general case of SFN ( 2 3 and 1 2 ) are also known [18]: rmin n(1 ) , rmax n( 1 )(13 2 ) , (15) where 0.5 1 is the nodes degree rank distribution scaling factor (10).
In this, general case, the boundaries (15) are wider than in the case of the BA-model (14), but the general properties of the asymptotic boundaries are preserved: the boundaries narrow to zero with increasing the network size, and the lower boundary tends to zero much faster than the upper one.
The seed of the EMDA network model was two nodes connected by an edge. At each step, one node was added and linked to the existing ones according to the EMDA algorithm. Thus, network models having size n (128,256,512,1024,2048,4096,8192) were built. For each of these networks, the assortativity index was calculated by (12)-(13). The results obtained were averaged over M 100 ensembles.
The dependence of the assortativity coefficient of the network on its size and control parameter (copy-factor q ) is shown in Fig. 8.
In Fig.9 is shown the dependence of the assortativity coefficient of the network with fixed size n 8192 on the control parameter.
Thus, numerical simulations show that the EMDA algorithm generates networks with significantly positive assortativity. Assortativity coefficient decreases with increasing copying factor. This is consistent with the fact that by increasing the copy factor, the scaling factor of the nodes degree distribution is also increase. Last years some new approaches to networks assortativity problem were presented [19-26]. Thus, applying it to the theoretical study of the assortativity of the EMDA model is considered as a direction for further research.
The analysis of dynamic models of complex networks and the corresponding attachment rules is provided. It was obtained that significant disadvantages of traditional models are the explicit use of information about the properties of existing nodes and the linear dependence of the number of links in the network on the number of nodes. It is shown that the EMDA model is free of these lacks: it is elastic and does not use node statistics. A brief description of this model is provided.
The analysis of the assortative property of real world networks and dynamic models of such networks is carried out. It was revealed that real networks have an explicit property of assortativity (positive or negative), while existing artificial models generate networks with zero assortativity, i.e. neutral. In this regard, the task of studying the assortativity of networks generated by the EMDAmodel was formulated and solved.
As a result of the provided numerical simulation, it was found that the EMDA algorithm generates networks with significantly positive assortativity. Assortativity coefficient decreases with increasing copying factor. Thus, it can be argued that the EMDA model reflects the most important properties of social networks: asymptotic scale invariance, implicit use of information about nodes, high density of links, and significantly expressed positive assortativity.
The theoretical study of the assortativity of the EMDA model is considered as a direction for further research.
[4] J. Kunegis, M. Blattner, C. Moser, "Preferential Attachment in Online Networks: Measurement and Explanations.", WebSci13 ACM Web Science Conference 2013. 13. doi: 10.1145/2464464.2464514. [5] M. E. J. Newman, "Power laws, Pareto distributions and Zipf's law", Contemporary Physics, 2005, 46(5). p.323-351. [6] A. D. Broido, A. Clauset, "Scale-free networks are rare". Nat Commun 10, 1017 (2019).
https://doi.org/10.1038/s41467-019-08746-5 [7] R. Albert, A.-L. Barabási, "Statistical mechanics of complex networks", Rev. Mod. Phys., 2002,
V. 74. - p. 42-97. [8] G. Bianconi, A.-L. Barabási, "Competition and multiscaling in evolving networks", Europhysics
Letters, 2001, 54 (4):436–442. [9] G. Caldarelli, Guido; Catanzaro, Michele (2012). Networks: A Very Short Introduction. Oxford
University Press. p. 78 [10] Ch. Dangalchev, "Generation models for scale-free networks", Physica A, 2004, 338, 659 [11] M. K. Hassan, L. Islam, S. A. Haque, "Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks". Physica A: Stat. Mech. and its Appl. 2017. 469 (2017): 23–30 [12] V. Shergin, L. Chala, S. Udovenko, M. Pogurskaya, "Elastic Scale-Free Networks Model Based on the Mediaton-Driven Attachment Rule", 2020 IEEE Third International Conference on Data Stream Mining & Processing (DSMP), Lviv, 2020, in press. [13] R. Noldus, P. Van Mieghem, "Assortativity in complex networks", J. Complex Networks, 2015, vol. 3, pp. 507-542. [14] V. Shergin, S. Udovenko, L. Chala. "Assortativity Properties of Barabási-Albert Networks," In
Data-Centric Business and Application. Springer, 2021.
[15] M. E. J. Newman. “Mixing patterns in networks”. Physical Review E. 67 (
ISSN 1063-651X. PMID 12636767 [16] V. Shergin, L. Chala, "The concept of elasticity of scale-free networks," 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 257-260. [17] V. L. Shergin, L. E. Chala and S. G. Udovenko, "Fractal dimension of infinitely growing discrete sets," 2018 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), Slavske, 2018, pp. 259-263. [18] V. Shergin, L. Chala, S. Udovenko. Assortativity Properties of Scale-Free Networks. In 2019 International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S&T). IEEE, Kharkiv, 2019, pp. 92-96. [19] B. K. Fosdick, D.B. Larremore, J. Nishimura, J. Ugander, "Configuring random graph models with fixed degree sequences.", 2016, arXiv:1608.00607. [20] L. Peela, J-C. Delvennea, R. Lambiotted, "Multiscale mixing patterns in networks", https://doi.org/10.1073/pnas.1713019115 [21] G. Q. Zhang, S. Q. Cheng, (2012) "A universal assortativity measure for network analysis", 2012, arXiv preprint arXiv:1212.6456 1: 1–8. [22] N. Meghanathan, "Assortativity Analysis of Real-World Network Graphs based on Centrality
Metrics", Computer and Information Science Archives, Vol. 9, No. 3 (2016) [23] D. N. Fisher, M. J. Silk, D. W. Franks "The Perceived Assortativity of Social Networks: Methodological Problems and Solutions." In: Trends in Social Network Analysis. Lecture Notes in Social Networks. Springer, Cham. 2017 https://doi.org/10.1007/978-3-319-53420-6_1 [24] Y. Yuan, J. Yan, P. Zhang, "Assortativity measures for weighted and directed networks", arXiv:2101.05389v1 [stat.AP] 13 Jan 2021 [25] G. Thedchanamoorthy, M. Piraveenan, D. Kasthuriratna, U. Senanayake, "Node Assortativity in Complex Networks: An Alternative Approach", Procedia Computer Science, Volume 29, 2014, Pages 2449-2461, ISSN 1877-0509, https://doi.org/10.1016/j.procs.2014.05.229. [26] M. Murakami, S. Ishikura, D. Kominami, Tetsuya Shimokawa, M. Murata, "Robustness and efficiency in interconnected networks with changes in network assortativity", Applied Network Science, vol. 2, No.6 (2017), DOI 10.1007/s41109-017-0025-4