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...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Elsevier
2015
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/e88f117aa75044cc8f71d66f29bed6af |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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. |
|---|