Link-centric preferential attachment

In mathematical modeling of social networks, link-centric preferential attachment[1][2] is a node's propensity to re-establish links to nodes it has previously been in contact with in time-varying networks.[3] This preferential attachment model relies on nodes keeping memory of previous neighbors up to the current time.[1][4]

Background

In real social networks individuals exhibit a tendency to re-connect with past contacts (ex. family, friends, co-workers, etc.) rather than strangers. In 1970, Mark Granovetter examined this behaviour in the social networks of a group of workers and identified tie strength, a characteristic of social ties describing the frequency of contact between two individuals. From this comes the idea of strong and weak ties,[5] where an individual's strong ties are those she has come into frequent contact with. Link-centric preferential attachment aims to explain the mechanism behind strong and weak ties as a stochastic reinforcement process for old ties in agent-based modeling where nodes have long-term memory.

Examples

In a simple model for this mechanism, a node's propensity to establish a new link can be characterized solely by ${\displaystyle n}$, the number of contacts it has had in the past. The probability for a node with n social ties to establish a new social tie could then be simply given by[4]

${\displaystyle P(n)={c \over n+c}\,}$

where c is an offset constant. The probability for a node to re-connect with old ties is then

${\displaystyle 1-P(n)={n \over n+c}.}$

Figure 1. shows an example of this process: in the first step nodes A and C connect to node B, giving B a total of two social ties. With c = 1, in the next step B has a probability P(2) = 1/(2 + 1) = 1/3 to create a new tie with D, whereas the probability to reconnect with A or C is twice that at 2/3.

More complex models may take into account other variables, such as frequency of contact, contact and intercontact duration, as well as short term memory effects.[1]

Effects on the spreading of contagions / weakness of strong ties

Understanding the evolution of a network's structure and how it can influence dynamical processes has become an important part of modeling the spreading of contagions.[6][7] In models of social and biological contagion spreading on time-varying networks link-centric preferential attachment can alter the spread of the contagion to the entire population. Compared to the classic rumour spreading process where nodes are memory-less, link-centric preferential attachment can cause not only a slower spread of the contagion but also one less diffuse. In these models an infected node's chances of connecting to new contacts diminishes as their size of their social circle ${\displaystyle n}$ grows leading to a limiting effect on the growth of n. The result is strong ties with a node's early contacts and consequently the weakening of the diffusion of the contagion.[1][4]

See also

• BA model
• Network science
• Interpersonal tie

References

1. Vestergaard, Christian L.; Genois, Mathieu; Barrat, Alain (October 9, 2014). "How memory generates hetergeneous dynamics in temporal networks". Physical Review E. 90 (4): 042805. arXiv:1409.1805. Bibcode:2014PhRvE..90d2805V. doi:10.1103/PhysRevE.90.042805. PMID 25375547.
2. Barabasi, Albert-Laszlo; Albert, Reka (October 15, 1999). "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. PMID 10521342.
3. Perra, Nicola; Goncalves, Bruno; Pastor-Satorras, Romualdo; Vespignani, Alessandro (June 25, 2012). "Activity driven modeling of time-varying networks". Scientific Reports. 2: 469. arXiv:1203.5351. Bibcode:2012NatSR...2E.469P. doi:10.1038/srep00469. PMC 3384079. PMID 22741058.
4. Karsai, Marton (February 10, 2014). "Time-varying networks and the weakness of strong ties". Scientific Reports. 4: 4001. arXiv:1303.5966. Bibcode:2014NatSR...4E4001K. doi:10.1038/srep04001. PMC 3918922. PMID 24510159. Retrieved 11 November 2014.
5. Granovetter, Mark (1973). "The strength of weak ties". American Journal of Sociology. 78 (6): 1360–1380. doi:10.1086/225469.
6. Newman, M. E. J. (July 26, 2002). "Spread of epidemic disease on networks". Physical Review E. 66 (16128): 016128. arXiv:cond-mat/0205009. Bibcode:2002PhRvE..66a6128N. doi:10.1103/PhysRevE.66.016128.
7. Kamp, Christel; Moslonka-Lefebvre, Mathieu; Alizon, Samuel (December 13, 2013). "Epidemic Spread on Weighted Networks". PLOS Computational Biology. 9 (1371): e1003352. Bibcode:2013PLSCB...9E3352K. doi:10.1371/journal.pcbi.1003352.