2026-07-25T14:07:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18364 2024-03-06T11:01:36Z ddc:004 open_access

A Graph-Theoretic Formulation of Exploratory Blockmodeling Bille, Alexander Grüttemeier, Niels Komusiewicz, Christian Morawietz, Nils Clustering Exact Algorithms ILP-Formulation Branch-and-Bound Social Networks We 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Bille and Niels Grüttemeier and Christian Komusiewicz and Nils Morawietz 2023 Is Part Of LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2023.14 urn:nbn:de:0030-drops-183648 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.14 eng https://creativecommons.org/licenses/by/4.0/legalcode