Function maxBlock

easygraph/functions/structural_holes/maxBlock.py:384–444

Structural hole spanners detection via maxBlock method. Parameters ---------- G: easygraph.DiGraph k: int top - k structural hole spanners. f_set: dict, optional user vi shares his/her information on network G at a rate fi. default is a random [0,1) int

(G, k, f_set=None, delta=1, eps=0.5, c=1, flag_weight=False)

@not_implemented_for("multigraph")
def maxBlock(G, k, f_set=None, delta=1, eps=0.5, c=1, flag_weight=False):
    """Structural hole spanners detection via maxBlock method.

    Parameters
    ----------
    G: easygraph.DiGraph

    k: int
        top - k structural hole spanners.

    f_set: dict, optional
        user vi shares his/her information on network G at a rate fi.
        default is a random [0,1) integer for each node

    delta: float, optional (default: 1)
        a small value delta > 0.

    eps: float, optional (default: 0.5)
        an error ratio eps with 0 < eps < 1.

    c: int, optional (default: 1)
        Success probability 1-n^-c of maxBlock.

    flag_weight: bool, optional (default: False)
        Denotes whether each edge has attribute 'weight'

    Returns
    -------
    S_list : list
        The list of each top-k structural hole spanners.

    See Also
    -------
    maxBlockFast

    Examples
    --------
    # >>> maxBlock(G, 100)

    References
    ----------
    .. [1] https://doi.org/10.1016/j.ins.2019.07.072

    """
    if f_set is None:
        f_set = {}
        for node in G.nodes:
            f_set[node] = random.random()
    if not flag_weight:
        for edge in G.edges:
            G[edge[0]][edge[1]]["weight"] = random.random()
    n = G.number_of_nodes()
    approximate_opt = _get_estimated_opt(G, f_set, k, c, delta)
    print("approximate_opt:", approximate_opt)
    L_min = (k + c) * math.log(n, 2) + math.log(4, 2)
    L_min = L_min * k * n * n * math.pow(eps, -2) * (8 * k + 2 * eps)
    L_min = L_min / approximate_opt
    L_min = math.ceil(L_min)