path: root/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/centrality/communicability_alg.py

"""
Communicability and centrality measures.
"""
#    Copyright (C) 2011 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
import networkx as nx
from networkx.utils import *
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
                        'Franck Kalala (franckkalala@yahoo.fr'])
__all__ = ['communicability_centrality_exp',
           'communicability_centrality',
           'communicability_betweenness_centrality',
           'communicability',
           'communicability_exp',
           'estrada_index',
           ]

@require('scipy')
@not_implemented_for('directed')
@not_implemented_for('multigraph')
def communicability_centrality_exp(G):
    r"""Return the communicability centrality for each node of G

    Communicability centrality, also called subgraph centrality, of a node `n`
    is the sum of closed walks of all lengths starting and ending at node `n`.

    Parameters
    ----------
    G: graph

    Returns
    -------
    nodes:dictionary
        Dictionary of nodes with communicability centrality as the value.

    Raises
    ------
    NetworkXError
        If the graph is not undirected and simple.

    See Also
    --------
    communicability:
        Communicability between all pairs of nodes in G.
    communicability_centrality:
        Communicability centrality for each node of G.

    Notes
    -----
    This version of the algorithm exponentiates the adjacency matrix.
    The communicability centrality of a node `u` in G can be found using
    the matrix exponential of the adjacency matrix of G  [1]_ [2]_,

    .. math::

        SC(u)=(e^A)_{uu} .

    References
    ----------
    .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
       "Subgraph centrality in complex networks",
       Physical Review E 71, 056103 (2005).
       http://arxiv.org/abs/cond-mat/0504730

    .. [2] Ernesto Estrada, Naomichi Hatano,
       "Communicability in complex networks",
       Phys. Rev. E 77, 036111 (2008).
       http://arxiv.org/abs/0707.0756

    Examples
    --------
    >>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
    >>> sc = nx.communicability_centrality_exp(G)
    """
    # alternative implementation that calculates the matrix exponential
    import scipy.linalg
    nodelist = G.nodes() # ordering of nodes in matrix
    A = nx.to_numpy_matrix(G,nodelist)
    # convert to 0-1 matrix
    A[A!=0.0] = 1
    expA = scipy.linalg.expm(A)
    # convert diagonal to dictionary keyed by node
    sc = dict(zip(nodelist,map(float,expA.diagonal())))
    return sc

@require('numpy')
@not_implemented_for('directed')
@not_implemented_for('multigraph')
def communicability_centrality(G):
    r"""Return communicability centrality for each node in G.

    Communicability centrality, also called subgraph centrality, of a node `n`
    is the sum of closed walks of all lengths starting and ending at node `n`.

    Parameters
    ----------
    G: graph

    Returns
    -------
    nodes: dictionary
       Dictionary of nodes with communicability centrality as the value.

    Raises
    ------
    NetworkXError
       If the graph is not undirected and simple.

    See Also
    --------
    communicability:
        Communicability between all pairs of nodes in G.
    communicability_centrality:
        Communicability centrality for each node of G.

    Notes
    -----
    This version of the algorithm computes eigenvalues and eigenvectors
    of the adjacency matrix.

    Communicability centrality of a node `u` in G can be found using
    a spectral decomposition of the adjacency matrix [1]_ [2]_,

    .. math::

       SC(u)=\sum_{j=1}^{N}(v_{j}^{u})^2 e^{\lambda_{j}},

    where `v_j` is an eigenvector of the adjacency matrix `A` of G
    corresponding corresponding to the eigenvalue `\lambda_j`.

    Examples
    --------
    >>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
    >>> sc = nx.communicability_centrality(G)

    References
    ----------
    .. [1] Ernesto Estrada, Juan A. Rodriguez-Velazquez,
       "Subgraph centrality in complex networks",
       Physical Review E 71, 056103 (2005).
       http://arxiv.org/abs/cond-mat/0504730
    .. [2] Ernesto Estrada, Naomichi Hatano,
       "Communicability in complex networks",
       Phys. Rev. E 77, 036111 (2008).
       http://arxiv.org/abs/0707.0756
    """
    import numpy
    import numpy.linalg
    nodelist = G.nodes() # ordering of nodes in matrix
    A = nx.to_numpy_matrix(G,nodelist)
    # convert to 0-1 matrix
    A[A!=0.0] = 1
    w,v = numpy.linalg.eigh(A)
    vsquare = numpy.array(v)**2
    expw = numpy.exp(w)
    xg = numpy.dot(vsquare,expw)
    # convert vector dictionary keyed by node
    sc = dict(zip(nodelist,map(float,xg)))
    return sc

@require('scipy')
@not_implemented_for('directed')
@not_implemented_for('multigraph')
def communicability_betweenness_centrality(G, normalized=True):
    r"""Return communicability betweenness for all pairs of nodes in G.

    Communicability betweenness measure makes use of the number of walks
    connecting every pair of nodes as the basis of a betweenness centrality
    measure.

    Parameters
    ----------
    G: graph

    Returns
    -------
    nodes:dictionary
        Dictionary of nodes with communicability betweenness as the value.

    Raises
    ------
    NetworkXError
        If the graph is not undirected and simple.

    See Also
    --------
    communicability:
       Communicability between all pairs of nodes in G.
    communicability_centrality:
       Communicability centrality for each node of G using matrix exponential.
    communicability_centrality_exp:
       Communicability centrality for each node in G using
       spectral decomposition.

    Notes
    -----
    Let `G=(V,E)` be a simple undirected graph with `n` nodes and `m` edges,
    and `A` denote the adjacency matrix of `G`.

    Let `G(r)=(V,E(r))` be the graph resulting from
    removing all edges connected to node `r` but not the node itself.

    The adjacency matrix for `G(r)` is `A+E(r)`,  where `E(r)` has nonzeros
    only in row and column `r`.

    The communicability betweenness of a node `r`  is [1]_

    .. math::
         \omega_{r} = \frac{1}{C}\sum_{p}\sum_{q}\frac{G_{prq}}{G_{pq}},
         p\neq q, q\neq r,

    where
    `G_{prq}=(e^{A}_{pq} - (e^{A+E(r)})_{pq}`  is the number of walks
    involving node r,
    `G_{pq}=(e^{A})_{pq}` is the number of closed walks starting
    at node `p` and ending at node `q`,
    and `C=(n-1)^{2}-(n-1)` is a normalization factor equal to the
    number of terms in the sum.

    The resulting `\omega_{r}` takes values between zero and one.
    The lower bound cannot be attained for a connected
    graph, and the upper bound is attained in the star graph.

    References
    ----------
    .. [1] Ernesto Estrada, Desmond J. Higham, Naomichi Hatano,
       "Communicability Betweenness in Complex Networks"
       Physica A 388 (2009) 764-774.
       http://arxiv.org/abs/0905.4102

    Examples
    --------
    >>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
    >>> cbc = nx.communicability_betweenness_centrality(G)
    """
    import scipy
    import scipy.linalg
    nodelist = G.nodes() # ordering of nodes in matrix
    n = len(nodelist)
    A = nx.to_numpy_matrix(G,nodelist)
    # convert to 0-1 matrix
    A[A!=0.0] = 1
    expA = scipy.linalg.expm(A)
    mapping = dict(zip(nodelist,range(n)))
    sc = {}
    for v in G:
        # remove row and col of node v
        i = mapping[v]
        row = A[i,:].copy()
        col = A[:,i].copy()
        A[i,:] = 0
        A[:,i] = 0
        B = (expA - scipy.linalg.expm(A)) / expA
        # sum with row/col of node v and diag set to zero
        B[i,:] = 0
        B[:,i] = 0
        B -= scipy.diag(scipy.diag(B))
        sc[v] = float(B.sum())
        # put row and col back
        A[i,:] = row
        A[:,i] = col
    # rescaling
    sc = _rescale(sc,normalized=normalized)
    return sc

def _rescale(sc,normalized):
    # helper to rescale betweenness centrality
    if normalized is True:
        order=len(sc)
        if order <=2:
            scale=None
        else:
            scale=1.0/((order-1.0)**2-(order-1.0))
    if scale is not None:
        for v in sc:
            sc[v] *= scale
    return sc


@require('numpy','scipy')
@not_implemented_for('directed')
@not_implemented_for('multigraph')
def communicability(G):
    r"""Return communicability between all pairs of nodes in G.

    The communicability between pairs of nodes in G is the sum of
    closed walks of different lengths starting at node u and ending at node v.

    Parameters
    ----------
    G: graph

    Returns
    -------
    comm: dictionary of dictionaries
        Dictionary of dictionaries keyed by nodes with communicability
        as the value.

    Raises
    ------
    NetworkXError
       If the graph is not undirected and simple.

    See Also
    --------
    communicability_centrality_exp:
       Communicability centrality for each node of G using matrix exponential.
    communicability_centrality:
       Communicability centrality for each node in G using spectral
       decomposition.
    communicability:
       Communicability between pairs of nodes in G.

    Notes
    -----
    This algorithm uses a spectral decomposition of the adjacency matrix.
    Let G=(V,E) be a simple undirected graph.  Using the connection between
    the powers  of the adjacency matrix and the number of walks in the graph,
    the communicability  between nodes `u` and `v` based on the graph spectrum
    is [1]_

    .. math::
        C(u,v)=\sum_{j=1}^{n}\phi_{j}(u)\phi_{j}(v)e^{\lambda_{j}},

    where `\phi_{j}(u)` is the `u\rm{th}` element of the `j\rm{th}` orthonormal
    eigenvector of the adjacency matrix associated with the eigenvalue
    `\lambda_{j}`.

    References
    ----------
    .. [1] Ernesto Estrada, Naomichi Hatano,
       "Communicability in complex networks",
       Phys. Rev. E 77, 036111 (2008).
       http://arxiv.org/abs/0707.0756

    Examples
    --------
    >>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
    >>> c = nx.communicability(G)
    """
    import numpy
    import scipy.linalg
    nodelist = G.nodes() # ordering of nodes in matrix
    A = nx.to_numpy_matrix(G,nodelist)
    # convert to 0-1 matrix
    A[A!=0.0] = 1
    w,vec = numpy.linalg.eigh(A)
    expw = numpy.exp(w)
    mapping = dict(zip(nodelist,range(len(nodelist))))
    sc={}
    # computing communicabilities
    for u in G:
        sc[u]={}
        for v in G:
            s = 0
            p = mapping[u]
            q = mapping[v]
            for j in range(len(nodelist)):
                s += vec[:,j][p,0]*vec[:,j][q,0]*expw[j]
            sc[u][v] = float(s)
    return sc

@require('scipy')
@not_implemented_for('directed')
@not_implemented_for('multigraph')
def communicability_exp(G):
    r"""Return communicability between all pairs of nodes in G.

    Communicability between pair of node (u,v) of node in G is the sum of
    closed walks of different lengths starting at node u and ending at node v.

    Parameters
    ----------
    G: graph

    Returns
    -------
    comm: dictionary of dictionaries
        Dictionary of dictionaries keyed by nodes with communicability
        as the value.

    Raises
    ------
    NetworkXError
        If the graph is not undirected and simple.

    See Also
    --------
    communicability_centrality_exp:
       Communicability centrality for each node of G using matrix exponential.
    communicability_centrality:
       Communicability centrality for each node in G using spectral
       decomposition.
    communicability_exp:
       Communicability between all pairs of nodes in G  using spectral
       decomposition.

    Notes
    -----
    This algorithm uses matrix exponentiation of the adjacency matrix.

    Let G=(V,E) be a simple undirected graph.  Using the connection between
    the powers  of the adjacency matrix and the number of walks in the graph,
    the communicability between nodes u and v is [1]_,

    .. math::
        C(u,v) = (e^A)_{uv},

    where `A` is the adjacency matrix of G.

    References
    ----------
    .. [1] Ernesto Estrada, Naomichi Hatano,
       "Communicability in complex networks",
       Phys. Rev. E 77, 036111 (2008).
       http://arxiv.org/abs/0707.0756

    Examples
    --------
    >>> G = nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
    >>> c = nx.communicability_exp(G)
    """
    import scipy.linalg
    nodelist = G.nodes() # ordering of nodes in matrix
    A = nx.to_numpy_matrix(G,nodelist)
    # convert to 0-1 matrix
    A[A!=0.0] = 1
    # communicability matrix
    expA = scipy.linalg.expm(A)
    mapping = dict(zip(nodelist,range(len(nodelist))))
    sc = {}
    for u in G:
        sc[u]={}
        for v in G:
            sc[u][v] = float(expA[mapping[u],mapping[v]])
    return sc

@require('numpy')
def estrada_index(G):
    r"""Return the Estrada index of a the graph G.

    Parameters
    ----------
    G: graph

    Returns
    -------
    estrada index: float

    Raises
    ------
    NetworkXError
        If the graph is not undirected and simple.

    See also
    --------
    estrada_index_exp

    Notes
    -----
    Let `G=(V,E)` be a simple undirected graph with `n` nodes  and let
    `\lambda_{1}\leq\lambda_{2}\leq\cdots\lambda_{n}`
    be a non-increasing ordering of the eigenvalues of its adjacency
    matrix `A`.  The Estrada index is

    .. math::
        EE(G)=\sum_{j=1}^n e^{\lambda _j}.

    References
    ----------
    .. [1] E. Estrada,  Characterization of 3D molecular structure,
       Chem. Phys. Lett. 319, 713 (2000).

    Examples
    --------
    >>> G=nx.Graph([(0,1),(1,2),(1,5),(5,4),(2,4),(2,3),(4,3),(3,6)])
    >>> ei=nx.estrada_index(G)
    """
    return sum(communicability_centrality(G).values())

# fixture for nose tests
def setup_module(module):
    from nose import SkipTest
    try:
        import numpy
    except:
        raise SkipTest("NumPy not available")
    try:
        import scipy
    except:
        raise SkipTest("SciPy not available")