摘要 Community detection in signed networks has been studied widely in recent years. In this paper, a discrete difference equation is proposed to imitate the consistently changing phases of the nodes. During the interaction, each node will update its phase based on the difference equation. Each node has many different nodes connected with it, and these neighbors have different influences on it. The similarity between two nodes is applied to describe the influences between them. Nodes with high positive similarities will get together and nodes with negative similarities will be far away from each other. Communities are detected ultimately when the phases of the nodes are stable. Experiments on real world and synthetic signed networks show the efficiency of detection performance. Moreover, the presented method gains better detection performance than two existing good algorithms.

Abstract：Community detection in signed networks has been studied widely in recent years. In this paper, a discrete difference equation is proposed to imitate the consistently changing phases of the nodes. During the interaction, each node will update its phase based on the difference equation. Each node has many different nodes connected with it, and these neighbors have different influences on it. The similarity between two nodes is applied to describe the influences between them. Nodes with high positive similarities will get together and nodes with negative similarities will be far away from each other. Communities are detected ultimately when the phases of the nodes are stable. Experiments on real world and synthetic signed networks show the efficiency of detection performance. Moreover, the presented method gains better detection performance than two existing good algorithms.

基金资助:Project supported by the National Natural Science Foundation of China (Grant Nos. 11261034, 71561020, 61503203, and 11326239), the Higher School Science and Technology Research Project of Inner Mongolia, China (Grant No. NJZY13119), and the Natural Science Foundation of Inner Mongolia, China (Grant Nos. 2015MS0103 and 2014BS0105).

通讯作者:
Jianrui Chen
E-mail: jianrui_chen@sina.com

引用本文:

陈建芮, 张莉, 刘维维, 闫在在. Community detection in signed networks based on discrete-time model[J]. 中国物理B, 2017, 26(1): 18901-018901.
Jianrui Chen(陈建芮), Li Zhang(张莉), Weiwei Liu(刘维维), Zaizai Yan(闫在在). Community detection in signed networks based on discrete-time model. Chin. Phys. B, 2017, 26(1): 18901-018901.

Chen J, Jiao L C, Wu J S and Wang X D 2010 Nonlinear Analysis:Real World Applications 4 3045

[2]

Jiang M S, Chen Y X and Chen L 2015 arXiv: 1502. 04380

[3]

Newman M J 2004 Phys. Rev. E 69 066133

[4]

Wu L T, Ying X W, Wu X T, Lu A D and Zhou Z H 2012 International Journal of Social Network Mining 1 91

[5]

Doreian P and Mrvar A 1996 Social Networks 2 149

[6]

Lin D K 1998 ICML 98 296

[7]

Kernighan B W and Lin S 1970 Bell System Technical Journal 2 291

[8]

Pothen A, Simon H D and Liou K P 1990 SIAM Journal on Matrix Analysis and Applications 3 430

[9]

Newman M E J 2004 Proc. Natl. Acad. Sci. USA 1 5200

[10]

Newman M E J 2006 Proc. Natl. Acad. Sci. USA 23 8577

[11]

Yang B, Cheung W K and Liu J 2007 Knowledge and Data Engineering, IEEE Transactions on 10 1333

[12]

Chen Y, Wang X L, Yuan B and Tang B Z 2014 Journal of Statistical Mechanics:Theory and Experiment 2014 03021

[13]

Sun L H, Huang J B, Tian Y Q, Song Q B and Liu H L 2015 Chin. Phys. B 24 551

[14]

Wang Y and Cao J 2013 Nonlinear Analysis:Real World Applications 1 842

[15]

Wu J S, Jiao L C and Jin C 2012 Phys. Rev. E 1 016115

[16]

Wu J C, Wang X H and Jiao L C 2012 Physica A 3 508

[17]

Almendral J A, Leyva I, Li D, Sendiña-Nadal, Havlin S and Boccaletti S 2010 Phys. Rev. E 1 016115

[18]

Li D, Leyva I and Almendral J A 2008 Phys. Rev. Lett. 16 168701

[19]

Wu J S and Jiao Y 2014 Chaos 3 033104

[20]

Zhang L S, Gu W F, Hu G and Mi Y Y 2014 Chin. Phys. B 10 626

[21]

Xiang J, Hu K, Zhang Y, Hu T and Li J M 2015 Europhys. Lett. 111 48003

[22]

Xiang J, Hu T, Hu K, Tang Y N, Gao Y Y, Chai C H and Liu X J 2015 Canadian Journal of Physics 93 418

[23]

Esmailian P and Jalili M 2015 Scientific Reports 5 14339

[24]

Xiang J, Tang Y N, Gao Y Y, Zhang Y, Deng K, Xu X K and Hu K 2015 Physica A 432 127

[25]

Xiang J, Hu T, Zhang Y, Hu K, Li J M, Xu X K, Liu C C and Chen S 2016 Physica A 443 451

[26]

Chang Z C, Liu Y, Yu H T, and Huang R Y 2015 Acta Phys. Sin. 21 218901(in Chinese)

[27]

Pizzuti C 2008 Parallel Problem Solving from Nature-PPSN X, 10th International Conference, September 13-17, 2008, Dortmund, Germany, p. 1081

[28]

Liu C L, Liu J and Jiang Z Z 2014 IEEE Transactions on Cybernetics 12 2274

[29]

Wu J S, Zhang L, Li Y and Jiao Y 2016 Physica A 443 568

[30]

Lü L Y and Zhou T 2011 Physica A 6 1150

[31]

Xiang J, Hu K, Zhang Y, Bao M H, Tang L, Tang Y N, Gao Y Y, Li J M, Chen B Y and Hu J B 2016 Journal of Statistical Mechanics:Theory and Experiment 2016 033405

[32]

Chen J R, Hong Z M, Wang L N and Wu L 2014 Chin. Phys. B 11 118903

[33]

Chen J R, Wang H, Wang L N and Liu W W 2015 Physica A 447 482

[34]

Tang J, Lou T C and Kleinberg J 2012 WSDM 743

[35]

Easley D and Kleinberg J 2010 Networks, Crowds, and Markets:Reasoning about a Highly Connected World (Cambridge:Cambridge University Press) p. 10

[36]

Khadivi A, Rad A A and Hasler M 2010 Circuits and Systems (ISCAS), Proceedings of 2010 IEEE International Symposium on IEEE 3777

[37]

Wu J S, Hou Y T, Jiao Y, Li Y, Li X X and Jiao L C 2015 Physica A 433 218

[38]

Sideris T C 2013 Ordinary Differential Equations and Dynamical Systems (New York:Atlantis Press)

[39]

Doreian P and Mrvar A 2009 Social Networks 31 1

[40]

Read K E 1954 Southwestern Jouranal of Anthropopgy 10 1

[41]

Zeng Y and Liu J 2015 Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems (Heidelberg:Springer) p. 259