(
    graph: nx.Graph,
    k: int,
    c: int = 1,
    alpha: float = 1.0,
    weight: str = "weight",
)
return results
Rank nodes in a network using the BestCoverage algorithm that attempts to
    balance between node centrality and diversity.

    Args:
        graph
        k: Number of results to return for top-k search.
        c: *l* parameter for *l*-step expansion; best if 1 or 2
        alpha: Float in [0.0, 1.0] specifying how much of central vertex's score
            to remove from its *l*-step neighbors; smaller value puts more emphasis
            on centrality, larger value puts more emphasis on diversity
        weight: Key in edge data that holds weights.

    Returns:
        Top ``k`` nodes as ranked by bestcoverage algorithm; keys as node
        identifiers, values as corresponding ranking scores

    References:
        Küçüktunç, O., Saule, E., Kaya, K., & Çatalyürek, Ü. V. (2013, May).
        Diversified recommendation on graphs: pitfalls, measures, and algorithms.
        In Proceedings of the 22nd international conference on World Wide Web
        (pp. 715-726). International World Wide Web Conferences Steering Committee.
        http://www2013.wwwconference.org/proceedings/p715.pdf
Rank nodes in a network using the BestCoverage algorithm that attempts to
    balance between node centrality and diversity.
Rank nodes in a network using the BestCoverage algorithm that attempts to balance between node centrality and diversity .
def rank_nodes_by_bestcoverage(
    graph: nx.Graph,
    k: int,
    c: int = 1,
    alpha: float = 1.0,
    weight: str = "weight",
) -> Dict[Any, float]:
    """
    Rank nodes in a network using the BestCoverage algorithm that attempts to
    balance between node centrality and diversity.

    Args:
        graph
        k: Number of results to return for top-k search.
        c: *l* parameter for *l*-step expansion; best if 1 or 2
        alpha: Float in [0.0, 1.0] specifying how much of central vertex's score
            to remove from its *l*-step neighbors; smaller value puts more emphasis
            on centrality, larger value puts more emphasis on diversity
        weight: Key in edge data that holds weights.

    Returns:
        Top ``k`` nodes as ranked by bestcoverage algorithm; keys as node
        identifiers, values as corresponding ranking scores

    References:
        Küçüktunç, O., Saule, E., Kaya, K., & Çatalyürek, Ü. V. (2013, May).
        Diversified recommendation on graphs: pitfalls, measures, and algorithms.
        In Proceedings of the 22nd international conference on World Wide Web
        (pp. 715-726). International World Wide Web Conferences Steering Committee.
        http://www2013.wwwconference.org/proceedings/p715.pdf
    """
    alpha = float(alpha)

    nodes_list = [node for node in graph]
    if len(nodes_list) == 0:
        LOGGER.warning("`graph` is empty")
        return {}

    # ranks: array of PageRank values, summing up to 1
    ranks = nx.pagerank_scipy(graph, alpha=0.85, max_iter=100, tol=1e-08, weight=weight)
    # sorted_ranks = sorted(ranks.items(), key=itemgetter(1), reverse=True)
    # avg_degree = sum(dict(graph.degree()).values()) / len(nodes_list)
    # relaxation parameter, k' in the paper
    # k_prime = int(k * avg_degree * c)

    # top_k_sorted_ranks = sorted_ranks[:k_prime]

    def get_l_step_expanded_set(vertices: Collection[str], n_steps: int) -> Set[str]:
        """
        Args:
            vertices: vertices to be expanded
            n_steps: how many steps to expand vertices set

        Returns:
            the l-step expanded set of vertices
        """
        # add vertices to s
        s = set(vertices)
        # s.update(vertices)
        # for each step
        for _ in range(n_steps):
            # for each node
            next_vertices = []
            for vertex in vertices:
                # add its neighbors to the next list
                neighbors = graph.neighbors(vertex)
                next_vertices.extend(neighbors)
                s.update(neighbors)
            vertices = set(next_vertices)
        return s

    # TODO: someday, burton, figure out what you were going to do with this...
    # top_k_exp_vertices = get_l_step_expanded_set(
    #     [item[0] for item in top_k_sorted_ranks], c
    # )

    # compute initial exprel contribution
    taken = collections.defaultdict(bool)
    contrib = {}
    for vertex in nodes_list:
        # get l-step expanded set
        s = get_l_step_expanded_set([vertex], c)
        # sum up neighbors ranks, i.e. l-step expanded relevance
        contrib[vertex] = sum(ranks[v] for v in s)

    sum_contrib = 0.0
    results = {}
    # greedily select to maximize exprel metric
    for _ in range(k):
        if not contrib:
            break
        # find word with highest l-step expanded relevance score
        max_word_score = sorted(contrib.items(), key=itemgetter(1), reverse=True)[0]
        sum_contrib += max_word_score[1]  # contrib[max_word[0]]
        results[max_word_score[0]] = max_word_score[1]
        # find its l-step expanded set
        l_step_expanded_set = get_l_step_expanded_set([max_word_score[0]], c)
        # for each vertex found
        for vertex in l_step_expanded_set:
            # already removed its contribution from neighbors
            if taken[vertex] is True:
                continue
            # remove the contribution of vertex (or some fraction) from its l-step neighbors
            s1 = get_l_step_expanded_set([vertex], c)
            for w in s1:
                try:
                    contrib[w] -= alpha * ranks[vertex]
                except KeyError:
                    LOGGER.error(
                        "Word %s not in contrib dict! We're approximating...", w
                    )
            taken[vertex] = True
        contrib[max_word_score[0]] = 0

    return results
def rank_nodes_by_bestcoverage ( graph : nx . Graph , k : int , c : int = 1 , alpha : float = 1.0 , weight : str = "weight" , ) -> Dict [ Any , float ] : alpha = float ( alpha ) nodes_list = [ node for node in graph ] if len ( nodes_list ) == 0 : LOGGER . warning ( "`graph` is empty" ) return { } # ranks: array of PageRank values, summing up to 1 ranks = nx . pagerank_scipy ( graph , alpha = 0.85 , max_iter = 100 , tol = 1e-08 , weight = weight ) # sorted_ranks = sorted(ranks.items(), key=itemgetter(1), reverse=True) # avg_degree = sum(dict(graph.degree()).values()) / len(nodes_list) # relaxation parameter, k' in the paper # k_prime = int(k * avg_degree * c) # top_k_sorted_ranks = sorted_ranks[:k_prime] def get_l_step_expanded_set ( vertices : Collection [ str ] , n_steps : int ) -> Set [ str ] : """
        Args:
            vertices: vertices to be expanded
            n_steps: how many steps to expand vertices set

        Returns:
            the l-step expanded set of vertices
        """ # add vertices to s s = set ( vertices ) # s.update(vertices) # for each step for _ in range ( n_steps ) : # for each node next_vertices = [ ] for vertex in vertices : # add its neighbors to the next list neighbors = graph . neighbors ( vertex ) next_vertices . extend ( neighbors ) s . update ( neighbors ) vertices = set ( next_vertices ) return s # TODO: someday, burton, figure out what you were going to do with this... # top_k_exp_vertices = get_l_step_expanded_set( #     [item[0] for item in top_k_sorted_ranks], c # ) # compute initial exprel contribution taken = collections . defaultdict ( bool ) contrib = { } for vertex in nodes_list : # get l-step expanded set s = get_l_step_expanded_set ( [ vertex ] , c ) # sum up neighbors ranks, i.e. l-step expanded relevance contrib [ vertex ] = sum ( ranks [ v ] for v in s ) sum_contrib = 0.0 results = { } # greedily select to maximize exprel metric for _ in range ( k ) : if not contrib : break # find word with highest l-step expanded relevance score max_word_score = sorted ( contrib . items ( ) , key = itemgetter ( 1 ) , reverse = True ) [ 0 ] sum_contrib += max_word_score [ 1 ] # contrib[max_word[0]] results [ max_word_score [ 0 ] ] = max_word_score [ 1 ] # find its l-step expanded set l_step_expanded_set = get_l_step_expanded_set ( [ max_word_score [ 0 ] ] , c ) # for each vertex found for vertex in l_step_expanded_set : # already removed its contribution from neighbors if taken [ vertex ] is True : continue # remove the contribution of vertex (or some fraction) from its l-step neighbors s1 = get_l_step_expanded_set ( [ vertex ] , c ) for w in s1 : try : contrib [ w ] -= alpha * ranks [ vertex ] except KeyError : LOGGER . error ( "Word %s not in contrib dict! We're approximating..." , w ) taken [ vertex ] = True contrib [ max_word_score [ 0 ] ] = 0 return results