Function eigenvector_centrality

pattern/graph/__init__.py:937–970

Eigenvector centrality for nodes in the graph (cfr. 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 con

(graph, normalized=True, reversed=True, rating={}, iterations=100, tolerance=0.0001)

    return b

def eigenvector_centrality(graph, normalized=True, reversed=True, rating={}, iterations=100, tolerance=0.0001):
    """ Eigenvector centrality for nodes in the graph (cfr. 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.        
    """
    # Based on: NetworkX, Aric Hagberg (hagberg@lanl.gov)
    # http://python-networkx.sourcearchive.com/documentation/1.0.1/centrality_8py-source.html
    # Note: much faster than betweenness centrality (which grows exponentially).
    def normalize(vector):
        w = 1.0 / (sum(vector.values()) or 1)
        for node in vector: 
            vector[node] *= w
        return vector
    G = adjacency(graph, directed=True, reversed=reversed)
    v = normalize(dict([(n, random()) for n in graph])) # Node ID => weight vector.
    # Eigenvector calculation using the power iteration method: y = Ax.
    # It has no guarantee of convergence.
    for i in range(iterations):
        v0 = v
        v  = dict.fromkeys(v0.iterkeys(), 0)
        for n1 in v:
            for n2 in G[n1]:
                v[n1] += 0.01 + v0[n2] * G[n1][n2] * rating.get(n1, 1)
        normalize(v)
        e = sum([abs(v[n]-v0[n]) for n in v]) # Check for convergence.
        if e < len(G) * tolerance:
            # Normalize between 0.0 and 1.0.
            m = normalized and max(v.values()) or 1
            v = dict((id, w/m) for id, w in v.iteritems())
            return v
    warn("node weight is 0 because eigenvector_centrality() did not converge.", Warning)
    return dict((n, 0) for n in G)

# a | b => all elements from a and all the elements from b. 
# a & b => elements that appear in a as well as in b.