Link-centric preferential attachment explained

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

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]

P(n)={c\overn+c}

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

1-P(n)={n\overn+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

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

Notes and References

  1. Vestergaard. Christian L.. Genois. Mathieu. Barrat. Alain. How memory generates hetergeneous dynamics in temporal networks. Physical Review E. October 9, 2014. 10.1103/PhysRevE.90.042805. 25375547. 90. 4. 042805. 1409.1805. 2014PhRvE..90d2805V. 16022001.
  2. Barabasi. Albert-Laszlo. Albert. Reka. Emergence of Scaling in Random Networks. Science. October 15, 1999. 286. 5439. 509–512. 10.1126/science.286.5439.509. 10521342. cond-mat/9910332. 1999Sci...286..509B. 524106.
  3. Perra. Nicola. Goncalves. Bruno. Pastor-Satorras. Romualdo. Vespignani. Alessandro. Activity driven modeling of time-varying networks. Scientific Reports. June 25, 2012. 2. 469. 10.1038/srep00469. 22741058. 3384079. 1203.5351. 2012NatSR...2E.469P.
  4. Karsai. Marton. Time-varying networks and the weakness of strong ties. Scientific Reports. February 10, 2014. 4. 4001. 10.1038/srep04001. 24510159. 3918922. 1303.5966. 2014NatSR...4E4001K.
  5. Granovetter. Mark. The strength of weak ties. American Journal of Sociology. 1973. 78. 6. 1360–1380. 10.1086/225469. 59578641.
  6. Newman. M. E. J.. Spread of epidemic disease on networks. Physical Review E. July 26, 2002. 66. 16128. 016128. 10.1103/PhysRevE.66.016128. 12241447. cond-mat/0205009. 2002PhRvE..66a6128N. 15291065.
  7. Kamp. Christel. Moslonka-Lefebvre. Mathieu. Alizon. Samuel. Epidemic Spread on Weighted Networks. PLOS Computational Biology. December 13, 2013. 1371. 10.1371/journal.pcbi.1003352. 9. e1003352. 24348225. 3861041. 2013PLSCB...9E3352K. free.