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

doi:10.1088/1674-1056/ac00a1

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.

Keywords: community detection interaction pattern Pitman-Yor process Markov chain Monte-Carlo

Received: 23 February 2021
Revised: 05 May 2021
Accepted manuscript online: 13 May 2021

PACS:	05.10.Ln	(Monte Carlo methods)
	89.75.Fb	(Structures and organization in complex systems)
	02.50.Tt	(Inference methods)

Fund: 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).

Corresponding Authors: Kan Li
E-mail: likan@bit.edu.cn

Cite this article:

Jing Wang(王晶) and Kan Li(李侃) Pitman-Yor process mixture model for community structure exploration considering latent interaction patterns 2021 Chin. Phys. B 30 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

[1]	Modularity-based representation learning for networks Jialin He(何嘉林), Dongmei Li(李冬梅), and Yuexi Liu(刘阅希). Chin. Phys. B, 2020, 29(12): 128901.
[2]	Community detection in signed networks based on discrete-time model Jianrui Chen(陈建芮), Li Zhang(张莉), Weiwei Liu(刘维维), Zaizai Yan(闫在在). Chin. Phys. B, 2017, 26(1): 018901.
[3]	Detecting overlapping communities in networks via dominant label propagation Sun He-Li (孙鹤立), Huang Jian-Bin (黄健斌), Tian Yong-Qiang (田勇强), Song Qin-Bao (宋擒豹), Liu Huai-Liang (刘怀亮). Chin. Phys. B, 2015, 24(1): 018703.
[4]	Detecting community structure using label propagation with consensus weight in complex network Liang Zong-Wen (梁宗文), Li Jian-Ping (李建平), Yang Fan (杨帆), Athina Petropulu. Chin. Phys. B, 2014, 23(9): 098902.
[5]	Dynamic evolutionary community detection algorithms based on the modularity matrix Chen Jian-Rui (陈建芮), Hong Zhi-Min (洪志敏), Wang Li-Na (汪丽娜), Wu Lan (乌兰). Chin. Phys. B, 2014, 23(11): 118903.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

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

Cite this article:

Online attention