Source code for networkx.algorithms.vitality

"""
Vitality measures.
"""
#    Copyright (C) 2012 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
__author__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)',
                        'Renato Fabbri'])
__all__ = ['closeness_vitality']

def weiner_index(G, weight=None):
    # compute sum of distances between all node pairs
    # (with optional weights)
    weiner=0.0
    if weight is None:
        for n in G:
            path_length=nx.single_source_shortest_path_length(G,n)
            weiner+=sum(path_length.values())
    else:
        for n in G:
            path_length=nx.single_source_dijkstra_path_length(G,
                    n,weight=weight)
            weiner+=sum(path_length.values())
    return weiner


[docs]def closeness_vitality(G, weight=None):
    """Compute closeness vitality for nodes.

    Closeness vitality of a node is the change in the sum of distances
    between all node pairs when excluding that node.

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

    weight : None or string (optional)
       The name of the edge attribute used as weight. If None the edge
       weights are ignored.

    Returns
    -------
    nodes : dictionary
       Dictionary with nodes as keys and closeness vitality as the value.

    Examples
    --------
    >>> G=nx.cycle_graph(3)
    >>> nx.closeness_vitality(G)
    {0: 4.0, 1: 4.0, 2: 4.0}

    See Also
    --------
    closeness_centrality()

    References
    ----------
    .. [1] Ulrik Brandes, Sec. 3.6.2 in
       Network Analysis: Methodological Foundations, Springer, 2005.
       http://books.google.com/books?id=TTNhSm7HYrIC
    """
    multigraph = G.is_multigraph()
    wig = weiner_index(G,weight)
    closeness_vitality = {}
    for n in G:
        # remove edges connected to node n and keep list of edges with data
        # could remove node n but it doesn't count anyway
        if multigraph:
            edges = G.edges(n,data=True,keys=True)
            if G.is_directed():
                edges += G.in_edges(n,data=True,keys=True)
        else:
            edges = G.edges(n,data=True)
            if G.is_directed():
                edges += G.in_edges(n,data=True)
        G.remove_edges_from(edges)
        closeness_vitality[n] = wig - weiner_index(G,weight)
        # add edges and data back to graph
        G.add_edges_from(edges)
    return closeness_vitality