基于节点演化分阶段优化的事件检测方法

doi:10.11896/jsjkx.190400072

摘要/Abstract

摘要： 链路预测技术是分析网络演化的有效方法,也为社会网络事件检测提供了一种新思路。当前采用链路预测进行事件检测的方法大多是从宏观的网络演化入手,也有少数结合节点演化的检测方法,但其稳定性不佳,对事件的敏感性也不够高,不能准确检测事件的发生。基于以上问题,提出了一种基于节点演化分阶段优化的事件检测方法(Node Evolution Staged Optimization,NESO_ED)。首先通过分阶段优化的方法加强事件检测的稳定性,并获取节点指标权重数组;然后根据不同阶段按不同规则选取节点的最佳相似性计算指标,使节点能更好地量化网络演化情况,以此提高事件检测的敏感性。此外,分析了网络演化过程中节点选取指标的变化情况,揭示了事件发生对节点演化产生的不同影响。基于真实社会网络VAST进行对比实验,结果显示NESO_ED方法在事件检测敏感性上比LinkEvent方法提高了227%,比NodeED方法提高了63%,NESO_ED方法的稳定性也比NodeED方法提高了66%,这表明NESO_ED方法能更加准确且稳定地进行事件检测。

关键词: 动态网络, 节点演化, 链路预测, 社会网络, 事件检测

Abstract: Link prediction technology is an effective method to analyze network evolution,it also provides a new idea to detect social events.Now,most of the event detections using link prediction start from the macroscopic overall network evolution.Although there are a few detection methods that combine node evolution,the stability of them are not good,and the sensitivity to the event are not high enough to accurately detect the occurrence of the event.Therefore,an event detection method based on node evolution staged optimization (NESO_ED) was proposed.Firstly,the stability of event detection is enhanced by a staged optimization method,and an array of node index weights is obtained.Then,according to different rules,the optimal similarity calculation index of the node is selected,so that the node can better quantify the network evolution and improve the sensitivity of event detection.In addition,the changes of indicators that selected by nodes in the process of network evolution were also analyzed.It reveals different effects of events on the evolution of nodes.On real social network VAST,the event detection sensibility of NESO_ED is increased by 227% compared with LinkEvent and 63% compared with NodeED.The stability of NESO_ED is also increased by 66% compared with NodeED,which shows that NESO_ED can detect events more accurately and stably.

Key words: Dynamic network, Event detection, Link prediction, Node evolution, Social network

中图分类号:

TP181

富坤, 仇倩, 赵晓梦, 高金辉. 基于节点演化分阶段优化的事件检测方法[J]. 计算机科学, 2020, 47(5): 96-102. https://doi.org/10.11896/jsjkx.190400072

FU Kun, QIU Qian, ZHAO Xiao-meng, GAO Jin-hui. Event Detection Method Based on Node Evolution Staged Optimization[J]. Computer Science, 2020, 47(5): 96-102. https://doi.org/10.11896/jsjkx.190400072

参考文献

[1]SHI L,DU J P,LIANG M Y.Social network burst topic disco-very based on RNN and topic model[J].Journal on Communications,2018,39(4):189- 198.
[2]JIE F,XIE F,LI L,et al.Latent event-related burst detection in social networks[J].Acta Automatica Sinica,2018,44(4):730-742.
[3]HAN Z M,CHEN Y,LIU W,et al.Research on node influence analysis in social network [J].Journal of Software,2017,28(1):84-104.
[4]ZHONG Z M,GUAN Y,LI C H,et al.Localized Top-k burstevent detection in microblog[J].Chinese Journal of Computers,2018,41(7):1504-1516.
[5]ZHANG L M,JIA Y,ZHOU B,et al.Online burst event detection based on emotions[J].Chinese Journal of Computers,2013,36(8):1659-1667.
[6]FEI S D,YANG Y Z,LIU P Y,et al.Method of burst events detection based on sentiment filter[J].Journal of Computer Applications,2015,35(5):1320-1323.
[7]XIONG Y,ZHANG Y F,FENG S,et al.Event detection andtracking in microblog stream based on multimodal feature deep fusion[J/OL].Control and Decision.[2019-05-30].http://kns.cnki.net/KCMS/detail/21.1124.TP.20180416.0932.015.html.
[8]WANG B Y,WU Z Y,SHEN S B,et al.Survey on event detection research in social media[J].Computer Technology and Development,2018,28(9):105-111.
[9]LIN C,LIN C,LI J,et al.Generating event storylines from microblogs[C]//Proceedings of the 21st ACM international conference on information and knowledge management (CIKM'12).Maui,Hawaii,USA,2012:175-184.
[10]LIU H K,LV L Y,ZHOU T.Uncovering the network evolution mechanism by link prediction [J].Scientia Sinica (Physica,Mechanica & Astronomica),2011,41(7):816-823.
[11]WANG H,HU W B,QIU Z Y,et al.Nodes' evolution diversity and link prediction in social networks[J].IEEE Transactions on Knowledge and Data Engineering,2017,29(10):2263-2274.
[12]HANLEY J A,MCNEIL B J.The meaning and use of the area under a receiver oSENating characteristic (ROC) curve[J].Radiology,1982,143(1):29-36.
[13]HERLOCKER J L,KONSTAN J A,TERVEEN L G,et al.Evaluating collaborative filtering recommender systems[J].ACM Transactions on Information Systems,2004,22(1):5-53.
[14]ZHOU T,REN J,MEDO M,et al.Bipartite network projection and personal recommendation[J].Physical Review E,2007,76(4):70-80.
[15]LI Q G,SHI J Q,QIN Z G,et al.Mining user behavior patterns for detection in email networks[J].Chinese Journal of Compu-ters,2014,37(5):1135-1146.
[16]YANG L M,ZHANG W,CHEN Y F,et al.Time-series prediction based on global fuzzy measure in social networks[J].Front Inform Technol Electron Eng,2015,16(10):805-816.
[17]WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world' networks[J].Nature,1998,393(6684):440-442.
[18]BARABASI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.
[19]RAPOPORT A.Spread of information through a populationwith socio-structural bias:I.assumption of transitivity[J].The Bulletin of Mathematical Biophysics,1953,15(4):523-533.
[20]XIONG C,CHEN Y F,CANG J Y.Event-based node influence analysis in social network evolution [J].Computer Science,2016,43(S1):404-409.
[21]WU X D,LI Y,LI L.Influence analysis of online social networks[J].Chinese Journal of Computers,2014,37(4):735-752.
[22]WANG Y,CUI J H,ZHANG T,et al.A complex network evolution model based on microscopic characteristic of nodes[C]//Proceedings of IEEE International Conference on Software Quality,Reliability and Security Companion (QRS-C).Lisbon,Portugal:IEEE Press,2018:388-393.
[23]LV L Y.Link prediction on complex network [J].Journal of University of Electronic Science and Technology of China,2010,39(5):651-661.
[24]LIBEN-NOWELL D,KLEINBERG J.The link-prediction problem for social networks[J].Journal of the American for Information Science and Technology,2007,58(7):1019-1031.
[25]JACCARD P.Etude comparative de la distribution florale dans une portion des Alpes et du Jura[J].Impr.Corbaz,1901,37(139):547-579.
[26]WU B,WANG B,YANG S Q.Framework for tracking theevent-based evolution in social networks[J].Journal of Software,2011,22(7):1488-1502.
[27]ZHANG Q M,XU X K,ZHU Y X,et al.Measuring multipleevolution mechanisms of complex networks[J].Scientific Reports,2015,5:10350.
[28]HU W B,PENG C,LIANG H L,et al.Event detection method based on link prediction for social network evolution[J].Journal of software,2015,26(9):2339-2355.
[29]WANG H,HU W B,QIU Z Y,et al.An event detection method for social networks based on evolution fluctuations of nodes[J].IEEE Access,2018,6:12351-12359.
[30]KENEDY J,EBERHART R.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Network.Perth,Australia:IEEE Press.1995:1942-1948.
[31]GRINSTEIN G,PLAISANT C,LASKOWSKI S,et al.VAST 2008 Challenge:Introducing mini-challenges[C]//Proceedings of IEEE Symposium on Visual Analytics Science and Technology.Columbus,OH,USA:IEEE Press,2008:195-196.
[32]WANG D F,MENG L.Performance analysis and parameter selection of PSO algorithm[J].Acta Automatica Sinica,2016,42(10):1552-1561.
[33]CAI Q,GONG M,MA L,et al.Greedy discrete particle swarm optimization for large-scale social network clustering[J].Information Sciences,2015,316(41):503-516.

相关文章 15

[1]	孙奇, 吉根林, 张杰. 基于非局部注意力生成对抗网络的视频异常事件检测方法 Non-local Attention Based Generative Adversarial Network for Video Abnormal Event Detection 计算机科学, 2022, 49(8): 172-177. https://doi.org/10.11896/jsjkx.210600061
[2]	李勇, 吴京鹏, 张钟颖, 张强. 融合快速注意力机制的节点无特征网络链路预测算法 Link Prediction for Node Featureless Networks Based on Faster Attention Mechanism 计算机科学, 2022, 49(4): 43-48. https://doi.org/10.11896/jsjkx.210800276
[3]	邵玉, 陈崚, 刘维. 独立级联模型下基于最大似然的负影响力源定位方法 Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model 计算机科学, 2022, 49(2): 204-215. https://doi.org/10.11896/jsjkx.201100190
[4]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[5]	蒲实, 赵卫东. 一种面向动态科研网络的社区检测算法 Community Detection Algorithm for Dynamic Academic Network 计算机科学, 2022, 49(1): 89-94. https://doi.org/10.11896/jsjkx.210100023
[6]	侯春萍, 赵春月, 王致芃. 基于自反馈最优子类挖掘的视频异常检测算法 Video Abnormal Event Detection Algorithm Based on Self-feedback Optimal Subclass Mining 计算机科学, 2021, 48(7): 199-205. https://doi.org/10.11896/jsjkx.200800146
[7]	卿来云, 张建功, 苗军. 在线异常事件检测的时序建模 Temporal Modeling for Online Anomaly Detection 计算机科学, 2021, 48(7): 206-212. https://doi.org/10.11896/jsjkx.200900093
[8]	杨林, 王永杰. 蚁群算法在动态网络持续性路径预测中的运用及仿真 Application and Simulation of Ant Colony Algorithm in Continuous Path Prediction of Dynamic Network 计算机科学, 2021, 48(6A): 485-490. https://doi.org/10.11896/jsjkx.200800132
[9]	丁玲, 向阳. 基于分层次多粒度语义融合的中文事件检测 Chinese Event Detection with Hierarchical and Multi-granularity Semantic Fusion 计算机科学, 2021, 48(5): 202-208. https://doi.org/10.11896/jsjkx.200800038
[10]	吴凡, 朱培培, 王中卿, 李培峰, 朱巧明. 基于字词联合表示的中文事件检测方法 Chinese Event Detection with Joint Representation of Characters and Words 计算机科学, 2021, 48(4): 249-253. https://doi.org/10.11896/jsjkx.200300156
[11]	龚追飞, 魏传佳. 基于改进AdaBoost算法的复杂网络链路预测 Link Prediction of Complex Network Based on Improved AdaBoost Algorithm 计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075
[12]	李鑫超, 李培峰, 朱巧明. 一种基于层级信息优化的有向网络表示学习方法 Directed Network Representation Method Based on Hierarchical Structure Information 计算机科学, 2021, 48(2): 100-104. https://doi.org/10.11896/jsjkx.191200033
[13]	龚追飞, 魏传佳. 基于拓扑相似和XGBoost的复杂网络链路预测方法 Complex Network Link Prediction Method Based on Topology Similarity and XGBoost 计算机科学, 2021, 48(12): 226-230. https://doi.org/10.11896/jsjkx.200800026
[14]	赵曼, 赵加坤, 刘金诺. 基于自我中心网络结构特征和网络表示学习的链路预测算法 Link Prediction Algorithm Based on Ego Networks Structure and Network Representation Learning 计算机科学, 2021, 48(11A): 211-217. https://doi.org/10.11896/jsjkx.201200231
[15]	黄寿孟. 一种基于监督学习的异构网链路预测模型 Heterogeneous Network Link Prediction Model Based on Supervised Learning 计算机科学, 2021, 48(11A): 111-116. https://doi.org/10.11896/jsjkx.210300030

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed