Computing core/periphery structures and permutation tests for social relations data

The core/periphery structure is ubiquitous in network studies. The discrete version of the concept is that individuals in a group belong to either the core, which has a high density of ties, or to the periphery, which has a low density of ties. The density of ties between the core and the periphery may be either high or low. If the core/periphery structure is given a priori, then there is no problem in finding a suitable statistical test. Often, however, the structure is not given, which presents us with two problems, searching for the optimal core/periphery structure, and devising a valid statistical test to replace the one invalidated by the search. UCINET [Borgatti, S.P., Everett, M.G., Freeman, L.C., 2002. UCINET for Windows, Version 6.59: Software for Social Network Analysis. Analytic Technologies, Harvard], the oldest and most trusted network program, gives incorrect answers in some simple cases for the first problem and does not address the second. This paper solves both problems with an adaptation of the Kernighan–Lin search algorithm, and with a permutation test incorporating this algorithm.     

An exact algorithm for a core/periphery bipartitioning problem

The discrete optimization problem associated with partitioning a set of actors into core and periphery subsets has typically been approached using approximate procedures such as exchange heuristics, genetic algorithms, and simulated annealing. Although these procedures are effective and scalable for large networks, they do not guarantee an optimal bipartition. In this paper, an exact algorithm is presented for a core/periphery bipartitioning problem. Unlike the approximate procedures in the extant literature, this new algorithm, which is based on the principles of branch-and-bound programming, affords a guarantee of an optimal bipartition. Computational results for empirical and simulated data sets reveal that the proposed algorithm is extremely efficient for networks with 40 or fewer actors, and is often scalable for networks with up to 60 actors.     

Dense core model for cohesive subgraph discovery

Discovery of cohesive subgraphs is an important issue in social network analysis. As representative cohesive subgraphs, pseudo cliques have been developed by relaxing the perfection of cliques. By enumerating pseudo clique subgraphs, we can find some structures of interest such as a star-like structure. However, a little more complicated structures such as a core/periphery structure is still hard to be found by them. Therefore, we propose a novel pseudo clique called ρ-dense core and show the connection with the other pseudo cliques. Moreover, we show that a set of ρ-dense core subgraphs gives an optimal solution in a graph partitioning problem. Several experiments on real-life networks demonstrated the effectiveness for cohesive subgraph discovery.     

Using modern methods for missing data analysis with the social relations model: A bridge to social network analysis

Social network analysis identifies social ties, and perceptual measures identify peer norms. The social relations model (SRM) can decompose interval-level perceptual measures among all dyads in a network into multiple person- and dyad-level components. This study demonstrates how to accommodate missing round-robin data using Bayesian data augmentation, including how to incorporate partially observed covariates as auxiliary correlates or as substantive predictors. We discuss how data augmentation opens the possibility to fit SRM to network ties (potentially without boundaries) rather than round-robin data. An illustrative application explores the relationship between sorority members’ self-reported body comparisons and perceptions of friends’ body talk.