3. Cấu trúc luận văn
3.1 Cài đặt thử nghiệm
3.1.1 Mục đích thử nghiệm
Mục đích thử nghiệm để so sánh hiệu quả, thời gian chạy của các thuật toán sử dụng bao gồm: thuật toán tham lam cải tiến IGA, thuật toán tham lam mở rộng GEA với các thuật toán phổ biến đối với các bài toán lan truyền thông tin (các thuật toán cơ sở) bao gồm:
• Random: Thuật toán chọn ngẫu nhiên k đỉnh trong đồ thị.
• Degree : Thuật toán Heuristic chọn lần lượt các đỉnh có bậc cao nhất và thêm vào tập đỉnh bị chặn.
Tập dữ liệu tác giả sử dụng là các tập dữ liệu chuẩn thường được sử dụng trong các bài toán lan truyền thông tin. Các thử nghiệm được thực hiện trên 03 tập dữ liệu, Gnutella [29], Epinions [30] và NetHepPh [31] của các mạng thực với kích thước lên đến hàng chục nghìn đỉnhvà hàng trăm nghìn cạnh, được thu thập Từ nguồn [http://snap.stanford.edu/data/]. Một số thống kê của các tập dữ liệu được cung cấp trong Bảng 2.
Bảng 2. Tập dữ liệu
Tập dữ liệu Loại Số đỉnh Số cạnh Bậc trung bình
Gnutella [29] Có hướng 6K 20K 3.29
Epinions [30] Có hướng 75K 508K 6.7 NetHepP [31] Có hướng 34K 421K 12.2
45
3.1.2 Cài đặt tham số
Vì khó có thể xác định chính xác trọng số ảnh hưởng của đỉnh 𝑢 đối với đỉnh 𝑣 trong đồ thị 𝐺, nên căn cứ trên các nghiên cứu trước [20, 24, 26], các nghiên cứu giả định rằng các tập cạnh vào ra của đỉnh bị nhiễm thông tin sai lệch có đóng góp như nhau trong việc kích hoạt các đỉnh lân cận, các tham số được thiết lập như sau:
• Trọng số của mỗi cạnh (𝑢, 𝑣) là: 𝑤(𝑢, 𝑣) = |Nin(𝑣)|1 , với Nin(𝑣) là tập đỉnh vào của đỉnh 𝑣.
• ∑𝑢∈𝑁𝑖𝑛(𝑣)𝑤(𝑢, 𝑣)= 1. Mỗi cạnh có đóng góp như nhau trong việc kích hoạt một đỉnh 𝑣.
• 𝑝𝑣𝑖 và 𝛾𝑣𝑖 được khởi tạo ngẫu nhiên trong phạm vi [0,1].
• Chi phí cho việc chặn đỉnh 𝑐(𝑣), 𝑣 ∈ 𝑉 được khởi tạo ngẫu nhiên trong khoảng [1.0, 3.0].
• Nguồn phát tán thông tin sai lệch 𝑆: 𝑆1 =𝑆2 =𝑆3 = 100.
Trong trường hợp chi phí giống hệt nhau, tác giả tiến hành đặt 𝑐(𝑣) = 1. Phương pháp mô phỏng MC trong các thuật toán được thực hiện để tính toán gần đúng kết quả. Đối với thuật toán IGA, mô phỏng MC được thực hiện để ước tính kết quả của hàm mục tiêu 𝜎(. ). Thuật toán GEA được cập nhật nhanh chóng với giá trị hàm mục tiêu dựa trên phép duyệtsâu sử dụng cấu trúc cây và mẫu số trung bình gần đúng trên tất cả các cây𝑇𝑖.
Tất cả các thuật toán được lập trình bằng ngôn ngữ Python. Các thử nghiệm được thực hiện trên hệ điều hành Linux với CPU Intel Core i7 – 8550U 1.8Ghz, RAM 8GB DDR4 2400MHz.
3.2 Đánh giá hiệu quả của thuật toán trong thiết lậpchi phí đơn vị
Để đánh giá hiệu quả của các thuật toán IGA và GEA, tác giả tiến hành một số thử nghiệm trong điều kiện thiết lập chi phí cho việc ngăn chặn mỗi đỉnh. Trong thiết lập chi phí đơn vị, chi phí cho việc chặn một đỉnh 𝑐(𝑣) là 1 cho tất cả các tập dữ liệu. Ngân sách 𝐵 được cài đặt cho thay đổi từ 0 đến 100. Hiệu quả được
46
đo dựa trên kết quả trung bình của hàm khuếch tán 𝜎 (𝐺, 𝑆, 𝐴) của công thức 4. Hình 3.2a, 3.2b, 3.2c cho thấy kết quả của tất cả các thuật toán. Khi ngân sách tăng lên, số lượt kích hoạt trung bình của đồ thị cũng tăng theo. Có thể thấy, với thiết lập 𝑐(𝑣)=1, GEA có hiệu quả tốt nhất, tiếp theo là IGA và cả hai thuật toán đều hoạt động tốt hơn Random và Degree với biên độ lớn. Lý do là Degree chỉ sử dụng các thuộc tính cấu trúc liên kết mạng xã hội mà không thể xem xét quá trình tác động của các đỉnh nguồn còn Random thì thêm các đỉnh ngẫu nhiên vào tập đỉnh chặn trong giới hạn ngân sách. Trong hình 3c, buộc phải dừng IGA sớm ở ngân sách lớn hơn 40 vì việc tính toánnày mất rất nhiều thời gian.
Hình 3.2 a. Hiệu quả các thuật toán với thiết lập 𝑐(𝑣)=1 trên tậpdữ liệu mạng
47
Hình 3.2 b. Hiệu quả các thuật toán với thiết lập 𝑐(𝑣)=1 trên tậpdữ liệu mạng
Gnutella
Hình 3.2 c. Hiệu quả các thuật toán với thiết lập 𝑐(𝑣)=1 trên tậpdữ liệumạng
48
3.3. Đánh giá hiệu quả của thuật toán trong chi phí chung
Trong thử nghiệm này, tác giả giữ nguyên ngân sách 𝐵 thay đổi từ 0 đến 100 và đối với thiết lập chi phí chung, chi phí cho việc chặn một đỉnh 𝑐(𝑣) trong phạm vi [1.0, 3.0] cho tất cả các tập dữ liệu. Trong hình 3.3 a, 3.3 b, 3.3 c, cả hai thuật toán GEA và IGA đều hoạt động tốt hơn các thuật toán Random và Degree. Thuật toán GEA hiệu quả hơn từ 1,1 đến 2,24 lần so với thuật toán IGA và hiệu quả hơn tới 121 lần so với thuật toán Degree xét về số lượt kích hoạt trung bình. Trong quá trình thử nghiệm, tiến hành dừng IGA sớm với ngân sách lớn hơn 40 trên tập dữ liệu mạng Epinions vì thuật toán này mất rất nhiều thời gian (lâu hơn 72 giờ).
Hình 3.3 a. Hiệu quả các thuật toán với thiết lập 𝑐(𝑣)∈ [1.0, 3.0] trên tậpdữ liệu mạng Gnutella
49
Hình 3.3 b. Hiệu quả các thuật toán với thiết lập 𝑐(𝑣)∈ [1.0, 3.0] trên tập dữ liệu mạng NetHepP
Hình 3.3 c. Hiệu quả các thuật toán với thiết lập 𝑐(𝑣)∈ [1.0, 3.0] trên tậpdữ liệu mạng Epinions
50
3.4. So sánh thời gian chạy
Cuối cùng, tác giả tiến hành so sánh các thuật toán IGA, GEA, Random và Degree với thời gian chạy của chúng. Hình 3.4 a, 3.4 b, 3.4 c và Hình 3.4 d, 3.4 e, 3.4 f hiển thị thời gian chạy của các thuật toán trong thiết lập chi phí đơn vị và chi phí chung trên 3 tập dữ liệu. Thời gian chạy tăng lên khi ngân sách 𝐵tăng lên. Việc lấy kết quả thời gian chạy của các thuật toán được thực hiện đồng thời với thử nghiệm đánh giá hiệu quả các thuật toán trong mục 3.2 và 3.3.
3.4.1 So sánh thời gian chạy các thuật toán trong cài đặt chi phí đơn vị
Để thể hiện rõ hơn về hiệu suất của các thuật toán này, tác giả thử nghiệm thời gian chạy của các thuật toán theo chi phí đơn vị (tất cả chi phí xóa bỏ một đỉnh 𝑐(𝑣)đều bằng 1) trên tất cả các tậpdữ liệu. Hình 3.4 a, 3.4 b, 3.4 c hiển thị kết quả của tất cả các thuật toán dưới cài đặt chi phí đơn vị.
Hình 3.4 a. Thời gian chạy các thuật toán với thiết lập 𝑐(𝑣)=1 trên tập dữ liệu mạng Gnutella
51
Hình 3.4 b. Thời gian chạy các thuật toán với thiết lập 𝑐(𝑣)=1 trên tập dữ liệu mạng NetHepP
Hình 3.4 c. Thời gian chạy các thuật toán với thiết lập 𝑐(𝑣)=1 trên tập dữ liệu mạng Epinions
Các thuật toán Tham lam và Random có thể chạy rất nhanh ngay cả trên các mạng lớn. Tuy nhiên, thuật toán GEA cũng đạt được thời gian chạy rất cạnh tranh. Lý do là kỹ thuật phân nhóm và tính toán cây hiệu quả. IGA là thuật toán chậm nhất vì tốn nhiều thời gian trong mô phỏng MC.
52
3.4.2 So sánh thời gian chạy các thuật toán trong cài đặt chi phí chung
Trong thử nghiệm thời gian chạy các thuật toán trong cài đặt chi phí chung, tác giả thiết lập chi phí cho việc chặn một đỉnh 𝑐(𝑣)trong phạm vi [1.0, 3.0] cho tất cả các tập dữ liệu. Hình 3.4 d, 3.4 e, 3.4 f hiển thị kết quả của tất cả các thuật toán dưới cài đặt chi phí chung.
Hình 3.4 d. Thời gian chạy các thuật toán với thiết lập 𝑐(𝑣)∈ [1.0, 3.0] trên tập dữ liệumạng Gnutella
53
Hình 3.4 e. Thời gian chạy các thuật toán với thiết lập 𝑐(𝑣)∈ [1.0, 3.0] trên tập dữ liệumạng NetHepP
Hình 3.4 f. Thời gian chạy các thuật toán với thiết lập 𝑐(𝑣)∈ [1.0, 3.0] trên tập dữ liệumạng Epinions
Thời gian chạy trong cài đặt chi phí chung của tất cả các thuật toán đều lớn hơn 1,05 đến 1,2 lần so với cài đặt chi phí đơn vị. Trong tất cả các cài đặt, GEA chạy nhanh hơn IGA tới 196 lần.
3.5 Kết luận chương
Trong phần này, tác giả đã tiến hành các thử nghiệm để cho thấy hiệu quả của các thuật toán IGA và GEA, các thuật toán được so sánh với các thuật toán Degree và Random trên cùng một thiết lập của mô hình MT-LT. Các tham số được cài đặt thủ công và giả định rằng các cạnh có vai trò như nhau trong việc kích hoạt một đỉnh trong đồ thị. Trong tất cả các thử nghiệm, IGA và GEA đều cho kết quả vượt trội về số lượt kích hoạt trung bình do hai thuật toán đã xét quá trình tác động của các đỉnh nguồn trên các tập dữ liệu. Thuật toán IGA chạy chậm nhất do việc mô phỏng MC mất rất nhiều thời gian.
54
KẾT LUẬN
Trong luận văn này, tác giả đã thực nghiệm mô hình ngăn chặn thông tin sai lệch đa chủ đề lan truyền trên MXH với nguồn ngân sách hạn chế. Tác giả lập mô hình bài toán dưới dạng bài toán tối ưu hóa kết hợp dựa trên mô hình MT-LT với các yêu cầu về đa chủ đề và ngân sách cố định cho việc lựa chọn đỉnh. Trong mô hình MT-LT, sự lan truyền thông tin được mô hình hóa dựa trên các mức độ ảnh hưởng và ngưỡng kích hoạt khác nhau cho từng chủ đề. Vấn đề MMTBcũng được đề cập dựa trên mô hình MT-LT. Tác giảchứng minhrằng bài toán MMTB là NP-Khó, tính toán của hàm mục tiêu là #P-Khó và hàm mục tiêu là đơn điệu và có tính chất Submodular. Tác giả ứng dụng thuật toán Tham lam cải tiến IGA và thuật toán Tham lam mở rộng GEA cho kết quả vượt trội trên thực nghiệm cho những tập dữ liệu mô phỏng MXH dưới dạng đồ thị có hàng trăm nghìn đỉnh và cạnh.
Kết quả đạt được:
• Tìm hiểu tổng quan về mạng xã hội, sự lây lan và tác hại của thông tin sai lệch trên mạng xã hội.
• Tìm hiểu cơ chế lan truyền thông tin và đặc tính của các mô hình lan truyền thông tin: mô hình ngưỡng tuyến tính (LT) và mô hình ngưỡng tuyến tính đa chủ đề MT-LT. Tác giả tìm hiểu các hướng nghiên cứu liên quan đến bài toán ngăn chặn thông tin sai lệch lan truyền trên mạng xã hội đã công bố.
• Thực nghiệm, đánh giámô hình lan truyền thông tin ngưỡng tuyến tính đa chủ đề với hai thuật toán IGA và GEA.Kết quả thực nghiệm cho thấy các thuật toán IGA và GEA vượt trội hơn thuật toán cơ sở Random và Greedy.
Mặc dù đã cố gắng và nỗ lực hết mình, nhưng do thời gian nghiên cứu và trình độ của bản thân có hạn nên luận văn không thể tránh khỏi những thiếu sót và hạn chế, tác giả rất mong nhận được những ý kiến đóng góp để luận văn đạt được kết quả tốt hơn.
55 Định hướng nghiên cứu tiếp theo:
✓ Nghiên cứu và tìm cách cải tiến các thuật toán tham lam để tối ưu bài toán hơn nữa.
✓ Có thể áp dụng các kỹ thuật Heuristic như thuật toán di truyền, đàn kiến…để giảm thời gian tính toán và giảm chi phí.
56
TÀI LIỆU THAM KHẢO
[1] P. Domm, “False rumor of explosion at white house causes stocks to briefly plunge; ap confirms its twitter feed was hacked,” 2018. [Online]. Available: http://www.cnbc.com/id/100646197.
[2] H. Allcott, M. Gentzkow, “Social media and fake news in the 2016 election,” 2019. [Online]. Available: https://web.stanford.edu/ gentzkow/ research/ fakenews.pdf.
[3] 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, pages 137–146, 2003.
[4] N. Barbieri, F. Bonchi, and G. Manco. Topic-aware social influence propagation models. Knowledge and Information Systems, 37(3):555– 584, 2013.
[5] W. Chen, L. V. S. Lakshmanan, and C. Castillo. Information and Influence Propagation in Social Networks. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2013.
[6] W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010, pages 1029–1038, 2010.
[7] 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, pages 88–97, 2010.
57
[8] N. P. Nguyen, G. Yan, and M. T. Thai. Analysis of misinformation containment in online social networks. Computer Networks, 57(10):2133– 2146, 2013.
[9] 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, pages 262–269, 2017.
[10] C. V. Pham, Q. V. Phu, and H. X. Hoang. Targeted misinformation blocking on online social networks. In Intelligent Information and Database Systems - 10th Asian Conference, ACIIDS 2018, Dong Hoi City, Vietnam, March 19-21, 2018, Proceedings, Part I, pages 107– 116, 2018.
[11] Dung V. Pham, Giang L. Nguyen, Tu N. Nguyen, Canh V. Pham, Anh V. Nguyen. Multi-Topic Misinformation Blocking With Budget Constraint on Online Social Networks, IEEE, 2020.
[12] Twitter deletes 125,000 isis accounts and expands anti-terror teams.
[13] C. Song, W. Hsu, and M. Lee. Node immunization over infectious period. In Proceedings of the 24th ACM International Conference on Information and Knowledge Management, CIKM 2015, Melbourne, VIC, Australia, October 19 - 23, 2015, pages 831–840, 2015.
[14] E. B. Khalil, B. N. Dilkina, and L. Song. Scalable diffusion-aware optimization of network topology. In The 20th ACM SIGKDD Inter- national Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014, pages 1226–1235, 2014. [15] H. T. Nguyen, A. Cano, T. N. Vu, and T. N. Dinh. Blocking self-avoiding
walks stops cyber-epidemics: A scalable gpu-based approach. IEEE Transactions on Knowledge and Data Engineering, 2019.
[16] Statista. 2021. Number of social network users worldwide from 2017 to 2025. 07/15/2021, from https://www.statista.com/statistics/ 278414/
58
[17] Statista. 2021. Facebook usage penetration in Vietnam from 2017 to 2023. 07/15/2021, From https://www.statista.com/statistics/553800/.
[18] Karlova and Fisher. A Social Diffusion Model of Misinformation and Disinformation for Understanding Human Information Behaviour. Proceedings of the ISIC (Tokyo), 2012.
[19] V. Luckerson. Fear, misinformation, and social media complicate ebola fight. In http://time.com/3479254/ebola-social-media/, 2014.
[20] Y. Zhang, A. Adiga, S. Saha, A. Vullikanti, and B. A. Prakash, “Near- optimal algorithms for controlling propagation at group scale on networks,” IEEE Trans. Knowl. Data Eng., vol. 28, no. 12, pp. 3339– 3352, 2016. [21] L. G. Valiant, W. Wu and D. Z. Du, "Distributed rumor blocking with
multiple positive cascades", IEEE Trans. Comput. Social Syst., vol. 5, no. 2, pp. 468-480, Mar. 2018.
[22] M. Kimura, K. Saito, and H. Motoda, “Solving the contamination minimization problem on networks for the linear threshold model,” in PRICAI 2008, Hanoi, Vietnam, December 15-19, 2008. Proceedings, 2008, pp. 977–984.
[23] M. Kimura, K. Saito, and H.Motoda, “Blocking links to minimize contamination spread in a social network,” ACM TKDD, vol. 3, no. 2, pp. 9:1–9:23, 2009.
[24] Y. Zhang and B. A. Prakash, “Data-aware vaccine allocation over large networks,” TKDD, vol. 10, no. 2, pp. 20:1–20:32, 2015.
[25] Y. Zhang and A. Prakash, “Scalable vaccine distribution in large graphs given uncertain data,” in The 23rd ACM CIKM 2014, Shanghai, China, November 3-7, 2014, 2014, pp. 1719–1728.
[26] C. V. Pham, M. T. Thai, H. V. Duong, B. Q. Bui, and H. X. Hoang. Maximizing misinformation restriction within time and budget con- straints. J. Comb. Optim., 35(4):1202–1240, 2018.
59
[27] C. V. Pham, Q. V. Phu, H. X. Hoang, J. Pei, and M. T. Thai. Mini – mum budget for misinformation blocking in online social networks. J. Comb. Optim., 38(4):1101–1127, 2019.
[28] L. G. Valiant, W. Wu and D. Z. Du, "Distributed rumor blocking with multiple positive cascades", IEEE Trans. Comput. Social Syst., vol. 5, no. 2, pp. 468-480, Mar. 2018.
[29] J. Leskovec, J. M. Kleinberg, and C. Faloutsos, “Graph evolution: Densification and shrinking diameters,” TKDD, vol. 1, no. 1, p. 2, 2007. [30] J. Leskovec, M. Kleinberg, and C. Faloutsos, “Graphs over time:
densification laws, shrinking diameters and possible explanations,” in The Eleventh ACM SIGKDD, Chicago, Illinois, USA, August 21-24, 2005, 2005, pp. 177–187.
[31] M. Richardson, R. Agrawal, and P. M. Domingos, “Trust management for