Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
复制标题
DOI：
10.1103/physreve.89.012804
复制
发表时间：
2014-01-13
影响因子：
2.4
通讯作者：
Peixoto, Tiago P.
中科院分区：
文献类型：
--
作者：
Peixoto, Tiago P.
我们提出了一个有效的算法推理的随机块模型在大型网络。该算法可以用作优化的马尔可夫链蒙特卡罗（MCMC）方法，具有快速的混合时间和更低的陷入亚稳态的敏感性，或者用作贪婪凝聚启发式算法，具有几乎线性的O（N ln（2）N）复杂度，其中N是网络中的节点数，独立于被推断的块数。我们表明，启发式是能够提供的结果是无法区分的更精确和数值昂贵的MCMC方法在许多人工和经验的网络，尽管要快得多。该方法对任何特定的混合模式都是完全无偏的，特别是它不支持竞争性的群落结构。
We present an efficient algorithm for the inference of stochastic block models in large networks. The algorithm can be used as an optimized Markov chain Monte Carlo (MCMC) method, with a fast mixing time and a much reduced susceptibility to getting trapped in metastable states, or as a greedy agglomerative heuristic, with an almost linear O(N ln(2) N) complexity, where N is the number of nodes in the network, independent of the number of blocks being inferred. We show that the heuristic is capable of delivering results which are indistinguishable from the more exact and numerically expensive MCMC method in many artificial and empirical networks, despite being much faster. The method is entirely unbiased towards any specific mixing pattern, and in particular it does not favor assortative community structures.