Statistics
| Branch: | Revision:

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

 1 ```# -*- coding: utf-8 -*- ``` ```"""Node redundancy for bipartite graphs.""" ``` ```# Copyright (C) 2011 by ``` ```# Jordi Torrents ``` ```# Aric Hagberg ``` ```# All rights reserved. ``` ```# BSD license. ``` ```from __future__ import division ``` ```from itertools import combinations ``` ```from networkx import NetworkXError ``` ```__author__ = """\n""".join(['Jordi Torrents ', ``` ``` 'Aric Hagberg (hagberg@lanl.gov)']) ``` ```__all__ = ['node_redundancy'] ``` ```def node_redundancy(G, nodes=None): ``` ``` r"""Computes the node redundancy coefficients for the nodes in the bipartite ``` ``` graph `G`. ``` ``` ``` ``` The redundancy coefficient of a node `v` is the fraction of pairs of ``` ``` neighbors of `v` that are both linked to other nodes. In a one-mode ``` ``` projection these nodes would be linked together even if `v` were ``` ``` not there. ``` ``` ``` ``` More formally, for any vertex `v`, the *redundancy coefficient of `v`* is ``` ``` defined by ``` ``` ``` ``` .. math:: ``` ``` ``` ``` rc(v) = \frac{|\{\{u, w\} \subseteq N(v), ``` ``` \: \exists v' \neq v,\: (v',u) \in E\: ``` ``` \mathrm{and}\: (v',w) \in E\}|}{ \frac{|N(v)|(|N(v)|-1)}{2}}, ``` ``` ``` ``` where `N(v)` is the set of neighbors of `v` in `G`. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` A bipartite graph ``` ``` ``` ``` nodes : list or iterable (optional) ``` ``` Compute redundancy for these nodes. The default is all nodes in G. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` redundancy : dictionary ``` ``` A dictionary keyed by node with the node redundancy value. ``` ``` ``` ``` Examples ``` ``` -------- ``` ``` Compute the redundancy coefficient of each node in a graph:: ``` ``` ``` ``` >>> import networkx as nx ``` ``` >>> from networkx.algorithms import bipartite ``` ``` >>> G = nx.cycle_graph(4) ``` ``` >>> rc = bipartite.node_redundancy(G) ``` ``` >>> rc ``` ``` 1.0 ``` ``` ``` ``` Compute the average redundancy for the graph:: ``` ``` ``` ``` >>> import networkx as nx ``` ``` >>> from networkx.algorithms import bipartite ``` ``` >>> G = nx.cycle_graph(4) ``` ``` >>> rc = bipartite.node_redundancy(G) ``` ``` >>> sum(rc.values()) / len(G) ``` ``` 1.0 ``` ``` ``` ``` Compute the average redundancy for a set of nodes:: ``` ``` ``` ``` >>> import networkx as nx ``` ``` >>> from networkx.algorithms import bipartite ``` ``` >>> G = nx.cycle_graph(4) ``` ``` >>> rc = bipartite.node_redundancy(G) ``` ``` >>> nodes = [0, 2] ``` ``` >>> sum(rc[n] for n in nodes) / len(nodes) ``` ``` 1.0 ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXError ``` ``` If any of the nodes in the graph (or in `nodes`, if specified) has ``` ``` (out-)degree less than two (which would result in division by zero, ``` ``` according to the definition of the redundancy coefficient). ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Latapy, Matthieu, Clémence Magnien, and Nathalie Del Vecchio (2008). ``` ``` Basic notions for the analysis of large two-mode networks. ``` ``` Social Networks 30(1), 31--48. ``` ``` ``` ``` """ ``` ``` if nodes is None: ``` ``` nodes = G ``` ``` if any(len(G[v]) < 2 for v in nodes): ``` ``` raise NetworkXError('Cannot compute redundancy coefficient for a node' ``` ``` ' that has fewer than two neighbors.') ``` ``` # TODO This can be trivially parallelized. ``` ``` return {v: _node_redundancy(G, v) for v in nodes} ``` ```def _node_redundancy(G, v): ``` ``` """Returns the redundancy of the node `v` in the bipartite graph `G`. ``` ``` ``` ``` If `G` is a graph with `n` nodes, the redundancy of a node is the ratio ``` ``` of the "overlap" of `v` to the maximum possible overlap of `v` ``` ``` according to its degree. The overlap of `v` is the number of pairs of ``` ``` neighbors that have mutual neighbors themselves, other than `v`. ``` ``` ``` ``` `v` must have at least two neighbors in `G`. ``` ``` ``` ``` """ ``` ``` n = len(G[v]) ``` ``` # TODO On Python 3, we could just use `G[u].keys() & G[w].keys()` instead ``` ``` # of instantiating the entire sets. ``` ``` overlap = sum(1 for (u, w) in combinations(G[v], 2) ``` ``` if (set(G[u]) & set(G[w])) - {v}) ``` ``` return (2 * overlap) / (n * (n - 1)) ```