CHƯƠNG 1 17 thông tin. Do số lượng người dùng rất lớn nên OHUSN đã tạo ra một khối lượng dữ liệu khổng lồ theo thời gian và những dữ liệu này có các đặc trưng dễ nhận biết như chất lượng cao, dữ liệu lớn, bán cấu trúc, thay đổi theo thời gian và phản ánh được một cách trực tiếp con người trong xã hội thực [88]. Tuy nhiên, vấn đề khai phá và phân tích dữ liệu liên quan đến OSN nói chung cũng như OHUSN nói riêng là một vấn đề không đơn giản vì gặp phải hai thách thức [87]: tính không đầy đủ và tính biến động cao. Hầu hết dữ liệu mạng xã hội đã nhận được là không đầy đủ vì chỉ có một phần thông tin xã hội được thu thập từ các nền tảng mạng xã hội.
Mạng xã hội còn có tính biến động cao do các nút và các liên kết có thể xuất hiện hoặc biến mất trong tương lai. Do vậy, việc dự đoán những liên kết bị khuyết hoặc không quan sát được trong OHUSN hiện thời và việc thêm mới hoặc loại bỏ những liên kết trong OHUSN tương lai là một vấn đề rất quan trọng [88]. Việc dự đoán này không chỉ nắm bắt được sự phát triển của OHUSN mà còn làm cho OHUSN hiện tại trở nên đầy đủ hơn. Vấn đề này thường được biết đến như vấn đề dự đoán liên kết trong OHUSN [88].
Cho tập các liên kết của một OHUSN tại thời điểm t, hãy tìm cách dự đoán các liên kết sẽ được thêm vào OHUSN trong khoảng thời gian từ thời điểm t đến thời điểm t’ trong tương lai [51]. Dự đoán liên kết là một trong những nhiệm vụ của phân tích, khai phá liên kết [35] và có nhiều ứng dụng quan trọng. Có thể kể đến ứng dụng cho các hệ khuyến nghị trong việc tìm kiếm thông tin và thương mại điện tử, hệ này trợ giúp người dùng có thêm những người bạn mới [3] và những người cộng tác tiềm năng [62, 93], cung cấp các mặt hàng được người dùng quan tâm trong mua bán trực tuyến [4], khuyến nghị những đối tác đồng sáng chế trong mạng cộng đồng doanh nghiệp [88] và các đối tác trong các lĩnh vực khác nhau [83], tìm những chuyên gia hoặc đồng tác giả trong các mạng cộng đồng khoa học [70, 92]. Theo [88], phương pháp dự đoán liên kết trong mạng xã hội bao gồm hai hướng tiếp cận (xem Hình 1.2) như sau: Thứ nhất, tiếp cận dựa trên độ đo liên kết hay còn gọi là học không giám sát.
Trong hướng tiếp cận này, hệ thống sẽ tính toán các giá trị tương đồng của các cặp nút ứng cử dựa trên các độ đo liên kết (chẳng hạn như CN [67], AA [1], JC [76], v.v…), sau đó sắp xếp theo chiều giảm dần về giá trị độ đo liên kết và lựa chọn ra danh sách các cặp nút ứng cử để dự đoán có liên kết (Hình 1. Tính các độ đo liên kết Sắp xếp các cặp nút theo độ đo liên kết Danh sách Top N cặp nút dự đoán có liên kết Hình 1.1 Tiếp cận dự đoán liên kết dựa trên các độ đo liên kết 18 Thứ hai, tiếp cận dựa trên mô hình phân lớp, hướng tiếp cận này coi bài toán dự đoán liên kết như là bài toán phân lớp nhị phân [5]. Để thực hiện được theo hướng tiếp cận này, hệ thống sẽ xây dựng tập các đặc trưng cho các cặp nút không có liên kết dựa trên các độ đo tương đồng và một số đặc trưng khác dựa trên thông tin từ mạng xã hội (chẳng hạn như các thông tin dạng văn bản của các thuộc tính và các miền tri thức), và tiến hành gán nhãn cho mỗi cặp nút theo cách thức sau: nếu có liên kết tiềm năng kết nối cặp nút thì cặp nút sẽ được gán nhãn 1 (positive), ngược lại sẽ được gán nhãn 0 (negative) (Hình 1. Mạng đồng tác giả là một trong những mạng OHUSN được nhiều nhà nghiên cứu quan tâm.
Newman [65, 66] được biết đến như là một trong những người đầu tiên xây dựng mạng đồng tác giả dựa trên bốn nguồn dữ liệu về các bài báo khoa học công khai trên mạng Internet Los Alamos e-Print Archive, Medline, SPIRES và NCSTRL. Theo [31], mạng đồng tác giả là một mạng xã hội mà ở đó các nút là các nhà khoa học và các cạnh (liên kết) là các quan hệ đồng tác giả. Đây là một mạng vô hướng và phần lớn các tác giả có kết nối thưa trong khi chỉ một số rất ít các tác giả có nhiều kết nối. Trên thực tế, hầu hết các nghiên cứu về bài toán dự đoán liên kết trong mạng OHUSN đều lựa chọn mạng đồng tác giả là một trong những mạng để tiến hành thực nghiệm.
Để minh họa cho mạng đồng tác giả, một định nghĩa hình thức về mạng đồng tác giả được đề xuất như sau: Định nghĩa 1.1 Một mạng đồng tác giả 𝐺(𝑇)là một bộ bốn (𝑉(𝑇), 𝐸(𝑇), 𝑃(𝑇), 𝑇), trong đó - 𝑇 = {𝑡1, 𝑡2, … , 𝑡𝑌} là tập mốc thời gian liên tiếp (𝑡𝑖 < 𝑡𝑗 với i < j, và i, j = 1: 𝑌̅̅ ̅̅ ̅), với 𝑌 là số mốc thời gian, - 𝑉(𝑇) = {𝑣1, 𝑣2,. , 𝑣𝑁} là một tập các tác giả, 𝑁 là số tác giả, - 𝑃(𝑇) = {(𝑝1, 𝑡𝑝1 , 𝑉𝑝1 ), (𝑝2, 𝑡𝑝2 , 𝑉𝑝2 ),. Các đặc trưng dựa trên độ đo liên kết Các đặc trưng khác Mô hình phân lớp Danh sách các cặp nút dự đoán có liên kết Hình 1.2 Tiếp cận dự đoán liên kết dựa trên phân lớp 19 Định nghĩa 1.1 sẽ được minh họa thông qua ví dụ về mạng đồng tác giả được biểu diễn trên Hình 1.3 dựa trên dữ liệu cho trong Bảng 1.3 là đồ thị biểu diễn quan hệ cộng tác giữa các tác giả, mỗi ei biểu diễn một quan hệ cộng tác giữa hai tác giả và được xác định trong Bảng 1. Trong ví dụ này, mạng đồng tác giả bao gồm 8 tác giả (N = 8), 10 bài báo (M = 10) và các bài báo được xuất bản từ năm 2000 đến năm 2002 (K = 3).
Tổng số cộng tác là 12 (xem Bảng 1.1 Danh sách các quan hệ cộng tác và các bài báo Quan hệ cộng tác Tác giả i Tác giả j Tập bài báo Bài báo Năm công bố Danh sách các tác giả e1 v2 v4 (𝑝1, 𝑝2, 𝑝4, 𝑝9) p1 2000 (𝑣5, 𝑣2, 𝑣4) e2 v2 v5 (𝑝1, 𝑝2) p2 2000 (𝑣1, 𝑣5, 𝑣3, 𝑣4) e3 v2 v3 ( 𝑝3, 𝑝7, 𝑝10) p3 2000 (𝑣2, 𝑣3) e4 v2 v1 ( 𝑝2) p4 2000 (𝑣4, 𝑣2) e5 v2 v6 ( 𝑝8) p5 2001 (𝑣7, 𝑣2, 𝑣8) e6 v2 v7 ( 𝑝5) p6 2001 (𝑣2, 𝑣8) e7 v2 v8 ( 𝑝5, 𝑝6, 𝑝8) p7 2001 (𝑣3, 𝑣2) e8 v1 v4 ( 𝑝2) p8 2002 (𝑣8, 𝑣6, 𝑣2) e9 v1 v5 ( 𝑝2) p9 2002 (𝑣2, 𝑣4) e10 v4 v5 (𝑝1, 𝑝2) p10 2002 (𝑣2, 𝑣3) e11 v6 v8 ( 𝑝8) e12 v7 v8 ( 𝑝5) v3 v2 v4 v5 v6 e2 e5 e8 e9 e4 e11 v1 e6 v7 v8 e12 Hình 1.3 Minh họa mạng đồng tác giả với dữ liệu trong Bảng 1.1 từ năm 2000 đến 2002 dưới dạng đồ thị 20 1.2 Bài toán khuyến nghị cộng tác Bài toán khuyến nghị cộng tác được bắt nguồn từ bài toán dự đoán liên kết trong mạng xã hội giả nhằm tìm ra những tác giả có tiềm năng cộng tác trong tương lai. Bài toán khuyến nghị cộng tác được phát biểu như sau: Cho thông tin về các tác giả đã từng viết chung bài báo khoa học đến thời điểm t, với một tác giả u nào đó, cần tìm ra một danh sách tác giả có tiềm năng cộng tác với tác giả u trong tương lai (từ thời điểm t’ > t). Như vậy, bài toán khuyến nghị cộng tác sẽ có hai trường hợp cần khuyến nghị: Thứ nhất là khuyến nghị cộng tác mới. Hệ thống sẽ lựa chọn ra danh sách các ứng cử viên chưa từng cộng tác với một tác giả nào đó có tiềm năng lớn sẽ cộng tác với họ trong tương lai.
Thứ hai là khuyến nghị cộng tác tăng cường. Hệ thống sẽ khuyến nghị cho một nhà nghiên cứu nào đó những tác giả đã từng cộng tác trước đó với họ có tiềm năng tiếp tục cộng tác tăng cường trong tương lai. Bài toán khuyến nghị cộng tác có sự khác biệt so với bài toán khuyến nghị truyền thống trong đó tập các ứng cử viên được khuyến nghị cần phải thỏa mãn về mức độ tương đồng về lĩnh vực nghiên cứu (thông qua tập các bài báo đã công bố); tức là người được khuyến nghị cần được biết lý do vì sao họ sẽ có tiềm năng cộng tác với ứng cử viên được lựa chọn trong tương lai. Đối với bài toán khuyến nghị truyền thống, chủ yếu tập trung vào ba hướng tiếp cận chính đó là: (i) hướng tiếp cận dựa trên lọc cộng tác [73, 77, 81, 84].
Trong đó, sử dụng thông tin về những đánh giá đối với các người dùng khác nhau, việc xác định những người dùng tương đồng (những người láng giềng) là người có lịch sử đánh giá tương tự như người dùng hiện tại và đưa ra những khuyến nghị dựa trên lịch sử đánh giá của những láng giềng đó. Một số thuật toán học máy khác nhau đã được áp dụng trong hướng tiếp cận này, chẳng hạn như Naive Bayes [15] và dựa trên luật [6]; với sự nhấn mạnh hơn trên các mô hình nhân tố tiềm ẩn đã được dùng trong thập kỷ qua như phân tích giá trị riêng (SVD) bởi Sarwar và cộng sự [78], phân tích nhân tố bởi Canny [42], phân tích ngữ nghĩa tiềm ẩn (PLSA) bởi Hofmann [41], và phân tích thừa số ma trận không âm [48]. (ii) hướng tiếp cận dựa trên nội dung [13, 17, 91], ý tưởng chủ đạo của hướng tiếp cận này là đưa ra khuyến nghị những sản phẩm tương tự (tương đồng) với những sản phẩm mà người dùng đã thích (quan tâm) trong quá khứ sẽ được xem xét. Trong đó, độ tương tự giữa hai sản phẩm được tính toán dựa trên những đặc điểm (đặc trưng) gắn với những sản phẩm được so sánh.
Ví dụ, nếu người dùng đã từng đánh giá một bộ phim nào đó thuộc thể loại hài kịch thì khi đó hệ thống sẽ học cách để khuyến nghị những bộ phim khác cũng thuộc thể loại này cho người dùng. (iii) hướng tiếp cận lai [18, 86], là một cách kết hợp hai hoặc nhiều phương pháp khuyến nghị nhằm đạt được độ chính xác (hiệu suất) tốt hơn so với khi áp dụng riêng lẻ phương pháp bất kỳ nào 21 đó. Liên quan đến hướng tiếp cận khuyến nghị lai, luận án đã đề xuất mô hình khuyến nghị được trình bày trong công trình CT1. Bài toán khuyến nghị trên mạng xã hội cũng được nhiều nghiên cứu quan tâm.