CC BY 4.0Bille, A.A.BilleGrüttemeier, NielsNielsGrüttemeierKomusiewicz, C.C.KomusiewiczMorawietz, N.N.Morawietz2023-10-262023-10-262023https://publica.fraunhofer.de/handle/publica/452278https://doi.org/10.24406/publica-208110.4230/LIPIcs.SEA.2023.1410.24406/publica-20812-s2.0-85168705948We present a new simple graph-Theoretic formulation of the exploratory blockmodeling problem on undirected and unweighted one-mode networks. Our formulation takes as input the network G and the maximum number t of blocks for the solution model. The task is to find a minimum-size set of edge insertions and deletions that transform the input graph G into a graph G with at most t neighborhood classes. Herein, a neighborhood class is a maximal set of vertices with the same neighborhood. The neighborhood classes of G directly give the blocks and block interactions of the computed blockmodel. We analyze the classic and parameterized complexity of the exploratory blockmodeling problem, provide a branch-And-bound algorithm, an ILP formulation and several heuristics. Finally, we compare our exact algorithms to previous ILP-based approaches and show that the new algorithms are faster for t ≥ 4.enBranch-And-BoundClusteringExact AlgorithmsILP-FormulationSocial Networksconference paper