Evaluating the quality of image matrices in blockmodeling

One approach for analyzing large networks is to partition its nodes into classes where the nodes in a class have similar characteristics with respect to their connections in the network. A class is represented as a blockmodel (or image matrix). In this context, a specific question is to test whether...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Stefan Wiesberg, Gerhard Reinelt
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2015
Materias:	80-08 90C11 90B10 05C82 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/e88f117aa75044cc8f71d66f29bed6af
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:e88f117aa75044cc8f71d66f29bed6af
record_format	dspace
spelling	oai:doaj.org-article:e88f117aa75044cc8f71d66f29bed6af2021-12-02T05:00:43ZEvaluating the quality of image matrices in blockmodeling2192-440610.1007/s13675-015-0034-yhttps://doaj.org/article/e88f117aa75044cc8f71d66f29bed6af2015-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000411https://doaj.org/toc/2192-4406One approach for analyzing large networks is to partition its nodes into classes where the nodes in a class have similar characteristics with respect to their connections in the network. A class is represented as a blockmodel (or image matrix). In this context, a specific question is to test whether a presumed blockmodel is well reflected in the network or to select from a choice of possible blockmodels the one fitting best. In this paper, we formulate these problems as combinatorial optimization problems. We show that the evaluation of a blockmodel’s quality is a generalization of well-known optimization problems such as quadratic assignment, minimum k-cut, traveling salesman, and minimum edge cover. A quadratic integer programming formulation is derived and linearized by making use of properties of these special cases. With a branch-and-cut approach, the resulting formulation is solved up to 10,000 times faster than a comparable formulation from the literature.Stefan WiesbergGerhard ReineltElsevierarticle80-0890C1190B1005C82Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 3, Iss 2, Pp 111-129 (2015)
institution	DOAJ
collection	DOAJ
language	EN
topic	80-08 90C11 90B10 05C82 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	80-08 90C11 90B10 05C82 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Stefan Wiesberg Gerhard Reinelt Evaluating the quality of image matrices in blockmodeling
description	One approach for analyzing large networks is to partition its nodes into classes where the nodes in a class have similar characteristics with respect to their connections in the network. A class is represented as a blockmodel (or image matrix). In this context, a specific question is to test whether a presumed blockmodel is well reflected in the network or to select from a choice of possible blockmodels the one fitting best. In this paper, we formulate these problems as combinatorial optimization problems. We show that the evaluation of a blockmodel’s quality is a generalization of well-known optimization problems such as quadratic assignment, minimum k-cut, traveling salesman, and minimum edge cover. A quadratic integer programming formulation is derived and linearized by making use of properties of these special cases. With a branch-and-cut approach, the resulting formulation is solved up to 10,000 times faster than a comparable formulation from the literature.
format	article
author	Stefan Wiesberg Gerhard Reinelt
author_facet	Stefan Wiesberg Gerhard Reinelt
author_sort	Stefan Wiesberg
title	Evaluating the quality of image matrices in blockmodeling
title_short	Evaluating the quality of image matrices in blockmodeling
title_full	Evaluating the quality of image matrices in blockmodeling
title_fullStr	Evaluating the quality of image matrices in blockmodeling
title_full_unstemmed	Evaluating the quality of image matrices in blockmodeling
title_sort	evaluating the quality of image matrices in blockmodeling
publisher	Elsevier
publishDate	2015
url	https://doaj.org/article/e88f117aa75044cc8f71d66f29bed6af
work_keys_str_mv	AT stefanwiesberg evaluatingthequalityofimagematricesinblockmodeling AT gerhardreinelt evaluatingthequalityofimagematricesinblockmodeling
_version_	1718400863545851904

Evaluating the quality of image matrices in blockmodeling

Ejemplares similares