Block Modeling in Large Social Networks with Many Clusters

In this paper, we present an optimized version of the previously developed Block Modularity algorithm (Anthony,2009). The original algorithm was a fast, greedy method that effectively discovered a structured clustering in linked data and scaled very well with the number of nodes and edges. The optimized version is scalable in terms of the model complexity; the technique can now be used effectively to discover thousands of clusters in data sets with hundreds of thousands (and possibly more) nodes and edges. The optimization leads to an improvement of the runtime per iteration from cubic to quadratic with a small increase in the constant factor. The algorithm compares favorably with Karrer and Newman's Degree-Corrected Block Model (DCBM) in both runtime and quality of results.