nested_blockmodel.py 45.8 KB
Newer Older
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015

    See [peixoto-hierarchical-2013]_ for details on the algorithm.

    This algorithm has a complexity of :math:`O(N \ln^2 N)`, where :math:`N`
    is the number of nodes in the network.

    Examples
    --------
    .. testsetup:: nested_mdl

       gt.seed_rng(42)
       np.random.seed(42)

    .. doctest:: nested_mdl

Tiago Peixoto's avatar
Tiago Peixoto committed
1016
1017
       >>> g = gt.collection.data["power"]
       >>> bstack, mdl = gt.minimize_nested_blockmodel_dl(g, deg_corr=True)
1018
1019
1020
1021
1022
1023
       >>> t = gt.get_hierarchy_tree(bstack)[0]
       >>> tpos = pos = gt.radial_tree_layout(t, t.vertex(t.num_vertices() - 1), weighted=True)
       >>> cts = gt.get_hierarchy_control_points(g, t, tpos)
       >>> pos = g.own_property(tpos)
       >>> b = bstack[0].vp["b"]
       >>> gt.graph_draw(g, pos=pos, vertex_fill_color=b, vertex_shape=b, edge_control_points=cts,
Tiago Peixoto's avatar
Tiago Peixoto committed
1024
       ...               edge_color=[0, 0, 0, 0.3], vertex_anchor=0, output="power_nested_mdl.pdf")
1025
1026
1027
1028
       <...>

    .. testcleanup:: nested_mdl

Tiago Peixoto's avatar
Tiago Peixoto committed
1029
       gt.graph_draw(g, pos=pos, vertex_fill_color=b, vertex_shape=b, edge_control_points=cts, edge_color=[0, 0, 0, 0.3], vertex_anchor=0, output="power_nested_mdl.png")
1030

Tiago Peixoto's avatar
Tiago Peixoto committed
1031
    .. figure:: power_nested_mdl.*
1032
1033
       :align: center

Tiago Peixoto's avatar
Tiago Peixoto committed
1034
       Block partition of a power-grid network, which minimizes the description
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
       length of the network according to the nested (degree-corrected) stochastic blockmodel.

    References
    ----------

    .. [peixoto-hierarchical-2013] Tiago P. Peixoto, "Hierarchical block structures and high-resolution
       model selection in large networks ", :arxiv:`1310.4377`.
    .. [peixoto-efficient-2013] Tiago P. Peixoto, "Efficient Monte Carlo and greedy
       heuristic for the inference of stochastic block models", :arxiv:`1310.4378`.
    """


    if Bs is None:
        Bs = [1]

        if minimize_state is not None:
            Bs = [ba.max() + 1 for ba in minimize_state.bs]

    if bs is not None:
        Bs = [ba.max() + 1 for ba in bs]

    if Bs[-1] > 1:
        Bs += [1]

    if minimize_state is None:
        minimize_state = NestedMinimizeState()

    if bs is None:
        state = init_nested_state(g, Bs=Bs, deg_corr=deg_corr,
                                  eweight=eweight, vweight=vweight,
                                  verbose=verbose, nsweeps=nsweeps,
                                  nmerge_sweeps=nmerge_sweeps,
                                  dense=dense,
                                  epsilon=epsilon,
                                  sparse_thresh=sparse_thresh,
                                  checkpoint=checkpoint,
                                  minimize_state=minimize_state)
    else:
        state = NestedBlockState(g, bs=bs, deg_corr=deg_corr, eweight=eweight,
                                 vweight=vweight)

    if checkpoint is not None:
        def check_wrap(bstate, S, delta, nmoves, ms):
            if bstate is not None:
                checkpoint(state, S, delta, nmoves, minimize_state)
            else:
                checkpoint(None, S, delta, nmoves, minimize_state)
        chkp = check_wrap
    else:
        chkp = None


    dS = nested_tree_sweep(state, verbose=verbose,
                            nsweeps=nsweeps,
                            nmerge_sweeps=nmerge_sweeps,
                            r=r,
                            epsilon=epsilon,
                            sparse_thresh=sparse_thresh,
                            checkpoint=chkp,
                            minimize_state=minimize_state)

    bstack = state.get_bstack()

    return bstack, state.entropy()


def get_hierarchy_tree(bstack):
    r"""Obtain the nested hierarchical levels as a tree.

    This transforms a list of :class:`~graph_tool.Graph` instances, given by the
    ``bstack`` parameter, representing the inferred hierarchy at each level, into
    a single :class:`~graph_tool.Graph` containing the hierarchy tree.

    It is expected for each graph in ``bstack`` to contain an internal vertex
    property map named "b" which contains the node partition at the
    corresponding level.

    Returns
    -------

    tree : :class:`~graph_tool.Graph`
       A directed graph, where vertices are blocks, and a directed edge points
       to an upper to a lower level in the hierarchy.
    label : :class:`~graph_tool.PropertyMap`
       A vertex property map containing the block label for each node.
    """

    g = bstack[0]
    b = g.vp["b"]
    bstack = bstack[1:]

    t = Graph()

    t.add_vertex(g.num_vertices())
    label = t.vertex_index.copy("int")

    last_pos = 0
    for l, s in enumerate(bstack):
        pos = t.num_vertices()
        t.add_vertex(s.num_vertices())
        label.a[-s.num_vertices():] = arange(s.num_vertices())

        for v in g.vertices():
            w = t.vertex(int(v) + last_pos)
            u = t.vertex(b[v] + pos)
            t.add_edge(u, w)

        last_pos = pos
        g = s
        if g.num_vertices() == 1:
            break
        b = g.vp["b"]
    return t, label
For faster browsing, not all history is shown. View entire blame