Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / reciprocity.py @ 5cef0f13

History | View | Annotate | Download (3.02 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2015-2019 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)