Deterministic Blockmodeling of Two-Mode Binary Networks Using a Two-Mode KL-Median Heuristic

Brusco, Michael; Stolze, Hannah J.; Hoffman, Michaela; Steinley, Douglas; Doreian, Patrick

doi:10.21307/joss-2018-007

Abstract

Deterministic blockmodeling of a two-mode binary network matrix based on structural equivalence is a well-known problem in the social network literature. Whether implemented in a standalone fashion, or embedded within a metaheuristic framework, a popular relocation heuristic (RH) has served as the principal solution tool for this problem. In this paper, we establish that a two-mode KL-median heuristic (TMKLMedH) seeks to optimize the same criterion as the RH for deterministic blockmodeling. The TMKLMedH runs much faster than the RH, so many more restarts of the TMKLMedH can be accomplished when the two methods are constrained to the same time limit. Three computational comparisons of RH and TMKLMedH were conducted using both synthetic and real-world networks. In all three comparisons, the superiority of TMKLMedH was unequivocal.

References

Arabie, P., Hubert, L., & Schleutermann, S. (1990). Blockmodels from the bond energy algorithm. Social Networks, 12, 99-126.
Search in Google Scholar Back to article
Baier, D., Gaul, W., & Schader, M. (1997). Two-mode overlapping clustering with applications in simultaneous benefit segmentation and market structuring. In Klar R. & Opitz O. (Eds), Classification and knowledge organization (pp. 557-566), Heidelberg: Springer.
Search in Google Scholar Back to article
Brusco, M. (2011). Analysis of two-mode network data using nonnegative matrix factorization. Social Networks, 33, 201-210.
Search in Google Scholar Back to article
Brusco, M., & Doreian, P. (2015a). A real-coded genetic algorithm for two-mode KL-means partitioning with application to homogeneity blockmodeling. Social Networks, 41, 26-35.
Search in Google Scholar Back to article
Brusco, M. J., & Doreian, P. (2015b). An exact algorithm for two-mode KL-means partitioning. Journal of Classification, 32, 481-515.
Search in Google Scholar Back to article
Brusco, M., Doreian, P., Lloyd, P., & Steinley, D. (2013a). A variable neighborhood search method for a two-mode blockmodeling problem in social network analysis, Network Science, 1 (2), 191-212.
Search in Google Scholar Back to article
Brusco, M., Doreian, P., Mrvar, A., & Steinley, D. (2013b). An exact algorithm for blockmodeling of two-mode network data. Journal of Mathematical Sociology, 37, 61-84.
Search in Google Scholar Back to article
Brusco, M. J., Doreian, P., & Steinley, D. (2016). Biclustering methods for one-mode asymmetric matrices. Behavior Research Methods, 48, 487-502.
Search in Google Scholar Back to article
Brusco, M., & Steinley, D. (2006). Inducing a blockmodel structure for two-mode binary data using seriation procedures. Journal of Mathematical Psychology, 50, 468-477.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Brusco, M. J., & Steinley, D. (2007b). A comparison of heuristic procedures for minimum within-cluster sums of squares partitioning. Psychometrika, 72, 583-600.
Search in Google Scholar Back to article
Brusco, M., & Steinley, D. (2011). A tabu search heuristic for deterministic two-mode blockmodeling of binary network matrices. Psychometrika, 76, 612-633.
Search in Google Scholar Back to article
Ceulemans, E., & Van Mechelen, I. (2005). Hierarchical classes models for three-way three-mode binary data: interrelations and model selection. Psychometrika, 70, 461-480.
Search in Google Scholar Back to article
Coombs, C. H. (1964). A theory of data. New York: Wiley.
Search in Google Scholar Back to article
Davis, A., Gardner, B., & Gardner, M. R. (1941). Deep south. Chicago, University of Chicago Press.
Search in Google Scholar Back to article
Doreian, P. (1979). On delineation of small group structure. In: Hudson, H. C. (Ed.), Classifying social data (pp. 215-230), San Francisco: Jossey-Bass.
Search in Google Scholar Back to article
Doreian, P., Batagelj, V., & Ferligoj, A. (2004). Generalized blockmodeling of two-mode network data. Social Networks, 26, 29-53.
Search in Google Scholar Back to article
Doreian, P., Batagelj, V., & Ferligoj, A. (2005). Generalized blockmodeling. Cambridge: Cambridge University Press.
Search in Google Scholar Back to article
Doreian, P., Lloyd, P., & Mrvar, A. (2013). Partitioning large signed two-mode networks: Problems and prospects. Social Networks, 35, 1-21.
Search in Google Scholar Back to article
Everett, M. G., & Borgatti, S. P. (2013). The dual-projection approach for two-mode networks. Social Networks, 35, 204-210.
Search in Google Scholar Back to article
Faust, K. (1997). Centrality in affiliation networks. Social Networks, 19, 157-191.
Search in Google Scholar Back to article
Forgy, E. W. (1965). Cluster analyses of multivariate data: Efficiency versus interpretability of classifications. Abstract in Biometrics, 21, 768-769.
Search in Google Scholar Back to article
Freeman, L. C. (1980). Q-analysis and the structure of friendship networks. International Journal of Man-Machine Studies, 12, 367-378.
Search in Google Scholar Back to article
Galaskiewicz, J. (1985). Social organization of an urban grants economy. New York: Academic Press.
Search in Google Scholar Back to article
Gaul, W., & Schader, M. (1996). A new algorithm for two-mode clustering. In Bock H. & Polasek W. (Eds.), Data analysis and information systems (pp. 15-23), Berlin: Springer.
Search in Google Scholar Back to article
Hansen, P., & Mladenović, N. (2001). J-Means: A new local search heuristic for minimum sum of squares clustering. Pattern Recognition, 34, 405-413.
Search in Google Scholar Back to article
Hansohm, J. (2002). Two-mode clustering with genetic algorithms. In Gaul W. & Ritter G. (Eds.), Classification, automation and new media (pp. 87-93), Berlin: Springer.
Search in Google Scholar Back to article
Harper, F. M., & Konstan, J. A. (2015). The MovieLens datasets: History and context. ACM Transactions on Interactive and Intelligent Systems, 5 (4), Article 19, 1-19.
Search in Google Scholar Back to article
Hubert, L. (1974). Problems of seriation using a subject by item response matrix. Psychological Bulletin, 81, 976-983.
Search in Google Scholar Back to article
Hubert L, & Arabie P. (1985). Comparing partitions. Journal of Classification, 2, 195-218.
Search in Google Scholar Back to article
Lorrain, F., & White, H. C. (1971). Structural equivalence of individuals in social networks. Journal of Mathematical Sociology, 1, 49-80.
Search in Google Scholar Back to article
MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. In Le Cam L. M. & Neyman J. (Eds.), Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1 (pp. 281-297), Berkeley, CA: University of California Press.
Search in Google Scholar Back to article
Milligan, G. W. (1980). An examination of the effects of six types of error perturbation on fifteen clustering algorithms. Psychometrika, 45, 325-342.
Search in Google Scholar Back to article
Mische, A., & Pattison, P. (2000). Composing a civic arena: Publics, projects, and social settings. Poetics, 27, 163-194.
Search in Google Scholar Back to article
Opsahl, T. (2013). Triadic closure in two-mode networks: Redefining the global and local clustering coefficients. Social Networks, 35, 159-167.
Search in Google Scholar Back to article
Pattison, P. E. (1993). Algebraic models for social networks. New York: Cambridge University Press.
Search in Google Scholar Back to article
Pattison, P. E., & Bartlett, W. K. (1982). A factorization procedure for finite algebras. Journal of Mathematical Psychology, 25, 51-81.
Search in Google Scholar Back to article
Pattison, P. E., & Brieger, R. L. (2002). Lattices and dimensional representations: matrix decompositions and ordering structures. Social Networks, 24, 423-444.
Search in Google Scholar Back to article
Späth, H. (1980). Cluster analysis algorithms for data reduction and classification of objects. Chichester, England: Ellis Horwood.
Search in Google Scholar Back to article
Steinhaus, H. (1956). Sur la division des corps matériels en parties. Bulletin de l’Académie Polonaise des Sciences, Classe III, IV(12), 801-804.
Search in Google Scholar Back to article
Steinley, D. (2004). Properties of the Hubert-Arabie adjusted Rand index. Psychological Methods, 9, 386-396.
Search in Google Scholar Back to article
Steinley, D. (2006a). K-means clustering: A half-century synthesis. British Journal of Mathematical and Statistical Psychology, 59, 1-34.
Search in Google Scholar Back to article
Steinley, D. (2006b). Profiling local optima in K-means clustering: Developing a diagnostic technique. Psychological Methods, 11, 178-192.
Search in Google Scholar Back to article
Trejos, J., & Castillo, W. (2000). Simulated annealing optimization for two-mode partitioning. In Gaul, W., Decker, R. (Eds.), Classification and information at the turn of the millennium (pp. 135-142), Heidelberg: Springer.
Search in Google Scholar Back to article
van Rosmalen, J., Groenen, P. J. F., Trejos, J., & Castillo, W. (2009). Optimization strategies for two-mode partitioning. Journal of Classification, 26, 155-181.
Search in Google Scholar Back to article
Vichi, M. (2001). Double K-means clustering for simultaneous classification of objects and variables. In Borra, S., Rocchi, R., Schader, M. (Eds.), Advances in classification and data analysis – studies in classification, data analysis and knowledge organization (pp. 43-52), Heidelberg: Springer.
Search in Google Scholar Back to article
Wasserman, S., & Faust, K. (1994). Social network analysis: methods and applications. Cambridge: Cambridge University Press.
Search in Google Scholar Back to article
Wilderjans, T. F., Ceulemans, E., & Meers, K. (2013). CHull: A generic convex hull based model selection method. Behavior Research Methods, 45, 1-15.
Search in Google Scholar Back to article
Xu, W., Liu, X, & Gong, Y. (2001). Document clustering based on non-negative matrix factorization. Proceedings of the 26th ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 267-273.
Search in Google Scholar Back to article

Deterministic Blockmodeling of Two-Mode Binary Networks Using a Two-Mode KL-Median Heuristic

Abstract

Paradigm

My account