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

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

Algorithm · Data mining · Discrete mathematics · Equivalence (formal languages · Heuristic · Heuristics · Mathematical optimization · Metaheuristic · Tabu search · Variable neighborhood search · Complex Network Analysis Techniques · Computer Science · Mathematics · Artificial Intelligence · Theoretical Computer Science

• Detecting Clusters/Communities in Social Networks

  M Hoffman, Douglas Steinley et al.•Multivariate Behavioral Research•2018

  Incluir item

• Eigenvector centrality and structural zeroes and ones

  Open Access•Phillip Bonacich, Paulette Lloyd•Social Networks•2015

  Incluir item

• Finding roles in sparse economic hierarchies

  Open Access•L Prota, P Doreian•Social Networks•2016

  Incluir item

• A real-coded genetic algorithm for two-mode KL-means partitioning with application to homogeneity blockmodeling

  Open Access•Michael J Brusco, Michael Brusco et al.•Social Networks•2015

  Incluir item

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

  Open Access•Michael J Brusco, Michael Brusco et al.•Journal of Social Structure•2018

  Incluir item

• Partitioning signed networks using relocation heuristics, tabu search, and variable neighborhood search

  Open Access•Michael J Brusco, P Doreian•Social Networks•2018

  Incluir item

• Inferring structure in bipartite networks using the latent blockmodel and exact ICL

  Open Access•Jason Wyse, Nial Friel et al.•Network Science•2017

  Incluir item

• Generalized Blockmodeling

  Open Access•P Doreian, Vladimir Batagelj et al.•Generalized Blockmodeling•2004

  Incluir item

• Spatial Models of Parliamentary Voting

  Open Access•Keith T Poole•Spatial Models of Parliamentary…•2005

  Incluir item

• Social Network Analysis

  Open Access•Stanley Wasserman, Katherine Faust•Social Network Analysis•1994

  Incluir item

• Comparing partitions

  Open Access•Lawrence J Hubert, Lawrence Hubert et al.•Journal of Classification•1985

  Incluir item

• Stochastic blockmodels and community structure in networks

  Open Access•Brian Karrer, M E J Newman•Physical Review E•2011

  Incluir item

• Generalized blockmodeling of two-mode network data

  Open Access•P Doreian, Vladimir Batagelj et al.•Social Networks•2004

  Incluir item

• Partitioning large signed two-mode networks

  Open Access•P Doreian, Paulette Lloyd et al.•Social Networks•2012

  Incluir item

• Basic notions for the analysis of large two-mode networks

  Open Access•Matthieu Latapy, Clémence Magnien et al.•Social Networks•2007

  Incluir item

• Structural equivalence of individuals in social networks

  Francois Lorrain, Harrison C White•Journal of Mathematical Sociology•1971

  Incluir item

• An Exact Algorithm for Blockmodeling of Two-Mode Network Data

  Michael J Brusco, Michael Brusco et al.•Journal of Mathematical Sociology•2013

  Incluir item

• Clashes in the Assembly

  Open Access•Erik Voeten•International Organization•2000

  Incluir item

• The new politics of voting alignments in the United Nations General Assembly

  Open Access•Soo Yeon Kim, Bruce Russett•International Organization•1996

  Incluir item

• A Spatial Model for Legislative Roll Call Analysis

  Keith T Poole, Howard Rosenthal et al.•American Journal of Political…•1985

  Incluir item

• Composing a civic arena

  Open Access•Ann Mische, P Pattison•Poetics•2000

  Incluir item

• The Statistical Analysis of Roll Call Data

  Open Access•Joshua D Clinton, Joshua Clinton et al.•American Political Science Review•2004

  Incluir item