Nghiên cứu tin ... vịt

Các tin đồn thiệt và thất thiệt có khả năng gây hiệu ứng xã hội mạnh (cả tốt lẫn xấu). Ví dụ như tin đồn đầu tháng 9 là giá xăng sắp tăng, bà con đổ đi mua xăng. Tin đồn ở một buổi hành lễ ở Iraq là sắp có đánh bom tự sát làm cả nghìn người dẫm đạp lên nhau mà chết.

Có lẽ ai cũng đồng ý là tin vịt ảnh hưởng xấu đến tương tác xã hội, và đến các cá thể liên quan nói riêng. Ngược lại, các đối trọng thiếu quyền lực trong một xã hội hay một nhóm người có thể lợi dụng tin đồn để tuyên truyền một thông tin chính xác nào đó mà họ không thể truyền qua các phương tiện công khai.

Thế nhưng, tầm quan trọng của tin đồn trong các tương tác xã hội và cơ học của sự lan truyền tin đồn vẫn chưa được nghiên cứu cẩn thận. Hầu như không có dữ liệu khoa học nào về tin đồn. Gần đây, một nhóm các nhà nghiên cứu khoa tâm lý học ở viện công nghệ Rochester (RIT) đã xin được tài trợ của NSF làm nghiên cứu về đề tài này.

Một trường hợp đơn giản của sự lan truyền các tin đồn và mô hình hóa chúng đã được nghiên cứu trong KHMT dưới cái tên bài toán gossiping. Đại khái, cho nhiều cá thể nối với nhau bởi một mạng thông tin liên lạc nào đó, mỗi cá thể có một mẩu tin muốn truyền cho tất cả các cá thể khác trên mạng lưới này. Cụ thể hơn, cho một đồ thị, trong đó mỗi đỉnh có một gói dữ liệu phải gửi đến tất cả các đỉnh khác.

Có rất nhiều biến thể của bài toán này, tôi liệt kê ra đây vài biến thể chính:

• Cho trước đồ thị, thiết kế một thuật toán để các tin đồn lan truyền nhanh nhất, để tổng số gói dữ liệu gửi thừa là ít nhất (ví dụ anh A nghe tin đồn 2, 3 lần thì phí băng thông). Có thể có các giới hạn khác như: mỗi đỉnh chỉ được gửi/chuyển tiếp vài gói dữ liệu (tránh tình trạng overload). Vài ví dụ bài báo dạng này: một, hai, ba.
• Tìm xem ít nhất cần bao nhiêu thời gian (cận dưới, cận trên) để các tin đồn hoàn tất, với nhiều dạng đồ thị khác nhau. Ví dụ một, hai.
• Với một thuật toán lan truyền tốt nào đó, thiết kế đồ thị cho thuật toán này chạy tốt nhất. Ví dụ một, hai .

Bài toán này có khá nhiều ứng dụng, từ giải các hệ thống tuyến tính trong xử lý song song, FFT, đến bài toán sắp xếp. Xem thêm một survey cũ. Bài này cũng có liên quan đến bài toán tôi đã đề cập nhân vụ bão Katrina.