Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (2): 204-215.doi: 10.11896/jsjkx.201100190

• Database & Big Data & Data Science • Previous Articles     Next Articles

Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model

SHAO Yu, CHEN Ling, LIU Wei   

  1. College of Information Engineering,Yangzhou University,Yangzhou,Jiangsu 225000,China
  • Received:2020-11-26 Revised:2021-03-24 Online:2022-02-15 Published:2022-02-23
  • About author:SHAO Yu,born in 1996,postgraduate,is a member of China Computer Federation.Her main research interests include data mining and complex network.
    CHEN Ling,born in 1951,professor,Ph.D supervisor,is a member of China Computer Federation,IEEE CS society and ACM,a senior member of the Chinese Computer Society.His main research interests include data mining complex network and artificial intelligence.
  • Supported by:
    National Natural Science Foundation of China(61379066,61702441,61070047,61379064,61472344,61402395,61602202),Natural Science Foundation of Jiangsu Province(BK20130452,BK2012672,BK2012128,BK20140492,BK20160428),Natural Science Foundation of Jiangsu Provincial Department of Education(12KJB520019,13KJB520026,09KJB20013) and Jiangsu Province Postgraduate Trai-ning Innovation Project(CXZZ13_0173).

PDF (PC)

487

Abstract: Nowadays,the spread of negative influences such as internet rumors,infectious diseases and computer viruses has caused huge hidden dangers to social stability,human health and information security.It is of great significance to identify the source of their propagation to control the harm caused by the negative influence.However,most of the existing methods only focus on locating a single propagation source,while in the real world network,negative influence often comes from multiple sources.And the methods require time consuming simulation of the propagation process.In addition,due to ignoring the difference of topology features between the nodes,the accuracy of propagation source locating is not high and large amount of computation time is required.In order to solve these problems,a maximum likelihood based method is proposed to locate multiple sources using the information provided by a small number of observation points.Firstly,the concept of propagation graph is defined,and a method for constructing propagation graph is proposed.In the propagation graph,nodes in the network are divided into several levels according to their degrees and the weight of the edges.The edges with low propagation probability are removed,and the propagation graph is formed by combining observation nodes.Then,the activation probability of each node in each layer of the propagation graph is calculated,and the k nodes with the maximum likelihood relative to the observation points are selected to form the source node set.The simulation results show that the proposed method can accurately identify multiple propagation sources in the network,and the results of source location is higher than other similar algorithms.At the same time,it is verified that the selection of observation points and the network structure also affect the positioning results of propagation sources to varying degrees.

Key words: Independent cascade model, Influence propagation, Likelihood maximization, Location of propagation source, Social networks

CLC Number: 

  • O157.5
[1]YANG F,YANG S,PENG Y,et al.Locating the propagation source in complex networks with a direction-induced search based Gaussian estimator[J].Knowledge-Based Systems,2020,195:105674.
[2]WANG H J,ZHANG F F,SUN K J.An algorithm for locating propagation source in complex networks[J].Physics Letters A,2021,393:127184.
[3]PALUCH R,LU X,SUCHECKI K,et al.Fast and accurate detection of spread source in large complex networks[J].Scientific Reports,2018,8(1):2508.
[4]PINTO P C,THIRAN P,VETTERLI M.Locating the source of diffusion in large-scale networks[J].Phys. Rev. Lett.,2012,109(6):68702.
[5]ZANG W,ZHANG P,ZHOU C,et al.Discovering Multiple Diffusion Source Nodes in Social Networks[J].Procedia Computerscience,2014,29:443-452.
[6]HU Z,SHEN Z,CAO S,et al.Locating multiple diffusionsources in time varying networks from sparse observations[J].Scientific Reports,2018,8(1):2685.
[7]JIANG J,WEN S,YU S,et al.Rumor Source Identification in Social Networks with Time-Varying Topology[J].IEEE Tran-sactions on Dependable and Secure Computing,2018,15(1):166-179.
[8]HUANG Q,ZHAO C,ZHANG X,et al.Locating the source of spreading in temporal networks[J].Physica A:Statistical Mechanics and its Applications,2017,468:434-444.
[9]DONG M,ZHENG B,HUNG N Q V,et al.Multiple rumor source detection with graphconvolutional networks[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management.2019:569-578.
[10]WANG H.An universal algorithm for source location in complex networks[J].Physica A:Statistical Mechanics and its Applications,2019,514:620-630.
[11]YANG X,ZHU Z,YU H,et al.A Naming Game-Based Method for the Location of Information Source in Social Networks[J].Complexity,2020,2020:1-8.
[12]ZANG W,ZHANG P,ZHOU C,et al.Locating multiple sources in social networks under the SIR model:A divide-and-conquer approach[J].Journal of Computational Science,2015,10:278-287.
[13]DING Y,CUI X,WANG H,et al.PRIA:a Multi-source Recognition Method Based on Partial Observation in SIR Model[J].Mobile Networks and Applications,2020,25(1):271-280.
[14]ZHANG Z,YUE K,SUN Z,et al.Locating Sources in OnlineSocial Networks via Random Walk[C]//2017 IEEE Internatio-nal Congress on Big Data (Big Data Congress).IEEE,2017:337-343.
[15]LI X,LIU Y,ZHAO C,et al.Locating Multiple Sources of Contagion in Complex Networks under the SIR Model[J].Applied Sciences,2019,9(20):4472.
[16]LI X,WANG X,ZHAO C,et al.Optimal Identification of Multiple Diffusion Sources in Complex Networks with Partial Observations[C]//The International Conference on Natural Computation,Fuzzy Systems and Knowledge Discovery.2019:214-223.
[17]ALI S S,ANWAR T,RIZVI S A M.A Revisit to the Infection Source Identification Problem under Classical Graph Centrality Measures[J].Online Social Networks and Media,2020,17(1):100061.
[18]SHAH D,ZAMAN T.Rumors in a Network:Who's the Culprit?[J].IEEE Transactions on Information Theory,2011,57(8):5163-5181.
[19]SEJEONG K,MEEYOUNG C,KYOMIN J.Rumor Detectionover Varying Time Windows[J].PloS one,2017,12(1):e0168344.
[20]FANG M,SHI P,SHANG W,et al.Locating the Source ofAsynchronous Diffusion Process in Online Social Networks[J].IEEE Access,2018,6:17699-17710.
[21]LI X,WANG X,ZHAO C,et al.Locating the Epidemic Source in Complex Networks with Sparse Observers[J].Applied Sciences,2019,9(18):3644.
[22]LI X,WANG X,ZHAO C,et al.Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction[J].Applied Sciences,2019,9(18):3758.
[23]LEE C,SUNG C,MA H,et al.IDR:Positive Influence Maximization and Negative Influence Minimization Under Competitive Linear Threshold Model[C]//2019 20th IEEE International Conference on Mobile Data Management (MDM).IEEE,2019:501-506.
[24]LI Y,FAN J,WANG Y,et al.Influence Maximization on Social Graphs:A Survey[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(10):1852-1872.
[25]TANG Y,SHI Y,XIAO X.Influence Maximization in Near-Li-near Time:A Martingale Approach[C]//Proceedings of the 2015 ACM SIGMOD Internatio-nal Conference on Management of Data.2015:1539-1554.
[26]ZHOU J,FAN J,WANG J,et al.Cost-Efficient Influence Maximization in Online Social Networks[C]//2017 Fifth Internatio-
nal Conference on Advanced Cloud and Big Data (CBD).IEEE,2017:232-237.
[27]WANG F,SHE J,OHYAMA Y,et al.Maximizing positive influence in competitive social networks:A trust-based solution[J].Information Sciences,2021,546:559-572.
[28]LI L,LIU Y,ZHOU Q,et al.Targeted influence maximizationunder a multifactor-based information propagation model[J].Information Sciences,2020,519:124-140.
[29]TRIVEDI N,SINGH A.Efficient Influence Maximization in Social-Networks Under Independent Cascade Model[J].Procedia Computer Science,2020,173:315-324.
[30]LV J,YANG B,YANG Z,et al.A community-based algorithm for influence blocking maximization in social networks[J].Cluster Computing,2019,22(3):5587-5602.
[31]DING J,SUN W,WU J,et al.Influence maximization based on the realistic independent cascade model[J].Knowledge-Based System,2020,191:105265.
[32]FU L,SHEN Z,WANG W X,et al.Multi-source localization on complex networks with limited observers[J].EPL (Europhysics Letters),2016,113(1):18006.
[33]WOO J,CHOI J.Estimating the Information Source under Deca-ying Diffusion Rates[J].Electronics,2019,8(12):1384.
[34]KONG F,LI Q Z,LI S.Survey on Online Influence Maximization[J].Computer Science,2020,47(5):7-13.
[35]MA Y Y,HAN H,QU Q Q.Importance Evaluation Algorithm Based on Node Intimate Degree[J].Computer Science,2021,48(5):140-146.
[36]DEVARAPALLI R K,BISWAS A.Rumor Detection and Tra-cing its Source to Prevent Cyber-Crimes on Social Media[C]//Intelligent Data Analytics for Terror Threat Prediction:Architectures,Methodologies,Techniques and Applications.2021:1-30.
[37]LI W M,LI Z,LUVEMBE A M,et al.Influence maximization algorithm based on Gaussian propagation model[J].Information Sciences,2021,568:386-402.
[1] WEI Peng, MA Yu-liang, YUAN Ye, WU An-biao. Study on Temporal Influence Maximization Driven by User Behavior [J]. Computer Science, 2022, 49(6): 119-126.
[2] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[3] ZHANG Shao-jie, LU Xu-dong, GUO Wei, WANG Shi-peng, HE Wei. Prevention of Dishonest Behavior in Supply-Demand Matching [J]. Computer Science, 2021, 48(4): 303-308.
[4] YUAN De-yu, CHEN Shi-cong, GAO Jian, WANG Xiao-juan. Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game [J]. Computer Science, 2021, 48(3): 313-319.
[5] MA Li-bo, QIN Xiao-lin. Topic-Location-Category Aware Point-of-interest Recommendation [J]. Computer Science, 2020, 47(9): 81-87.
[6] LIANG Jun-bin, ZHANG Min, JIANG Chan. Research Progress of Social Sensor Cloud Security [J]. Computer Science, 2020, 47(6): 276-283.
[7] KONG Fang, LI Qi-zhi, LI Shuai. Survey on Online Influence Maximization [J]. Computer Science, 2020, 47(5): 7-13.
[8] WU Lei,YUE Feng,WANG Han-ru,WANG Gang. Academic Paper Recommendation Method Combined with Researcher Tag [J]. Computer Science, 2020, 47(2): 51-57.
[9] GU Qiu-yang, JU Chun-hua, WU Gong-xing. Social Network Information Recommendation Model Combining Deep Autoencoder and Network Representation Learning [J]. Computer Science, 2020, 47(11): 101-112.
[10] ZHANG Zheng, WANG Hong-zhi, DING Xiao-ou, LI Jian-zhong, GAO Hong. Identification of Same User in Social Networks [J]. Computer Science, 2019, 46(9): 93-98.
[11] LV Zhi-quan, LI Hao, ZHANG Zong-fu, ZHANG Min. Topic-based Re-identification for Anonymous Users in Social Network [J]. Computer Science, 2019, 46(6): 143-147.
[12] YUAN De-yu, GAO Jian, YE Meng-xi, WANG Xiao-juan,. Malicious Information Source Locating Algorithm Based on Topological Extension in Online Social Network [J]. Computer Science, 2019, 46(5): 129-134.
[13] HAN Zhong-ming, ZHENG Chen-ye, DUAN Da-gao, DONG Jian. Associated Users Mining Algorithm Based on Multi-information Fusion Representation Learning [J]. Computer Science, 2019, 46(4): 77-82.
[14] XU Fang, DENG Min, XIONG Zeng-gang, YE Cong-huan, XU Ning. Data Forwarding Algorithm Based on Multidimensional Context Matching in Mobile Social Networks [J]. Computer Science, 2019, 46(2): 81-87.
[15] CHEN Jiong, ZHANG Hu, CAO Fu-yuan. Study on Point-of-interest Collaborative Recommendation Method Fusing Multi-factors [J]. Computer Science, 2019, 46(10): 77-83.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.