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
Go to the corresponding LIPIcs Volume Portal

Bille, Alexander ; Grüttemeier, Niels ; Komusiewicz, Christian ; Morawietz, Nils

A Graph-Theoretic Formulation of Exploratory Blockmodeling

LIPIcs-SEA-2023-14.pdf (2 MB)


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

  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 =		{},
  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}

Keywords: Clustering, Exact Algorithms, ILP-Formulation, Branch-and-Bound, Social Networks
Collection: 21st International Symposium on Experimental Algorithms (SEA 2023)
Issue Date: 2023
Date of publication: 19.07.2023
Supplementary Material: Software (Source Code and Results): archived at:

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI