ioftools / networkxMiCe / networkxmaster / networkx / algorithms / reciprocity.py @ 5cef0f13
History  View  Annotate  Download (3.02 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20152019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# All rights reserved.

7 
# BSD license.

8 
#

9 
# Authors: Haochen Wu (wuhaochen42@gmail.com)

10 
"""Algorithms to calculate reciprocity in a directed graph."""

11 
from networkx import NetworkXError 
12 
from ..utils import not_implemented_for 
13  
14 
__all__ = ['reciprocity', 'overall_reciprocity'] 
15  
16  
17 
@not_implemented_for('undirected', 'multigraph') 
18 
def reciprocity(G, nodes=None): 
19 
r"""Compute the reciprocity in a directed graph.

20 

21 
The reciprocity of a directed graph is defined as the ratio

22 
of the number of edges pointing in both directions to the total

23 
number of edges in the graph.

24 
Formally, $r = {(u,v) \in G(v,u) \in G} / {(u,v) \in G}$.

25 

26 
The reciprocity of a single node u is defined similarly,

27 
it is the ratio of the number of edges in both directions to

28 
the total number of edges attached to node u.

29 

30 
Parameters

31 


32 
G : graph

33 
A networkx directed graph

34 
nodes : container of nodes, optional (default=whole graph)

35 
Compute reciprocity for nodes in this container.

36 

37 
Returns

38 


39 
out : dictionary

40 
Reciprocity keyed by node label.

41 

42 
Notes

43 


44 
The reciprocity is not defined for isolated nodes.

45 
In such cases this function will return None.

46 

47 
"""

48 
# If `nodes` is not specified, calculate the reciprocity of the graph.

49 
if nodes is None: 
50 
return overall_reciprocity(G)

51  
52 
# If `nodes` represents a single node in the graph, return only its

53 
# reciprocity.

54 
if nodes in G: 
55 
reciprocity = next(_reciprocity_iter(G, nodes))[1] 
56 
if reciprocity is None: 
57 
raise NetworkXError('Not defined for isolated nodes.') 
58 
else:

59 
return reciprocity

60  
61 
# Otherwise, `nodes` represents an iterable of nodes, so return a

62 
# dictionary mapping node to its reciprocity.

63 
return dict(_reciprocity_iter(G, nodes)) 
64  
65  
66 
def _reciprocity_iter(G, nodes): 
67 
""" Return an iterator of (node, reciprocity).

68 
"""

69 
n = G.nbunch_iter(nodes) 
70 
for node in n: 
71 
pred = set(G.predecessors(node))

72 
succ = set(G.successors(node))

73 
overlap = pred & succ 
74 
n_total = len(pred) + len(succ) 
75  
76 
# Reciprocity is not defined for isolated nodes.

77 
# Return None.

78 
if n_total == 0: 
79 
yield (node, None) 
80 
else:

81 
reciprocity = 2.0 * float(len(overlap)) / float(n_total) 
82 
yield (node, reciprocity)

83  
84  
85 
@not_implemented_for('undirected', 'multigraph') 
86 
def overall_reciprocity(G): 
87 
"""Compute the reciprocity for the whole graph.

88 

89 
See the doc of reciprocity for the definition.

90 

91 
Parameters

92 


93 
G : graph

94 
A networkx graph

95 

96 
"""

97 
n_all_edge = G.number_of_edges() 
98 
n_overlap_edge = (n_all_edge  G.to_undirected().number_of_edges()) * 2

99  
100 
if n_all_edge == 0: 
101 
raise NetworkXError("Not defined for empty graphs") 
102  
103 
return float(n_overlap_edge) / float(n_all_edge) 