A new method for finding hierarchical subgroups from networks

We present a new method for decomposing a social network into an optimal number of hierarchical subgroups. With a perfect hierarchical subgroup defined as one in which every member is automorphically equivalent to each other, the method uses the REGGE algorithm to measure the similarities among nodes and applies the k-means method to group the nodes that have congruent profiles of dissimilarities with other nodes into various numbers of hierarchical subgroups. The best number of subgroups is determined by minimizing the intra-cluster variance of dissimilarity subject to the constraint that the improvement in going to more subgroups is better than a network whose n nodes are maximally dispersed in the n-dimensional space would achieve. We also describe a decomposability metric that assesses the deviation of a real network from the ideal one that contains only perfect hierarchical subgroups. Four well known network data sets are used to demonstrate the method and metric. These demonstrations indicate the utility of our approach and suggest how it can be used in a complementary way to Generalized Blockmodeling for hierarchical decomposition.