Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns

doi:10.1088/1674-1056/ac00a1

中国物理B ›› 2021, Vol. 30 ›› Issue (12): 120518-120518.doi: 10.1088/1674-1056/ac00a1

Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns

Jing Wang(王晶) and Kan Li(李侃)^†

School of Computer Science, Beijing Institute of Technology, Beijing 100088, China

收稿日期:2021-02-23 修回日期:2021-05-05 接受日期:2021-05-13 出版日期:2021-11-15 发布日期:2021-11-30
通讯作者: Kan Li E-mail:likan@bit.edu.cn
基金资助:
Project supported by Beijing Natural Science Foundation, China (Grant Nos. L181010 and 4172054), the National Key R&D Program of China (Grant No. 2016YFB0801100), and the National Basic Research Program of China (Grant No. 2013CB329605).

Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns

Jing Wang(王晶) and Kan Li(李侃)^†

School of Computer Science, Beijing Institute of Technology, Beijing 100088, China

Received:2021-02-23 Revised:2021-05-05 Accepted:2021-05-13 Online:2021-11-15 Published:2021-11-30
Contact: Kan Li E-mail:likan@bit.edu.cn
Supported by:
Project supported by Beijing Natural Science Foundation, China (Grant Nos. L181010 and 4172054), the National Key R&D Program of China (Grant No. 2016YFB0801100), and the National Basic Research Program of China (Grant No. 2013CB329605).

摘要/Abstract

摘要： The statistical model for community detection is a promising research area in network analysis. Most existing statistical models of community detection are designed for networks with a known type of community structure, but in many practical situations, the types of community structures are unknown. To cope with unknown community structures, diverse types should be considered in one model. We propose a model that incorporates the latent interaction pattern, which is regarded as the basis of constructions of diverse community structures by us. The interaction pattern can parameterize various types of community structures in one model. A collapsed Gibbs sampling inference is proposed to estimate the community assignments and other hyper-parameters. With the Pitman-Yor process as a prior, our model can automatically detect the numbers and sizes of communities without a known type of community structure beforehand. Via Bayesian inference, our model can detect some hidden interaction patterns that offer extra information for network analysis. Experiments on networks with diverse community structures demonstrate that our model outperforms four state-of-the-art models.

关键词: community detection, interaction pattern, Pitman-Yor process, Markov chain Monte-Carlo

Abstract: The statistical model for community detection is a promising research area in network analysis. Most existing statistical models of community detection are designed for networks with a known type of community structure, but in many practical situations, the types of community structures are unknown. To cope with unknown community structures, diverse types should be considered in one model. We propose a model that incorporates the latent interaction pattern, which is regarded as the basis of constructions of diverse community structures by us. The interaction pattern can parameterize various types of community structures in one model. A collapsed Gibbs sampling inference is proposed to estimate the community assignments and other hyper-parameters. With the Pitman-Yor process as a prior, our model can automatically detect the numbers and sizes of communities without a known type of community structure beforehand. Via Bayesian inference, our model can detect some hidden interaction patterns that offer extra information for network analysis. Experiments on networks with diverse community structures demonstrate that our model outperforms four state-of-the-art models.

Key words: community detection, interaction pattern, Pitman-Yor process, Markov chain Monte-Carlo

中图分类号: (Monte Carlo methods)

05.10.Ln

89.75.Fb (Structures and organization in complex systems) 02.50.Tt (Inference methods)

Jing Wang(王晶) and Kan Li(李侃). Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns[J]. 中国物理B, 2021, 30(12): 120518-120518.

Jing Wang(王晶) and Kan Li(李侃). Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns[J]. Chin. Phys. B, 2021, 30(12): 120518-120518.

参考文献

[1] David E and Jon K 2010 Networks, Crowds, and Markets:Reasoning About a Highly Connected World (New York:Cambridge University Press)
[2] Yang Y Z, Hu N and Huang T Y 2020 Chin. Phys. B 29 88903
[3] Hu J W, Gao S, Yan J W, Lou P and Yin Y 2020 Chin. Phys. B 29 88901
[4] Hou G Y, Jin C, Xu Z D, Yu P and Cao Y Y 2019 Chin. Phys. B 28 38901
[5] Pang M B and Huang Y M 2018 Chin. Phys. B 27 118902
[6] Fortunato S and Hric D 2016 Phys. Rep. 659 1
[7] Girvan M and Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821
[8] Newman M E J 2003 Phys. Rev. E 67 026126
[9] Barber M J 2007 Phys. Rev. E 76 66102
[10] Larremore D B, Clauset A and Jacobs A Z 2014 Phys. Rev. E 90 12805
[11] Tackx R, Tarissan F and Guillaume J L 2017 Complex Networks 2017, Nov. 2017, Lyon, France p. 278
[12] Newman M E J 2006 Phys. Rev. E 74 36104
[13] Chang C and Tang C 2014 New J. Phys. 16 93001
[14] Feng L, Zhou C and Zhao Q 2019 Phys. A 513 424
[15] Sun H, Ch'ng E, Yong X, Garibaldi J M, See S and Chen D 2018 Phys. A 496 108
[16] Stephan L and Massoulié L 2019 Proceedings of the 32nd Conference on Learning Theory, Jun. 25-28, Phoenix, USA p. 2831
[17] Zhang X, Ma Z, Zhang Z, Sun Q and Yan J 2018 J. Phys. Conf. Ser. 1069 12123
[18] Su Y, Wang B and Zhang X 2017 Sci. Rep. 7 41830
[19] Peel L, Larremore D B and Clauset A 2017 Sci. Adv. 3 1602548
[20] Holland P W, Laskey K B and Leinhardt S 1983 Soc. Networks 5 109
[21] Lee C and Wilkinson D J 2019 Appl. Netw. Sci. 4 122
[22] Funke T and Becker T 2019 PLoS One 14 1
[23] Yen T C and Larremore D B 2020 Phys. Rev. E 102 32309
[24] Cherifi H, Palla G, Szymanski B K and Lu X 2019 Appl. Netw. Sci. 4 117
[25] Abbe E 2018 J. Mach. Learn. Res. 18 1[26] Li Z and Tang J 2021 Sci. China Inf. Sci. 64 192108
[27] Li K and Pang Y 2014 Neurocomputing 130 36
[28] Liu F, Xue S, Wu J, Zhou C, Hu W, Paris C, Nepal S, Yang J and Yu P S 2020 Proceedings of the 29th International Joint Conference on Artificial Intelligence, Jan. 2021, Yokohama, Japan p. 4981
[29] Mehta N, Duke L C and Rai P Proceedings of the 36th International Conference on Machine Learning, June 2019, California, USA pp. 4466-4474
[30] Newman M E J 2004 Phys. Rev. E 69 066133
[31] Gao C, Ma Z, Zhang A Y and Zhou H H 2018 Ann. Stat. 46 2153
[32] Peixoto T P 2014 Phys. Rev. X 4 011047
[33] Karrer B and Newman M E J 2011 Phys. Rev. E 83 016107
[34] Herlau T, Schmidt M N and Morup M 2016 Proceedings of the 30th International Conference on Neural Information Processing, Dec. 2016, Barcelona, Spain, p. 4260
[35] Peixoto T P 2020 Phys. Rev. E 102 12305
[36] Kemp C, Tenenbaum J B, Griffiths T L, Yamada T and Ueda N 2006 Proceedings of the 21st National Conference on Artificial Intelligence, July 2006, Boston, USA, p. 381
[37] Schmidt M N and Morup M 2013 IEEE Signal Process. Mag. 30 110
[38] Herlau T, Schmidt M N and Morup M 2014 Phys. Rev. E 90 32819
[39] Ishwaran H and James L F 2001 J. Am. Stat. Assoc. 96 161
[40] Sato I and Nakagawa H 2010 Proceedings of the 16th International Conference on Knowledge Discovery and Data Mining, July 2010, New York, USA, p. 673
[41] Griffiths T L and Ghahramani Z 2011 J. Mach. Learn. Res. 12 1185[42] Gershman S J and Blei D M 2012 J. Math. Psychol. 56 1[43] Teh Y W 2006 A Bayesian Interpretation of Interpolated Kneser-Ney (Singapore)[44] Johnson M and Goldwater S 2009 Proceedings of Human Language Technologies:The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, May 2009, Boulder, USA, p. 317
[45] Knuth D E 1994 The Stanford GraphBase:A Platform for Combinatorial Computing (New York:ACM Press)
[46] Leskovec J and Krevl A 2014 SNAP Datasets:Stanford Large Network Dataset Collection, http://snap.stanford.edu/data, [2014]
[47] Bu D, Zhao Y, Cai L, Xue H, Zhu X, Lu H, Zhang J, Sun S, Ling L, Zhang N, Li G and Chen R 2003 Nucleic Acids Res. 31 2443[48] Lu Q and Getoor L 2003 Proceedings of the 20th International Conference on International Conference on Machine Learning Aug. 2003, Washington, USA p. 496
[49] Adamic L A and Glance N 2005 Proceedings of the 3rd International Workshop on Link Discovery, Aug. 2005, New York, USA, p. 36
[50] Davis A, Gardner B B and Gardner M R 1941 Deep South:A Social Anthropological Study of Caste and Class (Chicago:University of Chicago Press)
[51] Murphy A C, Muldoon S F, Baker D, Lastowka A, Bennett B, Yang M and Bassett D S 2018 PLOS Biol. 16 1[52] Kunegis J 2013 Proceedings of the 22nd International Conference on World Wide Web, May 2013, Rio de Janeiro, Brazil, p. 1343
[53] Harper F M and Konstan J A 2015 ACM Trans. Interact. Intell. Syst. 5 4[54] Gerstein M B, Kundaje A, Hariharan M, et al. 2012 Nature 489 91
[55] Miller K T, Griffiths T L and Jordan M I 2009 Proceedings of the 22nd International Conference on Neural Information Processing, Dec. 2009, Vancouver, Canada, p. 1276

Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns

Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

Metrics

本文评价

推荐阅读 0

[1]	陈建芮, 张莉, 刘维维, 闫在在. Community detection in signed networks based on discrete-time model[J]. 中国物理B, 2017, 26(1): 18901-018901.
[2]	孙鹤立, 黄健斌, 田勇强, 宋擒豹, 刘怀亮. Detecting overlapping communities in networks via dominant label propagation[J]. , 2015, 24(1): 18703-018703.
[3]	梁宗文, 李建平, 杨帆, Athina Petropulu. Detecting community structure using label propagation with consensus weight in complex network[J]. , 2014, 23(9): 98902-098902.
[4]	陈建芮, 洪志敏, 汪丽娜, 乌兰. Dynamic evolutionary community detection algorithms based on the modularity matrix[J]. , 2014, 23(11): 118903-118903.