Reciprocity (network science)

From HandWiki

In network science, reciprocity is a measure of the likelihood of vertices in a directed network to be mutually linked.[1] Like the clustering coefficient, scale-free degree distribution, or community structure, reciprocity is a quantitative measure used to study complex networks.

Motivation

In real network problems, people are interested in determining the likelihood of occurring double links (with opposite directions) between vertex pairs. This problem is fundamental for several reasons. First, in the networks that transport information or material (such as email networks,[2] World Wide Web (WWW),[3] World Trade Web,[4] or Wikipedia[5] ), mutual links facilitate the transportation process. Second, when analyzing directed networks, people often treat them as undirected ones for simplicity; therefore, the information obtained from reciprocity studies helps to estimate the error introduced when a directed network is treated as undirected (for example, when measuring the clustering coefficient). Finally, detecting nontrivial patterns of reciprocity can reveal possible mechanisms and organizing principles that shape the observed network's topology.[1]

Definitions

Traditional definition

A traditional way to define the reciprocity [math]\displaystyle{ r }[/math] is using the ratio of the number of links pointing in both directions [math]\displaystyle{ L^{\lt -\gt } }[/math] to the total number of links L [6] [math]\displaystyle{ r = \frac {L^{\lt -\gt }}{L} }[/math]

With this definition, [math]\displaystyle{ r = 1 }[/math] is for a purely bidirectional network while [math]\displaystyle{ r = 0 }[/math] for a purely unidirectional one. Real networks have an intermediate value between 0 and 1.

However, this definition of reciprocity has some defects. It cannot tell the relative difference of reciprocity compared with purely random network with the same number of vertices and edges. The useful information from reciprocity is not the value itself, but whether mutual links occur more or less often than expected by chance. Besides, in those networks containing self-linking loops (links starting and ending at the same vertex), the self-linking loops should be excluded when calculating [math]\displaystyle{ L }[/math].

Garlaschelli and Loffredo's definition

In order to overcome the defects of the above definition, Garlaschelli and Loffredo defined reciprocity as the correlation coefficient between the entries of the adjacency matrix of a directed graph ([math]\displaystyle{ a_{ij} = 1 }[/math] if a link from [math]\displaystyle{ i }[/math] to [math]\displaystyle{ j }[/math] exists, and [math]\displaystyle{ a_{ij} = 0 }[/math] if not):

[math]\displaystyle{ \rho \equiv \frac {\sum_{i \neq j} (a_{ij} - \bar{a}) (a_{ji} - \bar{a})}{\sum_{i \neq j} (a_{ij} - \bar{a})^2} }[/math],

where the average value [math]\displaystyle{ \bar{a} \equiv \frac {\sum_{i \neq j} a_{ij}} {N(N-1)} = \frac {L} {N(N-1)} }[/math].

[math]\displaystyle{ \bar{a} }[/math] measures the ratio of observed to possible directed links (link density), and self-linking loops are now excluded from [math]\displaystyle{ L }[/math] since [math]\displaystyle{ i }[/math] is not equal to [math]\displaystyle{ j }[/math].

The definition can be written in the following simple form:

[math]\displaystyle{ \rho = \frac {r - \bar{a}} {1- \bar{a}} }[/math]

The new definition of reciprocity gives an absolute quantity which directly allows one to distinguish between reciprocal ([math]\displaystyle{ \rho \gt 0 }[/math]) and antireciprocal ([math]\displaystyle{ \rho \lt 0 }[/math]) networks, with mutual links occurring more and less often than random respectively.

If all the links occur in reciprocal pairs, [math]\displaystyle{ \rho = 1 }[/math]; if [math]\displaystyle{ r=0 }[/math], [math]\displaystyle{ \rho = \rho_{min} }[/math]. [math]\displaystyle{ \rho_{min} \equiv \frac {- \bar{a}} {1- \bar{a}} }[/math]

This is another advantage of using [math]\displaystyle{ \rho }[/math], since it incorporates the idea that complete antireciprocality is more statistically significant in networks with larger density, while it must be regarded as a less pronounced effect in sparser networks.

References

  1. 1.0 1.1 Diego Garlaschelli; Loffredo, Maria I. (December 2004). "Patterns of Link Reciprocity in Directed Networks". Physical Review Letters (American Physical Society) 93 (26): 268701. doi:10.1103/PhysRevLett.93.268701. PMID 15698035. Bibcode2004PhRvL..93z8701G. 
  2. Newman, M. E. J.; Forrest, Stephanie; Balthrop, Justin (2002-09-10). "Email networks and the spread of computer viruses". Physical Review E (American Physical Society (APS)) 66 (3): 035101(R). doi:10.1103/physreve.66.035101. ISSN 1063-651X. PMID 12366169. Bibcode2002PhRvE..66c5101N. 
  3. Albert, Réka; Jeong, Hawoong; Barabási, Albert-László (1999). "Diameter of the World-Wide Web". Nature 401 (6749): 130–131. doi:10.1038/43601. ISSN 0028-0836. 
  4. Garlaschelli, Diego; Loffredo, Maria I. (2004-10-28). "Fitness-Dependent Topological Properties of the World Trade Web". Physical Review Letters (American Physical Society (APS)) 93 (18): 188701. doi:10.1103/physrevlett.93.188701. ISSN 0031-9007. PMID 15525215. Bibcode2004PhRvL..93r8701G. 
  5. Zlatić, V.; Božičević, M.; Štefančić, H.; Domazet, M. (2006-07-24). "Wikipedias: Collaborative web-based encyclopedias as complex networks". Physical Review E 74 (1): 016115. doi:10.1103/physreve.74.016115. ISSN 1539-3755. PMID 16907159. Bibcode2006PhRvE..74a6115Z. 
  6. Newman, M. E. J.; Forrest, Stephanie; Balthrop, Justin (2002-09-10). "Email networks and the spread of computer viruses". Physical Review E (American Physical Society (APS)) 66 (3): 035101(R). doi:10.1103/physreve.66.035101. ISSN 1063-651X. PMID 12366169. Bibcode2002PhRvE..66c5101N.