Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T21:19:27.342Z Has data issue: false hasContentIssue false
  • English
  • Français

A variable neighborhood search method for a two-mode blockmodeling problem in social network analysis

Published online by Cambridge University Press:  30 July 2013

MICHAEL BRUSCO ,
PATRICK DOREIAN ,
PAULETTE LLOYD  and
DOUGLAS STEINLEY
MICHAEL BRUSCO
Affiliation:
College of Business, Florida State University, Tallahassee, FL, USA (e-mail: [email protected])
PATRICK DOREIAN
Affiliation:
Department of Sociology, University of Pittsburgh, Pittsburgh, PA, USA Faculty of Social Sciences, University of Ljubljana, Ljubljana, Slovenia
PAULETTE LLOYD
Affiliation:
AAAS Fellow and US Department of State, Washington, DC, USA
DOUGLAS STEINLEY
Affiliation:
Department of Psychological Sciences, University of Missouri–Columbia, Columbia, MO, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper presents a variable neighborhood search (VNS) algorithm that is specially designed for the blockmodeling of two-mode binary network matrices in accordance with structural equivalence. Computational results for 768 synthetic test networks revealed that the VNS heuristic outperformed a relocation heuristic (RH) and a tabu search (TS) method for the same problem. Next, the three heuristics were applied to two-mode network data pertaining to the votes of member countries on resolutions in the United Nations General Assembly. A comparative analysis revealed that the VNS heuristic often provided slightly better criterion function values than RH and TS, and that these small differences in criterion function values could sometimes be associated with substantial differences in the actual partitions obtained. Overall, the results suggest that the VNS heuristic is a promising approach for blockmodeling of two-mode binary networks. Recommendations for extensions to stochastic blockmodeling applications are provided.

Keywords

deterministic blockmodelingtwo-mode binary networksheuristicsvariable neighborhood searchUNGA voting data
Type
Research Article
Information
Network Science , Volume 1 , Issue 2 , August 2013 , pp. 191 - 212
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Batagelj, V., & Mrvar, A. (1998). Pajek—Program for large network analysis. Connections, 21, 47–57.Google Scholar
Batagelj, V., Mrvar, A., Ferligoj, A., & Doreian, P. (2004). Generalized blockmodeling with Pajek. Metodoloski Zvezki: Journal of the Statistical Society of Slovenia, 1, 455–467.Google Scholar
Brusco, M., Doreian, P., Mrvar, A., & Steinley, D. (2013). An exact algorithm for blockmodeling of two-mode network data. Journal of Mathematical Sociology, 37, 61–84.Google Scholar
Brusco, M. J. & Köhn, H.-F. (2009). Clustering qualitative data based on binary equivalence relations: A neighborhood search heuristic for the clique partitioning problem. Psychometrika, 74, 685–703.Google Scholar
Brusco, M., & Steinley, D. (2007). A variable neighborhood search method for generalized blockmodeling of two-mode binary matrices. Journal of Mathematical Psychology, 51, 325–338.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.CrossRefGoogle ScholarPubMed
Brusco, M. J., & Steinley, D. (2011). A tabu search heuristic for deterministic two-mode blockmodeling of binary network matrices. Psychometrika, 76, 612–633.Google Scholar
Clinton, J., Jackman, S., & Rivers, D. (2004). The statistical analysis of roll call data. American Political Science Review, 98, 1–16.Google Scholar
Davis, A., Gardner, B., & Gardner, M. R. (1941). Deep south. Chicago: University of Chicago Press.Google Scholar
Doreian, P., Batagelj, V., & Ferligoj, A. (2004). Generalized blockmodeling of two-mode network data. Social Networks, 26, 29–53.Google Scholar
Doreian, P., Batagelj, V., & Ferligoj, A. (2005). Generalized blockmodeling. Cambridge, UK: Cambridge University Press.Google Scholar
Doreian, P., Lloyd, P., & Mrvar, M. (2013). Partitioning large signed two-mode networks: Problems and prospects. Social Networks, 35, 178–203.Google Scholar
Galaskiewicz, J. (1985). Social organization of an urban grants economy. New York: Academic Press.Google Scholar
Grötschel, M., & Wakabayashi, Y. (1989). A cutting plane algorithm for a clustering problem. Mathematical Programming, 45, 59–96.Google Scholar
Grötschel, M., & Wakabayashi, Y. (1990). Facets of the clique partitioning polytope. Mathematical Programming, 47, 367–387.CrossRefGoogle Scholar
Hansen, P. & Mladenović, N. (1997). Variable neighborhood search for the p-median. Location Science, 5, 207–226.CrossRefGoogle Scholar
Hansen, P. & Mladenović, N. (2001). J-Means: A new local search heuristic for minimum sum of squares clustering. Pattern Recognition, 34, 405–413.CrossRefGoogle Scholar
Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2, 193–218.Google Scholar
Karrer, B., & Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E, 83, 016107(1–10). doi:10.1103/PhysRevE.83.01607.Google Scholar
Kim, S. Y., & Russett, B. (1996). The new politics of voting alignments in the United Nations General Assembly. International Organization, 50, 629–652.Google Scholar
Latapy, M., Magnien, C. & Del Vecchio, N. (2008). Basic notions for the analysis of large two-mode networks, Social Networks, 30, 31–48.Google Scholar
Lorrain, F., & White, H. C. (1971). Structural equivalence of individuals in social networks. Journal of Mathematical Sociology, 1, 49–80.Google Scholar
Madeira, S. C., & Oliveira, A. L. (2004). Biclustering algorithms for biological data analysis: A survey. IEEE Transactions in Computational Biology and Bioinformatics, 1, 24–45.Google Scholar
Mirkin, B., Arabie, P., & Hubert, L. J. (1995). Additive two-mode clustering: The error-variance approach revisited. Journal of Classification, 12, 243–263.CrossRefGoogle Scholar
Mische, A., & Pattison, P. (2000). Composing a civic arena: Publics, projects, and social settings. Poetics, 27, 163–194.Google Scholar
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers and Operations Research, 24, 1097–1100.Google Scholar
Poole, K. T. (2005). Spatial models of parliamentary voting. Cambridge, UK: Cambridge University Press.Google Scholar
Poole, K. T., Lewis, J., Lo, J., & Carroll, R. (2011). Scaling roll call votes with wnominate in R. Journal of Statistical Software, 42 (14), 1–21.Google Scholar
Poole, K. T., & Rosenthal, H. (1985). A spatial model for legislative roll call analysis. American Journal of Political Science, 29, 357–384.CrossRefGoogle Scholar
Prelić, A., Blueler, S., Zimmermann, P., Wille, A., Bühlmann, P., Gruissem, W.,. . . Zitzler, E. (2006). A systematic comparison and evaluation of biclustering methods for gene expression data. Bioinformatics, 22, 1122–1129.Google Scholar
Protti, F., Dantas da Silva, M., & Szwarcfiter, J. L. (2009). Applying modular decomposition to parameterized cluster editing problems. Theory of Computer Systems, 44, 91–104.Google Scholar
Règnier, S. (1965). Sur quelques aspects mathématiques des problèmes de classification automatique. I.C.C. Bulletin, 4, 175–191.Google Scholar
Schepers, J. & Van Mechelen, I. (2011). A two-mode clustering method to capture the nature of the dominant interaction pattern in large profile data matrices. Psychological Methods, 16, 361–371.Google Scholar
Selim, H. M., Askin, R. G., & Vakharia, A. J. (1998). Cell formation in group technology: Review, evaluation and directions for future research. Computers and Industrial Engineering, 34, 3–20.Google Scholar
Steinley, D. (2004). Properties of the Hubert-Arabie adjusted Rand index. Psychological Methods, 9, 386–396.Google Scholar
van Mechelen, I., Bock, H. H., & DeBoeck, P. (2004). Two-mode clustering methods: A structured overview. Statistical Methods in Medical Research, 13, 363–394.Google Scholar
van Rosmalen, J., Groenen, P. J. F., Trejos, J., & Castillo, W. (2009). Optimization strategies for two-mode partitioning. Journal of Classification, 26, 155–181.Google Scholar
van Uitert, M., Meuleman, W., & Wessels, L. (2008). Biclustering sparse binary genomic data. Journal of Computational Biology, 15, 1329–1345.Google Scholar
Voeten, E. (2000). Clashes in the assembly. International Organization, 54, 185–217.Google Scholar
Wasserman, S., & Faust, K. (1994). Social network analysis: Methods and applications. Cambridge: Cambridge University Press.Google Scholar
Wilderjans, T. F., Depril, D. & Van Mechelen, I. (2013). Additive biclustering: A comparison of one new and two existing ALS algorithms. Journal of Classification, 30, 56–74.Google Scholar