Mediation-driven attachment model

Last updated November 30, 2024

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 ^[1] 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

\Pi (i)={\frac {k_{i}}{\sum _{j=1}k_{j}}}

where, $\Pi (i)$ is the probability that the new node picks a 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.^[2] 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 $\Pi (i)$ that an already existing node $i$ is finally picked to connect it with the new node? Say, the node $i$ has degree $k_{i}$ and hence it has $k_{i}$ neighbors. Consider that the neighbors of $i$ are labeled $1,2,\ldots ,k_{i}$ which have degrees $k_{1},k_{2},\ldots ,k_{k_{i}}$ respectively. One can reach the 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 $\Pi (i)$ of the MDA model is:

\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}}.

It can be re-written as

\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 the node $i$ . Extensive numerical simulation suggest that for small $m$ 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 $m$ (specially $m$ 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 $m$ limit. In this limit one finds that $\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 $\Pi (i)$ 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.^[3]^[4]

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 MDA rule is also scale-free in nature. The only difference is that the exponent $\gamma ={{1} \over {\beta (m)}}+1$ depends on $m$ where as in the BA model $\gamma =3$ independent 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 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.^[5] 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 aleader 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 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.^[6] Another model proposed by Boccaletti et al. may appear similar to ours, but it markedly differs on closer look.^[7] Recently, Yang {\it et al.} too gave a form for $\Pi (i)$ and resorted to mean-field approximation.^[8] 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$ .^[9] 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.

Related Research Articles

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as

In statistics, Gibbs sampling or a Gibbs sampler is a Markov chain Monte Carlo (MCMC) algorithm for sampling from a specified multivariate probability distribution when direct sampling from the joint distribution is difficult, but sampling from the conditional distribution is more practical. This sequence can be used to approximate the joint distribution ; to approximate the marginal distribution of one of the variables, or some subset of the variables ; or to compute an integral. Typically, some of the variables correspond to observations whose values are known, and hence do not need to be sampled.

In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.

The Barabási–Albert (BA) model is an algorithm for generating random scale-free networks using a preferential attachment mechanism. Several natural and human-made systems, including the Internet, the World Wide Web, citation networks, and some social networks are thought to be approximately scale-free and certainly contain few nodes with unusually high degree as compared to the other nodes of the network. The BA model tries to explain the existence of such nodes in real networks. The algorithm is named for its inventors Albert-László Barabási and Réka Albert.

The Watts–Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their article published in 1998 in the Nature scientific journal. The model also became known as the (Watts) beta model after Watts used $to formulate it in his popular science book Six Degrees .$

In complex network theory, the fitness model is a model of the evolution of a network: how the links between nodes change over time depends on the fitness of nodes. Fitter nodes attract more links at the expense of less fit nodes.

Assortativity, or assortative mixing, is a preference for a network's nodes to attach to others that are similar in some way. Though the specific measure of similarity may vary, network theorists often examine assortativity in terms of a node's degree. The addition of this characteristic to network models more closely approximates the behaviors of many real world networks.

In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing N nodes in some metric space and connecting two nodes by a link if and only if their distance is in a given range, e.g. smaller than a certain neighborhood radius, r.

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

Evolving networks are networks that change as a function of time. They are a natural extension of network science since almost all real world networks evolve over time, either by adding or removing nodes or links over time. Often all of these processes occur simultaneously, such as in social networks where people make and lose friends over time, thereby creating and destroying edges, and some people become part of new social networks or leave their networks, changing the nodes in the network. Evolving network concepts build on established network theory and are now being introduced into studying networks in many diverse fields.

Evolving networks are dynamic networks that change through time. In each period $there are new nodes and edges that join the network while the old ones disappear. Such dynamic behaviour is characteristic for most real-world networks, regardless of their range - global or local. However, networks differ not only in their range but also in their topological structure. It is possible to distinguish:$

Price's model is a mathematical model for the growth of citation networks. It was the first model which generalized the Simon model to be used for networks, especially for growing networks. Price's model belongs to the broader class of network growing models whose primary target is to explain the origination of networks with strongly skewed degree distributions. The model picked up the ideas of the Simon model reflecting the concept of rich get richer, also known as the Matthew effect. Price took the example of a network of citations between scientific papers and expressed its properties. His idea was that the way an old vertex gets new edges should be proportional to the number of existing edges the vertex already has. This was referred to as cumulative advantage, now also known as preferential attachment. Price's work is also significant in providing the first known example of a scale-free network. His ideas were used to describe many real-world networks such as the Web.

A hyperbolic geometric graph (HGG) or hyperbolic geometric network (HGN) is a special type of spatial network where (1) latent coordinates of nodes are sprinkled according to a probability density function into a hyperbolic space of constant negative curvature and (2) an edge between two nodes is present if they are close according to a function of the metric (typically either a Heaviside step function resulting in deterministic connections between vertices closer than a certain threshold distance, or a decaying function of hyperbolic distance yielding the connection probability). A HGG generalizes a random geometric graph (RGG) whose embedding space is Euclidean.

In network science, preferential attachment means that nodes of a network tend to connect to those nodes which have more links. If the network is growing and new nodes tend to connect to existing ones with linear probability in the degree of the existing nodes then preferential attachment leads to a scale-free network. If this probability is sub-linear then the network’s degree distribution is stretched exponential and hubs are much smaller than in a scale-free network. If this probability is super-linear then almost all nodes are connected to a few hubs. According to Kunegis, Blattner, and Moser several online networks follow a non-linear preferential attachment model. Communication networks and online contact networks are sub-linear while interaction networks are super-linear. The co-author network among scientists also shows the signs of sub-linear preferential attachment.

<span class="mw-page-title-main">Bianconi–Barabási model</span>

The Bianconi–Barabási model is a model in network science that explains the growth of complex evolving networks. This model can explain that nodes with different characteristics acquire links at different rates. It predicts that a node's growth depends on its fitness and can calculate the degree distribution. The Bianconi–Barabási model is named after its inventors Ginestra Bianconi and Albert-László Barabási. This model is a variant of the Barabási–Albert model. The model can be mapped to a Bose gas and this mapping can predict a topological phase transition between a "rich-get-richer" phase and a "winner-takes-all" phase.

In network science, a hub is a node with a number of links that greatly exceeds the average. Emergence of hubs is a consequence of a scale-free property of networks. While hubs cannot be observed in a random network, they are expected to emerge in scale-free networks. The uprise of hubs in scale-free networks is associated with power-law distribution. Hubs have a significant impact on the network topology. Hubs can be found in many real networks, such as the brain or the Internet.

In a scale-free network the degree distribution follows a power law function. In some empirical examples this power-law fits the degree distribution well only in the high degree region; in some small degree nodes the empirical degree-distribution deviates from it. See for example the network of scientific citations. This deviation of the observed degree-distribution from the theoretical prediction at the low-degree region is often referred as low-degree saturation. The empirical degree-distribution typically deviates downward from the power-law function fitted on higher order nodes, which means low-degree nodes are less frequent in real data than what is predicted by the Barabási–Albert model.

The initial attractiveness is a possible extension of the Barabási–Albert model. The Barabási–Albert model generates scale-free networks where the degree distribution can be described by a pure power law. However, the degree distribution of most real life networks cannot be described by a power law solely. The most common discrepancies regarding the degree distribution found in real networks are the high degree cut-off and the low degree saturation. The inclusion of initial attractiveness in the Barabási–Albert model addresses the low-degree saturation phenomenon.

Physicists often use various lattices to apply their favorite models in them. For instance, the most favorite lattice is perhaps the square lattice. There are 14 Bravais space lattice where every cell has exactly the same number of nearest, next nearest, nearest of next nearest etc. neighbors and hence they are called regular lattice. Often physicists and mathematicians study phenomena which require disordered lattice where each cell do not have exactly the same number of neighbors rather the number of neighbors can vary wildly. For instance, if one wants to study the spread of disease, viruses, rumors etc. then the last thing one would look for is the square lattice. In such cases a disordered lattice is necessary. One way of constructing a disordered lattice is by doing the following.

In network science, the configuration model is a method for generating random networks from a given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the modeler to incorporate arbitrary degree distributions.

References

↑ Barabási, Albert-László; Albert, Réka (1999-10-15). "Emergence of Scaling in Random Networks". Science. 286 (5439): 509–512. arXiv: cond-mat/9910332 . Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. ISSN 0036-8075. PMID 10521342. S2CID 524106.
↑ Hassan, Md. Kamrul; Islam, Liana; Haque, Syed Arefinul (2017). "Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks". Physica A: Statistical Mechanics and Its Applications. 469. Elsevier BV: 23–30. arXiv: 1411.3444 . Bibcode:2017PhyA..469...23H. doi:10.1016/j.physa.2016.11.001. ISSN 0378-4371. S2CID 51976352.
↑ Hassan, M K; Hassan, M Z; Pavel, N I (2010-09-27). "Scale-free network topology and multifractality in a weighted planar stochastic lattice". New Journal of Physics. 12 (9): 093045. arXiv: 1008.4994 . Bibcode:2010NJPh...12i3045H. doi: 10.1088/1367-2630/12/9/093045 . ISSN 1367-2630.
↑ Hassan, M K; Hassan, M Z; Pavel, N I (2011-05-01). "Scale-free coordination number disorder and multifractal size disorder in weighted planar stochastic lattice". Journal of Physics: Conference Series. 297 (1). IOP Publishing: 012010. arXiv: 1104.1831 . Bibcode:2011JPhCS.297a2010H. doi:10.1088/1742-6596/297/1/012010. ISSN 1742-6596. S2CID 119262569.
↑ Pastor-Satorras, Romualdo; Vespignani, Alessandro (2001-04-02). "Epidemic Spreading in Scale-Free Networks". Physical Review Letters. 86 (14): 3200–3203. arXiv: cond-mat/0010317 . Bibcode:2001PhRvL..86.3200P. doi:10.1103/physrevlett.86.3200. hdl: 2117/126209 . ISSN 0031-9007. PMID 11290142. S2CID 16298768.
↑ Saramäki, Jari; Kaski, Kimmo (2004). "Scale-free networks generated by random walkers". Physica A: Statistical Mechanics and Its Applications. 341: 80–86. arXiv: cond-mat/0404088 . Bibcode:2004PhyA..341...80S. doi:10.1016/j.physa.2004.04.110. ISSN 0378-4371. S2CID 119023363.
↑ Boccaletti, S.; Hwang, D.-U.; Latora, V. (2007). "Growing Hierarchical Scale-Free Networks by Means of Nonhierarchical processes". International Journal of Bifurcation and Chaos. 17 (7). World Scientific Pub Co Pte Lt: 2447–2452. Bibcode:2007IJBC...17.2447B. doi:10.1142/s0218127407018518. ISSN 0218-1274.
↑ Yang, Xu-Hua; Lou, Shun-Li; Chen, Guang; Chen, Sheng-Yong; Huang, Wei (2013). "Scale-free networks via attaching to random neighbors". Physica A: Statistical Mechanics and Its Applications. 392 (17). Elsevier BV: 3531–3536. Bibcode:2013PhyA..392.3531Y. doi:10.1016/j.physa.2013.03.043. ISSN 0378-4371.
↑ Krapivsky, P. L.; Redner, S. (2001-05-24). "Organization of growing random networks". Physical Review E. 63 (6). American Physical Society (APS): 066123. arXiv: cond-mat/0011094 . Bibcode:2001PhRvE..63f6123K. doi:10.1103/physreve.63.066123. ISSN 1063-651X. PMID 11415189. S2CID 16077521.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Barabási, Albert-László; Albert, Réka (1999-10-15). "Emergence of Scaling in Random Networks". Science. 286 (5439): 509–512. arXiv: cond-mat/9910332 . Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. ISSN 0036-8075. PMID 10521342. S2CID 524106.

[2] Hassan, Md. Kamrul; Islam, Liana; Haque, Syed Arefinul (2017). "Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks". Physica A: Statistical Mechanics and Its Applications. 469. Elsevier BV: 23–30. arXiv: 1411.3444 . Bibcode:2017PhyA..469...23H. doi:10.1016/j.physa.2016.11.001. ISSN 0378-4371. S2CID 51976352.

[3] Hassan, M K; Hassan, M Z; Pavel, N I (2010-09-27). "Scale-free network topology and multifractality in a weighted planar stochastic lattice". New Journal of Physics. 12 (9): 093045. arXiv: 1008.4994 . Bibcode:2010NJPh...12i3045H. doi: 10.1088/1367-2630/12/9/093045 . ISSN 1367-2630.

[4] Hassan, M K; Hassan, M Z; Pavel, N I (2011-05-01). "Scale-free coordination number disorder and multifractal size disorder in weighted planar stochastic lattice". Journal of Physics: Conference Series. 297 (1). IOP Publishing: 012010. arXiv: 1104.1831 . Bibcode:2011JPhCS.297a2010H. doi:10.1088/1742-6596/297/1/012010. ISSN 1742-6596. S2CID 119262569.

[5] Pastor-Satorras, Romualdo; Vespignani, Alessandro (2001-04-02). "Epidemic Spreading in Scale-Free Networks". Physical Review Letters. 86 (14): 3200–3203. arXiv: cond-mat/0010317 . Bibcode:2001PhRvL..86.3200P. doi:10.1103/physrevlett.86.3200. hdl: 2117/126209 . ISSN 0031-9007. PMID 11290142. S2CID 16298768.

[6] Saramäki, Jari; Kaski, Kimmo (2004). "Scale-free networks generated by random walkers". Physica A: Statistical Mechanics and Its Applications. 341: 80–86. arXiv: cond-mat/0404088 . Bibcode:2004PhyA..341...80S. doi:10.1016/j.physa.2004.04.110. ISSN 0378-4371. S2CID 119023363.

[7] Boccaletti, S.; Hwang, D.-U.; Latora, V. (2007). "Growing Hierarchical Scale-Free Networks by Means of Nonhierarchical processes". International Journal of Bifurcation and Chaos. 17 (7). World Scientific Pub Co Pte Lt: 2447–2452. Bibcode:2007IJBC...17.2447B. doi:10.1142/s0218127407018518. ISSN 0218-1274.

[8] Yang, Xu-Hua; Lou, Shun-Li; Chen, Guang; Chen, Sheng-Yong; Huang, Wei (2013). "Scale-free networks via attaching to random neighbors". Physica A: Statistical Mechanics and Its Applications. 392 (17). Elsevier BV: 3531–3536. Bibcode:2013PhyA..392.3531Y. doi:10.1016/j.physa.2013.03.043. ISSN 0378-4371.

[9] Krapivsky, P. L.; Redner, S. (2001-05-24). "Organization of growing random networks". Physical Review E. 63 (6). American Physical Society (APS): 066123. arXiv: cond-mat/0011094 . Bibcode:2001PhRvE..63f6123K. doi:10.1103/physreve.63.066123. ISSN 1063-651X. PMID 11415189. S2CID 16077521.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]