License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2023.14
URN: urn:nbn:de:0030-drops-183648
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18364/
Bille, Alexander ;
Grüttemeier, Niels ;
Komusiewicz, Christian ;
Morawietz, Nils
A Graph-Theoretic Formulation of Exploratory Blockmodeling
Abstract
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.
BibTeX - Entry
@InProceedings{bille_et_al:LIPIcs.SEA.2023.14,
author = {Bille, Alexander and Gr\"{u}ttemeier, Niels and Komusiewicz, Christian and Morawietz, Nils},
title = {{A Graph-Theoretic Formulation of Exploratory Blockmodeling}},
booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)},
pages = {14:1--14:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-279-2},
ISSN = {1868-8969},
year = {2023},
volume = {265},
editor = {Georgiadis, Loukas},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18364},
URN = {urn:nbn:de:0030-drops-183648},
doi = {10.4230/LIPIcs.SEA.2023.14},
annote = {Keywords: Clustering, Exact Algorithms, ILP-Formulation, Branch-and-Bound, Social Networks}
}
