A Markov Chain Monte Carlo Approach for Source Detection in Networks

被引:3
作者
Zhang, Le [1 ]
Jin, Tianyuan [1 ]
Xu, Tong [1 ]
Chang, Biao [1 ]
Wang, Zhefeng [1 ]
Chen, Enhong [1 ]
机构
[1] Univ Sci & Technol China, Sch Comp Sci & Technol, Anhui Prov Key Lab Big Data Anal & Applicat, Hefei, Anhui, Peoples R China
来源
SOCIAL MEDIA PROCESSING, SMP 2017 | 2017年 / 774卷
基金
美国国家科学基金会; 中国国家自然科学基金;
关键词
Social network; Source detection; Markov Chain Monte Carlo;
D O I
10.1007/978-981-10-6805-8_7
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The source detection task, which targets at finding the most likely source given a snapshot of the information diffusion, has attracted wide attention in theory and practice. However, due to the hardness of this task, traditional techniques may suffer biased solution and extraordinary time complexity. Specially, source detection task based on the widely used Linear Threshold (LT) model has been largely ignored. To that end, in this paper, we formulate the source detection task as a Maximum Likelihood Estimation (MLE) problem, and then proposed a Markov Chain Monte Carlo (MCMC) algorithm, whose convergence is demonstrated. Along this line, to further improve efficiency of proposed algorithm, the sampling method is simplified only on the observed graph rather than the entire one. Extensive experiments on public data sets show that our MCMC algorithm significantly outperforms several state-of- the-art baselines, which validates the potential of our algorithm in source detection task.
引用
收藏
页码:77 / 88
页数:12
相关论文
共 50 条
[31]   Towards derandomising Markov chain Monte Carlo [J].
Feng, Weiming ;
Guo, Heng ;
Wang, Chunyang ;
Wang, Jiaheng ;
Yin, Yitong .
2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS, 2023, :1963-1990
[32]   Proximal Markov chain Monte Carlo algorithms [J].
Pereyra, Marcelo .
STATISTICS AND COMPUTING, 2016, 26 (04) :745-760
[33]   Proximal Markov chain Monte Carlo algorithms [J].
Marcelo Pereyra .
Statistics and Computing, 2016, 26 :745-760
[34]   Approaching MIMO Capacity Using Bitwise Markov Chain Monte Carlo Detection [J].
Chen, Rong-Rong ;
Peng, Ronghui ;
Ashikhmin, Alexei ;
Farhang-Boroujeny, Behrouz .
IEEE TRANSACTIONS ON COMMUNICATIONS, 2010, 58 (02) :423-428
[35]   Front-view vehicle detection by Markov chain Monte Carlo method [J].
Jia, Yangqing ;
Zhang, Changshui .
PATTERN RECOGNITION, 2009, 42 (03) :313-321
[36]   Sample caching Markov chain Monte Carlo approach to boson sampling simulation [J].
Liu, Yong ;
Xiong, Min ;
Wu, Chunqing ;
Wang, Dongyang ;
Liu, Yingwen ;
Ding, Jiangfang ;
Huang, Anqi ;
Fu, Xiang ;
Qiang, Xiaogang ;
Xu, Ping ;
Deng, Mingtang ;
Yang, Xuejun ;
Wu, Junjie .
NEW JOURNAL OF PHYSICS, 2020, 22 (03)
[37]   A straightforward approach to Markov chain Monte Carlo methods for item response models [J].
Patz, RJ ;
Junker, BW .
JOURNAL OF EDUCATIONAL AND BEHAVIORAL STATISTICS, 1999, 24 (02) :146-178
[38]   A Multilevel Markov Chain Monte Carlo Approach for Uncertainty Quantification in Deformable Registration [J].
Schultz, Sandra ;
Handels, Heinz ;
Ehrhardt, Jan .
MEDICAL IMAGING 2018: IMAGE PROCESSING, 2018, 10574
[39]   Bayesian connective field modeling using a Markov Chain Monte Carlo approach [J].
Invernizzi, Azzurra ;
Haak, Koen V. ;
Carvalho, Joana C. ;
Renken, Remco J. ;
Cornelissen, Frans W. .
NEUROIMAGE, 2022, 264
[40]   A multiobjective Markov chain Monte Carlo approach for history matching and uncertainty quantification [J].
Olalotiti-Lawal, Feyi ;
Datta-Gupta, Akhil .
JOURNAL OF PETROLEUM SCIENCE AND ENGINEERING, 2018, 166 :759-777