Luận án Một số bài toán tối ưu trên mạng xã hội

án tính bằng công thức sau: TimeSPBA = max{TimePBA(L,G,,δ), T imePBA(U,G,,δ)}+ Timetính Iˆ (3.61) = O(nk1 −2 ln( ( n kmax ) /δ)M) + Time tính Iˆ (3.62) 3.3. Thực nghiệm và kết quả Luận án so sánh Thuật toán SPBA với các thuật toán khác trên nhiều bộ dữ liệu khác nhau để đánh giá hiệu quả của SPBA đối với bài toán BCIM. Các thuật toán được so sánh bao gồm: - Thuật toán BCT [76]: là thuật toán cho tỷ lệ xấp xỉ (1− 1√ e − ) đối với bài toán IM có xét chi phí mỗi đỉnh là khác nhau và tổng chi phí (ngân sách) là giới hạn. Lý do luận án sử dụng BCT để so sánh vì BCIM là một biến thể của IM có sự tương đồng với biến thể mà BCT giải quyết. Với mỗi đỉnh có chi phí khác nhau, các thuật toán xử lý được ràng buộc này đối với IM thì BCT đang là thuật toán tốt nhất. - Degree: chọn lần lượt các đỉnh có bậc cao nhất tới khi đạt đến chi phí giới hạn L. - Random: Chọn ngẫu nhiên các đỉnh cho đến khi đạt đến ngân sách giới hạn L. Các thuật toán Degree và Random là các thuật toán cơ sở (baseline). Lý do chọn chúng trong thực nghiệm là do chúng được sử dụng rộng rãi trong các bài toán lan truyền thông tin [43, 19, 39, 95, 11]. 3.3.1. Dữ liệu và tham số a. Dữ liệu. Luận án sử dụng 6 bộ dữ liệu về các mạng bao gồm: Gnutella, Enron, Epinions, Email-Eu, DBLP và Wiki. Các dữ liệu này đã được thu tập và có sẵn tại Stanford Network Analysis Project 1. Dữ liệu này được sử dụng rộng rãi trong các nghiên cứu liên quan về các bài toán lan truyền thông tin [75, 76]. Thông tin về các bộ dữ liệu này được biểu diễn trong Bảng 3.2. Gnutella. Là một hệ thống mạng ngang hàng trong đó các nút đại diện cho các máy chủ trong cấu trúc liên kết mạng Gnutella và các cạnh thể hiện các kết nối giữa các máy chủ Gnutella. 1https://snap.stanford.edu/data/ 67 Bảng 3.2: Dữ liệu được sử dụng trong thực nghiệm Tên mạng Số đỉnh Số cạnh Loại mạng Bậc trung bình Gnutella[56] 6,301 20,777 Có hướng 3.29 Enron[58] 36.692 183,831 Vô hướng 5.01 Epinions[82] 75,879 508,837 Có hướng 6.7 Email-Eu[56] 265,214 420,045 Có hướng 1.58 DBLP[107] 317,080 1,049,866 Vô hướng 5.01 Wiki-vote [108] 1,791,489 28,511,807 Có hướng 6.7 Eron.Mạng lưới liên lạc email Enron bao gồm tất cả các giao tiếp email trong một bộ dữ liệu khoảng nửa triệu email với các địa chỉ email của Enron. Epinions. Đây là một mạng xã hội trực tuyến đánh giá sự tin cậy của người tiêu dùng Epinions.com. Các thành viên của trang web có thể quyết định có nên “tin tưởng” lẫn nhau hay không. Tất cả các mối quan hệ tin cậy tương tác sau đó được kết hợp với xếp hạng đánh giá để xác định đánh giá nào được hiển thị cho người dùng. Email-Eu.Mạng được tạo bằng dữ liệu email từ một tổ chức nghiên cứu lớn ở châu Âu. DBLP. Là một mạng lưới đồng tác giả, nơi hai tác giả được kết nối nếu họ xuất bản ít nhất một bài báo cùng nhau. Trong mạng này, các tác giả có thể ảnh hưởng lẫn nhau thông qua mối liên hệ đồng tác giả. Wiki-vote. Là một bách khoa toàn thư miễn phí được viết bởi các tình nguyện viên trên khắp thế giới. Một phần nhỏ những người đóng góp Wikipedia là quản trị viên, là người dùng có quyền truy cập vào các tính năng kỹ thuật bổ sung hỗ trợ bảo trì. Trong các dữ liệu trên, các mạng Eron, Epinions, Email-Eu, DPLB, và Wiki-vote là các mạng xã hội hoặc có những tính năng như mạng xã hội. Mục đích thực nghiệm trên các bộ dữ liệu còn lại đánh giá khả năng áp dụng của bài toán BCIM trên các loại mạng khác nhau. b. Tham số. Các tham số của SPBA được thiết lập như trong Bảng 3.3. Cách thiết lập giống với các nghiên cứu trước đó đối với IM [18, 22, 76, 75, 95, 94]. Ngoài ra, tập SB được chọn ngẫu nhiên 10% số đỉnh đối với mỗi mạng. Chi phí của mỗi đỉnh c(u) được chọn ngẫu nhiên trong khoảng [1, 3] theo nghiên cứu trước đối với bài toán IM có xét chi phí [72, 60]. c. Độ đo. Luận án sử dụng thuật toán điều kiện dừng trong [27] để tính Iˆ theo 68 Bảng 3.3: Bảng tham số thí nghiệm cho BCIM Tham số  δ ′ δ′ w(u, v) L τ Giá trị 0.1 1n 0.01 0.01 1 din(v) 100 3, 4, 5 (, δ)-xấp xỉ và so sánh giá trị của ước lượng Iˆ đối với mỗi thuật toán. d. Môi trường. Các thuật toán được viết bằng C++ với trình biên dịch GCC 4.7 trên hệ điều hành Linux với máy cấu hình như sau: 2 x Intel(R) Xeon(R) CPU E5-2697 v4 @ 2.30GHz 8 x 16 GB DIMM ECC DDR4 @ 2400MHz. Tiêu chí đánh giá. Luận án đánh giá sự hiệu quả của các thuật toán thông qua hai tiêu chí: (1) chất lượng lời giải (hàm mục tiêu) và (2) thời gian chạy của các thuật toán. 3.3.2. Kết quả thực nghiệm Để đánh giá toàn diện về kết quả các thuật toán, luận án tiến hành đánh giá các thuật toán theo hai trường hợp: (1) chi phí tổng quát (mỗi đỉnh có chi phí khác nhau được chọn trong khoảng [1, 3]) và (2) chi phí đồng nhất (các đỉnh có chi phí giống nhau bằng 1). 3.3.2.1. Trường hợp chi phí tổng quát Trong kịch bản này, tham số τ = 5, ngân sách L thay đổi từ 0 to 100. Hình 3.6 biểu diễn hiệu quả của các thuật toán theo hàm ảnh hưởng I(SA) trên các bộ dữ liệu Gnutella, Enron, Epinions, Email-Eu, DBLP và Wiki. Trong hình này, trục tung biểu diễn giá trị của hàm mục tiêu I(SA) (ảnh hưởng của tập hạt giống SA), trục hoành biểu diễn các giá trị của ngân sách L. Thuật toán SPBA luôn cho kết quả tốt nhất. Cụ thể SPBA tốt hơn từ 10% đến 30% so với BCT. Lý do cho kết quả này là BCT chỉ xem xét ảnh hưởng của tập hạt giống SA nhưng không xem xét tác động của SB. Thêm vào đó BCT cũng bỏ qua ảnh hưởng của τ . Trong khi đó SPBA có xét các yếu tố về ràng buộc thời gian trong việc ước lượng các hàm xấp xỉ trên và dưới. SPBA gồm ba thành phần và việc chọn lời giải cuối cùng dựa trên kết quả tốt nhất. Kết quả này cũng khẳng định thuật toán cho CTVM và IM (bài toán gần nhất với BCIM) có hiệu quả không cao với BCIM. Degree chỉ hoạt động tốt với bộ dữ liệu Enron nhưng không tốt với các bộ dữ liệu còn lại. SPBA tốt hơn tới 7.7 lần so với Degree. Degree là thuật toán heuristic đơn giản chỉ xét bậc của đỉnh trong quá trình ảnh hưởng cạnh tranh nên cho kết quả không tốt. 69 20 40 60 80 100 Budget(L) 0 1000 2000 3000 4000 5000 In flu en ce sp re ad GNUTELLA Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 5000 10000 15000 20000 In flu en ce sp re ad ENRON Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 5000 10000 15000 20000 In flu en ce sp re ad EPINIONS Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 5000 10000 15000 20000 In flu en ce sp re ad EMAIL-Eu Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 20000 40000 60000 80000 100000 120000 In flu en ce sp re ad DBLP Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 50000 100000 150000 200000 250000 In flu en ce sp re ad Wiki Ramdom Degree SPBA BCT Hình 3.6: So sánh các thuật toán trong trường hợp chi phí tổng quát với τ = 5. 3.3.2.2. Trường hợp chi phí đồng nhất Để chỉ rõ hơn hiệu quả của các thuật toán, luận án so sánh các thuật toán trong trường hợp chi phí bằng nhau và bằng 1 trên các bộ dữ liệu Gnutella, Enron, Epinions and Email-Eu. Hình 3.7 biểu diễn kết quả của các thuật toán trong trường hợp này. SPBA vẫn cho kết quả tốt nhất. Cụ thể, SPBA tốt hơn 1.06 tới 1.76 so với BCT và tốt hơn 1.2 tới 17.2 lần so với Degree. Kết quả này phù hợp với trường hợp trước và khẳng định kết quả nổi trội của thuật toán SPBA. 3.3.2.3. So sánh thời gian chạy Hình 3.8 biểu diễn thời gian chạy của các thuật toán trên 6 bộ dữ liệu với trục tung biểu diễn thời gian chạy, trục hoành biểu diễn các giả trị của ngân sách L. SPBA cho thời gian chạy lâu nhất. Điều này là do thuật toán này gồm ba thành 70 20 40 60 80 100 Budget(L) 0 2000 4000 6000 8000 In flu en ce sp re ad GNUTELLA Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 5000 10000 15000 20000 In flu en ce sp re ad ENRON Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 5000 10000 15000 20000 In flu en ce sp re ad EPINIONS Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 5000 10000 15000 20000 25000 In flu en ce sp re ad EMAIL-Eu Ramdom Degree SPBA BCT Hình 3.7: So sánh các thuật toán trong trường hợp chi phí đồng nhất phần chính là: PBA(L, G, L, , δ), PBA(U, G, L, , δ) và tính toán ước lượng Iˆ(·). Random và Degree là các thuật toán đơn giản nên thời gian chạy rất ngắn. Mặc dù BCT cũng là thuật toán xấp xỉ ngẫu nhiên, tuy nhiên thời gian chạy khá nhanh do có cấu trúc đơn giản hơn so với SPBA. Tuy vậy, SPBA cho thấy thời gian chạy tương đối nhanh với các bộ dữ liệu. Đặc biệt, với mạng Wiki (với 1.79 triệu đỉnh và 28.5 triệu cạnh) SPBA có thể hoàn thành trong 90 giây. 3.3.2.4. Ảnh hưởng của bước thời gian τ Luận án đánh giá ảnh hưởng của τ đối với các thuật toán trong đó τ được thay đổi từ 3 đến 5, ngân sách được cố định L = 50. Các kết quả được biểu diễn trong Hình 3.9 với trục tung biểu diễn hàm mục tiêu và trục hoành biểu diễn các mốc thời gian τ . SPBA vẫn cho kết quả tốt nhất, nó tốt hơn từ 1.01 đến 1.23 lần so với BCT và 2.5 lần so với Degree. Kết quả này cho thấy hiệu quả của SPBA so với các bước thời gian τ . Khi τ càng lớn, ảnh các thuật toán cho kết quả càng cao, điều này cũng cho thấy việc xem xét ảnh hưởng của bước thời gian trong chiến lược cạnh tranh. Trong trường hợp này, thuật toán SPBA cũng cho thấy sự tăng đáng kể nhất với các thuật toán còn lại. Điều này khẳng định thêm tầm quan trọng của ràng buộc thời gian và thuật toán đề xuất. 71 20 40 60 80 100 Budget(L) 0.00 0.25 0.50 0.75 1.00 1.25 1.50 Ru nn in g tim e( s) GNUTELLA Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 10 20 30 40 Ru nn in g tim e( s) ENRON Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 10 20 30 40 Ru nn in g tim e( s) ENRON Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 5 10 15 20 25 30 Ru nn in g tim e( s) EMAIL-Eu Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 10 20 30 40 Ru nn in g tim e( s) DBLP Ramdom Degree SPBA BCT 20 40 60 80 100 Budget(L) 0 20 40 60 80 Ru nn in g tim e( s) WIKI Ramdom Degree SPBA BCT Hình 3.8: So sánh thời gian thực hiện của các thuật toán 3.4. Bài toán tối đa ảnh hưởng cạnh tranh trên mô hình cạnh tranh ngưỡng tuyến tính xác định Trong mục này, luận án mở rộng các kết quả nghiên cứu cho bài toán CIM trên mô hình Cạnh tranh ngưỡng tuyến tính xác định DCLT (Deterministic Competitive Linear Threshold). Mô hình này được tác giả đề xuất dựa trên việc mở rộng mô hình ngưỡng tuyến tính xác định DLT [68] và mô hình CLT [19]. Khác với mô hình LT, trên mô hình này các ngưỡng kích hoạt của các đỉnh được cho trước với giả thuyết rằng các ngưỡng này có thể đánh giá được thông qua các phương pháp khai thác dữ liệu hoặc khảo sát. Một số biến thể của mô hình này như Mô hình bỏ phiếu [118], mô hình phát tán giới hạn cục bộ (Locally Bounded Diffusion Model) [28]. 72 3 4 5 0 1000 2000 3000 4000 In flu en ce sp re ad GNUTELLA Ramdom Degree SPBA BCT 3 4 5 0 2000 4000 6000 8000 10000 12000 In flu en ce sp re ad EPINIONS Ramdom Degree SPBA BCT 3 4 5 0 2000 4000 6000 8000 10000 12000 14000 In flu en ce sp re ad EMAIL-Eu Ramdom Degree SPBA BCT 3 4 5 0 10000 20000 30000 40000 50000 60000 In flu en ce sp re ad DBLP Ramdom Degree SPBA BCT Hình 3.9: So sánh các thuật toán khi τ thay đổi và L cố định Việc sử dụng loại mô mình này và các biến thể làm giảm bớt thời gian tính toán hàm ảnh hưởng cạnh tranh. Trên mô hình này, hàm ảnh hưởng cạnh tranh có thể tính toán được trong thời gian đa thức. 3.4.1. Mô hình và định nghĩa bài toán Trong mô hình này, mỗi cạnh (u, v) cũng có hai trọng số wA(u, v) và wB(u, v) biểu diễn ảnh hưởng của A và B trên cạnh (u, v). Sự khác nhau giữa mô hình CLT với mô hình DCLT là: mỗi đỉnh v có hai ngưỡng kích hoạt θA(v) và θB(v) được cho trước, và (ii) bước lan truyền giới hạn là (steps) d. Quá trình lan truyền diễn ra theo các bước rời rạc t = 1, . . . , d như sau: Tại bước t = 0, A0 = A, B0 = B. Tại bước t ≥ 1, mỗi đỉnh v sẽ bị kích hoạt bởi A nếu thõa mãn điều kiện sau: ∑ u∈Nin(v)wA(u, v) ≥ θA(v)∑ u∈Nin(v)wB(u, v) < θB(v) (3.63) hoặc ∑ u∈Nin(v) wA(u, v) ≥ ∑ u∈Nin(v) wB(u, v) + αA (3.64) 73 Tương tự, đỉnh v bị kích hoạt bở B nếu: ∑ u∈Nin(v)wA(u, v) < θA(v)∑ u∈Nin(v)wB(u, v) ≥ θB(v) (3.65) hoặc ∑ u∈Nin(v) wB(u, v) ≥ ∑ u∈Nin(v) wA(u, v) + αB (3.66) Trong đó αA, αB được gọi hệ số kiềm chế của A với B và B với A. αA giải thích rằng v bị ảnh hưởng bởi A khi tổng trọng số ảnh hưởng của A lớn hơn đáng kể so với tổng trọng số ảnh hưởng của B. Quá trình lan truyền dừng lại tại bước lan truyền d. Với tập SA ⊆ V chúng ta có thể tính toán ảnh hưởng IA(SA) trong thời gianO(m+n) bằng việc sử dụng thuật toán BFS. Trong trường hợp này bài toán CIM được định nghĩa cụ thể như sau: Định nghĩa 3.6. (Tối đa ảnh hưởng cạnh tranh -CIM trên DCLT) • Input: Cho một MXHTT G = (V,E) dưới một mô hình ảnh hưởng cạnh tranh DCLT. Có hai đối thủ cạnh tranh là A và B, cho trước SB, thời gian giới hạn là d, ngân sách k2. • Output: Tìm tập hạt giống của A là SA với SA ∈ V \ SB, |SA| ≤ k sao cho số người dùng bị ảnh hưởng bởi SA là lớn nhất. Độ phức tạp của bài toán CIM trên mô hình DCLT được phát biểu qua định lý sau: Định lý 3.7. CIM là bài toán NP-Khó và không thể xấp xỉ được trong thời gian đa thức với tỷ lệ n1− trên mô hình DCLT với giả thuyết P 6= NP. Chứng minh. Ta chứng minh rằng nếu có thuật toán đa thức P có thể xấp xỉ CIM với tỷ lệ n1−, thì tồn tại thuật toán xấp xỉ bài toán Tập phủ (SC) trong thời gian đa thức. Xét phiên bản quyết định của SC được định nghĩa như sau: Tập phủ (SC) Cho số nguyên dương t, tập vũ trụ U = {e1, e2, ..., eM} và bộ sưu tập các tập con S = {S1, S2, ..., SN}, với t < M < N . Có hay không tập con gồm t phần tử của S sao cho hợp của chúng bằng U? Cho một thể hiện ISC = (U , t, S) ta xây dựng phép dẫn đa thức tới thể hiện ICIM = (G,SB, k) như sau: Phép dẫn. Với mỗi tập Si ∈ S, tạo đỉnh ui; với mỗi ej , tạo một đỉnh vj , đặt X = 2sử dụng trong trường hợp chi phí các đỉnh đồng nhất và số đỉnh chọn là k 74 {ui|i = 1 . . . n}, Y = {vj |j = 1 . . .m}. Thêm các cạnh (ui, vj) vào E nếu ej ∈ Si, với i = 1 . . . n, j = 1, . . . ,m, ta đặt SA = X và SB = ∅. Đặt các trọng số wA(ui, vj) = 1 |Nin(vj)| , wB(ui, vj) = 0, với (ui, vj) ∈ E, θA(ui) = 1|Nin(ui)| , θB(vj) = 1|Nin(vj)| , αA = αB = 0, t = k. Với mỗi đỉnh vj ∈ Y ta thêm một tập Z = {z1, z2, . . . , zQ} gồm Q đỉnh với Q > max{N, 13e ln(6N)  }. Thêm Q cạnh (vj , zl), l = 1 . . . Q, với các trọng số wA(vj , zl) = 1, wB(vj , zl) = 0, l = 1 . . . Q. Dễ thấy phép dẫn có thể thực hiện được trong thời gian đa thức. Ta xét hai trường hợp sau: Trường hợp 1: Nếu ISC không có lời giải dễ thấy có ít nhất một đỉnh v ∈ Y không bị kích hoạt bởi tập SA được chọn bất kỳ. Điều này dẫn tới tập Z không bị ảnh hưởng bởi A. Do đó OPT < k +M < 2N . Trường hợp 2: Nếu ISC có lời giải S′, ta chọn SA = {ui|Si ∈ S′} là lời giải của CIM. Bằng phép dẫn ở trên, ta thấy rằng các đỉnh trong Y đều bị kích hoạt bởi A. Xét các đỉnh zl ∈ Z, ta có ∑ v∈Nin(zl) = 1 = θA(zl). Bởi vậy σ(SA) = t+ |Y |+ |Z| = k+M+Q = OPT. Trong trường hợp này, vì thuật toán P có thể xấp xỉ CIM với tỷ lệ n1− (n = N +M +Q), nên nó có thể tìm S′A thỏa mãn: σ(S′A) ≥ 1 n1− OPT = k +M +Q (N +M +Q)1− (3.67) > Q (3Q)1− = (3Q) 3 (do Q > N > M) (3.68) > 2N (do Q > 13e ln(6N)  ) (3.69) Điều này chứng tỏ ISC có lời giải t nếu và chỉ nếu σ(S′A) < 2N . Do vậy ta có thể dùng P để tìm lời giải cho SC. Điều này trái với việc SC là bài toán thuộc lớp NP-đầy đủ. 3.4.2. Các thuật toán cho CIM trên mô hình DCLT Trong phần này, tác giả đề xuất hai thuật toán cho bài toán CIM bao gồm Thuật toán tham lam (Greedy) và Thuật toán tham lam nâng cao (Greedy+ +). Vì hàm mục tiêu không có tính chất submodular nên hai thuật toán này không cho tỷ lệ xấp xỉ. Thuật toán tham lam phỏng theo ý tưởng của thuật toán tham lam đối với IM của Kempe [43]. Tại mỗi bước nó chọn đỉnh u có hàm đo lợi ích lớn nhất δ(SA, u) = σA(SA + {u})− σA(SA). (3.70) đến khi lựa chọn được k đỉnh. Các bước chi tiết được mô tả trong Thuật toán 14. Độ phức tạp của thuật toán này là O(kn(m + n)). Thuật toán Greedy + + là một phiên bản cải tiến của thuật toán tham lam trong đó cải tiến kỹ thuật “lazy evaluation" trong [57]. Các bước chi tiết được trình bày trong Thuật toán 15. Thuật toán này dựa trên giả sử hàm 75 mục tiêu vẫn là submodular với ý tưởng chính không xem xét các đỉnh có lợi ích thấp trong các vòng lặp sau. Algorithm 14: Thuật toán tham lam (Greedy) Data: Graph G = (V,E), SB, propagation hop d, budget k Result: SA 1 begin 2 SA ←− ∅ 3 for i = 1 to k do do 4 δmax ←− 0 5 foreach u ∈ V \ {SA ∪ SB} do 6 if δ(A ∪ u) > δmax then 7 δmax ←− δ(A ∪ u), umax ←− u; 8 end 9 end 10 If δmax = 0 then return SA else A←− A ∪ {umax} 11 end 12 return SA; 13 end Algorithm 15: Thuật toán Greedy + + Input: Graph G = (V,E, θ), SB, d, k, p Output: SA 1 begin 2 A←− ∅; Priority queue Q←− ∅; 3 iteration←− 1; 4 foreach u ∈ V \ {B} do 5 u.value←− δ(u) u.iteration←− 1 6 insert u into Q with u.value as the key; 7 end 8 choose p top elements of queue Q; 9 while iteration ≤ k do 10 extract top element u of Q; 11 if u.iteration = iteration then 12 SA ←− SA ∪ {u}; 13 iteration+ + 14 pop element u of Q; 15 else 16 u.value←− σA(SA ∪ u)− σA(SA); 17 u.iteration←− iteration 18 re-insert u into Q 19 end 20 end 21 return SA; 22 end Thuật toán sử dụng một hàng đợi Q để lưu p đỉnh ứng viên. Trong đó mỗi đỉnh u có hai trường: u.value chỉ giá trị δ(SA, u) ở vòng lặp hiện tại và u.iteration chỉ vòng lặp hiện tại mà đỉnh u đang được xem xét. Để hạn chế thời gian tính toán, thuật toán chọn p đỉnh ứng viên có giá trị lợi ích lớn nhất trong Q (dòng 7). Trong mỗi vòng lặp, thuật toán chọn đỉnh u có giá trị u.value lớn nhất, kiểm tra vòng lặp của đỉnh này, nếu giá trị này được xét ở vòng lặp hiện tại thì thêm vào tập lời giải SA (dòng 11-14). Nếu không 76 cập nhật lại giá trị của đỉnh này và vị trí của nó trong Q (dòng 16-18). Độ phức tạp của thuật toán Greedy+ + vẫn là O(kn(m+n)), tuy nhiên thực nghiệm chỉ ra nó có thời gian chạy nhanh hơn Greedy nhiều lần. 3.4.3. Thực nghiệm Luận án tiến hành thực nghiệm so sánh thuật toán Greedy,Greedy + + với hai thuật toán cơ sở là: Random và Degree. a. Dữ liệu và tham số. Dữ liệu thực nghiệm được mô tả trong Bảng 3.4 3. Bảng 3.4: Dữ liệu được sử dụng trong thực nghiệm Mạng Số đỉnh Số cạnh Loại Bậc trung bình Nguồn email-EU 1005 25571 có hướng 25.44 [56] Gnutella#1 6,301 20,777 có hướng 3.30 [56] Gnutella#2 36682 88328 có hướng 2.41 [56] Epinions 75879 508837 có hướng 6.71 [82] Trọng số được chọn theo các nghiên cứu trước đối với IM [43, 75, 22, 18]. SB được chọn ngẫu nhiên với số đỉnh là 50 và 100 tùy theo kích cỡ mạng. Các tham số được trình bày trong Bảng 3.5. Bảng 3.5: Bảng tham số thí nghiệm cho CIM Tham số θA(v), θB(v) w(u, v) k d p (Greedy + +) Giá trị ngẫu nhiên trong [0, 1] 1 din(v) 50 3, 4, 5 1000 Các thí nghiệm được thực hiện trên máy tính có cấu hình Intel (R) Core i7-4510U CPUs with 2.00GHz, 8GB RAM với ngôn ngữ C++. Thời gian giới hạn cho các thuật toán là 12h. b. Kết quả thực nghiệm. Các kết quả thực nghiệm được biểu diễn trong các Hình 3.10 và Hình 3.11. Greedy cho kết quả tốt nhất nhưng không áp dụng được với các mạng Gnutella-2 và Epinion vì vượt quá thời gian giới hạn là 12h. Thuật toán Greedy + + cho kết quả xấp xỉ với Greedy 3Phần mô tả các loại mạng được trình bày trong thực nghiệm trước nên luận án không trình bày ở các mục sau. 77 nhưng có thời gian chạy nhanh hơn từ 17.5 đến 103 lần. Lý do là thuật tham lam phải 0 50 100 150 200 250 300 350 400 0 5 10 15 20 nu m be r o f i nf lu en ce d no de s by A k email-EU, d = 5, B = 50 nodes Greedy Greedy++ Max Degree Random 0 200 400 600 800 1000 1200 0 5 10 15 20 ru nt im e (s ec on ds ) k email-EU, d = 5, B = 50 nodes Greedy Greedy++ Max Degree Random 0 500 1000 1500 2000 2500 3000 0 10 20 30 40 50 nu m be r o f i nf lu en ce d no de s by A k gnutella#1, d = 5, B = 100 nodes Greedy Greedy++ Max Degree Random 0 5000 10000 15000 20000 25000 30000 35000 40000 0 10 20 30 40 50 ru nt im e (s ec on ds ) k gnutella#1, d = 5, B = 100 nodes Greedy Greedy++ Max Degree Random 0 1000 2000 3000 4000 5000 6000 7000 0 10 20 30 40 50 nu m be r o f i nf lu en ce d no de s by A k gnutella#2, d = 5, B = 100 nodes Greedy++ Max Degree Random 0 200 400 600 800 1000 0 10 20 30 40 50 ru nt im e (s ec on ds ) k gnutella#2, d = 5, B = 100 nodes Greedy++ Max Degree Random 0 2000 4000 6000 8000 10000 12000 0 10 20 30 40 50 nu m be r o f i nf lu en ce d no de s by A k epinion, d = 5, B = 100 nodes Greedy++ Max Degree Random 0 10000 20000 30000 40000 50000 60000 70000 0 10 20 30 40 50 ru nt im e (s ec on ds ) k epinion, d = 5, B = 100 nodes Greedy++ Max Degree Random Hình 3.10: So sánh các thuật toán khi k thay đổi 0 500 1000 1500 2000 2500 3000 0 1 2 3 4 5 nu m be r o f i nf lu en ce d no de s by A d gnutella#1, k = 50, B = 315 nodes Greedy++ Max Degree Random 0 200 400 600 800 1000 0 1 2 3 4 5 ru nt im e (s ec on ds ) d gnutella#1, k = 50, B = 315 nodes Greedy++ Max Degree Random 0 1000 2000 3000 4000 5000 6000 7000 0 1 2 3 4 5 nu m be r o f i nf lu en ce d no de s by A d gnutella#2, k = 50, B = 100 nodes Greedy++ Max Degree Random 0 200 400 600 800 1000 0 1 2 3 4 5 ru nt im e (s ec on ds ) d gnutella#2, k = 50, B = 100 nodes Greedy++ Max Degree Random Hình 3.11: So sánh các thuật toán khi d thay đổi tính lại hàm lợi ích của tất cả các đỉnh ở mỗi vòng lặp còn Greedy++ đã rút ngắn được thời gian chạy do chỉ xét các đỉnh có lợi ích cao nhất và cập nhật lại thay vì tính giá trị này đối với tất cả các đỉnh. Về chất lượng lời giải, Greedy++ cho kết quả tương tự Greedy chứng tỏ hiệu quả của chỉ chọn p = 1000 đỉnh có lợi ích lớn nhất cũng đảm bảo chất lượng lời giải. Các thuật toán cơ sở cho kết quả không tốt, Greedy + + và Greedy cho kết quả hơn Degree tới 1.65 lần. Điều này chứng tỏ hiệu quả của việc lựa chọn các đỉnh dựa trên hàm lợi ích đối với Greedy và Greedy + +. Luận án cũng thực nghiệm trường hợp khi k cố định và d thay đổi bằng 3, 4, 5. Thuật toán Greedy + + vẫn hoạt động tốt và cho giá trị tăng dần khi d tăng. 3.5. Kết luận chương Trong chương này, luận án trình bày kết quả nghiên cứu bài toán tối đa ảnh hưởng cạnh tranh tổng quát với thời gian và ngân sách hạn chế BCIM trên các MXHTT. Luận án đề xuất thuật xấp xỉ SPBA cho BCIM trên mô hình TCLT. Các thực nghiệm được tiến hành trên các bộ dữ liệu chuẩn được công bố chỉ ra thuật toán đề xuất cho hiệu quả nổi trội so với các thuật toán hiện dùng bao gồm: Kết quả cũng chỉ ra SPBA có thể 78 áp dụng với các mạng lớn hàng triệu đỉnh và cạnh (bộ dữ liệu Wiki bao gồm gần 1,8 triệu đỉnh và 28,5 triệu cạnh). Luận án cũng đề xuất nghiên cứu bài toán CIM trên mô hình ngưỡng tuyến tính cạnh tranh xác định DCLT. Trên mô hình này, luận án chỉ ra có thể tính toán hàm mục tiêu trong thời gian đa thức và đề xuất hai thuật toán hiệu quả là Greedy và Greedy + +. Thực nghiệm cũng được tiến hành để chỉ ra hiệu quả của 2 thuật toán đề xuất. Tuy vậy, một nhược điểm khi áp dụng giải pháp giải pháp này trong thực tiễn cần có nhưng giải pháp thu thập dữ liệu một cách hiệu quả cho các MXHTT, tiền xử lý các tham số cho mô hình để đáp ứng các yêu cầu đầu vào của bài toán BCIM. Ngoài ra cần “ làm mịn” thêm mô hình để phù hợp hơn với thực tiễn. Trong tương lai, tác giả sẽ tiếp tục cải tiến thêm thuật toán SPBA về thời gian chạy và đề xuất thuật toán heuristic tốt hơn đối với thuật toán CIM trên mô hình DCLT. Ngoài ra tác giả mở rộng các nghiên cứu theo khắc phục các nhược điểm trên để phù hợp hơn với thực tiễn. 79 CHƯƠNG 4 NGĂN CHẶN THÔNG TIN SAI LỆCH VỚI RÀNG BUỘC VỀ NGÂN SÁCH VÀ THỜI GIAN Việc ngăn chặn thông tin sai lệch (TTSL) được quan tâm nghiên cứu nhiều trong những năm gần đây do những tác hại lớn của TTSL gây ra. Tuy nhiên, những nghiên cứu trước đó thường bỏ qua hai yếu tố quan trọng trong việc giảm thiểu thiệt hai do TTSL gây là: ngân sách cho việc phòng ngừa và thời gian ngăn chặn sự phát tán. Trong chương này, luận án nghiên cứu bài toán hạn chế thông tin sai lệch với ràng buộc về ngân sách và thời gian (MMR) trên mô hình LT. Luận án đưa ra một số kết quả lý thuyết về độ khó của bài toán và đề xuất một số thuật toán hiệu quả cho bài toán. Các thuật