Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (2.47 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Spectral bipartivity measure.
4
"""
5
import networkx as nx
6
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
7
#    Copyright (C) 2011 by
8
#    Aric Hagberg <hagberg@lanl.gov>
9
#    Dan Schult <dschult@colgate.edu>
10
#    Pieter Swart <swart@lanl.gov>
11
#    All rights reserved.
12
#    BSD license.
13
__all__ = ['spectral_bipartivity']
14

    
15

    
16
def spectral_bipartivity(G, nodes=None, weight='weight'):
17
    """Returns the spectral bipartivity.
18

19
    Parameters
20
    ----------
21
    G : NetworkX graph 
22

23
    nodes : list or container  optional(default is all nodes)
24
      Nodes to return value of spectral bipartivity contribution.
25

26
    weight : string or None  optional (default = 'weight')
27
      Edge data key to use for edge weights. If None, weights set to 1.
28

29
    Returns
30
    -------
31
    sb : float or dict
32
       A single number if the keyword nodes is not specified, or
33
       a dictionary keyed by node with the spectral bipartivity contribution
34
       of that node as the value.
35

36
    Examples
37
    --------
38
    >>> from networkx.algorithms import bipartite
39
    >>> G = nx.path_graph(4)
40
    >>> bipartite.spectral_bipartivity(G)
41
    1.0
42

43
    Notes
44
    -----
45
    This implementation uses Numpy (dense) matrices which are not efficient
46
    for storing large sparse graphs.  
47

48
    See Also
49
    --------
50
    color
51

52
    References
53
    ----------
54
    .. [1] E. Estrada and J. A. Rodríguez-Velázquez, "Spectral measures of
55
       bipartivity in complex networks", PhysRev E 72, 046105 (2005)
56
    """
57
    try:
58
        import scipy.linalg
59
    except ImportError:
60
        raise ImportError('spectral_bipartivity() requires SciPy: ',
61
                          'http://scipy.org/')
62
    nodelist = list(G)  # ordering of nodes in matrix
63
    A = nx.to_numpy_matrix(G, nodelist, weight=weight)
64
    expA = scipy.linalg.expm(A)
65
    expmA = scipy.linalg.expm(-A)
66
    coshA = 0.5 * (expA + expmA)
67
    if nodes is None:
68
        # return single number for entire graph
69
        return coshA.diagonal().sum() / expA.diagonal().sum()
70
    else:
71
        # contribution for individual nodes
72
        index = dict(zip(nodelist, range(len(nodelist))))
73
        sb = {}
74
        for n in nodes:
75
            i = index[n]
76
            sb[n] = coshA[i, i] / expA[i, i]
77
        return sb
78

    
79

    
80
def setup_module(module):
81
    """Fixture for nose tests."""
82
    from nose import SkipTest
83
    try:
84
        import numpy
85
    except:
86
        raise SkipTest("NumPy not available")
87
    try:
88
        import scipy
89
    except:
90
        raise SkipTest("SciPy not available")