Decomposition‐based solution algorithms for optimization problems depend on the underlying latent block structure of the problem. Methods for detecting this structure are currently lacking. In this ...article, we propose stochastic blockmodeling (SBM) as a systematic framework for learning the underlying block structure in generic optimization problems. SBM is a generative graph model in which nodes belong to some blocks and the interconnections among the nodes are stochastically dependent on their block affiliations. Hence, through parametric statistical inference, the interconnection patterns underlying optimization problems can be estimated. For benchmark optimization problems, we show that SBM can reveal the underlying block structure and that the estimated blocks can be used as the basis for decomposition‐based solution algorithms which can reach an optimum or bound estimates in reduced computational time. Finally, we present a general software platform for automated block structure detection and decomposition‐based solution following distributed and hierarchical optimization approaches.
Variational methods for parameter estimation are an active research area, potentially offering computationally tractable heuristics with theoretical performance bounds. We build on recent work that ...applies such methods to network data, and establish asymptotic normality rates for parameter estimates of stochastic blockmodel data, by either maximum likelihood or variational estimation. The result also applies to various sub-models of the stochastic blockmodel found in the literature.
Blockmodeling refers to a variety of statistical methods for reducing and simplifying large and complex networks. While methods for blockmodeling networks observed at one time point are well ...established, it is only recently that researchers have proposed several methods for analysing dynamic networks (i.e., networks observed at multiple time points). The considered approaches are based on k-means or stochastic blockmodeling, with different ways being used to model time dependency among time points. Their novelty means they have yet to be extensively compared and evaluated and the paper therefore aims to compare and evaluate them using Monte Carlo simulations. Different network characteristics are considered, including whether tie formation is random or governed by local network mechanisms. The results show the Dynamic Stochastic Blockmodel (Matias and Miele 2017) performs best if the blockmodel does not change; otherwise, the Stochastic Blockmodel for Multipartite Networks (Bar-Hen et al. 2020) does.
•We consider dynamic networks, i.e., networks measured at multiple time points.•We show which blockmodeling approach is preferred in different conditions.•Blockmodel stability should be considered while selecting a blockmodeling approach.•A larger network and greater differences among block densities produce better results.
Blockmodeling linked networks aims to simultaneously cluster two or more sets of units into clusters based on a network where ties are possible both between units from the same set as well as between ...units of different sets. While this has already been developed for generalized and k-means blockmodeling, our approach is based on the well-known stochastic blockmodeling technique, utilizing a mixture model. Estimation is performed using the CEM algorithm, which iteratively estimates the parameters by maximizing a suitable likelihood function and reclusters the units according to the parameters. The steps are repeated until the likelihood function ceases to improve.
A key drawback of the basic algorithm is that it treats all units equally, consequently yielding higher influence to larger parts of the data. The greater size, however, does not necessarily imply higher importance. To mitigate this asymmetry, we propose a solution where underrepresented parts of the data are given more influence through an appropriate weighting. This idea leads to the so-called weighted likelihood approach, where the ordinary likelihood function is replaced by a weighted likelihood.
The efficiency of the different approaches is tested via simulations. It is shown through simulations that the weighted likelihood approach performs better for larger networks and a clearer blockmodel structure, especially when the one-mode blockmodels within the smaller sets are clearer.
•Linked networks contain two or more sets of units and subnetworks.•Subnetworks contain ties among the units of one set or between units of two sets.•Examples of linked networks are also dynamic networks and multilevel networks.•Blockmodeling linked networks jointly partitions all sets of units.•A stochastic blockmodeling approach is utilized to blockmodeling linked networks.•Weighted likelihood is used to balance the impact of different subnetworks.
Community detection aims to identify densely connected groups of nodes in complex networks. Although a variety of methods have been proposed for community detection, the relationship between them is ...not well understood. Recently, researchers have shown the equivalence between modularity optimization and likelihood maximization in stochastic block models (SBMs) for static networks. Showing this equivalence is important for both understanding the different community detection methods and selecting the hyperparameters in the different algorithms in a more principled way. In this paper, we extend this equivalence for dynamic community detection algorithms. In particular, we show the equivalence of evolutionary spectral clustering to a variant of dynamic stochastic blockmodel. For this purpose, we first introduce a novel dynamic SBM where the evolution of communities over time is modeled with pairwise Markov random fields. We then show that the log-posterior of the proposed model is equivalent to the quality function of evolutionary spectral clustering. This equivalence is used to determine the forgetting factor in evolutionary spectral clustering and to develop two new algorithms for dynamic community detection. Compared to original evolutionary spectral clustering, the forgetting factor is time-dependent and derived directly from the parameters of the proposed dynamic SBM. The proposed algorithms are shown to be superior to state-of-the-art dynamic community detection methods for both simulated and real-world dynamic networks.
Methods that are both computationally feasible and practically effective are needed to make sense of big corpuses of content, or "big content." For example, supervised categorization techniques for ...open-access academic publishing are ill-suited for automated categorization because they rely on an existing categorization scheme, but no supervised scheme can stay abreast of the rapidly evolving landscape of scholarly work. This problem also applies to any domain with very large document corpuses where no good categorization scheme exists. To address this challenge, we present an unsupervised method to fit a hierarchical categorization scheme to a corpus based on clustering the network of shared concepts in the corpus, or its "concept topology." Our method potentially applies to any type of content, and it scales to large networks of millions of vertices. We have demonstrated the application of our method to a corpus of 1.5 million scholarly texts representing the majority of open access (OA) academic publications on the web, validating our results using expert librarian annotations. We have made our datasets openly accessible for research by others. We believe that our resulting categorization scheme best represents OA academic publishing as it exists today.
PDF
