Alternative Blockmodelling

Oscar Correa, Jeffrey Chan, Xuan Vinh Nguyen

Abstract

Traditional network analysis often focuses on community detection—identifying groups with dense internal connections. However, networks frequently harbor multiple, overlapping structural patterns, such as core-periphery or hierarchical arrangements, that are obscured by the dominant community paradigm. This paper introduces "Alternative Blockmodelling," a framework utilizing Symmetric Non-negative Matrix Tri-Factorization (SNMTF) to uncover distinct, high-quality summaries of network topology. By incorporating constraints that penalize similarity to known models, the authors demonstrate the ability to reveal hidden latent configurations in classic datasets like Zachary’s Karate Club and American political book networks.

1. Introduction

In network science, the search for "communities"—subsets of nodes more densely connected to each other than to the rest of the graph—has long been the primary method for structural analysis. While effective, this approach assumes a single "correct" partition and often overlooks alternative structural roles. For instance, a network might simultaneously exhibit a community structure based on shared interests and a core-periphery structure based on influence or hierarchy.

"Alternative Blockmodelling" addresses this gap by extending the concept of alternative clustering—well-established in tabular data—to relational networks. The goal is to provide a systematic way to generate a secondary model that is both high-quality (fitting the data well) and significantly different from a known reference model.

2. Methodology

The framework is built upon Symmetric Non-negative Matrix Tri-Factorization (SNMTF). Given an adjacency matrix $A$, the method seeks to approximate it as:

$$A \approx CMC^T$$

where:

  • $C$ is the node membership matrix, assigning nodes to specific "positions."
  • $M$ is the image matrix, providing a high-level summary of how these positions relate to one another.

Unlike standard community detection, which often restricts $M$ to be diagonal (indicating only within-group connections), this blockmodelling approach allows $M$ to take any non-negative form. This flexibility enables the discovery of non-assortative structures like bipartite or core-periphery roles.

2.1 Optimization Strategies

To find alternative models, the authors propose two distinct optimization functions:

  1. Cannot-Link Constraints: This method introduces a penalty for placing pairs of nodes in the same cluster if they were already grouped together in the reference model. This forces the algorithm to "shatter" existing communities to find new groupings.
  2. Image Matrix Dissimilarity: Rather than focusing on node-level assignments, this approach encourages the summary matrix $M$ to be as different as possible from the reference summary. This is particularly effective for moving from a community-based view (diagonal $M$) to a role-based view (e.g., core-periphery).

To ensure numerical stability and proper normalization of membership probabilities, the authors employ an Iterative Lagrangian Solution, which prevents the common pitfalls and instabilities found in standard NMF algorithms.

3. Experimental Evaluation

The authors tested their framework on several benchmark datasets to validate its ability to find meaningful alternatives:

  • Zachary’s Karate Club: A social network of 34 members. While the primary split is into two factions, the alternative model revealed a core-periphery structure where instructors acted as a central hub for a student periphery.
  • Books on American Politics: A network of 105 books. The primary model reflects political alignment (Liberal vs. Conservative). The alternative model uncovered a "two-tier" core-periphery structure, identifying the most influential "core" books within the broader ideological landscape.
  • Synthetic Data: A 50-node network designed with overlapping community and core-periphery structures. The algorithm successfully "unmixed" these signals, proving its ability to recover latent structures that are mathematically distinct.

4. Key Insights

The research highlights that community finding is merely a special case of blockmodelling. By relaxing the constraints on the image matrix $M$, researchers can move beyond simple grouping to understand complex social roles. A significant finding is the prevalence of core-periphery structures as valid alternatives to communities; many networks perceived as simple groups actually contain "power players" who mediate connections for the rest of the network.

Furthermore, the authors identify a fundamental trade-off between model quality and dissimilarity. By adjusting a trade-off parameter ($\beta$), users can navigate the search space between a model that perfectly fits the data and one that is entirely novel. The use of iVAT (Enhanced Visual Analysis for Cluster Tendency) further assists in visualizing the "search space" of these alternative solutions.

5. Conclusion and Future Work

Alternative Blockmodelling provides a robust mathematical foundation for exploring the multi-faceted nature of networks. While the current approach is highly effective, it remains sensitive to the choice of constraints and shows a slight bias toward core-periphery structures due to the normalization techniques used. Future research will focus on automating the selection of constraints and identifying "correct" alternative models without requiring a pre-defined target, making the exploration of complex relational data more autonomous.

Summary updated

Abstract

Many approaches have been proposed to discover clusters within networks. Community finding field encompasses approaches which try to discover clusters where nodes are tightly related within them but loosely related with nodes of other clusters. However, a community network configuration is not the only possible latent structure in a graph. Core-periphery and hierarchical network configurations are valid structures to discover in a relational dataset. On the other hand, a network is not completely explained by only knowing the membership of each node. A high level view of the inter-cluster relationships is needed. Blockmodelling techniques deal with these two issues. Firstly, blockmodelling allows finding any network configuration besides to the well-known community structure. Secondly, blockmodelling is a summary representation of a network which regards not only membership of nodes but also relations between clusters. Finally, a unique summary representation of a network is unlikely. Networks might hide more than one blockmodel. Therefore, our proposed problem aims to discover a secondary blockmodel representation of a network that is of good quality and dissimilar with respect to a given blockmodel. Our methodology is presented through two approaches, (a) inclusion of cannot-link constraints and (b) dissimilarity between image matrices. Both approaches are based on non-negative matrix factorisation NMF which fits the blockmodelling representation. The evaluation of these two approaches regards quality and dissimilarity of the discovered alternative blockmodel as these are the requirements of the problem.
BibTeX
@misc{correa2019alternative,
  author = {Oscar Correa and Jeffrey Chan and Xuan Vinh Nguyen},
  title = {{Alternative Blockmodelling}},
  year = {2019},
  eprint = {1908.02575},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.02575},
}
Figure