The problem of modeling scale-free networks is considered. Mediation-driven attachment rule with constant number of incoming links is studied. According to that rule, new nodes do not need access to node statistics of the network, although the probability of joining to existing node is determined by its degree, this information is used implicitly. Such feature looks quite natural and is a key advantage of mediation-driven attachment rule. The dependence of the scaling factor of nodes degree distribution on the control parameter - the number of links associated with incoming nodes - is analyzed both analytically and by numerical simulation.
The scale-free network’s theory is a relatively new science area. The key feature of such networks is that their nodes distribution by degree follows to a power law [1]. Social networks, citations of scientific papers, collaboration networks, neural and protein networks and many other real-world networks [2] are scale-free. On the other hand, power law distribution is a characteristic feature of fractal properties of the system. This is another reason for the interest to the scale-free networks.
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) [3]. It is based on two fundamental concepts: concept of growth and concept of preferential attachment: the probability for a new node to link with some existing one is proportional to its degree. Although at present there exists many specifications and generalizations for the generative rule used to create network models [4-17], their common features ascends to BA-model.
The concept of implicit use of node statistics, implied in the mediation-driven attachment (MDA) model, was proposed by Hassan [13]. Forming and analysis the dynamic model of network, controlled by MDA-rule is the subject of current interest.
Scale-Free Network Models Overview
According to the concept of growth, the seed network comprises n0 nodes and L0 / 2 edges, and then at each time step, a new node is added to the network. Thus, network size n (i.e. number of nodes) can be used as time measure without lost of generality. In this case, the node number ( i ) is considered as the time of its birth (i.e. n − i is the node's age).
Aside from the time of birth, each node is characterized by its degree ( di ) and other properties Pi (fitness, etc.). Network growth dynamics is determined by the number of links m(n) that connect the incoming node with existing ones, or by the average degree of nodes k (n) . The network may also have other control parameters C (such as additional attractiveness, elasticity etc.).
Network properties are determined by the attachment rule, i.e. the probability i that a new added node links to existing one i , as a function of the above parameters: i = f (i, ki , n0 , L0 , Pi , C) .
A key feature of the scale-free networks is the distribution of the nodes by degree p(k ) that should follow (at least, asymptotically) to the Yule-Simon law (which is a discrete analogue of the power law): p(k ) = C
(k ) (k + ) k − , k k0 .
The parameter 2 is called the scale factor.
(
The simplest and most known model for scale-free networks is the BA model [3]. It is based on two fundamental concepts: concept of growth and concept of preferential attachment, according to which each incoming node connects to m = const existing ones. The probability i that a new edge points to some node i is proportional to its degree ki : i = ki / ki .
i
Thus, BA attachment rule is the simplest case of a general form (
According to the fitness model [4], each node is associated with its fitness value i .
Therefore, rule (
Another extensions of BA model are based on aging [6], i.e. using the attachment
rule (
In the Price model [2] the network is supplied by global additional attractiveness
parameter a , and attachment rule has the form i = (ki + a) / (ki + a) . This
approach was used for modelling citation networks, which are considered as directed.
Therefore, in the attachment rule ki denotes only in-links. Clearly, if a = 0 (i.e. if the
BA rule (
At now, there exists many other specifications and generalizations for the
generative mechanism (
Not all of the above models produce scale-free networks. In fact [9, 12], the only
class of attachment rules (
However, the BA-model just as all above inherited ones, has bears some original features that limit their application area. One of them is explicit using of nodes degree information. In real-world networks, the incoming node cannot assess the information for the whole of existing nodes due to the large size of the network, confidentiality reasons etc. Really, for a first choose a site or scientific paper, we are not interested how many references to other sites or papers it has. Similarly, a novice businessman cannot obtain the information about who of his potential trade partners has how many trade links. However, after visiting the initial website or reading an introductory scientific paper, the reader may want to follow some available links from this site / paper to other sources. Thus, this original site / paper act as a mediator.
The mediation-driven attachment (MDA) model was proposed by Hassan et al. [13] to overcome the above restriction. It can be regarded as a version of the earlier copy-model [15-16]. MDA model forms a subject of interest of current paper. 2
The Mediation-Driven Attachment Rule Model
According to MDA rule, each incoming node chooses some existing one uniformly at random. This node is called mediator. Then incoming node links at random to m neighbors of this mediator. The probability i for node i to link with incoming one can be found by the following way: let the neighbors of node i are enumerated 1, 2,..., ki . The probabilities for each of them to be chosen as mediator are equal to 1/ n . The probability for node i to be reached through mediator j is 1 / k j . Thus, i = 1 ki 1
n j=1, k j j i
As per (
The comparison of BA and MDA rules is illustrated on Fig. 1. According to (
1 1/4
The evolution of the MDA network in the case m = 1 is shown on Fig. 2. The nodes of the networks are labelled by the probabilities of joining a new node. The probabilities of implementing the corresponding network structures are shown in the headers.
It can be seen that in contrast to the BA-model, the probability of forming a starshaped structure (hyperhab) is very high, so, if m is small, the MDA model is prone to the "winner takes all" paradigm.
Indeed, if the network with n nodes is star-shaped, then the new node will be linked with the central one if any non-central node is choosen as the mediator. Thus, the probability of persisting the star-like structure on n-th step is equal to
Therefore, the unconditional probability of forming a star-like structure under MDA-rule with m = 1 is very high: (n) = (n −1) / n .
P(n) =
2 n −1 .
(
In comparison, the probability of forming a star-like network under the BA model is only PBA = 23−n .
The first two step of evolution of the MDA network under the case of m = 2 are shown on Fig. 3.
Prob = 1 1/6 2/3 1/6
Prob = 2/3 1/12 3/4 1/12
Prob = 1/3 3/8 1/8 1/12 1/15 1/4 1/8
However, this dependence is purely empirical. It does not reflect the nature of the impact of the control parameter ( m ) on the scaling factor. Thus, it is necessary to consider a dynamic model of network, controlled by MDA-rule. 3
Dynamic Properties of the MDA Network
Lets consider the general case of MDA-network dynamics in the case of an arbitrary (but constant) value of the control parameter m = const .
We assume that the initial network is a complete graph of n0 = m + 1 nodes. Thus, all nodes have degree m . A complete graph of m + 1 nodes is the minimum number of nodes among all graphs for which the degree of nodes is not less than m . Initially network contains L0 = m n0 = m(m + 1) links (or e0 = m(m + 1) / 2 edges).
Since each step a single node is added to the network, it is natural to use the network size as the step number (i.e. as the time measure). Each new node adds m edges, or 2m links, so the total number of links and the average node degree can be expressed as
L(n) = m (2n − n0 ) , k (n) = m(2 − nn0 ) , lim k (n) = 2m .
n→
The probability for an existing node i to get a new link is m i (n) , so the expected value of i-th node degree increased just on this value:
ki (n + 1) − ki (n) = m i (n) .
The expression (
n j=1, k j (n) j i
= ki (n) m ki (n)
m n ki (n) j=1, k j (n) j i
1 .
We may denote the expression in parentheses of (
Next, we assume that for a large network ( n → ), parameter (
Then, substituting (
ki (n) j=1, k j (n) j i
, Ci = m
(i) (i + )
i m .
Ci = m
(
1
Without lost of generality, we can assume, that the nodes are sorted by age, so, at Then at step i n0 the network consists of i nodes. The new node will receive the number i +1 , and, in accordance with the MDA rule, it will establish exactly m connections with existing nodes. So, ki (i) = m , and, therefore,
For nodes that are the "founding parents" of the network, i.e. for the first n0 = m + 1 nodes, the initial conditions are ki (n0 ) = m , so
Taking into account (
(i) (i + ) (n + ) (n)
The dependence (18) is a Yule-Simon distribution (
ki (n) m (n / i) .
From (18)-(19) it is easy to see that the dependence of the node degree on its number is monotonically decreasing, so the node number (i.e. age) can be an expectation of its rank.
Considering the age distribution (18), or its approximation (19), as a nodes rank distribution, the power rank distribution with the scaling factor corresponds to the power law of frequency distribution with the scaling factor (exponent)
Thus, we can summarize that applying the MDA rule as well as in the case of using the explicit preferential linking (BA-model) should lead to a scale-free network. The only difference is the value of the scaling factor: = 3 for the BA model, but has the form (20) for the MDA one.
However, it should be noted that the above conclusion is based on assumption (
As n → , the second component in (22) decreases to zero as O(n− ) , so the (20) (21) (22) (23) 4
Scaling Factor Estimation for MDA Model
The assumption of independence bi (n) on i (as well as on ki ) means that asymptotically the average values of inverse degrees of nodes connected to the node i is the same as the average of the values inverse to the degree nodes throughout the whole network:
The sum in the approximate expression (21) can be found by summing 1 / ki (n) from (18): estimate of parameter bi (n) (21) has the form
m n + lni→m bi (n) = lim = n→ n m( +1)
On the other hand, according to (
Equation (24) is well-known and its solution is the golden ratio:
Numerical simulations were made. Initially, M = 100 networks each of 4096 nodes was generated to find whether they could be considered as scale-free (i.e. whether the nodes degree is distributed by a power law). Rank distributions of nodes degree for cases m = 1 and m = 5 are shown on Fig. 4 and Fig. 5. The distribution of nodes degree by their age for the case m = 100 is shown on Fig. 6. ) e e r egD 6 (go2 l 4 2 00
6 log2(Range) 2 4 8 10 12 Fig. 4. Rank distribution of nodes degree for the case m = 1
Range <= m+1 Degree < m+0.5
According to Fig.4-Fig.6, the graphs can be segmented into three sections: initial (left tail), middle, and final (right tail). It is easy to see that rank distributions of nodes degree of the middle section follow to the power law with great accuracy. Regression lines are also shown on Fig. 4 - Fig. 6, and the corresponding estimates of scaling factor are shown in the graphs headings.
As one can see, the first n0 = m + 1 nodes significantly deviate from the power law sequence, i.e. from regression lines, shortage the links. This phenomenon is quite natural, because the distribution law (18) is a Yule-Simon distribution, which coincides with the power law only asymptotically. In addition, according to (18) there is an operation of rounding small values of n up to n0 . That is why the regression lines were built without the initial nodes.
On the other hand, the end nodes are also not subject to a power law. The existence of this tail has no theoretical justification, but it can be explained empirically: in the super-preferential network, the nodes that appeared later do not have time to collect links, additional to those they have at birth. During the numerical simulation, the threshold was set manually as m + 0.5 . According to the simulation results (Fig. 4 Fig. 6), such threshold value allows to separate quite clearly the "young" nodes (i.e. the right tail) from the "middle-aged" nodes, which follows to a power law. It can be noted that the fraction of the tail section decreases rapidly with increasing the control parameter m : the tail contains almost 98% of the total number of nodes under m = 1 , but about half under m = 5 , and less than 10% under m = 100 .
Studying the empirical dependence of the scaling factor under control parameter was the next stage of current research.
According to the results of the initial research (Fig. 4 - Fig. 6), the distribution of nodes by degree can be considered as power law, but it's scaling factor differs from the theoretically predicted golden ratio (25), and secondly, significantly depends on the control parameter m : it is equal to 1.8335, 1.2861, 0.8599, 0.6731, 0.5775 under m = 1, 2, 5,10,100 respectively. Thereby, the dependence of the scaling index ( ) on the control parameter m (the number of links for newly added nodes) were studied.
For each m from a given set of values 1 m 100 , M = 100 networks each of
N = 4096 nodes were generated. For each network, the scaling factor was estimated
separately. The results are shown in Fig. 7. Single dots correspond to the individual
networks. Since obtained estimates has a very high variability, especially for small
values of m , the median averaging is more appropriate instead of mean one. The
solid line connects the medians of the obtained estimates. For comparison, in the same
figure, the empirical dependence (
Nodes = 4096 ens = 100
3
2.8
2.6
2.4
/
1
1+2.2
=
2
1.8
1.6
1.4
1
2
3
─ for small values of the control parameter m the variability of exponents is so high
that we cannot talk about their more or less reliable value;
─ moreover, under m 5 the scaling factor of frequency distribution of the nodes
degree is 2 , so it does not even have an expected value. This means that for
small m the network is super-preferential;
─ with increasing the control parameter, the fraction of nodes, which degree follows
to a power law, increases (Fig. 4 - Fig. 6), and the variability of the scaling factor
decreases;
─ the dependence of scaling factor (m) is not monotonous; it reaches a maximum
under m 50 , however, this effect may be caused by the bounded networks size,
so it needs additional research;
─ the obtained empirical dependence (m) does not correspond to either the
theoretical model developed in Section 4 (according to which = 2.618 ) or the model (
Given the above, the MDA model requires a more detailed analytical study of its properties.
The problem of modeling scale-free networks is considered. The properties of generated network are strongly depends on the attachment rule. An actual models and corresponding attachment rules were analyzed.
The mediation-driven attachment rule has an undoubted advantage due to indirect using of nodes statistics, which is fully consistent with the properties of the real-world networks. The properties of networks controlled by the above rule were analyzed. These properties are mainly determined by the control parameter – number of incoming links brought by each incoming node.
The scaling properties of the network, formed according to the studied rule, were analyzed in detail, both analytically and numerically. The threshold boundaries of the scale-free segment of network were found as well as its dependence on the control parameter. The dependence of the scaling factor of the frequency distribution of the nodes degree on the control parameter for networks under mediation-driven attachment rule were obtained numerically and analyzed in detail. An estimate of the threshold boundary of the control parameter at which the network is super-preferential is obtained.
A detailed study of the properties of studied model, as well as analysis of its assortativity properties, forms the subject of interest for future research.