graphit/graph_algorithms.py
def eigenvector_centrality(graph, normalized=True, reverse=True, rating=None,
                           start=None, iterations=100, tolerance=0.0001):
    """
    Eigenvector centrality for nodes in the graph (like Google's PageRank).
    
    Eigenvector centrality is a measure of the importance of a node in a directed network.
    It rewards nodes with a high potential of (indirectly) connecting to high-scoring nodes.
    Nodes with no incoming connections have a score of zero.
    If you want to measure outgoing connections, reversed should be False.
    
    The eigenvector calculation is done by the power iteration method.
    It has no guarantee of convergence.
    A starting vector for the power iteration can be given in the start dict.
    
    You can adjust the importance of a node with the rating dictionary,
    which links node id's to a score.
    
    The algorithm is adapted from NetworkX, Aric Hagberg (hagberg@lanl.gov):
    https://networkx.lanl.gov/attachment/ticket/119/eigenvector_centrality.py
    
    TODO: Implementation does not work yet. Need to look into adjacency function
    """
    
    if rating is None:
        rating = {}
    
    G = graph.nodes.keys()
    W = adjacency(graph, directed=True, reverse=reverse)
    
    def _normalize(x):
        s = sum(x.values())
        if s != 0:
            s = 1.0 / s
        for k in x:
            x[k] *= s
    
    x = start
    if x is None:
        x = dict([(n, random()) for n in G])
    _normalize(x)
    
    # Power method: y = Ax multiplication.
    for i in range(iterations):
        x0 = x
        x = dict.fromkeys(x0.keys(), 0)
        for n in x:
            for nbr in graph.adjacency[n]:
                r = 1
                if n in rating:
                    r = rating[n]
                x[n] += 0.01 + x0[nbr] * graph.adjacency[n][nbr] * r
        _normalize(x)
        e = sum([abs(x[n] - x0[n]) for n in x])
        if e < len(graph.nodes) * tolerance:
            if normalized:
                # Normalize between 0.0 and 1.0.
                m = max(x.values())
                if m == 0:
                    m = 1
                x = dict([(id, w / m) for id, w in x.iteritems()])
            return x
    
    # raise NoConvergenceError
    logger.warning("node weight is 0 because eigenvector_centrality() did not converge.")
    return dict([(n, 0) for n in G])

    Eigenvector centrality for nodes in the graph (like Google's PageRank).
    
    Eigenvector centrality is a measure of the importance of a node in a directed network.
    It rewards nodes with a high potential of (indirectly) connecting to high-scoring nodes.
    Nodes with no incoming connections have a score of zero.
    If you want to measure outgoing connections, reversed should be False.
    
    The eigenvector calculation is done by the power iteration method.
    It has no guarantee of convergence.
    A starting vector for the power iteration can be given in the start dict.
    
    You can adjust the importance of a node with the rating dictionary,
    which links node id's to a score.
    
    The algorithm is adapted from NetworkX, Aric Hagberg (hagberg@lanl.gov):
    https://networkx.lanl.gov/attachment/ticket/119/eigenvector_centrality.py
    
    TODO: Implementation does not work yet. Need to look into adjacency function
    
Eigenvector centrality for nodes in the graph (like Google's PageRank).
Eigenvector centrality is a measure of the importance of a node in a directed network.
It rewards nodes with a high potential of (indirectly) connecting to high-scoring nodes.
Nodes with no incoming connections have a score of zero.
If you want to measure outgoing connections, reversed should be False.

The eigenvector calculation is done by the power iteration method.
It has no guarantee of convergence.
A starting vector for the power iteration can be given in the start dict.

You can adjust the importance of a node with the rating dictionary,
which links node id's to a score.



Implementation does not work yet. Need to look into adjacency function
Eigenvector centrality for nodes in the graph ( like Google ' s PageRank ) . Eigenvector centrality is a measure of the importance of a node in a directed network . It rewards nodes with a high potential of ( indirectly ) connecting to high - scoring nodes . Nodes with no incoming connections have a score of zero . If you want to measure outgoing connections reversed should be False . The eigenvector calculation is done by the power iteration method . It has no guarantee of convergence . A starting vector for the power iteration can be given in the start dict . You can adjust the importance of a node with the rating dictionary which links node id ' s to a score . Implementation does not work yet . Need to look into adjacency function
def eigenvector_centrality(graph, normalized=True, reverse=True, rating=None,
                           start=None, iterations=100, tolerance=0.0001):
    if rating is None:
        rating = {}
    G = graph.nodes.keys()
    W = adjacency(graph, directed=True, reverse=reverse)
    def _normalize(x):
        s = sum(x.values())
        if s != 0:
            s = 1.0 / s
        for k in x:
            x[k] *= s
    x = start
    if x is None:
        x = dict([(n, random()) for n in G])
    _normalize(x)
    for i in range(iterations):
        x0 = x
        x = dict.fromkeys(x0.keys(), 0)
        for n in x:
            for nbr in graph.adjacency[n]:
                r = 1
                if n in rating:
                    r = rating[n]
                x[n] += 0.01 + x0[nbr] * graph.adjacency[n][nbr] * r
        _normalize(x)
        e = sum([abs(x[n] - x0[n]) for n in x])
        if e < len(graph.nodes) * tolerance:
            if normalized:
                m = max(x.values())
                if m == 0:
                    m = 1
                x = dict([(id, w / m) for id, w in x.iteritems()])
            return x
    logger.warning("node weight is 0 because eigenvector_centrality() did not converge.")
    return dict([(n, 0) for n in G])
def eigenvector_centrality ( graph , normalized = True , reverse = True , rating = None , start = None , iterations = 100 , tolerance = 0.0001 ) : if rating is None : rating = { } G = graph . nodes . keys ( ) W = adjacency ( graph , directed = True , reverse = reverse ) def _normalize ( x ) : s = sum ( x . values ( ) ) if s != 0 : s = 1.0 / s for k in x : x [ k ] *= s x = start if x is None : x = dict ( [ ( n , random ( ) ) for n in G ] ) _normalize ( x ) for i in range ( iterations ) : x0 = x x = dict . fromkeys ( x0 . keys ( ) , 0 ) for n in x : for nbr in graph . adjacency [ n ] : r = 1 if n in rating : r = rating [ n ] x [ n ] += 0.01 + x0 [ nbr ] * graph . adjacency [ n ] [ nbr ] * r _normalize ( x ) e = sum ( [ abs ( x [ n ] - x0 [ n ] ) for n in x ] ) if e < len ( graph . nodes ) * tolerance : if normalized : m = max ( x . values ( ) ) if m == 0 : m = 1 x = dict ( [ ( id , w / m ) for id , w in x . iteritems ( ) ] ) return x logger . warning ( "node weight is 0 because eigenvector_centrality() did not converge." ) return dict ( [ ( n , 0 ) for n in G ] )
Eigenvector centrality for nodes in the graph (like Google's PageRank).
Eigenvector centrality for nodes in the graph ( like Google ' s PageRank ) .
"""
    Eigenvector centrality for nodes in the graph (like Google's PageRank).
    
    Eigenvector centrality is a measure of the importance of a node in a directed network.
    It rewards nodes with a high potential of (indirectly) connecting to high-scoring nodes.
    Nodes with no incoming connections have a score of zero.
    If you want to measure outgoing connections, reversed should be False.
    
    The eigenvector calculation is done by the power iteration method.
    It has no guarantee of convergence.
    A starting vector for the power iteration can be given in the start dict.
    
    You can adjust the importance of a node with the rating dictionary,
    which links node id's to a score.
    
    The algorithm is adapted from NetworkX, Aric Hagberg (hagberg@lanl.gov):
    https://networkx.lanl.gov/attachment/ticket/119/eigenvector_centrality.py
    
    TODO: Implementation does not work yet. Need to look into adjacency function
    """ # Power method: y = Ax multiplication. # Normalize between 0.0 and 1.0. # raise NoConvergenceError
graph
normalized
reverse
rating
start
iterations
tolerance