---- > [!definition] Definition. ([[reciprocity]]) > The **reciprocity** of a [[network|directed network]] $G$ with the fraction of its $m$ edges that are reciprocated, $r=\frac{1}{m}\text{Tr }A^{2},$ > where $\text{Tr}$ is the [[trace of a matrix|trace]] operation and $A$ is $Gs [[adjacency matrix]]. > [!basicexample] > The reciprocity of the below network is $\frac{6}{8}$.![[CleanShot 2023-10-01 at 13.25.39.jpg]] > [!justification] > The derivation is as follows: $A_{ij}A_{ji}=1$ if and only if $i \leftrightarrow j$. Summing over all node pairs yields $\begin{align} \sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}A_{ji} = & \sum_{i=1}^{n} (AA)_{ii}= \text{Tr }A^{2}. \end{align}$ This the number of reciprocated edges; divide by $m$ to get the desired proportion. > [!note] Remark on Time Complexity. > If the [[degree|in-degrees]] and [[degree|out-degrees]] of the nodes in $G$ are [[uncorrelated]], then computing the reciprocity of $G$ can be done (naively, at least) in $O\left( \frac{m^{2}}{n} \right)$ time. > Each node $i$ in $G$ has, [[mean degree|on average]], an [[expectation|expected]] $O(\frac{m}{n})$ in- and out- neighbors. To compute reciprocity, we need to check those neighbors' neighbors to see if $i$ is one of time — requiring $O(\left( \frac{m}{n} \right)^{2})$ operations per node $i$. There are $n$ nodes in $G$, hence this is $O(n \cdot m^{2} / n^{2})=O\left( \frac{m^{2}}{n} \right).$ Note that the assumption that the nodes of $G$ are [[uncorrelated]] is important. This is because we implicitly assumed that the [[expectation is multiplicative for independent random variables]] when concluding the $O(\left( \frac{m}{n} \right)^{2})$ result, which is not true in general. Perhaps a more sophisticated approach would consider [[covariance]]s. ---- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```