Skip to main content
SpringerLink
Log in

A Tabu-Search Heuristic for Deterministic Two-Mode Blockmodeling of Binary Network Matrices

  • Published:
Psychometrika Aims and scope Submit manuscript

Abstract

Two-mode binary data matrices arise in a variety of social network contexts, such as the attendance or non-attendance of individuals at events, the participation or lack of participation of groups in projects, and the votes of judges on cases. A popular method for analyzing such data is two-mode blockmodeling based on structural equivalence, where the goal is to identify partitions for the row and column objects such that the clusters of the row and column objects form blocks that are either complete (all 1s) or null (all 0s) to the greatest extent possible. Multiple restarts of an object relocation heuristic that seeks to minimize the number of inconsistencies (i.e., 1s in null blocks and 0s in complete blocks) with ideal block structure is the predominant approach for tackling this problem. As an alternative, we propose a fast and effective implementation of tabu search. Computational comparisons across a set of 48 large network matrices revealed that the new tabu-search heuristic always provided objective function values that were better than those of the relocation heuristic when the two methods were constrained to the same amount of computation time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aarts, E., & Korst, J. (1989). Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing. New York: Wiley.

    Google Scholar 

  • Airoldi, E.M., Blei, D.M., Fienberg, S.E., & Xing, E.P. (2008). Mixed-membership stochastic blockmodels. Journal of Machine Learning Research, 9, 1981–2014.

    PubMed  Google Scholar 

  • Arabie, P., Hubert, L., & Schleutermann, S. (1990). Blockmodels from the bond energy algorithm. Social Networks, 12, 99–126.

    Article  Google Scholar 

  • Batagelj, V., Ferligoj, A., & Doreian, P. (1992). Direct and indirect methods for structural equivalence. Social Networks, 14, 63–90.

    Article  Google Scholar 

  • Bickel, P.J., & Chen, A. (2009). A nonparametric view of network models and Newman-Girvan and other modularities. Proceedings of the National Academy of Sciences, 106, 21068–21073.

    Article  Google Scholar 

  • Borgatti, S.P., & Everett, M.G. (1997). Network analysis of 2-mode data. Social Networks, 19, 243–269.

    Article  Google Scholar 

  • Borgatti, S.P., Everett, M.G., & Freeman, L. (2002). Ucinet for Windows: software for social network analysis. Harvard: Analytic Technologies.

    Google Scholar 

  • Breiger, R.L., Boorman, S.A., & Arabie, P. (1975). An algorithm for clustering relational data with applications to social network analysis and comparison to multidimensional scaling. Journal of Mathematical Psychology, 12, 328–383.

    Article  Google Scholar 

  • Brusco, M., Doreian, P., Mrvar, A., & Steinley, D. (2011). Linking theory, models, and data to understand social network phenomena: two algorithms for relaxed structural balance partitioning. Sociological Methods & Research, 40, 57–87.

    Article  Google Scholar 

  • Brusco, M.J., & Köhn, H.F. (2009). Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem. Psychometrika, 74, 685–703.

    Article  Google Scholar 

  • Brusco, M.J., & Stahl, S. (2001). An interactive approach to multiobjective combinatorial data analysis. Psychometrika, 66, 5–24.

    Article  Google Scholar 

  • Brusco, M.J., & Stahl, S. (2005). Optimal least-squares unidimensional scaling: improved branch-and-bound procedures and comparison to dynamic programming. Psychometrika, 70, 253–270.

    Article  Google Scholar 

  • Brusco, M., & Steinley, D. (2006). Inducing a blockmodel structure of two-mode binary data using seriation procedures. Journal of Mathematical Psychology, 50, 468–477.

    Article  Google Scholar 

  • Brusco, M., & Steinley, D. (2007a). A variable neighborhood search method for generalized blockmodeling of two-mode binary matrices. Journal of Mathematical Psychology, 51, 325–338.

    Article  Google Scholar 

  • Brusco, M.J., & Steinley, D. (2007b). A comparison of heuristic procedures for minimum within-cluster sums of squares partitioning. Psychometrika, 72, 583–600.

    Article  Google Scholar 

  • Brusco, M.J., & Steinley, D. (2009). Integer programs for one- and two-mode blockmodeling based on prespecified image matrices for structural and regular equivalence. Journal of Mathematical Psychology, 53, 577–585.

    Article  Google Scholar 

  • Brusco, M., & Steinley, D. (2010). K-balance partitioning: an exact method with application to generalized structural balance and other psychological contexts. Psychological Methods, 15, 145–157.

    Article  PubMed  Google Scholar 

  • Charon, I., & Hudry, O. (2006). Noising methods for a clique partitioning problem. Discrete Applied Mathematics, 154, 754–769.

    Article  Google Scholar 

  • Clapham, C. (1996). The concise Oxford dictionary of mathematics (2nd ed.). Oxford: Oxford University Press.

    Google Scholar 

  • Davis, A., Gardner, B., & Gardner, M.R. (1941). Deep south. Chicago: University of Chicago Press.

    Google Scholar 

  • De Amorim, S.G., Barthélemy, J.-P., & Ribeiro, C.C. (1992). Clustering and clique partitioning: simulated annealing and tabu search approaches. Journal of Classification, 9, 17–41.

    Article  Google Scholar 

  • Doreian, P., Batagelj, V., & Ferligoj, A. (2004). Generalized blockmodeling of two-mode network data. Social Networks, 26, 29–53.

    Article  Google Scholar 

  • Doreian, P., Batagelj, V., & Ferligoj, A. (2005). Generalized blockmodeling. Cambridge: Cambridge University Press.

    Google Scholar 

  • Doreian, P., & Mrvar, A. (1996). A partitioning approach to structural balance. Social Networks, 18, 149–168.

    Article  Google Scholar 

  • Doreian, P., & Mrvar, A. (2009). Partitioning signed social networks. Social Networks, 31, 1–11.

    Article  Google Scholar 

  • Fienberg, S.E., Meyer, M.M., & Wasserman, S.S. (1985). Statistical analysis of multiple sociometric relations. Journal of the American Statistical Association, 80, 51–67.

    Article  Google Scholar 

  • Freeman, L.C. (2003). Finding social groups: a meta-analysis of the Southern Women data. In R. Brieger, C. Carley, & P. Pattison (Eds.), Dynamic social network modeling and analysis: workshop summary and papers (pp. 39–97). Washington: The National Academies Press.

    Google Scholar 

  • Glover, F., & Laguna, M. (1993). Tabu search. In C. Reeves (Ed.), Modern heuristic techniques for combinatorial problems (pp. 70–141). Oxford: Blackwell.

    Google Scholar 

  • Goldberg, D.E. (1989). Genetic algorithms in search, optimization, and machine learning. New York: Addison-Wesley.

    Google Scholar 

  • Goldenberg, A., Zheng, A., Fienberg, S.E., & Airoldi, E.M. (2009). A survey of statistical network models. Foundations and Trends in Machine Learning, 2, 1–117.

    Article  Google Scholar 

  • Govaert, G., & Nadif, M. (2003). Clustering with block mixture models. Pattern Recognition, 36, 463–473.

    Article  Google Scholar 

  • Groenen, P.J.F., & Heiser, W.J. (1996). The tunneling method for global optimization in multidimensional scaling. Psychometrika, 61, 529–550.

    Article  Google Scholar 

  • Hand, D.J. (1981). Discrimination and classification. New York: Wiley.

    Google Scholar 

  • Handcock, M.S., Raftery, A.E., & Tantrum, J. (2007). Model-based clustering for social networks (with discussion). Journal of the Royal Statistical Society A, 170, 301–354.

    Article  Google Scholar 

  • Hartigan, J. (1972). Direct clustering of a data matrix. Journal of the American Statistical Association, 67, 123–129.

    Article  Google Scholar 

  • Heller, J. (1961). Catch-22: a novel. New York: Simon and Schuster.

    Google Scholar 

  • Holland, P.W., & Leinhardt, S. (1976). Local structure in social networks. Sociological Methodology, 7, 1–45.

    Article  Google Scholar 

  • Holland, P.W., & Leinhardt, S. (1977). A dynamic model for social networks. Journal of Mathematical Sociology, 5, 5–20.

    Article  Google Scholar 

  • Holland, P.W., & Leinhardt, S. (1981). An exponential family of probability distributions for directed graphs (with discussion). Journal of the American Statistical Association, 76, 33–65.

    Article  Google Scholar 

  • Holland, P.W., Laskey, K.B., & Leinhardt, S. (1983). Stochastic blockmodels: first steps. Social Networks, 5, 109–137.

    Article  Google Scholar 

  • Homans, G.C. (1950). The human group. New York: Harcourt-Brace.

    Google Scholar 

  • Kaiser, S., & Leisch, F. (2008). A toolbox for bicluster analysis in R (Technical Report 028). Munich: Department of Statistics, University of Munich.

  • Koyutürk, M., Szpanowski, W., & Grama, A. (2004). Biclustering gene-feature matrices for statistically significant patterns. In Proceedings of the 2004 IEEE computational systems bioinformatics conference (pp. 480–484). Washington: IEEE Comput. Soc.

    Google Scholar 

  • Krolak-Schwerdt, S. (2003). Two-mode clustering methods: compare and contrast. In M. Schader, W. Gaul, & M. Vichi (Eds.), Between data science and applied data analysis (pp. 270–278). Berlin: Springer.

    Chapter  Google Scholar 

  • Lauritzen, S.L. (2008). Exchangeable Rasch matrices. Rendiconti di Matematica, 28, 83–95.

    Google Scholar 

  • Lorrain, F., & White, H.C. (1971). Structural equivalence of individuals in social networks. Journal of Mathematical Sociology, 1, 49–80.

    Article  Google Scholar 

  • Madeira, S.C., & Oliveira, A.L. (2004). Biclustering algorithms for biological data analysis: a survey. IEEE/ACM Transactions on Computational Biology and Informatics, 1, 24–45.

    Article  Google Scholar 

  • McLachlan, G.J. (2011). Commentary on Steinley and Brusco (2011): recommendations and cautions. Psychological Methods, 16, 80–81.

    Article  PubMed  Google Scholar 

  • Mische, A., & Pattison, P. (2000). Composing a civic arena: publics, projects, and social settings. Poetics, 27, 163–194.

    Article  Google Scholar 

  • Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24, 1097–1100.

    Article  Google Scholar 

  • Mrvar, A., & Doreian, P. (2009). Partitioning signed two-mode networks. Journal of Mathematical Sociology, 33, 196–221.

    Article  Google Scholar 

  • Mulvey, J.M., & Crowder, H.P. (1979). Cluster analysis: an application of Lagrangian relaxation. Management Science, 25, 329–340.

    Article  Google Scholar 

  • Newman, M.E.J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69, 026113. doi:10.1103/PhysRevE.69.026113.

    Article  Google Scholar 

  • Nowicki, K., & Snijders, T.A.B. (2001). Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association, 96, 1077–1087.

    Article  Google Scholar 

  • Pacheco, J., & Valencia, O. (2003). Design of hybrids for the minimum sum-of-squares clustering problem. Computational Statistics and Data Analysis, 43, 235–248.

    Google Scholar 

  • Pattison, P.E., & Breiger, R.L. (2002). Lattices and dimensional representations: matrix decompositions and ordering structures. Social Networks, 24, 423–444.

    Article  Google Scholar 

  • Prelić, A., Blueler, S., Zimmerman, P., Wille, A., Bühlmann, P., Gruissem, W., Hennig, L., Thiele, L., & Zitzler, E. (2006). A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics, 22, 1122–1129.

    Article  PubMed  Google Scholar 

  • Rolland, E., Schilling, D.A., & Current, J.R. (1996). An efficient tabu search procedure for the p-median problem. European Journal of Operational Research, 96, 329–342.

    Article  Google Scholar 

  • Steinhaus, H. (1956). Sur la division des corps matétiels en parties. Bulletin de l’Académie Polonaise des Sciences, Classe III, IV(12), 801–804.

    Google Scholar 

  • Steinley, D., & Brusco, M.J. (2011a). An evaluation of mixture model clustering: recommendations and cautions. Psychological Methods, 16, 63–79.

    Article  PubMed  Google Scholar 

  • Steinley, D., & Brusco, M.J. (2011b). K-means clustering and mixture model clustering: reply to McLachlan and Vermunt. Psychological Methods, 16, 89–92.

    Article  Google Scholar 

  • van Rosmalen, J., Groenen, P.J.F., Trejos, P., & Castillo, W. (2009). Optimization strategies for two-mode partitioning. Journal of Classification, 26, 155–181.

    Article  Google Scholar 

  • van Uitert, M., Meuleman, W., & Wessels, L. (2008). Biclustering sparse binary genomic data. Journal of Computational Biology, 15, 1329–1345.

    Article  PubMed  Google Scholar 

  • Vermunt, J. (2011). K-means may perform as well as mixture model clustering but may also be much worse: comment on Steinley and Brusco (2011). Psychological Methods, 16, 82–88.

    Article  PubMed  Google Scholar 

  • von Luxburg, U. (2007). A tutorial on spectral clustering. Statistical Computing, 17, 395–416.

    Article  Google Scholar 

  • Ward, J.H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58, 236–244.

    Article  Google Scholar 

  • Wasserman, S., & Faust, K. (1994). Social network analysis: methods and applications. Cambridge: Cambridge University Press.

    Google Scholar 

  • White, D.R., & Reitz, K.P. (1983). Graph and semigroup homomorphisms on networks of relations. Social Networks, 5, 193–234.

    Article  Google Scholar 

  • Xu, W., Liu, X., & Gong, Y. (2003). Document clustering based on non-negative matrix factorization. In SIGIR‘03: proceedings of the 26th annual international ACM SIGIR conference on research and development in information retrieval (pp. 267–273). New York: Association for Computing Machinery.

    Google Scholar 

  • Žiberna, A. (2007). Generalized blockmodeling of valued networks. Social Networks, 29, 105–126.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Marketing, College of Business, Florida State University, Tallahassee, FL, 32306-1110, USA

    Michael Brusco

  2. Department of Psychological Sciences, University of Missouri-Columbia, Columbia, MO, USA, 65211

    Douglas Steinley

Authors
  1. Michael Brusco
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Douglas Steinley
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael Brusco.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brusco, M., Steinley, D. A Tabu-Search Heuristic for Deterministic Two-Mode Blockmodeling of Binary Network Matrices. Psychometrika 76, 612–633 (2011). https://doi.org/10.1007/s11336-011-9221-9

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11336-011-9221-9

Keywords

Search

Navigation