Phân nhóm người dùng dựa vào hành vi tương tác trong mạng xã hội

Abstract

Hiện nay mạng xã hội được sử dụng rộng rãi trên thế giới nói chung và tại Việt Nam nói riêng. Vì vậy trong nhiều lĩnh vực của đời sống xã hội như khoa học máy tính, sinh học, kinh tế, chính trị… việc phát hiện nhóm người dùng trong mạng xã hội có một vai trò quan trọng. Nhằm mục đích phát hiện và phân nhóm người dùng trong mạng xã hội đã có nhiều thuật toán được phát triển, tiêu biểu có các thuật toán: thuật toán di truyền, thuật toán Kernighan-Lin, họ thuật toán Girvan-Newman, thuật toán tham lam Newman, thuật toán Clauset-Newman-Moore (CNM). Trong số các thuật toán đó, thuật toán CNM được đánh giá là tốt nhất, khá phù hợp với các mô hình thực tế với độ phức tạp cỡ O(mdlogn) trong đó d là độ sâu của dữ liệu “dendrogram” mô tả cấu trúc của nhóm mạng, m là số đỉnh và n là số cạnh. Nhưng mặc dù thuật toán CNM cho thời gian chạy nhanh và độ đo chất lượng phân chia khá phù hợp với các mô hình thực tế tuy nhiên vẫn còn hạn chế đó là cho ra kết quả nhiều nhóm có cấu trúc lớn đồng thời việc cực đại hoá giá trị modularity chưa thể khẳng định là đồ thị có cấu trúc nhóm trừ khi các nhóm tìm được là clique. Để khắc phục các hạn chế và tận dụng được lợi thế về thời gian thực thi của thuật toán CNM thì thuật toán INC được phát triển dựa vào nó, để đưa ra các cấu trúc nhóm có kích thước nhỏ hơn thể hiện mối quan hệ mật thiết hơn giữa các đối tượng trong cùng nhóm. Để phù hợp với thực tế hơn trong luận văn này tác giả đã xây dựng mạng xã hội dựa vào hành vi tương tác của người dùng so với các mô hình xây dựng mạng xã hội dựa trên mối quan hệ xã hội hay là lượng theo dõi như các đề tài nghiên cứu trước đây. Từ tập dữ liệu tự thu thập là 1500 tài khoản Facebook, luận văn xây dựng được một đồ thị mạng xã hội gồm 1500 đỉnh, 101.537 cạnh và 2.400.534 người dùng bình luận. Kết quả thực nghiệm cho thấy INC cho thời gian chạy chậm hơn CNM không đáng kể (0.24 giây của INC so với 0.18 giây của CNM), trong khi số lượng nhóm lớn hơn rất nhiều (321 nhóm của INC so với 92 nhóm của CNM) và chất lượng phân chia nhóm là vượt trội (độ đo chất lượng là 2480,094 của INC so với 1212,408 của CNM). Kết quả thực nghiệm cho thấy tính khả quan cao của INC khi áp dụng để phân nhóm người dùng trong các mạng xã hội.