← Back to branch summary

~ubuntu-branches/ubuntu/utopic/python-networkx/utopic

« back to all changes in this revision

Viewing changes to networkx/algorithms/bipartite/redundancy.py

  • Committer: Package Import Robot
  • Author(s): Sandro Tosi
  • Date: 2012-08-11 12:41:30 UTC
  • mfrom: (1.4.1) (5.1.13 sid)
  • Revision ID: package-import@ubuntu.com-20120811124130-whr6uso7fncyg8bi
Tags: 1.7-1
* New upstream release
* debian/patches/changeset_*
  - removed, included upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/bipartite/redundancy.py
 
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 itertools import combinations
 
9
import networkx as nx
 
10
 
 
11
__author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>',
 
12
                            'Aric Hagberg (hagberg@lanl.gov)'])
 
13
__all__ = ['node_redundancy']
 
14
 
 
15
def node_redundancy(G, nodes=None):
 
16
    r"""Compute bipartite node redundancy coefficient.
 
17
 
 
18
    The redundancy coefficient of a node `v` is the fraction of pairs of 
 
19
    neighbors of `v` that are both linked to other nodes. In a one-mode
 
20
    projection these nodes would be linked together even if `v`  were 
 
21
    not there.
 
22
    
 
23
    .. math::
 
24
 
 
25
        rc(v) = \frac{|\{\{u,w\} \subseteq N(v),
 
26
        \: \exists v' \neq  v,\: (v',u) \in E\: 
 
27
        \mathrm{and}\: (v',w) \in E\}|}{ \frac{|N(v)|(|N(v)|-1)}{2}}
 
28
 
 
29
    where `N(v)` are the neighbors of `v` in `G`.
 
30
 
 
31
    Parameters
 
32
    ----------
 
33
    G : graph
 
34
        A bipartite graph
 
35
 
 
36
    nodes : list or iterable (optional)
 
37
        Compute redundancy for these nodes. The default is all nodes in G.
 
38
 
 
39
    Returns
 
40
    -------
 
41
    redundancy : dictionary
 
42
        A dictionary keyed by node with the node redundancy value.
 
43
 
 
44
    Examples
 
45
    --------
 
46
    >>> from networkx.algorithms import bipartite
 
47
    >>> G = nx.cycle_graph(4)
 
48
    >>> rc = bipartite.node_redundancy(G)
 
49
    >>> rc[0]
 
50
    1.0
 
51
 
 
52
    Compute the average redundancy for the graph:
 
53
 
 
54
    >>> sum(rc.values())/len(G)
 
55
    1.0
 
56
 
 
57
    Compute the average redundancy for a set of nodes:
 
58
 
 
59
    >>> nodes = [0, 2]
 
60
    >>> sum(rc[n] for n in nodes)/len(nodes)
 
61
    1.0
 
62
 
 
63
    References
 
64
    ----------
 
65
    .. [1] Latapy, Matthieu, Clémence Magnien, and Nathalie Del Vecchio (2008).
 
66
       Basic notions for the analysis of large two-mode networks. 
 
67
       Social Networks 30(1), 31--48.
 
68
    """
 
69
    if nodes is None:
 
70
        nodes = G
 
71
    rc = {}
 
72
    for v in nodes:
 
73
        overlap = 0.0
 
74
        for u, w in combinations(G[v], 2):
 
75
            if len((set(G[u]) & set(G[w])) - set([v])) > 0:
 
76
                overlap += 1
 
77
        if overlap > 0:
 
78
            n = len(G[v])
 
79
            norm = 2.0/(n*(n-1))
 
80
        else:
 
81
            norm = 1.0
 
82
        rc[v] = overlap*norm
 
83
    return rc
 
84