Kết quả đề xuất thuật toán phát hiện cộng đồng trên mạng xã hội

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Thanh Tùng Cáp, Hiền Trinh Nguyễn, Vinh Quang Vũ

Ngôn ngữ: Vie

Ký hiệu phân loại: 004 Data processing || Computer science

Thông tin xuất bản: Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên, 2020

Mô tả vật lý: 103-111

Bộ sưu tập: Metadata

ID: 409032

Thêm vào giỏ Liên kết toàn văn

Hiện nay, phát hiện cộng đồng trên mạng xã hội là một hướng nghiên cứu đang được nhiều nhà khoa học quan tâm. Đã có rất nhiều thuật toán được đề xuất, nhưng một trong những vấn đề cần phải khắc phục đối với các mạng xã hội là trong thực tế số lượng đỉnh và cạnh của đồ thị cực kỳ lớn dẫn tới khối lượng tính toán trong các thuật toán rất lớn, khó đáp ứng được với yêu cầu thực tiễn. Trong bài báo này, chúng tôi đề xuất một giải pháp mới dựa trên tính chất của một số đỉnh đặc biệt có trên đồ thị, từ đó đưa ra thuật toán biến đổi đồ thị ban đầu về dạng rút gọn tương đương nhằm giảm kích thước của đồ thị, đồng thời kết hợp với kỹ thuật lan truyền nhãn, xây dựng hàm heuristic để tăng tốc độ xử lý cho thuật toán phát hiện cộng đồng. Kết quả thực nghiệm trên các bộ dữ liệu chuẩn cho thấy so với phương pháp lan truyền nhãn gốc LPA thời gian xử lý trung bình giảm xuống còn 85,5% trong khi đó chất lượng cộng đồng tăng lên trung bình là 1,145 lần, từ đó đã khẳng định được tính hiệu quả của thuật toán đề xuất., Tóm tắt tiếng anh, Nowadays, community detecting on social network has been an orientation which draws attention of many researchers. Numerous algorithms have been proposed, but one of the problems that need to be solved for social networks is the fact that the number of vertices and edges of the graph is extremely large. As a result, the volume of calculations in the algorithms could be significantly large, and thus it is difficult to meet with practical requirements. In this article, we introduce a new approach based on certain attributes of special vertex on network and then propose the algorithm of merging vertices of the same centrality to reduce input vertices/ edges of network, and develop in conjunction with label propagation techniques, build a heuristic function to speed up community detection algorithms. Experimental results on the standard data sets showed that, compared to the original label propagation method LPA, the average processing time was reduced down to only 85.5%, while the quality of the community is increased by an average of 1.145 times, thereby confirming the effectiveness of the proposed algorithm.

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR