Alternative Blockmodelling

Oscar Correa, Jeffrey Chan, Vinh Nguyen

Abstract

Many approaches have been proposed to discover clusters within networks. The 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 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.

Introduction

In network science, the dominant paradigm for structural analysis has long been "community finding"—the identification of groups where internal connectivity is significantly denser than external connectivity. While useful, this perspective is inherently limited. Real-world networks often exhibit diverse latent structures, such as core-periphery patterns (central hubs connected to a fringe) or hierarchical arrangements, which traditional community detection algorithms fail to capture.

Furthermore, complex networks are rarely defined by a single "correct" partition. Much like a dataset of documents can be categorized by either topic or authorship, a social or biological network may contain multiple valid structural interpretations. This research addresses the challenge of discovering an alternative blockmodel: a secondary, high-quality summary of a network that reveals structural insights distinct from an existing model.

Methodology: Symmetric Non-negative Matrix Tri-Factorization

The framework utilizes Symmetric Non-negative Matrix Tri-Factorization (SNMTF) to decompose a network's adjacency matrix ($A$). This approach represents the network through two primary components:

  1. Position Membership Matrix ($C$): Defines which nodes belong to which "positions" or clusters.
  2. Image Matrix ($M$): Provides a high-level summary of how these positions relate to one another (e.g., whether a cluster connects to itself or to others).

To identify a secondary structure that is both accurate and novel, two distinct algorithmic approaches were developed:

This method applies semi-supervised clustering logic at the node level. By introducing penalties for grouping nodes that were already clustered together in the initial model, the algorithm is forced to explore different membership configurations. However, this approach faces high computational complexity, as finding optimal constraints can become an NP-complete problem.

Approach 2: Image Matrix Dissimilarity

Rather than focusing on individual node assignments, this approach enforces dissimilarity at the structural level. It optimizes the new model such that its Image Matrix ($M$) is as different as possible from the original. This method proved more robust and user-friendly, as it relies on a single trade-off parameter ($\beta$) to balance the tension between model quality and structural novelty.

Experimental Validation

The methodology was tested on three distinct types of data:

  • Zachary’s Karate Club: A classic social network benchmark representing a factional split.
  • Books on American Politics: A network of 105 books where nodes are linked by frequent co-purchasing on Amazon.
  • Synthetic Datasets: 50-node graphs engineered to contain overlapping structures (e.g., a community structure and a core-periphery structure simultaneously).

Key Insights

  • Flexibility of Blockmodelling: The study demonstrates that community detection is actually a specialized subset of blockmodelling where the Image Matrix is diagonal. Blockmodelling allows for much broader structural discovery, including "structural equivalence," where nodes are grouped because they play the same role, even if they are not directly connected.
  • The Quality-Dissimilarity Trade-off: There is a fundamental tension in finding alternative models. As the requirement for dissimilarity increases, the reconstruction quality of the model may decrease. The authors used Minimum Description Length (MDL) and Kullback-Leibler (KL) Reconstruction to quantitatively validate that the discovered alternatives were statistically significant and not merely noise.
  • Discovery of Core-Periphery Structures: In tests like the Karate Club, while the primary model showed the standard two-community split, the SNMTF approach successfully uncovered a hidden core-periphery structure as a valid alternative.

Conclusion

This research moves network analysis beyond the "one-size-fits-all" approach of community detection. By leveraging SNMTF and image matrix dissimilarity, it is possible to systematically uncover multiple layers of latent structure within a single network. Future work will focus on refining the construction of instance-level constraints and exploring the potential of "must-link" constraints to further guide the discovery of complex network topologies.

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 Vinh Nguyen},
  title = {{Alternative Blockmodelling}},
  year = {2019},
  eprint = {1908.02575},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.02575},
}
Figure