Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Algorithms to calculate reciprocity in a directed graph."""
3import networkx as nx
4from networkx import NetworkXError
6from ..utils import not_implemented_for
8__all__ = ["reciprocity", "overall_reciprocity"]
11@not_implemented_for("undirected", "multigraph")
12@nx._dispatchable
13def reciprocity(G, nodes=None):
14 r"""Compute the reciprocity in a directed graph.
16 The reciprocity of a directed graph is defined as the ratio
17 of the number of edges pointing in both directions to the total
18 number of edges in the graph.
19 Formally, $r = |{(u,v) \in G|(v,u) \in G}| / |{(u,v) \in G}|$.
21 The reciprocity of a single node u is defined similarly,
22 it is the ratio of the number of edges in both directions to
23 the total number of edges attached to node u.
25 Parameters
26 ----------
27 G : graph
28 A networkx directed graph
29 nodes : container of nodes, optional (default=whole graph)
30 Compute reciprocity for nodes in this container.
32 Returns
33 -------
34 out : dictionary
35 Reciprocity keyed by node label.
37 Notes
38 -----
39 The reciprocity is not defined for isolated nodes.
40 In such cases this function will return None.
42 """
43 # If `nodes` is not specified, calculate the reciprocity of the graph.
44 if nodes is None:
45 return overall_reciprocity(G)
47 # If `nodes` represents a single node in the graph, return only its
48 # reciprocity.
49 if nodes in G:
50 reciprocity = next(_reciprocity_iter(G, nodes))[1]
51 if reciprocity is None:
52 raise NetworkXError("Not defined for isolated nodes.")
53 else:
54 return reciprocity
56 # Otherwise, `nodes` represents an iterable of nodes, so return a
57 # dictionary mapping node to its reciprocity.
58 return dict(_reciprocity_iter(G, nodes))
61def _reciprocity_iter(G, nodes):
62 """Return an iterator of (node, reciprocity)."""
63 n = G.nbunch_iter(nodes)
64 for node in n:
65 pred = set(G.predecessors(node))
66 succ = set(G.successors(node))
67 overlap = pred & succ
68 n_total = len(pred) + len(succ)
70 # Reciprocity is not defined for isolated nodes.
71 # Return None.
72 if n_total == 0:
73 yield (node, None)
74 else:
75 reciprocity = 2 * len(overlap) / n_total
76 yield (node, reciprocity)
79@not_implemented_for("undirected", "multigraph")
80@nx._dispatchable
81def overall_reciprocity(G):
82 """Compute the reciprocity for the whole graph.
84 See the doc of reciprocity for the definition.
86 Parameters
87 ----------
88 G : graph
89 A networkx graph
91 """
92 n_all_edge = G.number_of_edges()
93 n_overlap_edge = (n_all_edge - G.to_undirected().number_of_edges()) * 2
95 if n_all_edge == 0:
96 raise NetworkXError("Not defined for empty graphs")
98 return n_overlap_edge / n_all_edge