Shen Xin, Magnani Matteo, Rohner Christian, Skerman Fiona
InfoLab, Department of Information Technology, Uppsala University, 75105, Uppsala, Sweden.
Department of Mathematics, Uppsala University, 75105, Uppsala, Sweden.
Sci Rep. 2025 May 30;15(1):19062. doi: 10.1038/s41598-025-99114-5.
Modularity is one of the most widely used measures for evaluating communities in networks. In probabilistic networks, where the existence of edges is uncertain and uncertainty is represented by probabilities, the expected value of modularity can be used instead. However, efficiently computing expected modularity is challenging. To address this challenge, we propose a novel and efficient technique ([Formula: see text]) for computing the probability distribution of modularity and its expected value. In this paper, we implement and compare our method and various general approaches for expected modularity computation in probabilistic networks. These include: (1) translating probabilistic networks into deterministic ones by removing low-probability edges or treating probabilities as weights, (2) using Monte Carlo sampling to approximate expected modularity, and (3) brute-force computation. We evaluate the accuracy and time efficiency of [Formula: see text] through comprehensive experiments on both real-world and synthetic networks with diverse characteristics. Our results demonstrate that removing low-probability edges or treating probabilities as weights produces inaccurate results, while the convergence of the sampling method varies with the parameters of the network. Brute-force computation, though accurate, is prohibitively slow. In contrast, our method is much faster than brute-force computation, but guarantees an accurate result.
模块度是评估网络中社区结构最广泛使用的度量之一。在概率网络中，边的存在是不确定的，不确定性由概率表示，此时可以使用模块度的期望值。然而，有效地计算期望模块度具有挑战性。为应对这一挑战，我们提出了一种新颖且高效的技术（[公式：见原文]）来计算模块度的概率分布及其期望值。在本文中，我们实现并比较了我们的方法以及概率网络中期望模块度计算的各种通用方法。这些方法包括：（1）通过去除低概率边或将概率视为权重将概率网络转换为确定性网络，（2）使用蒙特卡罗采样来近似期望模块度，以及（3）暴力计算。我们通过对具有不同特征的真实世界网络和合成网络进行全面实验，评估了[公式：见原文]的准确性和时间效率。我们的结果表明，去除低概率边或将概率视为权重会产生不准确的结果，而采样方法的收敛性随网络参数而变化。暴力计算虽然准确，但速度极慢。相比之下，我们的方法比暴力计算快得多，同时保证结果准确。
