Clustering Mixtures of Discrete Distributions: A Note on Mitra's Algorithm

Clustering is a critical challenge in network science, pivotal for detecting underlying patterns and structures in unlabeled data. To explore the boundaries of this challenge, stochastic block models (SBMs) have been effectively utilized as a mathematical framework to assess the performance of clustering algorithms. Specifically, an SBM is a statistical model developed to reveal the structural dynamics of networks or graphs, where nodes represent individual entities and edges symbolize the connections between them. In a typical SBM, nodes are categorized into blocks or communities according to their connectivity patterns, with the probability of an edge existing between any two nodes depending on the blocks to which they belong [3]. For example, in a social network using an SBM, nodes might be organized by attributes such as age, gender, or geographic location, with friendship probabilities determined by their block memberships [1, 6]. The Bipartite Stochastic Block Model(B-SBM)[2] extends the conventional SBM to accommodate networks comprising two distinct node types, forming a bipartite graph structure. This adaptation is particularly beneficial in contexts such as recommendation systems, where nodes represent users and products, or in particular social networks, where nodes might denote individuals and the groups or events they participate in. In B-SBMs, the connections between nodes from different sets are governed by an "affinity matrix" that specifies the likelihood of linkage based on group affiliations. This matrix is integral to capturing interaction patterns within the network, allowing for a sophisticated estimation of model parameters from observed connections.