计算机科学 ›› 2020, Vol. 47 ›› Issue (11A): 449-453.doi: 10.11896/jsjkx.200200049
王帅辉1,2, 胡谷雨3, 潘雨1, 张志越2, 张海峰2, 潘志松3
WANG Shuai-hui1,2, HU Gu-yu3, PAN Yu1, ZHANG Zhi-yue2, ZHANG Hai-feng2, PAN Zhi-song3
摘要: 社团结构作为复杂网络的中尺度特征,对于深入理解网络的结构和属性具有重要的意义。与无符号网络不同,符号网络包括正边和负边,分别代表了友好和敌对的关系。在形成社团时,节点通常会选择与朋友在同一社团内,而与对手在不同的社团。基于这种思想,构建了一种用于符号网络中社团发现的博弈论模型,设计了一种社团发现算法。实验结果表明,该算法在非重叠社团和重叠社团的识别中都具有卓越的性能。另外,对算法的运行效率进行了分析,提出了一种优化方法,有效地提高了算法的运行效率。
中图分类号:
[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] | 姜洋洋, 宋丽华, 邢长友, 张国敏, 曾庆伟. 蜜罐博弈中信念驱动的攻防策略优化机制 Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game 计算机科学, 2022, 49(9): 333-339. https://doi.org/10.11896/jsjkx.220400011 |
[2] | 方韬, 杨旸, 陈佳馨. D2D辅助移动边缘计算下的卸载策略优化 Optimization of Offloading Decisions in D2D-assisted MEC Networks 计算机科学, 2022, 49(6A): 601-605. https://doi.org/10.11896/jsjkx.210200114 |
[3] | 胥昊, 曹桂均, 闫璐, 李科, 王振宏. 面向铁路集装箱的高可靠低时延无线资源分配算法 Wireless Resource Allocation Algorithm with High Reliability and Low Delay for Railway Container 计算机科学, 2022, 49(6): 39-43. https://doi.org/10.11896/jsjkx.211200143 |
[4] | 潘雨, 邹军华, 王帅辉, 胡谷雨, 潘志松. 基于网络表示学习的深度社团发现方法 Deep Community Detection Algorithm Based on Network Representation Learning 计算机科学, 2021, 48(11A): 198-203. https://doi.org/10.11896/jsjkx.210200113 |
[5] | 魏礼奇, 赵志宏, 白光伟, 沈航. 基于生成对抗网络的位置隐私博弈机制 Location Privacy Game Mechanism Based on Generative Adversarial Networks 计算机科学, 2021, 48(10): 266-271. https://doi.org/10.11896/jsjkx.200900021 |
[6] | 毛莺池, 周彤, 刘鹏飞. 基于延迟接受的多用户任务卸载策略 Multi-user Task Offloading Based on Delayed Acceptance 计算机科学, 2021, 48(1): 49-57. https://doi.org/10.11896/jsjkx.200600129 |
[7] | 包峻波, 闫光辉, 李俊成. 结合非完全信息博弈的SIR传播模型 SIR Propagation Model Combing Incomplete Information Game 计算机科学, 2020, 47(6): 230-235. https://doi.org/10.11896/jsjkx.190400164 |
[8] | 刘苗苗,扈庆翠,郭景峰,陈晶. 符号网络链接预测算法研究综述 Survey of Link Prediction Algorithms in Signed Networks 计算机科学, 2020, 47(2): 21-30. https://doi.org/10.11896/jsjkx.190600104 |
[9] | 陈梦蓉,林英,兰微,单今朝. 基于“奖励制度”的DPoS共识机制改进 Improvement of DPoS Consensus Mechanism Based on Positive Incentive 计算机科学, 2020, 47(2): 269-275. https://doi.org/10.11896/jsjkx.190400013 |
[10] | 翟永, 刘津, 刘磊, 陈杰. 基于博弈论的空间数据中心私有云资源分配管理分析 Analysis of Private Cloud Resource Allocation Management Based on Game Theory in Spatial Data Center 计算机科学, 2020, 47(11A): 373-379. https://doi.org/10.11896/jsjkx.200500106 |
[11] | 蔡威, 白光伟, 沈航, 成昭炜, 张慧丽. 移动群智感知中基于强化学习的双赢博弈 Reinforcement Learning Based Win-Win Game for Mobile Crowdsensing 计算机科学, 2020, 47(10): 41-47. https://doi.org/10.11896/jsjkx.200700070 |
[12] | 刘海波,武天博,沈晶,史长亭. 基于GAN-LSTM的APT攻击检测 Advanced Persistent Threat Detection Based on Generative Adversarial Networks and Long Short-term Memory 计算机科学, 2020, 47(1): 281-286. https://doi.org/10.11896/jsjkx.181102103 |
[13] | 杜威, 丁世飞. 多智能体强化学习综述 Overview on Multi-agent Reinforcement Learning 计算机科学, 2019, 46(8): 1-8. https://doi.org/10.11896/j.issn.1002-137X.2019.08.001 |
[14] | 徐飞, 王少昌, 杨卫霞. 基于博弈论的云资源调度算法 Cloud Resource Scheduling Algorithm Based on Game Theory 计算机科学, 2019, 46(6A): 295-299. |
[15] | 付立东, 李丹, 李占利. 从属度树算法检测复杂网络重叠社团 Following-degree Tree Algorithm to Detect Overlapping Communities in Complex Networks 计算机科学, 2019, 46(12): 322-326. https://doi.org/10.11896/jsjkx.190200293 |
|