Research Article: A simulated annealing heuristic for maximum correlation core/periphery partitioning of binary networks

Date Published: May 9, 2017

Publisher: Public Library of Science

Author(s): Michael Brusco, Hannah J. Stolze, Michaela Hoffman, Douglas Steinley, Sergio Gómez.

http://doi.org/10.1371/journal.pone.0170448

Abstract

A popular objective criterion for partitioning a set of actors into core and periphery subsets is the maximization of the correlation between an ideal and observed structure associated with intra-core and intra-periphery ties. The resulting optimization problem has commonly been tackled using heuristic procedures such as relocation algorithms, genetic algorithms, and simulated annealing. In this paper, we present a computationally efficient simulated annealing algorithm for maximum correlation core/periphery partitioning of binary networks. The algorithm is evaluated using simulated networks consisting of up to 2000 actors and spanning a variety of densities for the intra-core, intra-periphery, and inter-core-periphery components of the network. Core/periphery analyses of problem solving, trust, and information sharing networks for the frontline employees and managers of a consumer packaged goods manufacturer are provided to illustrate the use of the model.

Partial Text

The problem of partitioning a set of actors into two clusters, core and periphery, is a well-studied problem in the social network literature [1–8]. Excellent recent reviews of core/periphery analysis are available in [9, 10]. Conceptually, the goal is to partition the actors so as to maximize the intra-core density, while minimizing the intra-periphery density. This goal can be operationalized in different ways. One approach employs a continuous model for developing a core-to-periphery continuum whereby a degree “coreness” is established for each actor [3, 5]. However, the continuous approach does not explicitly assign actors to core and periphery subsets. Contrastingly, the discrete core/periphery approaches explicitly allocate the actors into mutually exclusive and exhaustive subsets. Throughout the remainder of this paper, attention is restricted to discrete core/periphery methods.

To complete our analyses, we studied the efficiency and effectiveness of the simulated annealing algorithm by applying it to a larger binary network (n = 2114). The data correspond to a protein interaction network of yeast [31] and are available from several sources including: http://www3.nd.edu. We applied the 10 restarts of the simulated annealing algorithm to these data using ξ = 100,000. For comparison purposes, we also conducted maximum-correlation core/periphery partitioning using Ucinet [11].

We have presented a new simulated annealing algorithm for maximum correlation core/periphery partitioning of binary networks. The algorithm is exceptionally fast and requires minimal parameterization. A key component of the algorithm is that it uses an efficient process for updating the Pearson correlation measure between two binary vectors as trial solutions are generated. This is in contrast to some earlier implementations whereby trial solutions were evaluated by recomputing the correlation measure from scratch [2].

 

Source:

http://doi.org/10.1371/journal.pone.0170448

 

0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments