Mediation-driven attachment model

In the scale-free network theory (mathematical theory of networks or graph theory), a mediation-driven attachment (MDA) model appears to embody a preferential attachment rule tacitly rather than explicitly. According to the MDA rule, a new node first picks a node from the existing network at random and connects itself not with that node but with one of its neighbors, also picked at random.

Barabasi and Albert in 1999 noted, through their seminal paper that (i) most natural and man-made networks are not static, rather they grow with time and (ii) new nodes do not connect with an already connected node randomly, rather preferentially with respect to their degrees. The latter mechanism is called preferential attachment (PA) rule, which embodies the rich get richer phenomena in economics. In their first model, known as the Barabási–Albert model, Barabási and Albert (BA model) choose

$\mathrm{\Pi }(i)=\frac{k_i}{\sum _{j=1}{k}_j}$

where, $\mathrm{\Pi }(i)$ is the probability that the new node picks node $i$ from the labelled nodes of the existing network. It directly embodies the rich get richer mechanism.

Recently, Hassan et al. proposed a mediation-driven attachment model which appears to embody the PA rule, but not directly, rather in disguise. In the MDA model, an incoming node chooses an existing node to connect by first picking one of the existing nodes at random, which is regarded as a mediator. The new node then connects with one of the neighbors of the mediator, which is also picked at random. Now the question is: What is the probability $\mathrm{\Pi }(i)$ that an already existing node $i$ is finally picked to connect it with the new node? Say, node $i$ has degree $k_i$ and hence it has $k_i$ neighbors. Consider that the neighbors of $i$ are labeled $1,2,\dots ,k_i$ which have degrees $k_1,k_2,\dots ,k_{k_i}$ respectively. One can reach node $i$ from each of these $k_i$ nodes with probabilities inverse of their respective degrees, and each of the $k_i$ nodes are likely to be picked at random with probability $1/N$. Thus the probability $\mathrm{\Pi }(i)$ of the MDA model is:

$\mathrm{\Pi }(i)=\frac{1}{N}[\frac{1}{k_1}+\frac{1}{k_2}+\cdots +\frac{1}{k_{k_i}}]=\frac{\sum _{j=1}^{k_i}\frac{1}{k_j}}{N}.$

It can be rewritten as

$\mathrm{\Pi }(i)=\frac{k_i}{N}\cdot \frac{\sum _{j=1}^{k_i}\frac{1}{k_j}}{k_i},$

where the factor $\frac{\sum _{j=1}^{k_i}\frac{1}{k_j}}{k_i}$ is the inverse of the harmonic mean (IHM) of degrees of the $k_i$ neighbors of node $i$. Extensive numerical simulation suggests that for small $m$ the IHM value of each node fluctuates so wildly that the mean of the IHM values over the entire network bears no meaning. However, for large $m$ (specially $m$ approximately greater than 14) the distribution of IHM value of the entire network becomes left skewed Gaussian type and the mean starts to have a meaning, which becomes a constant value in the large $m$ limit. In this limit one finds that $\mathrm{\Pi }(i)\propto k_i$ which is exactly the PA rule. It implies that the higher the links (degree) a node has, the higher its chance of gaining more links since they can be reached in a larger number of ways through mediators, which essentially embodies the intuitive idea of rich get richer mechanism. Therefore, the MDA network can be seen to follow the PA rule but in disguise. Moreover, for small $m$ the MFA is no longer valid, rather the attachment probability $\mathrm{\Pi }(i)$ becomes super-preferential in character.

The idea of the MDA rule can be found in the growth process of the weighted planar stochastic lattice (WPSL). An existing node (the center of each block of the WPSL is regarded as nodes and the common border between blocks as the links between the corresponding nodes) during the process gains links only if one of its neighbors is picked, not itself. It implies that the higher the links (or degree) a node has, the higher its chance of gaining more links since they can be reached in a larger number of ways. It essentially embodies the intuitive idea of the PA rule. Therefore, the dual of the WPSL is a network which can be seen to follow preferential attachment rule but in disguise. Indeed, its degree distribution is found to exhibit a power-law as underlined by Barabasi and Albert as one of the essential ingredients.

Mediation-driven attachment network of size 256 nodes

Degree distribution: The two factors that the mean of the IHM is meaningful and it is independent of $N$ implies that one can apply the mean-field approximation (MFA). That is, within this approximation one can replace the true IHM value $\beta /m$ of each node by their mean, where the factor $m$ that the number of edges the new nodes come with is introduced for latter convenience. The rate equation to solve then becomes exactly like that of the BA model and hence the network that emerges following the MDA rule is also scale-free in nature. The only difference is that the exponent $\gamma =\frac{1}{\beta (m)}+1$ depends on $m$ whereas in the BA model $\gamma =3$ independent of $m$.

Plots of degree distribution for the MDA model. The distinct plots are for incoming nodes coming edges m = 1, m = 15 and m = 100. In the inset we show the variation in the exponent of the degree distribution as a function of m.

Leadership persistence probability

In the growing network not all nodes are equally important. The extent of their importance is measured by the value of their degree $k$. Nodes which are linked to an unusually large number of other nodes, i.e. nodes with exceptionally high $k$ value, are known as hubs. They are special because their existence makes the mean distance, measured in units of the number of links, between nodes incredibly small, thereby playing a key role in spreading rumors, opinions, diseases, computer viruses etc. It is, therefore, important to know the properties of the largest hub, which we regard as the leader. Like in society, the leadership in a growing network is not permanent. That is, once a node becomes the leader, it does not mean that it remains the leader ad infinitum. An interesting question is: how long does the leader retain this leadership property as the network evolves? To find an answer to this question, we define the leadership persistence probability $F(\tau )$ that a leader retains its leadership for at least up to time $\tau$. Persistence probability has been of interest in many different systems ranging from coarsening dynamics to fluctuating interfaces or polymer chains.

The two plots at the top reveal the power-law behavior of the leadership persistence probability. To appreciate the role of m we give leadership persistence probability for two values (m=1 and m=100) in the same plot: (a) BA networks and (b) MDA networks. The two plots at the bottom are for the persistence exponent as a function of m in (c) BA networks and (d) MDA networks.

The basic idea of the MDA rule is, however, not completely new as either this or models similar to this can be found in a few earlier works, albeit their approach, ensuing analysis and their results are different from ours. For instance, Saramaki and Kaski presented a random-walk based model. Another model proposed by Boccaletti et al. may appear similar to ours, but it markedly differs on closer look. Recently, Yang et al. too gave a form for $\mathrm{\Pi }(i)$ and resorted to mean-field approximation. However, the nature of their expressions are significantly different from the one studied by Hassan et al.. Yet another closely related model is the Growing Network with Redirection (GNR) model presented by Gabel, Krapivsky and Redner where at each time step a new node either attaches to a randomly chosen target node with probability $1-r$, or to the parent of the target with probability $r=1$. The GNR model with $r=1$ may appear similar to the MDA model. However, unlike the GNR model, the MDA model is for undirected networks, and that the new link can connect with any neighbor of the mediator-parent or not. One more difference is that, in the MDA model new node may join the existing network with $m$ edges and in the GNR model it is considered $m=1$ case only.

References

This article "Mediation-driven attachment model" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Mediation-driven attachment model. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Pósa theorem
• EasyGraph
• Bose–Einstein condensation (network theory)
• Kirchhoff graph
• Distinctiveness centrality
• Cut-insertion theorem
• Unified Geometric Number Theory

---