Computer Science ›› 2020, Vol. 47 ›› Issue (11A): 449-453.doi: 10.11896/jsjkx.200200049

• Big Data & Data Science • Previous Articles     Next Articles

Community Detection in Signed Networks with Game Theory

WANG Shuai-hui1,2, HU Gu-yu3, PAN Yu1, ZHANG Zhi-yue2, ZHANG Hai-feng2, PAN Zhi-song3   

  1. 1 Graduate School,Army Engineering University of PLA,Nanjing 210007,China
    2 The Third Flight Training Base of Naval Aeronautical University,Qinhuangdao,Hebei 066000,China
    3 Command and Control Engineering College,Army Engineering University of PLA,Nanjing 210007,China
  • Online:2020-11-15 Published:2020-11-17
  • About author:WANG Shuai-hui,born in 1984,Ph.D candidate.His main research interests include graph data mining and graph neural networks.
    PAN Zhi-song,born in 1973,Ph.D,professor.His main research interests include pattern recognition,machine learning and neural networks.
  • Supported by:
    This work was supported by the National Key Research Development Program of China (2017YFB0802800) and National Natural Science Foundation of China (61473149).

Abstract: As a meso-scale feature of complex networks,community structure is of great significance for understanding the structure and property of networks.Unlike unsigned networks,signed networks include positive and negative edges,which represent friendly and hostile relations,respectively.When forming a community,a node usually chooses to be in the same community with friends,but in different communities with enemies.Based on this idea,a game theory model for community detection in signed networks is constructed,and a related algorithm is designed.Experimental results show that the algorithm performs well inidenti-fying non-overlapping and overlapping communities.In addition,the efficiency of the algorithm has been verified,and an optimization method,which can effectively improve the efficiency of the proposed algorithm,is proposed.

Key words: Community detection, Game theory, Overlapping community, Signed networks

CLC Number: 

  • TP393
[1] TANG L,LIU H.Community detection and mining in socialmedia [J].Synthesis Lectures on Data Mining and Knowledge Discovery,2010,2(1):1-137.
[2] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[3] NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.
[4] HEIDER F.Attitudes and cognitive organization[J].The Journal of Psychology,1946,21(1):107-112.
[5] ZHAO X,YANG B,LIU X,et al.Statistical inference for communitydetection in signed networks[J].Physical Review E,2017,95(4-1):042313.
[6] LI Z,CHEN J,FU Y,et al.Community Detection Based on Regularized Semi-Nonnegative Matrix Tri-Factorization in Signed Networks[J].Mobile Networks & Applications,2017(2):1-9.
[7] GIRDHAR N,BHARADWAJ K K.Community Detection inSigned Social Networks Using Multiobjective Genetic Algorithm[J].Journal of the Association for Information Science and Technology,2019,70(8).
[8] YANG B,CHEUNG W,LIU J.Community Mining from Signed Social Networks[J].IEEE Transactions on Knowledge & Data Engineering,2007,19(10):1333-1348.
[9] GÓMEZ S,JENSEN P,ARENAS A.Analysis of communitystructure in networks of correlated data[J].Physical Review E,2009,80(1):016114.
[10] ANCHURI P,MAGDONISMAIL M.Communities and Balance in Signed Networks:A Spectral Approach [C]//IEEE/ACM International Conference on Advances in Social Networks Analysis &Mining.ACM,2012:235-242.
[11] KUNEGIS J,SCHMIDT S,LOMMATZSCH A,et al.Spectral Analysis ofSigned Graphs for Clustering,Prediction andVisuali-zation [C] //Siaminternational Conference on Data Mining.2010:559-570.
[12] CHEN W,LIU Z,SUN X,et al.A game-theoretic framework toidentify overlapping communities in social networks[J].Data Mining& Knowledge Discovery,2010,21(2):224-240.
[13] ALVARI H,HASHEMI S,HAMZEH A.Discovering overlappingcommunities in social networks:A novel game-theoreticapproach[M].IOS Press,2013.
[14] LUNG R I,GOG A,CHIRA C.A Game Theoretic Approach toCommunity Detection in Social Networks[M].Nature InspiredCooperative Strategies for Optimization (NICSO 2011).Springer Berlin Heidelberg,2011:121-131.
[15] CHOPADE P,ZHAN J.A Framework for Community Detection in LargeNetworks Using Game-Theoretic Modeling[J].IEEE Transactionson Big Data,2017,PP(99):1-1.
[16] LANCICHINETTI A,FORTUNATO S.Community detectionalgorithms:a comparative analysis[J].Phys Rev E Stat Nonlin Soft Matter Phys,2009,80(2):056117.
[17] DANON L,DIAZGUILERA A,DUCH J,et al.Comparing communitystructure identification[J].Journal of Statistical Mechanics:Theoryand Experiment,2005,2005(9).
[18] MCDAID A F,GREENE D,HURLEY N.Normalized mutual information to evaluate overlapping community finding algorithms[J].arXiv:1110.2515,2011.
[1] JIANG Yang-yang, SONG Li-hua, XING Chang-you, ZHANG Guo-min, ZENG Qing-wei. Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game [J]. Computer Science, 2022, 49(9): 333-339.
[2] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[3] FANG Tao, YANG Yang, CHEN Jia-xin. Optimization of Offloading Decisions in D2D-assisted MEC Networks [J]. Computer Science, 2022, 49(6A): 601-605.
[4] XU Hao, CAO Gui-jun, YAN Lu, LI Ke, WANG Zhen-hong. Wireless Resource Allocation Algorithm with High Reliability and Low Delay for Railway Container [J]. Computer Science, 2022, 49(6): 39-43.
[5] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[6] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[7] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[8] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[9] YANG Xu-hua, WANG Chen. Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force [J]. Computer Science, 2021, 48(4): 229-236.
[10] XU Xin-li, XIAO Yun-yue, LONG Hai-xia, YANG Xu-hua, MAO Jian-fei. Attributed Network Embedding Based on Matrix Factorization and Community Detection [J]. Computer Science, 2021, 48(12): 204-211.
[11] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[12] PAN Yu, ZOU Jun-hua, WANG Shuai-hui, HU Gu-yu, PAN Zhi-song. Deep Community Detection Algorithm Based on Network Representation Learning [J]. Computer Science, 2021, 48(11A): 198-203.
[13] LOU Zheng-zheng, WANG Guan-wei, LI Hui, WU Yun-peng. Community Mining Based on KL-Ball [J]. Computer Science, 2021, 48(11A): 236-243.
[14] WEI Li-qi, ZHAO Zhi-hong, BAI Guang-wei, SHEN Hang. Location Privacy Game Mechanism Based on Generative Adversarial Networks [J]. Computer Science, 2021, 48(10): 266-271.
[15] MAO Ying-chi, ZHOU Tong, LIU Peng-fei. Multi-user Task Offloading Based on Delayed Acceptance [J]. Computer Science, 2021, 48(1): 49-57.
Full text



No Suggested Reading articles found!