Reciprocity (network science)

Network science

Theory · History
Graph · Complex network · Contagion Small-world · Scale-free · Community structure · Percolation · Evolution · Controllability · Topology · Graph drawing · Social capital · Link analysis · Optimization Reciprocity · Closure · Homophily Transitivity · Preferential attachment Balance · Network effect · Influence
Types of Networks
Information · Telecommunication Social · Biological · Neural · Semantic Random · Dependency · Flow
Graphs
Vertex · Edge · Component Directed · Multigraph · Bipartite Weighted · Hypergraph · Random Cycle · Loop · Path Neighborhood · Clique · Complete · Cut Data structure · Adjacency list & matrix Incidence list & matrix
Metrics and Algorithms
Centrality · Degree · Betweenness Closeness · PageRank · Motif Clustering · Degree distribution · Assortativity · Distance · Modularity
Models
Random · Erdős–Rényi Barabási–Albert · Watts–Strogatz ERGM · Epidemic · Hierarchical
Browse
Topics · Software · Network scientists Graph theory · Network theory

Theoretical efforts have been made to study the nontrivial properties of complex networks, such as clustering, scale-free degree distribution, community structures, etc. Here Reciprocity is another quantity to specifically characterize directed networks. Link reciprocity measures the tendency of vertex pairs to form mutual connections between each other.^[1]

1 Why we need to introduce it?
2 How is it defined?
- 2.1 Traditional definition
- 2.2 Garlaschelli and Loffredo's definition
3 Reciprocity for various types of networks
4 References

Why we need to introduce it?

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] ), the 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 tells us how much is deviated from the truth when a directed network is treated as undirected (for example, when measuring the cluster coefficient). Finally, detecting nontrivial patterns of reciprocity can reveal possible mechanisms and organizing principles that shape the observed network topology.^[1]

How is it defined?

Traditional definition

A traditional way to define the reciprocity r is using the ratio of the number of links pointing in both directions $L^{<->}$ to the total number of links L ^[6] $r = \frac {L^{<->}}{L}$

With this definition, $r = 1$ is for a purely bidirectional network while $r = 0$ 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 L.

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 ( $a_{ij} = 1$ if a link from i to j is there, and $a_{ij} = 0$ if not):

$\rho \equiv \frac {\sum_{i \neq j} (a_{ij} - \bar{a}) (a_{ji} - \bar{a})}{\sum_{i \neq j} (a_{ij} - \bar{a})^2}$ ,

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

$\bar{a}$ measures the ratio of observed to possible directed links (link density), and self-linking loops are now excluded from L because of i not equal to j.

The definition can be written in the following simple form:

$\rho = \frac {r - \bar{a}} {1- \bar{a}}$

The new definition of reciprocity gives an absolute quantity which directly allows one to distinguish between reciprocal ( $\rho > 0$ ) and antireciprocal ( $\rho < 0$ ) networks, with mutual links occurring more and less often than random respectively.

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

This is another advantage of using $\rho$ , because it incorporates the idea that complete antireciprocal is more statistical significant in the networks with larger density, while it has to be regarded as a less pronounced effect in sparser networks.

Reciprocity for various types of networks

The following table shows the calculated values of reciprocity for various types of networks, from the result we can see that networks of same type displays similar value of reciprocity.^[7] Fig. 1 shows the reciprocity for three kinds of networks. In different types of networks, $\rho$ has different relations with $r$ and $\bar{a}$ .

. .

References

^ ^a ^b Diego Garlaschelli, and Maria I. Loffredo. Patterns of Link Reciprocity in Directed Networks. Phys. Rev. Lett. 93, 268701 (2004).
^ M. E. J. Newman, S. Forrest, and J. Balthrop, Phys. Rev. E 66, 035101(R) (2002).
^ R. Albert, H. Jeong, and A.-L. Baraba´si, Nature (London) 401, 130 (1999).
^ D. Garlaschelli and M. I. Loffredo, Phys. Rev. Lett. 93, 188701 (2004).
^ V. Zlatic, M. Bozicevic, H. Stefancic, and M. Domazet, Phys. Rev. E 74, 016115 (2006)
^ M. E. J. Newman, S. Forrest, and J. Balthrop, Phys. Rev. E 66, 035101(R) (2002).
^ Diego Garlaschelli, and Maria I. Loffredo. Patterns of Link Reciprocity in Directed Networks. Phys. Rev. Lett. 93, 268701 (2004)