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


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 onemode

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 twomode networks.

93 
Social Networks 30(1), 3148.

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)) 