Ngân sách tối thiểu phát hiện thông tin sai lệch trên mạng xã hội trực tuyến, đảm bảo đạt ít nhất một ngưỡng cho trước
Minimum Budget for Misinformation Source Detection in Online Social Networks with Guaranteed to Reach at Least a Given Threshold
Abstract
Phát hiện nguồn phát tán thông tin sai lệch trên mạng xã hội trực tuyến đóng vai trò quan trọng trong việc hạn
chế hành vi sai trái trên mạng. Các nghiên cứu gần đây cho thấy, phương pháp đặt máy giám sát có thể phát hiện nguồn thông tin sai lệch. Tuy nhiên, không thể đặt máy giám sát đối với tất cả người dùng mạng vì ngân sách hạn chế. Trong bài báo này, một mạng xã hội được biểu diễn bởi đồ thị có hướng, mỗi người dùng là một nút trên đồ thị và phát tán thông tin trên đồ thị theo mô hình Bậc độc lập. Trên mô hình này, giả sử biết trước tập nút nghi ngờ sẽ phát tán thông tin sai lệch, chúng tôi đề xuất tìm tập nút nhỏ nhất để đặt giám sát sao cho số nút bị phát hiện đạt ít nhất một ngưỡng cho trước. Ba thuật toán xấp xỉ được đề xuất, bao gồm: Tham lam, phát hiện thông tin sai lệch dựa trên tập mẫu phát hiện và phát hiện thông tin sai lệch dựa trên tập mẫu phát hiện quan trọng. Các thử nghiệm được thực hiện trên bộ dữ liệu của mạng xã hội thực cho thấy các thuật toán của chúng tôi đề xuất vượt trội hơn các thuật toán khác cả về hiệu suất và thời gian thực hiện.
References
“Misinformation on social media led to pune violence: Minister,” in https://www.ndtv.com/mumbainews/misinformation-on-social-media-led-to-pune-violenceminister-1795562, 2018.
P. Domm, “False rumor of explosion at white house causes stocks to briefly plunge; ap confirms its twitter feed was hacked,” in Available: https://www.cnbc.com/id/100646197, 2013.
V. Luckerson, “Fear, misinformation, and social media complicate ebola fight,” in http://time.com/3479254/ebolasocial-media/, 2014.
S. Kwon, M. Cha, K. Jung, W. Chen, and Y. Wang, “Prominent features of rumor propagation in online social media,” in 2013 IEEE 13th International Conference on Data Mining, Dallas, TX, USA, December 7-10, 2013, 2013, pp. 1103–1108. [Online]. Available: https://doi.org/10.1109/ICDM.2013.61
J. Ma, W. Gao, and K. Wong, “Detect rumors in microblog posts using propagation structure via kernel learning,” in Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017, Vancouver, Canada, July 30 - August 4, Volume 1: Long Papers, 2017, pp. 708–717. [Online]. Available: https://doi.org/10.18653/v1/P17-1066
W. Chen, Y. Yuan, and L. Zhang, “Scalable influence maximization in social networks under the linear threshold model,” in ICDM 2010, The 10th IEEE International Conference on Data Mining, Sydney, Australia, 14-17 December 2010, 2010, pp. 88–97. [Online]. Available: https://doi.org/10.1109/ICDM.2010.118
J. Leskovec, M. McGlohon, C. Faloutsos, N. S. Glance, and M. Hurst, “Patterns of cascading behavior in large blog graphs,” in Proceedings of the Seventh SIAM International Conference on Data Mining, April 26-28, 2007, Minneapolis, Minnesota, USA, 2007, pp. 551–556. [Online]. Available: https://doi.org/10.1137/1.9781611972771.60
H. Zhang, A. Kuhnle, H. Zhang, and M. T. Thai, “Detecting misinformation in online social networks before it is too late,” in 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2016, San Francisco, CA, USA, August 18-21, 2016, 2016, pp. 541–548. [Online]. Available: https://doi.org/10.1109/ASONAM.2016.7752288
H. Zhang, H. Zhang, X. Li, and M. T. Thai, “Limiting the spread of misinformation while effectively raising awareness in social networks,” in Computational Social Networks - 4th International Conference, CSoNet 2015, Beijing, China, August 4-6, 2015, Proceedings, 2015, pp. 35–47. [Online]. Available: https://doi.org/10.1007/978-3-319-21786-4_4
H. Zhang, M. A. Alim, X. Li, M. T. Thai, and H. T. Nguyen, “Misinformation in online social networks: Detect them all with a limited budget,” ACM Trans. Inf. Syst., vol. 34, no. 3, pp. 18:1–18:24, 2016. [Online]. Available: http://doi.acm.org/10.1145/2885494
C. V. Pham, H. M. Dinh, H. D. Nguyen, H. T. Dang, and H. X. Hoang, “Limiting the spread of epidemics within
time constraint on online social networks,” in Proceedings of the Eighth International Symposium on Information and Communication Technology, Nha Trang City, Viet Nam, December 7-8, 2017, 2017, pp. 262–269. [Online]. Available: https://doi.org/10.1145/3155133.3155157
D. V. Pham, G. L. Nguyen, T. N. Nguyen, C. V. Pham, and A. V. Nguyen, “Multi-topic misinformation blocking with budget constraint on online social networks,” IEEE Access, vol. 8, pp. 78 879–78 889, 2020.
E. B. Khalil, B. N. Dilkina, and L. Song, “Scalable diffusion-aware optimization of network topology,” in The
th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014, 2014, pp. 1226–1235. [Online]. Available: http://doi.acm.org/10.1145/2623330.2623704
C. V. Pham, M. T. Thai, H. V. Duong, B. Q. Bui, and H. X. Hoang, “Maximizing misinformation restriction within time and budget constraints,” J. Comb. Optim., vol. 35, no. 4, pp. 1202–1240, 2018. [Online]. Available: https://doi.org/10.1007/s10878-018-0252-3
H. T. Nguyen, A. Cano, V. Tam, and T. N. Dinh, “Blocking self-avoiding walks stops cyber-epidemics: A scalable gpubased approach,” IEEE Transactions on Knowledge and Data Engineering, pp. 1–1, 2019.
D. Kempe, J. M. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 24 - 27, 2003, 2003, pp. 137–146. [Online]. Available: http://doi.acm.org/10.1145/956750.956769
W. Chen, A. Collins, R. Cummings, T. Ke, Z. Liu, D. Rincón, X. Sun, Y. Wang, W. Wei, and Y. Yuan, “Influence maximization in social networks when negative opinions may emerge and propagate,” in Proceedings of the Eleventh SIAM International Conference on Data Mining, SDM 2011, April 28-30, 2011, Mesa, Arizona, USA, 2011, pp. 379–390. [Online]. Available: https://doi.org/10.1137/1.9781611972818.33
C. V. Pham, D. V. Pham, B. Q. Bui, and A. V. Nguyen, “Minimum budget for misinformation detection in online social networks with provable guarantees,” Optimization Letters, pp. 1–30, 2021.
C. Borgs, M. Brautbar, J. T. Chayes, and B. Lucier, “Maximizing social influence in nearly optimal time,” in
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, 2014, pp. 946–957. [Online]. Available: https://doi.org/10.1137/1.9781611973402.70
Y. Tang, X. Xiao, and Y. Shi, “Influence maximization: near-optimal time complexity meets practical efficiency,” in International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, 2014, pp. 75–86. [Online]. Available: http://doi.acm.org/10.1145/2588555.2593670
Y. Tang, Y. Shi, and X. Xiao, “Influence maximization in near-linear time: A martingale approach,” in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, 2015, pp. 1539–1554. [Online]. Available: http://doi.acm.org/10.1145/2723372.2723734
G. Das, C. M. Jermaine, and P. A. Bernstein, Eds., Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018. ACM, 2018. [Online]. Available: https://doi.org/10.1145/3183713
H. T. Nguyen, M. T. Thai, and T. N. Dinh, “Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks,” in Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, 2016, pp. 695–710. [Online]. Available: http://doi.acm.org/10.1145/2882903.2915207
A. Goyal, F. Bonchi, L. V. S. Lakshmanan, and S. Venkatasubramanian, “On minimizing budget and time in influence propagation over social networks,” Social Netw. Analys. Mining, vol. 3, no. 2, pp. 179–192, 2013. [Online]. Available: https://doi.org/10.1007/s13278-012-0062-z
F. R. K. Chung and L. Lu, “Survey: Concentration inequalities and martingale inequalities: A survey,” Internet Mathematics, vol. 3, no. 1, pp. 79–127, 2006. [Online]. Available: https://doi.org/10.1080/15427951.2006.10129115
H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich,“Local higher-order graph clustering,” in Proceedings of the
rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13 - 17, 2017, 2017, pp. 555–564. [Online]. Available: https://doi.org/10.1145/3097983.3098069
J. Leskovec, J. M. Kleinberg, and C. Faloutsos, “Graph evolution: Densification and shrinking diameters,” TKDD, vol. 1, no. 1, p. 2, 2007. [Online]. Available: https://doi.org/10.1145/1217299.1217301
J. Leskovec, D. P. Huttenlocher, and J. M. Kleinberg, “Signed networks in social media,” in Proceedings of the 28th International Conference on Human Factors in Computing Systems, CHI 2010, Atlanta, Georgia, USA, April 10-15, 2010, 2010, pp. 1361–1370. [Online]. Available: https://doi.org/10.1145/1753326.1753532
——, “Predicting positive and negative links in online social networks,” in Proceedings of the 19th International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, USA, April 26-30, 2010, 2010, pp. 641–650. [Online]. Available: https://doi.org/10.1145/1772690.1772756
Y. Zhang and B. A. Prakash, “Data-aware vaccine allocation over large networks,” TKDD, vol. 10, no. 2, pp. 20:1–20:32, 2015. [Online]. Available: http://doi.acm.org/10.1145/2803176