Khóa luận tốt nghiệp: Họ thuật toán Girvan-Newman trong phát hiện cộng đồng và cài đặt thử nghiệm trên mạng xã hội trực tuyến

Trong kỷ nguyên số hóa hiện nay, mạng xã hội trực tuyến đã trở thành một phần không thể thiếu của đời sống, tạo ra các cấu trúc phức tạp cần được phân tích sâu sắc. Một trong những thách thức quan trọng là phát hiện cộng đồng, tức là xác định các nhóm người dùng có mối liên kết chặt chẽ trong một mạng lưới rộng lớn. Việc này không chỉ có ý nghĩa lý thuyết trong lĩnh vực khoa học máy tính và xã hội học mà còn mang lại giá trị ứng dụng to lớn trong phân tích hành vi, tiếp thị và nghiên cứu xã hội. Khóa luận này tập trung nghiên cứu sâu rộng về họ thuật toán Girvan-Newman, đặc biệt là thuật toán CONGA, và đề xuất một mô hình thực nghiệm để ứng dụng chúng vào việc phát hiện cộng đồng trên mạng xã hội Twitter, nhằm đánh giá hiệu quả và tính khả thi của phương pháp.

Sinh viên, nghiên cứu sinh, và các nhà khoa học trong lĩnh vực Công nghệ thông tin, Khoa học máy tính, Khoa học dữ liệu, và Xã hội học quan tâm đến phân tích mạng xã hội và phát hiện cộng đồng.

Bài toán phát hiện cộng đồng trong các mạng xã hội trực tuyến là một lĩnh vực nghiên cứu thời sự và cấp thiết, thu hút sự quan tâm từ nhiều ngành khoa học khác nhau. Luận văn này đi sâu vào phân tích họ thuật toán Girvan-Newman, một trong những phương pháp hiệu quả nhất để xác định các cấu trúc cộng đồng. Cụ thể, nghiên cứu tập trung vào thuật toán CONGA (Cluster Overlapping Newman Girvan Algorithm) của Steve Gregory, một cải tiến đáng chú ý trong việc phát hiện cộng đồng chồng lấn. Nội dung chính của khóa luận bao gồm việc đề xuất một mô hình ứng dụng thuật toán CONGA để thực hiện phát hiện cộng đồng trên mạng xã hội Twitter. Phương pháp tiếp cận bao gồm việc xây dựng một hệ thống thực nghiệm, tích hợp phần mềm CONGA hiện có với giao diện lập trình ứng dụng (API) của Twitter để thu thập và xử lý dữ liệu. Sau đó, mô hình được kiểm chứng thông qua việc phân cụm thử nghiệm trên một đồ thị con của Twitter được xây dựng riêng. Giá trị ứng dụng và hàm ý của nghiên cứu được thể hiện rõ qua kết quả đánh giá thực nghiệm. Bằng cách sử dụng phương pháp phân lớp SVM, mô hình đã đạt được độ đo F1 khoảng 81%, một chỉ số khả quan cho thấy tính khả thi và hiệu quả của việc áp dụng thuật toán CONGA trong bối cảnh thực tế của mạng xã hội. Kết quả này không chỉ đóng góp vào sự hiểu biết về cơ chế hình thành và cấu trúc của các cộng đồng ảo mà còn mở ra tiềm năng phát triển các công cụ phân tích mạng xã hội tiên tiến, hỗ trợ cho nhiều mục đích từ nghiên cứu học thuật đến ứng dụng thương mại và xã hội.