Chia sẻ bài báo qua Email KẾT QUẢ ĐỀ XUẤT THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI
Thông tin bài báo
Ngày nhận bài: 17/06/20 Ngày hoàn thiện: 31/08/20 Ngày đăng: 31/08/20Các tác giả
1. Nguyễn Hiền Trinh, Trường Đại học Công nghệ thông và truyền thông - ĐH Thái Nguyên2. Vũ Vinh Quang
, Trường Đại học Công nghệ thông và truyền thông - ĐH Thái Nguyên3. Cáp Thanh Tùng, Trường Đại học Sư phạm - ĐH Thái Nguyên
Tóm tắt
Hiện nay, phát hiện cộng đồng trên mạng xã hội là một hướng nghiên cứu đang được nhiều nhà khoa học quan tâm. Đã có rất nhiều thuật toán được đề xuất, nhưng một trong những vấn đề cần phải khắc phục đối với các mạng xã hội là trong thực tế số lượng đỉnh và cạnh của đồ thị cực kỳ lớn dẫn tới khối lượng tính toán trong các thuật toán rất lớn, khó đáp ứng được với yêu cầu thực tiễn. Trong bài báo này, chúng tôi đề xuất một giải pháp mới dựa trên tính chất của một số đỉnh đặc biệt có trên đồ thị, từ đó đưa ra thuật toán biến đổi đồ thị ban đầu về dạng rút gọn tương đương nhằm giảm kích thước của đồ thị, đồng thời kết hợp với kỹ thuật lan truyền nhãn, xây dựng hàm heuristic để tăng tốc độ xử lý cho thuật toán phát hiện cộng đồng. Kết quả thực nghiệm trên các bộ dữ liệu chuẩn cho thấy so với phương pháp lan truyền nhãn gốc LPA thời gian xử lý trung bình giảm xuống còn 85,5% trong khi đó chất lượng cộng đồng tăng lên trung bình là 1,145 lần, từ đó đã khẳng định được tính hiệu quả của thuật toán đề xuất.
Từ khóa
Toàn văn:
PDFTài liệu tham khảo
[1]. G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee, “Self organization and identification of web communities,” Computer, vol. 35, no. 3, pp. 66-70, 2002.
[2]. F. Radicchi, and F. Castellano, “Defining and identifying communities in network,” Proceedings of the National Academy of Sciences of the United States of America, 2004.
[3]. M. Girvan, and M. E. Newman, “Community structure in social and biological networks,” Physical review E, vol. 99, pp. 7821-7826, 2002.
[4]. J. R. Tyler, and D. M. Wilkinson, “Automated discovery of community structure within organization,” Physical review E, vol. 15, pp. 723-739, 2003.
[5]. J. W. Pinney, and D. R. Westhead, Betweenness-based decomposition methods for social and biological network. Leeds University Press, 2006.[6]. M. J. Rattigan, M. Maier, and D. Jensen, “Graph clustering with network structure indices,” Proceedings of the 24th international conference on Machine learning, 2007.[7]. S. Gregory, An algorithm to find overlapping community structure in network. Springer Heidelberg, 2007.
[8]. S. Fortunato, Community Detection in Graphs, Physics Reports, 2010.
[9]. U. Brandes, “A faster algorithm for betweenness centrality,” Journal of Mathematical sociology, vol. 25, no. 2, pp. 163-177, 2001.
[10]. M. E. Newman, and M Girvan, “Finding and evaluating community structure in networks,” Phys Rev E Stat Nonlin Soft Matter Phys, vol. 76, pp. 106-119, 2004.[11]. X. Liu, H. M. Cheng, and Z. Y.Zhang, “Evaluation of community detection methods,” IEEE Transactions on Knowledge and Data Engineering, vol. 32, no. 9, pp. 1736-1746, 2019.
[12]. U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale network,” Physics Reports, vol. 23, pp. 306-323, 2007.
[13]. Sara E. Garza, and S. E. Schaeffer, “Community detection with the Label Propagation Algorithm,” Elsevier B.V, vol. 534, pp. 1024-1059, 2019.
[14]. Z. Wu, A. Efros, and S. X. Yu, “Improving generalization via scalable neighborhood component analysis,” In Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, Proceedings, Part VII, 2018, pp. 712-728.
[15]. Meilian, Zh. Zhang, Zh. Qu, and Yukang, “Overlapping Community Detection Using Label Propagation in Large-Scale Complex Networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 31, pp. 1736- 1749, 2019.
[16]. A. Zhang, G. Ren, and Y. Lin, “Detecting community structures in network by label propagation with prediction of percolation transition,” The Scientific word Journal, vol. 14, pp. 315-336, 2014.
[17]. T. Wu, Y. Guo, and L. Chen, “Integrated structure investigation in complex networks by label propagation,” Physica A: Statistical Mechanics and its Applications, vol. 448, pp. 68-80, 2016.
[18]. P. Bonacich, Introduction to Mathematical Sociology. Princeton University Press, 2013.
[19]. L. C. Freeman, “Maintaining the Duality Closeness and Betweenness Centrality,” Social Network, vol. 44, pp. 153-159, 2016.
[20]. J. Leskovec, and Krevl, “A. SNAP Datasets Stanford large network dataset collection,” 2014. [Online]. Available: https://snap.stanford.edu. [Accessed Feb. 26, 2020].
Các bài báo tham chiếu
- Hiện tại không có bài báo tham chiếu