Increasing the Scalability of the Fitting of Generalised Block Models for Social Networks

Jeffrey Chan, Samantha Lam, Conor Hayes

Abstract

Generalized blockmodeling is a powerful tool for uncovering complex role-based structures in social networks, yet its computational intensity has historically limited its application to very small datasets. This paper presents two meta-heuristic algorithms—Simulated Annealing (saBM) and a Grouping Genetic Algorithm (gaBM)—that achieve a 100x speedup over traditional methods, enabling the analysis of networks with hundreds of vertices for the first time.

The Scalability Challenge in Blockmodeling

In social network analysis, "summarizing" connections typically involves community detection, which identifies cliques where members are densely interconnected. However, real-world social structures often involve functional roles rather than simple clusters. For instance, in biological or corporate networks, one group may consistently provide a service or "groom" another without reciprocity.

Generalized blockmodeling allows researchers to define these diverse relationship types, such as "Regular," "Null," or "Complete" blocks. Fitting these models—finding the optimal partition of nodes into groups that match these roles—is a difficult combinatorial problem. Until now, the standard greedy approach (KL-based) was computationally prohibitive for networks exceeding 100 nodes, often requiring tens of thousands of restarts to find a global optimum.

Roles vs. Communities

The core advantage of generalized blockmodeling is its ability to move beyond simple community finding. By allowing for "Regular" blocks—where every member of one group interacts with at least one member of another—researchers can identify hierarchies and specialized functional roles.

An image diagram illustrating functional roles (Groomers vs. Groomed) in a social network.

As shown in the diagram above, a "Grooming" network can be modeled with specific directional roles. This structural nuance is lost in traditional clustering but captured effectively through blockmodeling.

Proposed Meta-heuristic Approaches

To overcome the "scalability wall," the authors propose two algorithms:

  1. Simulated Annealing (saBM): This approach explores the solution space by swapping vertices between groups, using a "temperature" schedule to escape local optima.
  2. Genetic Algorithm (gaBM): Utilizing a Grouping Genetic Algorithm (GGA) representation, this method avoids the "isomorphism" problem common in standard GAs. It features a custom crossover operator that injects partitions from parent solutions and repairs inconsistencies, while simultaneously optimizing block type assignments during the recombination process.

The Power of Pre-specification

A significant finding of this research is the efficiency gain when a researcher has a prior hypothesis about the network's structure. By providing a "pre-specified image matrix," the gaBM algorithm can target a specific structural template, leading to faster convergence and higher accuracy.

A pre-specified image matrix defining the expected relationship types (Complete, Regular, Null) between partitions.

Key Results and Real-World Application

The proposed algorithms demonstrate a 100x speedup compared to the KL-based gold standard. On synthetic benchmarks of up to 800 nodes, gaBM consistently outperformed saBM in finding lower-cost (more accurate) models.

The utility of these methods was validated using the Enron email dataset. The algorithms successfully mapped the evolution of the corporate hierarchy during the 2001 crisis. They revealed a shift from a rigid hierarchy to a state of broad communication between executives and specialists as the crisis peaked, providing a data-driven view of organizational stress and adaptation.

Conclusion and Future Directions

While these algorithms push the boundary of blockmodeling to networks of nearly 1,000 nodes, further work is needed to reach the scale of modern "big data" social networks. Future research may explore hierarchical compression techniques or hybridizing GA and SA approaches to further enhance performance and model selection.

Summary updated

Abstract

In recent years, the summarisation and decomposition of social networks has become increasingly popular, from community finding to role equivalence. However, these approaches concentrate on one type of model only. Generalised blockmodelling decomposes a network into independent, interpretable, labeled blocks, where the block labels summarise the relationship between two sets of users. Existing algorithms for fitting generalised blockmodels do not scale beyond networks of 100 vertices. In this paper, we introduce two new algorithms, one based on genetic algorithms and the other on simulated annealing, that is at least two orders of magnitude faster than existing algorithms and obtaining similar accuracy. Using synthetic and real datasets, we demonstrate their efficiency and accuracy and show how generalised block-modelling and our new approaches enable tractable network summarisation and modelling of medium sized networks.
BibTeX
@inproceedings{chan2011increasing,
  author = {Jeffrey Chan and Samantha Lam and Conor Hayes},
  title = {{Increasing the Scalability of the Fitting of Generalised Block Models for Social Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-207},
}
Figure