summpy/misc/divrank.py
def divrank(G, alpha=0.25, d=0.85, personalization=None,
            max_iter=100, tol=1.0e-6, nstart=None, weight='weight',
            dangling=None):
    '''
    Returns the DivRank (Diverse Rank) of the nodes in the graph.
    This code is based on networkx.pagerank.

    Args: (diff from pagerank)
      alpha: controls strength of self-link [0.0-1.0]
      d: the damping factor

    Reference:
      Qiaozhu Mei and Jian Guo and Dragomir Radev,
      DivRank: the Interplay of Prestige and Diversity in Information Networks,
      http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.174.7982
    '''

    if len(G) == 0:
        return {}

    if not G.is_directed():
        D = G.to_directed()
    else:
        D = G

    # Create a copy in (right) stochastic form
    W = nx.stochastic_graph(D, weight=weight)
    N = W.number_of_nodes()

    # self-link (DivRank)
    for n in W.nodes_iter():
        for n_ in W.nodes_iter():
            if n != n_ :
                if n_ in W[n]:
                    W[n][n_][weight] *= alpha
            else:
                if n_ not in W[n]:
                    W.add_edge(n, n_)
                W[n][n_][weight] = 1.0 - alpha

    # Choose fixed starting vector if not given
    if nstart is None:
        x = dict.fromkeys(W, 1.0 / N)
    else:
        # Normalized nstart vector
        s = float(sum(nstart.values()))
        x = dict((k, v / s) for k, v in nstart.items())

    if personalization is None:
        # Assign uniform personalization vector if not given
        p = dict.fromkeys(W, 1.0 / N)
    else:
        missing = set(G) - set(personalization)
        if missing:
            raise NetworkXError('Personalization dictionary '
                                'must have a value for every node. '
                                'Missing nodes %s' % missing)
        s = float(sum(personalization.values()))
        p = dict((k, v / s) for k, v in personalization.items())

    if dangling is None:
        # Use personalization vector if dangling vector not specified
        dangling_weights = p
    else:
        missing = set(G) - set(dangling)
        if missing:
            raise NetworkXError('Dangling node dictionary '
                                'must have a value for every node. '
                                'Missing nodes %s' % missing)
        s = float(sum(dangling.values()))
        dangling_weights = dict((k, v/s) for k, v in dangling.items())
    dangling_nodes = [n for n in W if W.out_degree(n, weight=weight) == 0.0]

    # power iteration: make up to max_iter iterations
    for _ in range(max_iter):
        xlast = x
        x = dict.fromkeys(xlast.keys(), 0)
        danglesum = d * sum(xlast[n] for n in dangling_nodes)
        for n in x:
            D_t = sum(W[n][nbr][weight] * xlast[nbr] for nbr in W[n])
            for nbr in W[n]:
                #x[nbr] += d * xlast[n] * W[n][nbr][weight]
                x[nbr] += (
                    d * (W[n][nbr][weight] * xlast[nbr] / D_t) * xlast[n]
                )
            x[n] += danglesum * dangling_weights[n] + (1.0 - d) * p[n]

        # check convergence, l1 norm
        err = sum([abs(x[n] - xlast[n]) for n in x])
        if err < N*tol:
            return x
    raise NetworkXError('divrank: power iteration failed to converge '
                        'in %d iterations.' % max_iter)
def divrank(G, alpha=0.25, d=0.85, personalization=None,
            max_iter=100, tol=1.0e-6, nstart=None, weight='weight',
            dangling=None):
    '''
    Returns the DivRank (Diverse Rank) of the nodes in the graph.
    This code is based on networkx.pagerank.

    Args: (diff from pagerank)
      alpha: controls strength of self-link [0.0-1.0]
      d: the damping factor

    Reference:
      Qiaozhu Mei and Jian Guo and Dragomir Radev,
      DivRank: the Interplay of Prestige and Diversity in Information Networks,
      http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.174.7982
    '''

    if len(G) == 0:
        return {}

    if not G.is_directed():
        D = G.to_directed()
    else:
        D = G

    # Create a copy in (right) stochastic form
    W = nx.stochastic_graph(D, weight=weight)
    N = W.number_of_nodes()

    # self-link (DivRank)
    for n in W.nodes_iter():
        for n_ in W.nodes_iter():
            if n != n_ :
                if n_ in W[n]:
                    W[n][n_][weight] *= alpha
            else:
                if n_ not in W[n]:
                    W.add_edge(n, n_)
                W[n][n_][weight] = 1.0 - alpha

    # Choose fixed starting vector if not given
    if nstart is None:
        x = dict.fromkeys(W, 1.0 / N)
    else:
        # Normalized nstart vector
        s = float(sum(nstart.values()))
        x = dict((k, v / s) for k, v in nstart.items())

    if personalization is None:
        # Assign uniform personalization vector if not given
        p = dict.fromkeys(W, 1.0 / N)
    else:
        missing = set(G) - set(personalization)
        if missing:
            raise NetworkXError('Personalization dictionary '
                                'must have a value for every node. '
                                'Missing nodes %s' % missing)
        s = float(sum(personalization.values()))
        p = dict((k, v / s) for k, v in personalization.items())

    if dangling is None:
        # Use personalization vector if dangling vector not specified
        dangling_weights = p
    else:
        missing = set(G) - set(dangling)
        if missing:
            raise NetworkXError('Dangling node dictionary '
                                'must have a value for every node. '
                                'Missing nodes %s' % missing)
        s = float(sum(dangling.values()))
        dangling_weights = dict((k, v/s) for k, v in dangling.items())
    dangling_nodes = [n for n in W if W.out_degree(n, weight=weight) == 0.0]

    # power iteration: make up to max_iter iterations
    for _ in range(max_iter):
        xlast = x
        x = dict.fromkeys(xlast.keys(), 0)
        danglesum = d * sum(xlast[n] for n in dangling_nodes)
        for n in x:
            D_t = sum(W[n][nbr][weight] * xlast[nbr] for nbr in W[n])
            for nbr in W[n]:
                #x[nbr] += d * xlast[n] * W[n][nbr][weight]
                x[nbr] += (
                    d * (W[n][nbr][weight] * xlast[nbr] / D_t) * xlast[n]
                )
            x[n] += danglesum * dangling_weights[n] + (1.0 - d) * p[n]

        # check convergence, l1 norm
        err = sum([abs(x[n] - xlast[n]) for n in x])
        if err < N*tol:
            return x
    raise NetworkXError('divrank: power iteration failed to converge '
                        'in %d iterations.' % max_iter)
def divrank ( G , alpha = 0.25 , d = 0.85 , personalization = None , max_iter = 100 , tol = 1.0e-6 , nstart = None , weight = 'weight' , dangling = None ) : if len ( G ) == 0 : return { } if not G . is_directed ( ) : D = G . to_directed ( ) else : D = G # Create a copy in (right) stochastic form W = nx . stochastic_graph ( D , weight = weight ) N = W . number_of_nodes ( ) # self-link (DivRank) for n in W . nodes_iter ( ) : for n_ in W . nodes_iter ( ) : if n != n_ : if n_ in W [ n ] : W [ n ] [ n_ ] [ weight ] *= alpha else : if n_ not in W [ n ] : W . add_edge ( n , n_ ) W [ n ] [ n_ ] [ weight ] = 1.0 - alpha # Choose fixed starting vector if not given if nstart is None : x = dict . fromkeys ( W , 1.0 / N ) else : # Normalized nstart vector s = float ( sum ( nstart . values ( ) ) ) x = dict ( ( k , v / s ) for k , v in nstart . items ( ) ) if personalization is None : # Assign uniform personalization vector if not given p = dict . fromkeys ( W , 1.0 / N ) else : missing = set ( G ) - set ( personalization ) if missing : raise NetworkXError ( 'Personalization dictionary ' 'must have a value for every node. ' 'Missing nodes %s' % missing ) s = float ( sum ( personalization . values ( ) ) ) p = dict ( ( k , v / s ) for k , v in personalization . items ( ) ) if dangling is None : # Use personalization vector if dangling vector not specified dangling_weights = p else : missing = set ( G ) - set ( dangling ) if missing : raise NetworkXError ( 'Dangling node dictionary ' 'must have a value for every node. ' 'Missing nodes %s' % missing ) s = float ( sum ( dangling . values ( ) ) ) dangling_weights = dict ( ( k , v / s ) for k , v in dangling . items ( ) ) dangling_nodes = [ n for n in W if W . out_degree ( n , weight = weight ) == 0.0 ] # power iteration: make up to max_iter iterations for _ in range ( max_iter ) : xlast = x x = dict . fromkeys ( xlast . keys ( ) , 0 ) danglesum = d * sum ( xlast [ n ] for n in dangling_nodes ) for n in x : D_t = sum ( W [ n ] [ nbr ] [ weight ] * xlast [ nbr ] for nbr in W [ n ] ) for nbr in W [ n ] : #x[nbr] += d * xlast[n] * W[n][nbr][weight] x [ nbr ] += ( d * ( W [ n ] [ nbr ] [ weight ] * xlast [ nbr ] / D_t ) * xlast [ n ] ) x [ n ] += danglesum * dangling_weights [ n ] + ( 1.0 - d ) * p [ n ] # check convergence, l1 norm err = sum ( [ abs ( x [ n ] - xlast [ n ] ) for n in x ] ) if err < N * tol : return x raise NetworkXError ( 'divrank: power iteration failed to converge ' 'in %d iterations.' % max_iter )
Returns the DivRank (Diverse Rank) of the nodes in the graph.
    This code is based on networkx.pagerank.

    Args: (diff from pagerank)
      alpha: controls strength of self-link [0.0-1.0]
      d: the damping factor

    Reference:
      Qiaozhu Mei and Jian Guo and Dragomir Radev,
      DivRank: the Interplay of Prestige and Diversity in Information Networks,
      http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.174.7982
Returns the DivRank ( Diverse Rank ) of the nodes in the graph . This code is based on networkx . pagerank .