K-balance partitioning: an exact method with applications to generalized structural balance and other psychological contexts.
Structural balance theory (SBT) has maintained a venerable status in the psychological literature for more than 5 decades. One important problem pertaining to SBT is the approximation of structural or generalized balance via the partitioning of the vertices of a signed graph into K clusters. This K-balance partitioning problem also has more general psychological applications associated with the analysis of similarity/dissimilarity relationships among stimuli. Accordingly, K-balance partitioning can be gainfully used in a wide variety of SBT applications, such as attraction and child development, evaluation of group membership, marketing and consumer issues, and other psychological contexts not necessarily related to SBT. We present a branch-and-bound algorithm for the K-balance partitioning problem. This new algorithm is applied to 2 synthetic numerical examples as well as to several real-world data sets from the behavioral sciences literature.
Brusco
Michael
M
Department of Marketing, College of Business, Florida State University, Tallahassee, FL 32306-1110, USA. mbrusco@cob.fsu.edu
Steinley
Douglas
D
D000465:Algorithms; D016000:Cluster Analysis; D003627:Data Interpretation, Statistical; D006801:Humans; D008432:Mathematical Computing; D008960:Models, Psychological; D015233:Models, Statistical; D011582:Psychological Theory; D011584:Psychology / Q000706:statistics & numerical data*; D012984:Software