-
As a mainstream algorithm for inferring probabilistic graphical models, belief propagation (BP) algorithm is one of the most important methods to solve the joint probability distribution in the stochastic block model. However, existing methods either lead to low accuracy in dealing with the core-periphery structure problem, or the theoretical derivation is difficult to understand due to a large number of approximation, or both exist. Of course, the reason for low accuracy comes from too many approximations. The main reason for many approximations and complex theoretical derivation is that the joint probability distribution in the inference process of the stochastic block model is not directly solved by the BP algorithm, that is, the graph (network) being processed is not consistent with the graph considered in the probabilistic graph model. Therefore, in this paper, a mean-field approximation is developed to modify the joint probability distribution to make the BP algorithm match perfectly, which makes the theoretical derivation easy to understand. Finally, the effectiveness of the proposed method is validated by the experimental results.
-
Keywords:
- stochastic block model /
- belief propagation algorithm /
- joint probability distribution /
- mean-field approximation
[1] 张海峰, 王文旭 2020 69 088906
Google Scholar
Zhang H F, Wang W X 2020 Acta Phys. Sin. 69 088906
Google Scholar
[2] Guimerà R, Mossa S, Turtschi A, Amaral L A N 2005 PNAS 102 7794
Google Scholar
[3] Newman M E J 2006 Phys. Rev. E 74 36104
Google Scholar
[4] Benson A R, Gleich D F, Leskovec J 2016 Science 353 163
Google Scholar
[5] Xiang B B, Bao Z K, Ma C, Zhang X, Chen H S, Zhang H F 2018 Chaos 28 13122
Google Scholar
[6] Newman M E J 2003 SIAM Rev. 45 167
Google Scholar
[7] Leicht E A, Newman M E J 2008 Phys. Rev. Lett. 100 118703
Google Scholar
[8] Newman M E J 2006 Proc. Natl Acad. Sci. U.S.A. 103 8577
Google Scholar
[9] Newman M E J 2012 Nat. Phys. 8 25
Google Scholar
[10] Zhang X, Newman M E J 2015 Phys. Rev. E 92 52808
Google Scholar
[11] Lee D D, Seung H S 1999 Nature 401 788
Google Scholar
[12] 常振超, 陈鸿昶, 刘阳, 于洪涛, 黄瑞阳 2015 64 218901
Google Scholar
Chang Z C, Chen H C, Liu Y, Yu H T, Huang R Y 2015 Acta Phys. Sin. 64 218901
Google Scholar
[13] Shao J, Han Z, Yang Q, Zhou T 2015 Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Sydney NSW, Australia, August 10–13, 2015 p1075
[14] Gregory S 2010 New J. Phys. 12 103018
Google Scholar
[15] Karrer B, Newman M E J 2011 Phys. Rev. E 83 16107
Google Scholar
[16] Decelle A, Krzakala F, Moore C, ZdeborováL 2011 Phys. Rev. Lett. 107 65701
Google Scholar
[17] Ledwith M 2020 Community development: A critical approach (Bristol: Policy Press) pp1–252
[18] 王兴元, 赵仲祥 2014 63 178901
Google Scholar
Wang X Y, Zhao Z X 2014 Acta Phys. Sin. 63 178901
Google Scholar
[19] Everett M G, Borgatti S P 2000 Social Networks 21 397
Google Scholar
[20] Verma T, Russmann F, Araújo N A M, Nagler J, Herrmann H J 2016 Nat. Commun. 7 10441
Google Scholar
[21] Lee S H, Cucuringu M, Porter M A 2014 Phys. Rev. E 89 32810
Google Scholar
[22] Rombach P, Porter M A, Fowler J H, Mucha P J 2017 SIAM Rev. 59 619
Google Scholar
[23] Kojaku S, Masuda N 2017 Phys. Rev. E 96 52313
Google Scholar
[24] Kojaku S, Masuda N 2018 New J. Phys. 20 43012
Google Scholar
[25] Ma C, Xiang B B, Chen H S, Zhang H F 2020 Chaos 30 23112
Google Scholar
[26] Zhang X, Martin T, Newman M E J 2015 Phys. Rev. E 91 32803
Google Scholar
[27] Della Rossa F, Dercole F, Piccardi C 2013 Sci. Rep. 3 1467
Google Scholar
[28] Ma C, Xiang B B, Chen H S, Small M, Zhang H F 2018 Chaos 28 53121
Google Scholar
[29] 康玲, 项冰冰, 翟素兰, 鲍中奎, 张海峰 2018 67 198901
Google Scholar
Kang L, Xiang B B, Zhai S L, Bao Z K, Zhang H F 2018 Acta Phys. Sin. 67 198901
Google Scholar
[30] Ball B, Karrer B, Newman M E J 2011 Phys. Rev. E 84 36103
Google Scholar
[31] Decelle A, Krzakala F, Moore C, ZdeborováL 2011 Phys. Rev. E 84 66106
Google Scholar
[32] Mugisha S, Zhou H J 2016 Phys. Rev. E 94 12305
Google Scholar
[33] Yedidia J S, Freeman W T, Weiss Y 2005 IEEE Trans. Inf. Theory 51 2282
Google Scholar
[34] Mezard M, Montanari A 2009 Information, Physics, and Computation (Oxford: Oxford University Press) pp304–305
[35] Perotti J I, Tessone C J, Clauset A, Caldarelli G 2018 arXiv: 1806.07005 v1[soc-ph]
[36] Dempster A P, Laird N M, Rubin D B 1977 Journal of the Royal Statistical Society: Series B (Methodological) 39 1
Google Scholar
[37] Tiago P, Peixoto 2019 Advances in Network Clustering and Blockmodeling (New York:Wiley) pp289–332
[38] Zhang P, Moore C 2014 Proc. Natl. Acad. Sci. U.S.A. 111 18144
Google Scholar
[39] Gerlof B 2009 Proceedings of the 21th Biennial GSCL Conference Potsdam, Germany, September 30–October 2 2009 p31
[40] Sokolova M, Laxpalme G 2009 Inf. Process. Manage. 45 427
Google Scholar
-
图 1 稀疏基准网络社团结构探测 (a)
$n = 10000$ ,$c = 3$ ,$\gamma = {[0.5,\; 0.5]^{\rm T}}$ ,$\varepsilon^* = 0.27$ ; (b)$n = 200$ ,$c = 10$ ,$\gamma = {[0.5,\; 0.5]^{\rm T}}$ ,$\varepsilon^* = 0.520$ ; (c)$n = 200$ ,$c = 10$ ,$\gamma = {[0.3,\; 0.7]^{\rm T}}$ ; (d)$n = 200$ ,$c = 10$ ,$\gamma = {[1/3,\; 1/3,\; 1/3]^{\rm T}}$ ,$\varepsilon^* = 0.419$ Figure 1. Community structure detection in sparse benchmark networks: (a)
$n = 10000$ ,$c = 3$ ,$\gamma = {[0.5,\; 0.5]^{\rm T}}$ ,$\varepsilon^* = 0.27$ ; (b)$n = 200$ ,$c = 10$ ,$\gamma = {[0.5,\; 0.5]^{\rm T}}$ ,$\varepsilon^* = 0.520$ ; (c)$n = 200$ ,$c = 10$ ,$\gamma = {[0.3,\; 0.7]^{\rm T}}$ ; (d)$n = 200$ ,$c = 10$ ,$\gamma = {[1/3,\; 1/3, \;1/3]^{\rm T}},$ $\varepsilon^* = 0.419$ 
图 2 稠密基准网络社团结构探测 (a)
$n = 200$ ,$c = 50$ ,$\gamma = {[0.5,\; 0.5]^{\rm T}}$ ,$\varepsilon^* = 0.75$ ; (b)$n = 200$ ,$c = 50$ ,$\gamma = {[0.3, \;0.7]^{\rm T}}$ , (c)$n = 200$ ,$c = 30$ ,$\gamma = {[1/3,\; 1/3,\; 1/3]^{\rm T}}$ ,$\varepsilon^* = 0.599$ Figure 2. Community structure detection in dense benchmark networks: (a)
$n = 200$ ,$c = 50$ ,$\gamma = {[0.5,\; 0.5]^{\rm T}}$ ,$\varepsilon^* = 0.75$ ; (b)$n = 200$ ,$c = 50$ ,$\gamma = {[0.3,\; 0.7]^{\rm T}}$ ; (c)$n = 200$ ,$c = 30$ ,$\gamma = {[1/3,\; 1/3,\; 1/3]^{\rm T}}$ ,$\varepsilon^* = 0.599$ 
图 3 基准网络的核边结构探测
Figure 3. CP structure detection in benchmark networks.
-
[1] 张海峰, 王文旭 2020 69 088906
Google Scholar
Zhang H F, Wang W X 2020 Acta Phys. Sin. 69 088906
Google Scholar
[2] Guimerà R, Mossa S, Turtschi A, Amaral L A N 2005 PNAS 102 7794
Google Scholar
[3] Newman M E J 2006 Phys. Rev. E 74 36104
Google Scholar
[4] Benson A R, Gleich D F, Leskovec J 2016 Science 353 163
Google Scholar
[5] Xiang B B, Bao Z K, Ma C, Zhang X, Chen H S, Zhang H F 2018 Chaos 28 13122
Google Scholar
[6] Newman M E J 2003 SIAM Rev. 45 167
Google Scholar
[7] Leicht E A, Newman M E J 2008 Phys. Rev. Lett. 100 118703
Google Scholar
[8] Newman M E J 2006 Proc. Natl Acad. Sci. U.S.A. 103 8577
Google Scholar
[9] Newman M E J 2012 Nat. Phys. 8 25
Google Scholar
[10] Zhang X, Newman M E J 2015 Phys. Rev. E 92 52808
Google Scholar
[11] Lee D D, Seung H S 1999 Nature 401 788
Google Scholar
[12] 常振超, 陈鸿昶, 刘阳, 于洪涛, 黄瑞阳 2015 64 218901
Google Scholar
Chang Z C, Chen H C, Liu Y, Yu H T, Huang R Y 2015 Acta Phys. Sin. 64 218901
Google Scholar
[13] Shao J, Han Z, Yang Q, Zhou T 2015 Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Sydney NSW, Australia, August 10–13, 2015 p1075
[14] Gregory S 2010 New J. Phys. 12 103018
Google Scholar
[15] Karrer B, Newman M E J 2011 Phys. Rev. E 83 16107
Google Scholar
[16] Decelle A, Krzakala F, Moore C, ZdeborováL 2011 Phys. Rev. Lett. 107 65701
Google Scholar
[17] Ledwith M 2020 Community development: A critical approach (Bristol: Policy Press) pp1–252
[18] 王兴元, 赵仲祥 2014 63 178901
Google Scholar
Wang X Y, Zhao Z X 2014 Acta Phys. Sin. 63 178901
Google Scholar
[19] Everett M G, Borgatti S P 2000 Social Networks 21 397
Google Scholar
[20] Verma T, Russmann F, Araújo N A M, Nagler J, Herrmann H J 2016 Nat. Commun. 7 10441
Google Scholar
[21] Lee S H, Cucuringu M, Porter M A 2014 Phys. Rev. E 89 32810
Google Scholar
[22] Rombach P, Porter M A, Fowler J H, Mucha P J 2017 SIAM Rev. 59 619
Google Scholar
[23] Kojaku S, Masuda N 2017 Phys. Rev. E 96 52313
Google Scholar
[24] Kojaku S, Masuda N 2018 New J. Phys. 20 43012
Google Scholar
[25] Ma C, Xiang B B, Chen H S, Zhang H F 2020 Chaos 30 23112
Google Scholar
[26] Zhang X, Martin T, Newman M E J 2015 Phys. Rev. E 91 32803
Google Scholar
[27] Della Rossa F, Dercole F, Piccardi C 2013 Sci. Rep. 3 1467
Google Scholar
[28] Ma C, Xiang B B, Chen H S, Small M, Zhang H F 2018 Chaos 28 53121
Google Scholar
[29] 康玲, 项冰冰, 翟素兰, 鲍中奎, 张海峰 2018 67 198901
Google Scholar
Kang L, Xiang B B, Zhai S L, Bao Z K, Zhang H F 2018 Acta Phys. Sin. 67 198901
Google Scholar
[30] Ball B, Karrer B, Newman M E J 2011 Phys. Rev. E 84 36103
Google Scholar
[31] Decelle A, Krzakala F, Moore C, ZdeborováL 2011 Phys. Rev. E 84 66106
Google Scholar
[32] Mugisha S, Zhou H J 2016 Phys. Rev. E 94 12305
Google Scholar
[33] Yedidia J S, Freeman W T, Weiss Y 2005 IEEE Trans. Inf. Theory 51 2282
Google Scholar
[34] Mezard M, Montanari A 2009 Information, Physics, and Computation (Oxford: Oxford University Press) pp304–305
[35] Perotti J I, Tessone C J, Clauset A, Caldarelli G 2018 arXiv: 1806.07005 v1[soc-ph]
[36] Dempster A P, Laird N M, Rubin D B 1977 Journal of the Royal Statistical Society: Series B (Methodological) 39 1
Google Scholar
[37] Tiago P, Peixoto 2019 Advances in Network Clustering and Blockmodeling (New York:Wiley) pp289–332
[38] Zhang P, Moore C 2014 Proc. Natl. Acad. Sci. U.S.A. 111 18144
Google Scholar
[39] Gerlof B 2009 Proceedings of the 21th Biennial GSCL Conference Potsdam, Germany, September 30–October 2 2009 p31
[40] Sokolova M, Laxpalme G 2009 Inf. Process. Manage. 45 427
Google Scholar
DownLoad:
Catalog
Metrics
- Abstract views: 4023
- PDF Downloads: 64
- Cited By: 0
