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:
- 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.
- 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