Luận án Một số phương pháp nâng cao hiệu quả dự báo lan truyền thông tin trên mạng xã hội

Nội dung text: Luận án Một số phương pháp nâng cao hiệu quả dự báo lan truyền thông tin trên mạng xã hội

1. 72 trong đó,훿 𝑖 là xác suất mà nội dung c thuộc về chủ đề Ci, P(Ci) là xác suất của chủ đề Ci, 푃( | 𝑖) là xác suất mà thuộc tính xk thuộc về chủ đề Ci và xk là một thuộc tính của nội dung c. Giả định rằng sự ưu tiên (hay sở thích) của người dùng với các chủ đề là độc lập. Dựa trên các sự kiện mà người dùng v đã thực hiện trong lịch sử hoạt động, ta có thể xác ịđ nh mức độ quan tâm của v đối với chủ đề Ci, được biểu thị bởi ρv,i, như sau: 푙 ℎ 𝜌푣,𝑖 = 1 − ∏(1 − 훿𝑖 ) (21) ℎ=1 ℎ trong đól là số lượng nội dung mà v đãch ấp nhận và 훿𝑖 là xác suất mà nội dung thứ h kích hoạtv , thuộc về chủ đề Ci được đưa ra trong công thức (20). Khi một nội dung c đang được lan truyền trong mạng xã hội, xác suất dựa trên sở thích người dùng rằng người dùng v sẽ được kích hoạt bởi c được tính bằng sự giống nhau giữa chủ đề của c và sở thích của v về chủ đề đó. Ta sẽ áp dụng thước đo độ tương tự Cosine để xác ịđ nh độ tương tự giữa c và sở thích của v đối với chủ đề của c, ký hiệu là 휇푣, như: ∑ 𝑖=0 𝜌푣,𝑖훿𝑖 휇푣 = (22) 2 2 √∑𝑖=0(𝜌푣,𝑖) √∑𝑖=0(훿𝑖 ) Trong đó, ρv,i là mức độ quan tâm của v đối với chủ đề Ci như được đưa ra trong công thức (21). Như vậy, kết hợp ảnh hưởng của mối quan hệ người dùng và sở thích của người dùng, ta tính được xác suất người dùng u kích hoạt người dùng v liên quan đến nội dung c như sau: 푣 = 훼(휏 푣) + (1 − 훼)휇푣 (23) Trong đó, α ∊ [0, 1], τuv là phép đo ảnh hưởng của u trên v, được đưa ra trong công thức (17) và 휇푣 được đưa ra trong công thức (22) ở trên. Công thức được xây dựng dựa trên xác định mối tương quan giữa hai ảnh hưởng, cho thấy quyết định chủ quan của người dùng trong việc lan truyền thông tin. Lưu ý rằng, không giống nhưảnh hưởng sở thích người dùng, ảnh hưởngtừ mối quan hệ giữa những người dùng là độc lập, không phụ thuộc vàonội dung.
2. 74 Số lượng nút kích hoạt dự kiến cho tập S các nút lan truyền được xác định bởi công thức: (푆) = ∑ 훾(푣) (25) 푣∈ 푆 Vì chúng ta đã biếtp uv và bằng cách đặtI(S) = k, ta có thể dễ dàng ước tính giá trị của Δext bằng cách giải quyết công thức (25). Như vậy, ảnh hưởng kết hợp giữa hai unút và v có thể được định nghĩa đơn giản là tổng củap uv và Δext. Tuy nhiên, có một vấn đề là tổng này có thể có giá trị lớn hơn 1. Để buộc giá trị nằm trong khoảng từ 0 đến 1, ta ánh xạ nó thông qua hàm logistic, được giới hạn trong khoảng từ 0 đến 1 là: 1 ( 푣 + ∆푒 푡) = (26) 1 + 푒 − ( 푣+∆푒 푡) Để đơn giản, ta có thể chọn A=1/2 và B=4. Hình dạng của hàm logistic tương ứng được hiển thị trong Hình 3.3. Hình 3.3. Hình dạng của hàm logistic 3.3.4. Xây dựng cây lan truyền Nội dung thứ hai của phương pháp nâng cao độ chính xác dự báo lan truyền thông tin trên mạng xã hội là việc xây dựng cây lan truyền “có khả năng nhất” cho một nội dung cụ thể dựa trên các xác suất đã tính. Mỗi nút của cây tương ứng với một người dùng đã chấp nhận nội dung và mỗi cạnh liên kết với một người dùng khác được gọi là“gốc” của nó. Việc xây dựng cây sẽ tương đối đơn giản nếu chúng ta biết chính xác người dùng nào khiến người dùng khác chấp nhận
3. 76 6: Vu ← tập các nút không hoạt động ∊ V là hàng xóm của u; 7: for each nốt v ∊ Vu do; 8: calculate xác xuất lan truyền puv từ u đến v theo công thức (23); 9: for each nút hoạt động mới v do; 10: find gốc có khả năng nhất u của v theo công thức (27); 11: make một liên kết từ u đến v; 12: stop nếu không có nút lan truyền nào nữa; 13: end Thuật toán 3.1 tạo ra cây lan truyền có khả năng nhất (cây có xác suất cao nhất). Xác suất của việc tạo ra cây T được xác định bởi công thức: 푃( ) = ∏ 푣 (28) ( ,푣)∈ ( ) Công thức trên cho thấy xác suất của một cây chính xác là rất nhỏ, tuy nhiên, nó sẽ là cây gần với “sự thật cơ bản” nhất. Hình dạng của cây lan truyền với một nội dung có dạng như sau: u0 t0 u1 u2 t1 u3 u4 u5 u6 t2 Hình 3.5. Hình dạng cây lan truyền Trong đó, u0, u1, un là người dùng tiếp nhận nội dung tại các thời điểm t1, t2, tn. Từ cây lan truyền ta có thể xác định bậc lan truyền, số người dùng tiếp nhận thông tin và đường đi của thông tin. 3.4. Thực nghiệm và kết quả 3.4.1. Dữ liệu thực nghiệm Trong phạm vi Luận án, Nghiên cứu sinh sử dụng ba bộ dữ liệu: - Bộ dữ liệu mô phỏng (DS1): bộ dữ liệu do nhóm nghiên cứu Viện Công nghệ thông tin phát triển,sử dụng chương trình Kronecker [99] với phương pháp tạo dữ liệuđược mô tả trong100 [ ], [101], [102] để tạo10 đồ thị có cấu trúc “lõi -
4. 78 truyền được tính là puv = 1/din(v) trong đó din(v) là bậc vào của nút v, như trong [94], [97]. - Mô hình tương tác người dùng UI: có xem xét ảnh hưởng quan hệ người dùng [107]. - Mô hình hồi quy RM: ước tính kích thước lan truyền bằng cách hồi quy các tính năng dựa trên người dùng, nội dung và thời gian [108]. Để so sánh các phương pháp,t a áp dụng sai số tương đối để thấy kích thước lan truyền ước tính từ “sự thật cơ bản”. Các sai số tươngđối của lan truyền ước tính được tính như sau: Î(푆) | − 1|.100% (29) (푆) Trong đóÎ(S) là kích thước lan truyền ước tínhtập của hạt giống S theo các phương pháp I(S)và là sự thật cơ bản Scho . Trong các thực nghiệm,để đơn giản, tậpS chỉ có 1 nút. Tiếp theo là đánh giá việc sử dụng các phương pháp đểtạora Cây lan truyền có khả năng nhất (cây có xác suất cao nhất). Do mô hình RM chỉ có thể ước tính kích thước lan truyền, nên sẽ loại ra khỏi thực nghiệm. Đối với phương pháp đề xuất, mô hình IC và UI, để công bằng, ta “tỉa” lại cây bằng cách sử dụng ngưỡng θ: bất kỳ cạnh nào có xác suất lan truyền dướiθ sẽ bị loại bỏ khỏi cây. Trong thực nghiệm, ta đặt θ = 50% và so sánh kích thước của các cây ước tính vớicây lan truyền thực tế. 3.4.3. Kết quả thực nghiệm Với các dữ liệu, ta sẽ sử dụng 5000 lần thông tin được lan truyền. Trong đó,sử dụng 4000 lần thông tin lan truyền để tính toán các tham số trong các công thức tính xác suất, sau đó sử dụng 1000 lần lan truyền để thử nghiệm, tính toán kết quả theo các phương pháp và so sánh với thực tế lan truyền Đầu tiên, ta tiến hành thực nghiệm việc ước tính kích thước lan truyền và kích thước cây có khả năng nhấtcủa các phương pháp trong trường hợp khi chưa xét đến ảnh hưởng từ bên ngoài. Lưu ý, trong tất cả các thực nghiệm, giá trị của
5. 80 Hình 3.6. Biểu diễn chi tiết hiệu suất của các phương pháp chưa xét ảnh hưởng bên ngoài Tiếp theo, ta thêm yếu tố bên ngoài ảnh hưởng đến xác suất lan truyền của các mô hình. Ta sẽ kiểm tra ảnh hưởng này bằng cách sử dụng 5% các bậc lớn nhất từ bộ dữ liệu Meme và Tencent Weibo (do Bộ dữ liệu mô phỏng không thể xét đến ảnh hưởng bên ngoài). Kết quả thực nghiệm được đưa ra trong bảng sau: Sai số tương đối trung bình (%) Dữ liệu Mô hình Ước tính kích Kích thước cây có thước lan truyền khả năng nhất IC 42.60 47.32 UI 34.47 37.65 DS2 RM 32.53 - Phương pháp đề xuất 23.86 28.82 IC 43.24 46.12 UI 35.61 37.89 DS3 RM 29.87 - Phương pháp đề xuất 26.10 30.17 Bảng 3.3. So sánh hiệu suất của các phương pháp khi xuất hiện ảnh hưởng bên ngoài Kết quả trong Bảng3.3 cho thấy, khi ước tínhkích thước lan truyền và tạo cây có khả năng nhất có xuất hiện ảnh hưởng bên ngoài, các phương thức hiện có
6. 82 thực nghiệm cho thấy phương pháp đề xuất của Luận án hiệu quả hơn ba phương pháp còn lại đối với cả ba bộ dữ liệu trong việc dự đoán kích thước lan truyềnvà tạo cây có khả năng nhất. Trong trường hợp xét đến ảnh hưởng từ bên ngoài, phương pháp của Luận án có hiệu quả vượt trộihơn.
7. 84 Việc duyệt đồ thịsử dụng phương pháp BFS và được lồng ghép vào pha duyệt đồ thị của Thuật toán Brandes. Cuối cùng, chọn một đỉnh duy nhất làm đại diện, hay tức là xóa các đỉnh tương đương và để lại một đỉnh duy nhất. Đối với kỹ thuật song song hóa, đó là việc thi hành song song các phép tính Độ trung tâm trung gian trên các đỉnh khác nhau để khai thác được hiệu năng của CPU đa lõi. Sử dụng bộ thư viện Cilkplus với trọng tâmlà vector reducerBC[v] trong bộ thư viện Cilkplusđể cập nhật tương tranh giá trị BC của đỉnh v khi thi hành song song. Ngoài ra, đối với dữ liệu được biểu diễn theo phương pháp danh sách liền kề và lưu trữ dưới dạng mảng. Đối với bài toán tính xác suất chấp nhận thông tin của người dùng (hay xác suất lan truyền), đó là việc xác định ảnh hưởng từ mối quan hệ người dùng (được xác định dựa trên lịch sử hoạt động) và có xét đến lan truyền sơ cấp và thứ cấp; ảnh hưởng từ sở thích, quan tâm của người dùng đối với nội dung; ảnh hưởng từ bên ngoài đến quyết định của người dùng. Cuối cùng là xây dựng cây lan truyền “có khả năng nhất” cho một nội dung cụ thể dựa trên các xác suất đã tínhớ v i xác suất tạo cây là 푃( ) = ∏( ,푣)∈ ( ) 푣. Tiến hành thực nghiệm cho thấy, phương pháp nâng cao tốc độ tính toán dự báo lan truyền của Luận án đã mang lại hiệu quả hơn so với bộ công cụ TeexGraph từ 1,2 đến 1,41 lần và so với bộ công cụ NetworKit là từ 1,76 đến 2,55 lần khi thực nghiệm với một số bộ dữ liệu của được công bố bởi SNAP. Phương pháp nâng cao độ chính xác dự báo lan truyền thông tin của Luận án mang lại hiệu quả hơn, sai số thấp hơn hay độ chính xác cao hơnba mô hình phổ biến hiện nay là mô hình bậc độc lập IC, mô hình tương tác người dùng UI, mô hình hồi quy RM trong việc dự đoán kích thước lan truyền và tạo cây có khả năng nhất đốivới ba bộ dữ liệu mô phỏng, Meme, Tencent Weibo. Đặc biệt hiệu quả hơn nữa khi xét đến ảnh hưởng từ bên ngoài. Toàn bộ các công trìnhnghiên cứu của Luận ánđều đượccông bố hoặc chờ công bố và xuất bản trong các kỷ yếu hội thảo, tạp chí có chỉ mục trong SCOPUS. Hạn chế của luận án Do những hạn chế cả về thời gian, về nguồn lực lẫn sự giới hạn về không
8. 86 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ C1. Duong Ngoc Son, Nguyen Ngoc Cuong, Nguyen Nhu Son (2019), Một phương pháp rút gọn đồ thị của mạng xã hội dựa trên thay thế lớp đỉnh tương đương, The 22nd National Symposium of Selected ICT Problems, pp: 27. C2. Duong Ngoc Son, Nguyen Ngoc Cuong, Nguyen Nhu Son, Nguyen Ngoc Hoa (2020), Một phương pháp nâng cao hiệu năng tính toán trên đồ thị, The 23rd National Symposium of Selected ICT Problems, pp: 60. C3. Du Phuong Hanh, Duong Ngoc Son, Nguyen Ngoc Cuong, Nguyen Ngoc Hoa (2020), A Fast Computation of Betweenness Centrality in Large-Scale Unweighted Graphs, International Journal on Emerging Technologies 11(2): 370- 377. C4. Duong Ngoc Son, Nguyen Ngoc Cuong, Nguyen Ngoc Hoa, Du Phuong Hanh (2021), A RED-BET Method to Improve the Information Diffusion on Social Networks, International Journal of Advanced Computer Science and Applications, 12(8): 867-875. C5. Nguyen Viet Anh, Duong Ngoc Son, Nguyen Thi Thu Ha, Sergey Kuznetsov, Nguyen Tran Quoc Vinh (2018), A Method for determining information diffusion cascades on social networks, Eastern-European Journal of Enterprise Technologies, Vol. 6, No. 2 (96), pp: 61-69.
9. 88 12 Guimerà, R., & Sales-Pardo, M. (2009). Missing and spurious interactions and the reconstruction of complex networks. Proceedings of the National Academy of Sciences, 106(52), 22073-22078. 13 Domingos, P., & Richardson, M. (2001, August). Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 57-66). 14 Yang, W., Brenner, L., & Giua, A. (2018, April). Computation of activation probabilities in the independent cascade model. In 2018 5th International Conference on Control, Decision and Information Technologies (CoDIT) (pp. 791-797). IEEE. 15 Cohen, E., Delling, D., Pajor, T., & Werneck, R. F. (2014, November). Sketch-based influence maximization and computation: Scaling up with guarantees. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management (pp. 629-638). 16 Kempe, D., Kleinberg, J., & Tardos, É. (2003, August). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 137-146). 17 Lucier, B., Oren, J., & Singer, Y. (2015, August). Influence at scale: Distributed computation of complex contagion in networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 735-744). 18 Dinh, T. N., Shen, Y., & Thai, M. T. (2012, October). The walls have ears: optimize sharing for visibility and privacy in online social networks. In Proceedings of the 21st ACM international conference on Information and knowledge management (pp. 1452-1461). 19 Shen, Y., Syu, Y. S., Nguyen, D. T., & Thai, M. T. (2012, June). Maximizing circle of trust in online social networks. In Proceedings of the 23rd ACM conference on Hypertext and social media (pp. 155-164).
10. 90 Symposium on Information and Communication Technology (pp. 456- 462). 30 Bernaschi, M., Carbone, G., & Vella, F. (2015, November). Betweenness centrality on multi-GPU systems. In Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms (pp. 1-4). 31 Fan, R., Xu, K., & Zhao, J. (2017). A GPU-based solution for fast calculation of the betweenness centrality in large weighted networks. PeerJ Computer Science, 3, e140. 32 McLaughlin, A., & Bader, D. A. (2018). Accelerating gpu betweenness centrality. Communications of the ACM, 61(8), 85-92. 33 Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of mathematical sociology, 25(2), 163-177. 34 Mahmoody, A., Tsourakakis, C. E., & Upfal, E. (2016, August). Scalable betweenness centrality maximization via sampling. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1765-1773). 35 Riondato, M., & Kornaropoulos, E. M. (2016). Fast approximation of betweenness centrality through sampling. Data Mining and Knowledge Discovery, 30(2), 438-475. 36 Wei, J., Chen, K., Zhou, Y., Zhou, Q., & He, J. (2016, March). Benchmarking of distributed computing engines spark and graphlab for big data analytics. In 2016 IEEE Second International Conference on Big Data Computing Service and Applications (BigDataService) (pp. 10-13). IEEE. 37 Kwak, H., Lee, C., Park, H., & Moon, S. (2010, April). What is Twitter, a social network or a news media?. In Proceedings of the 19th international conference on World wide web (pp. 591-600). 38 Haveliwala, T. H. (2002). Topic-sensitive pagerank. In Proceedings of the 11th International Conference on World Wide Web (pp. 517-526).
11. 92 48 Zhang, L. , Luo, M. & Boncella, R. J. (2020). Product information diffusion in a social network, Electronic Commerce Research, 20(1), pp. 3-19. 49 Hinz, O., Skiera, B., Barrot, C. & Becker, J. U. (2011). Seeding strategies for viral marketing: An empirical comparison, Journal of Marketing, 75(6), pp. 55-71. 50 Trudeau, R. J. (1994). Introduction to graph theory. Dover Pubns. 51 Wilson, R. J. (1979). Introduction to graph theory. Pearson Education India. 52 Sakr, S., & Pardede, E. (2011). Graph data management: techniques and applications. Information Science Reference-Imprint of: IGI Publishing. 53 Buluç, A., Fineman, J. T., Frigo, M., Gilbert, J. R., & Leiserson, C. E. (2009, August). Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks. In Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures (pp. 233-244). 54 Sedgewick, R., & Flajolet, P. (2013). An introduction to the analysis of algorithms. Pearson Education India. 55 Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Principles of parallel algorithm design. Introduction to Parallel Computing, 2nd ed. Addison Wesley, Harlow. 56 Asanovic, K., Bodik, R., Catanzaro, B. C., Gebis, J. J., Husbands, P., Keutzer, K., & Yelick, K. A. (2006). The landscape of parallel computing research: A view from berkeley, EECS Technical Report UCB/EECS-2006-183. 57 Adve, S., Adve, V. S., Agha, G., Frank, M. I., Garzarán, M. J., Hart, J. C., & Zilles, C. (2008). Parallel computing research at Illinois: The UPCRC agenda. Urbana, IL: Univ. Illinois Urbana-Champaign.
12. 94 67 Rodriguez, M. G., Balduzzi, D., & Schölkopf, B. (2011). Uncovering the temporal dynamics of diffusion networks. In Proceedings of the 28th International Conference on Machine Learning, ICML '11 (pp. 561-568). 68 Chen, W., Collins, A., Cummings, R., Ke, T., Liu, Z., Rincon, D., & Yuan, Y. (2011, April). Influence maximization in social networks when negative opinions may emerge and propagate. In Proceedings of the 2011 siam international conference on data mining (pp. 379-390). Society for Industrial and Applied Mathematics. 69 Barbieri, N., Bonchi, F., & Manco, G. (2013). Topic-aware social influence propagation models. In Proceedings of the 12th International Conference in Data Mining (pp. 81-90). IEEE. 70 Li, Y., Chen, W., Wang, Y., & Zhang, Z. L. (2013, February). Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. In Proceedings of the sixth ACM international conference on Web search and data mining (pp. 657-666). 71 Du, N., Liang, Y., Balcan, M. F., Gomez-Rodriguez, M., Zha, H., & Song, L. (2017). Scalable Influence Maximization for Multiple Products in Continuous-Time Diffusion Networks. J. Mach. Learn. Res., 18(2), 1-45. 72 Du, N., Song, L., Gomez-Rodriguez, M., & Zha, H. (2013). Scalable influence estimation in continuous-time diffusion networks. Advances in neural information processing systems, 26, 3147-3155. 73 Li, Y., Zhang, D., & Tan, K. L. (2015). Real-time Targeted Influence Maximization for Online Advertisements. Proceedings of the VLDB Endowment, 8(10), 1070-1081. 74 Kurka, D. B., Godoy, A., & Von Zuben, F. J. (2015). Online social network analysis: A survey of research applications in computer science. arXiv preprint arXiv:1504.05655. 75 Wasserman, S., & Faust, K. (1994). Social Network Analysis: Methods and Applications., Cambridge University Press.
13. 96 89 Leist, A., & Gilman, A. (2014). A comparative analysis of parallel programming models for c++, In The 9th International Multi-Conference on Computing in the Global Information Technology (pp. 121-127). 90 Rossetti, G., Mill, L., Rinzivillo, S., Sirbu, A., Pedreschi, D. & Giannotti, F. (2018). NDlib: a python library to model and analyze diffusion processes over complex networks, International Journal of Data Science and Analytics. 5(1), pp. 61-79. 91 Frigo, M., Halpern, P., Leiserson, C. E., & Lewin-Berlin, S. (2009, August). Reducers and other Cilk++ hyperobjects. In Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures (pp. 79-90). 92 Yakovleva, O. V., Rudakov, I. V., & Stroganov, Y. V. (2019, December). Predict post spreading in online social networks based on independent cascade model. In Journal of Physics: Conference Series (Vol. 1419, No. 1, p. 012017). IOP Publishing. 93 Newman, M. E. (2002). Spread of epidemic disease on networks. Physical review E, 66(1), 016128. 94 Chen, W., Wang, C., & Wang, Y. (2010, July). 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 (pp. 1029-1038). 95 Borgs, C., Brautbar, M., Chayes, J., & Lucier, B. (2014, January). Maximizing social influence in nearly optimal time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (pp. 946-957). Society for Industrial and Applied Mathematics. 96 Nguyen, H. T., Thai, M. T., & Dinh, T. N. (2016, June). Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In Proceedings of the 2016 International Conference on Management of Data (pp. 695-710).
14. 98 implications. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 6-14). 106 Hui, C., Tyshchuk, Y., Wallace, W. A., Magdon-Ismail, M., & Goldberg, M. (2012, April). Information cascades in social media in response to a crisis: a preliminary model and a case study. In Proceedings of the 21st International Conference on World Wide Web (pp. 653-656). 107 Zhang, J., Liu, B., Tang, J., Chen, T., & Li, J. (2013, August). Social influence locality for modeling retweeting behaviors. In IJCAI (Vol. 13, pp. 2761-2767). 108 Suh, B., Hong, L., Pirolli, P., & Chi, E. H. (2010, August). Want to be retweeted? large scale analytics on factors impacting retweet in twitter network. In 2010 IEEE Second International Conference on Social Computing (pp. 177-184). IEEE.