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 MDA rule, a new node first picks a node from the existing network at random and connect itself not with that but with one of the neighbors also picked at random. Barabasi and Albert in 1999 noted through their seminal paper noted 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 one randomly rather preferentially with respect to their degrees. The later 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

[math]\displaystyle{ \Pi(i) = \frac{k_i}{\sum_{j=1} k_j} }[/math]

where, [math]\displaystyle{ \Pi(i) }[/math] is the probability that the new node picks a node [math]\displaystyle{ i }[/math] 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 choose an existing node to connect by first picking one of the existing nodes at random which is regarded as mediator. The new node then connect with one of the neighbors of the mediator which is also picked at random. Now the question is: What is the probability [math]\displaystyle{ \Pi(i) }[/math] that an already existing node [math]\displaystyle{ i }[/math] is finally picked to connect it with the new node? Say, the node [math]\displaystyle{ i }[/math] has degree [math]\displaystyle{ k_i }[/math] and hence it has [math]\displaystyle{ k_i }[/math] neighbors. Consider that the neighbors of [math]\displaystyle{ i }[/math] are labeled [math]\displaystyle{ 1,2,\ldots ,k_i }[/math] which have degrees [math]\displaystyle{ k_1,k_2,\ldots,k_{k_i} }[/math] respectively. One can reach the node [math]\displaystyle{ i }[/math] from each of these [math]\displaystyle{ k_i }[/math] nodes with probabilities inverse of their respective degrees, and each of the [math]\displaystyle{ k_i }[/math] nodes are likely to be picked at random with probability [math]\displaystyle{ 1/N }[/math]. Thus the probability [math]\displaystyle{ \Pi(i) }[/math] of the MDA model is:

[math]\displaystyle{ \Pi(i)= \frac 1 N \left[ \frac 1 {k_1}+ \frac 1 {k_2} + \cdots + \frac 1 {k_{k_i}} \right] =\frac{\sum_{j=1}^{k_i} \frac 1 {k_j}} N. }[/math]

It can be re-written as

[math]\displaystyle{ \Pi(i) = \frac{k_i}N \cdot \frac{\sum_{j=1}^{k_i} \frac 1 {k_j}}{k_i}, }[/math]

where the factor [math]\displaystyle{ \frac{\sum_{j=1}^{k_i}{\frac{1}{k_j}}}{k_i} }[/math] is the inverse of the harmonic mean (IHM) of degrees of the [math]\displaystyle{ k_i }[/math] neighbors of the node [math]\displaystyle{ i }[/math]. Extensive numerical simulation suggest that for small [math]\displaystyle{ m }[/math] the IHM value of each node fluctuate so wildly that the mean of the IHM values over the entire network bears no meaning. However, for large [math]\displaystyle{ m }[/math] (specially [math]\displaystyle{ m }[/math] approximately greater than 14) the distribution of IHM value of the entire network become left skewed Gaussian type and mean starts to have a meaning which becomes a constant value in the large [math]\displaystyle{ m }[/math] limit. In this limit one finds that [math]\displaystyle{ \Pi(i)\propto k_i }[/math] 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 [math]\displaystyle{ m }[/math] the MFA is no longer valid rather the attachment probability [math]\displaystyle{ \Pi(i) }[/math] becomes super-preferential in character.

The idea of 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 gain links only if one of its neighbor 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 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 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 [math]\displaystyle{ N }[/math] implies that one can apply the mean-field approximation (MFA). That is, within this approximation one can replace the true IHM value [math]\displaystyle{ \beta/m }[/math] of each node by their mean, where the factor [math]\displaystyle{ m }[/math] 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 MDA rule is also scale-free in nature. The only difference is that the exponent [math]\displaystyle{ \gamma={{1}\over{\beta(m)}}+1 }[/math] depends on [math]\displaystyle{ m }[/math] where as in the BA model [math]\displaystyle{ \gamma=3 }[/math] independent of [math]\displaystyle{ m }[/math].

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 [math]\displaystyle{ k }[/math]. Nodes which are linked to an unusually large number of other nodes, i.e. nodes with exceptionally high [math]\displaystyle{ k }[/math] value, are known as hubs. They are special because their existence make the mean distance, measured in units of the number of links, between nodes incredibly small thereby playing the 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 [math]\displaystyle{ F(\tau) }[/math] that aleader retains its leadership for at least up to time [math]\displaystyle{ \tau }[/math]. 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 {\it et al.} too gave a form for [math]\displaystyle{ \Pi(i) }[/math] 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 [math]\displaystyle{ 1-r }[/math], or to the parent of the target with probability [math]\displaystyle{ r=1 }[/math]. The GNR model with [math]\displaystyle{ r=1 }[/math] 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 [math]\displaystyle{ m }[/math] edges and in the GNR model it is considered [math]\displaystyle{ m=1 }[/math] case only.