Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.83 KB)

1
# -*- coding: utf-8 -*-
2
"""Node redundancy for bipartite graphs."""
3
#    Copyright (C) 2011 by
4
#    Jordi Torrents <jtorrents@milnou.net>
5
#    Aric Hagberg <hagberg@lanl.gov>
6
#    All rights reserved.
7
#    BSD license.
8
from __future__ import division
9

    
10
from itertools import combinations
11

    
12
from networkx import NetworkXError
13

    
14
__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>',
15
                            'Aric Hagberg (hagberg@lanl.gov)'])
16
__all__ = ['node_redundancy']
17

    
18

    
19
def node_redundancy(G, nodes=None):
20
    r"""Computes the node redundancy coefficients for the nodes in the bipartite
21
    graph `G`.
22

23
    The redundancy coefficient of a node `v` is the fraction of pairs of
24
    neighbors of `v` that are both linked to other nodes. In a one-mode
25
    projection these nodes would be linked together even if `v` were
26
    not there.
27

28
    More formally, for any vertex `v`, the *redundancy coefficient of `v`* is
29
    defined by
30

31
    .. math::
32

33
        rc(v) = \frac{|\{\{u, w\} \subseteq N(v),
34
        \: \exists v' \neq  v,\: (v',u) \in E\:
35
        \mathrm{and}\: (v',w) \in E\}|}{ \frac{|N(v)|(|N(v)|-1)}{2}},
36

37
    where `N(v)` is the set of neighbors of `v` in `G`.
38

39
    Parameters
40
    ----------
41
    G : graph
42
        A bipartite graph
43

44
    nodes : list or iterable (optional)
45
        Compute redundancy for these nodes. The default is all nodes in G.
46

47
    Returns
48
    -------
49
    redundancy : dictionary
50
        A dictionary keyed by node with the node redundancy value.
51

52
    Examples
53
    --------
54
    Compute the redundancy coefficient of each node in a graph::
55

56
        >>> import networkx as nx
57
        >>> from networkx.algorithms import bipartite
58
        >>> G = nx.cycle_graph(4)
59
        >>> rc = bipartite.node_redundancy(G)
60
        >>> rc[0]
61
        1.0
62

63
    Compute the average redundancy for the graph::
64

65
        >>> import networkx as nx
66
        >>> from networkx.algorithms import bipartite
67
        >>> G = nx.cycle_graph(4)
68
        >>> rc = bipartite.node_redundancy(G)
69
        >>> sum(rc.values()) / len(G)
70
        1.0
71

72
    Compute the average redundancy for a set of nodes::
73

74
        >>> import networkx as nx
75
        >>> from networkx.algorithms import bipartite
76
        >>> G = nx.cycle_graph(4)
77
        >>> rc = bipartite.node_redundancy(G)
78
        >>> nodes = [0, 2]
79
        >>> sum(rc[n] for n in nodes) / len(nodes)
80
        1.0
81

82
    Raises
83
    ------
84
    NetworkXError
85
        If any of the nodes in the graph (or in `nodes`, if specified) has
86
        (out-)degree less than two (which would result in division by zero,
87
        according to the definition of the redundancy coefficient).
88

89
    References
90
    ----------
91
    .. [1] Latapy, Matthieu, Clémence Magnien, and Nathalie Del Vecchio (2008).
92
       Basic notions for the analysis of large two-mode networks.
93
       Social Networks 30(1), 31--48.
94

95
    """
96
    if nodes is None:
97
        nodes = G
98
    if any(len(G[v]) < 2 for v in nodes):
99
        raise NetworkXError('Cannot compute redundancy coefficient for a node'
100
                            ' that has fewer than two neighbors.')
101
    # TODO This can be trivially parallelized.
102
    return {v: _node_redundancy(G, v) for v in nodes}
103

    
104

    
105
def _node_redundancy(G, v):
106
    """Returns the redundancy of the node `v` in the bipartite graph `G`.
107

108
    If `G` is a graph with `n` nodes, the redundancy of a node is the ratio
109
    of the "overlap" of `v` to the maximum possible overlap of `v`
110
    according to its degree. The overlap of `v` is the number of pairs of
111
    neighbors that have mutual neighbors themselves, other than `v`.
112

113
    `v` must have at least two neighbors in `G`.
114

115
    """
116
    n = len(G[v])
117
    # TODO On Python 3, we could just use `G[u].keys() & G[w].keys()` instead
118
    # of instantiating the entire sets.
119
    overlap = sum(1 for (u, w) in combinations(G[v], 2)
120
                  if (set(G[u]) & set(G[w])) - {v})
121
    return (2 * overlap) / (n * (n - 1))