In
network science
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 rep ...
, reciprocity is a measure of the likelihood of
vertices in a
directed network to be mutually linked.
Like the
clustering coefficient
In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups ...
,
scale-free degree distribution
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.
Definition
The degre ...
, or
community structure
In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into (potentially overlapping) sets of nodes such that each set of nodes is densely connected internally. In the part ...
, reciprocity is a quantitative measure used to study
complex network
In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real ...
s.
Motivation
In real network problems, people are interested in determining the
likelihood
The likelihood function (often simply called the likelihood) represents the probability of random variable realizations conditional on particular values of the statistical parameters. Thus, when evaluated on a given sample, the likelihood functi ...
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,
World Wide Web (WWW),
World Trade Web,
or Wikipedia
), 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
In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups ...
). Finally, detecting nontrivial patterns of reciprocity can reveal possible mechanisms and organizing principles that shape the observed network's topology.
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
to the total number of links L
With this definition,
is for a purely bidirectional network while
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 (
if a link from i to j is there, and
if not):
,
where the average value
.
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:
The new definition of reciprocity gives an absolute quantity which directly allows one to distinguish between reciprocal (
) and antireciprocal (
) networks, with mutual links occurring more and less often than random respectively.
If all the links occur in reciprocal pairs,
; if r=0,
.
This is another advantage of using
, 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.
References
{{Reflist
Computer networking