Luận án Nghiên cứu và phát triển một số độ đo liên kết trong bài toán khuyến nghị cộng tác - Phạm Minh Chuẩn

đo liên kết dựa trên trọng số mở rộng Dễ nhận thấy, trong mạng đồng tác giả việc xác định trọng số cộng tác giữa hai tác giả đã được nhiều nghiên cứu quan tâm bởi nó là cơ sở để xây dựng các độ đo liên kết trọng số. Nếu trọng số liên kết càng phản ánh một cách khách quan thì hiệu quả của các độ đo liên kết trọng số càng lớn trong việc dự đoán cộng tác. Trong [28] đã đề xuất cách tính trọng số cộng tác giữa hai tác giả là số lượng bài báo đã cộng tác với nhau (𝜔𝑛𝑝). Với cách này, đã phản ánh được một phần mức độ cộng tác giữa hai tác giả. Tuy nhiên, trong một số trường hợp nếu hai cặp tác giả cùng có số lượng bài báo đã viết chung giống nhau thì không thể xác định được cặp tác giả nào có mức độ cộng tác cao hơn nếu không xem xét thêm các thông tin khác. Do vậy, để giải quyết được tình huống này, trong [66] đã đề xuất trọng số cộng tác dựa trên số tác giả trong mỗi bài báo (𝜔𝑛𝑎). Trên thực tế, mức độ cộng tác giữa các tác giả trong bài báo có số lượng đồng tác giả ít hơn sẽ cao hơn so với những bài báo có số lượng đồng tác giả nhiều hơn. Mức độ cộng tác giữa các tác giả ngoài việc phụ thuộc vào số lượng tác giả trong mỗi bài báo còn phụ thuộc vào thứ tự của mỗi tác giả trong bài báo. Chẳng hạn, trong một bài báo một số tác giả đứng đầu tiên thường có mức độ cộng tác với nhau cao hơn so với những trường hợp còn lại. Ngoài ra, yếu tố thời gian công bố của mỗi bài báo cũng phản ánh mức độ thường xuyên cộng tác giữa các tác giả. Vì vậy, trọng số liên kết giữa hai tác giả được tính dựa trên thứ tự của các tác giả trong bài báo và thời gian mà bài báo công bố đã được đề xuất trong [94] (xem công thức (1.5)). Để minh họa rõ hơn độ đo liên kết dựa trên trọng số như đã đề cập, luận án sẽ xem xét việc tính toán giá trị độ đo liên kết thông qua ví dụ về mạng đồng tác giả trong (Hình 1.3 và Bảng 1.1) đối với hai cặp tác giả là (v3, v1) và (v3, v6). Đối với trọng số liên kết dựa trên số lượng bài báo đã viết chung giữa hai tác giả thì 𝑆𝐶𝑁 𝑛𝑝 (v3, v1) = 2 do giữa hai tác giả v3 và v1 có một tác giả láng giềng chung là tác giả v2 (xem Hình 1.3), và số lượng bài báo viết chung giữa hai tác giả v3 và v2 là 3, giữa hai tác giả v2 và CHƯƠNG 2 45 v1 là 1 bài báo (xem Bảng 1.1); tương tự 𝑆𝐶𝑁 𝑛𝑝 (v3, v6) = 2. Như vậy, thông qua giá trị của độ đo liên kết trọng số dựa trên số lượng bài báo viết chung, có thể nhận thấy khả năng cộng tác giữa tác giả v3 và tác giả v1 cũng như tác giả v3 và tác giả v6 trong tương lai là như nhau. Tiếp đến, tính giá trị độ đo liên kết trọng số dựa trên số lượng tác giả trong mỗi bài báo sẽ nhận được 𝑆𝐶𝑁 𝑛𝑎(v3, v1) = (3 + 1/3)/2  1.67, và 𝑆𝐶𝑁 𝑛𝑎(v3, v6) = (3 + 1/2)/2 = 1.75 do giữa hai tác giả v3 và v2 có 3 bài báo được viết chung và trong cả ba bài báo này đều chỉ do hai tác giả này viết. Vì vậy, trọng số liên kết trong mỗi bài báo được xác định bằng 1 (theo công thức (1.15)) và do đó tổng trọng số giữa tác giả v3 và v2 là 3; đối với tác giả v2 và tác giả v1 có một bài báo được viết chung song trong bài báo đó lại bao gồm 4 tác giả vì thế trọng số liên kết giữa hai tác giả v2 và v1 được xác định bằng 1/3. Tương tự như vậy, giữa hai tác giả v2 và v6 có một bài báo được viết chung và số lượng tác giả trong bài báo đó là 3 vì vậy trọng số liên kết giữa hai tác giả này là 1/3. Dễ nhận thấy rằng, đối với độ đo liên kết trọng số dựa trên số lượng bài báo chung trong một số trường hợp cho ra giá trị độ đo liên kết như nhau. Điều này gây khó khăn trong việc dự đoán mức độ cộng tác trong tương lai. Khi áp dụng độ đo liên kết trọng số dựa trên số lượng tác giả trong mỗi bài báo, giá trị độ đo liên kết đã có sự phân biệt hơn (𝑆𝐶𝑁 𝑛𝑎(v3, v1) = 1.67 so với 𝑆𝐶𝑁 𝑛𝑎(v3, v6) = 1.75). Tuy vậy, sự khác biệt giữa 𝑆𝐶𝑁 𝑛𝑎(v3, v1) và 𝑆𝐶𝑁 𝑛𝑎(v3, v6) là chưa nhiều để tác giả v3 đưa ra quyết định cộng tác với tác giả v1 hay v6. Giả sử trong công thức (1.11), nếu thay thế trọng số cộng tác 𝜔𝑛𝑝 bởi 𝜔𝑝𝑡 thì giá trị độ đo liên kết trọng số dựa trên thứ tự tác giả và thời gian công bố của mỗi bài báo đối với hai cặp tác giả (v3, v1) và (v3, v6) được tính bằng 𝑆𝐶𝑁 𝑝𝑡 (v3, v1) = 1.29 và 𝑆𝐶𝑁 𝑝𝑡 (v3, v6)  0.805. Khác với độ đo trọng số dựa trên số tác giả trong mỗi bài báo, mức độ tương đồng 𝑆𝐶𝑁 𝑝𝑡 (v3, v1) > 𝑆𝐶𝑁 𝑝𝑡 (v3, v6), có sự khác biệt này là do giữa hai cặp tác giả (v2, v1) và (v2, v6) có sự khác biệt về thứ tự tác giả trong bài báo cùng với thời gian công bố giữa hai bài báo được viết chung bởi cặp tác giả (v2, v1) và (v2, v6). Có thể thấy rằng, trọng số liên kết 𝜔𝑝𝑡 cũng đã phản ánh được một khách quan hơn mức độ cộng tác giữa hai tác giả so với hai loại trọng số liên kết 𝜔𝑛𝑝 và 𝜔𝑛𝑎. Thật tiếc, cho đến nay, chưa có nghiên cứu nào sử dụng loại trọng số này trong các độ đo liên kết có trọng số như đã đề cập. Do vậy, luận án đã đề xuất các độ đo liên kết trọng số mở rộng dựa trên thứ tự của các tác giả và thời gian bài báo được xuất bản xác định bởi các công thức (2.1), (2.2), và (2.3) tương ứng với các ký hiệu độ đo liên kết lần lượt là 𝑆𝐶𝑁 𝑝𝑡 , 𝑆𝐴𝐴 𝑝𝑡 , 𝑆𝐽𝐶 𝑝𝑡 . 46 Các công thức từ (2.1) đến (2.3) đã được công bố trong nghiên cứu CT5. ( ) ( ) ( , ) ( , ) ( , ) 2 pt ptpt CN z u v u z v z S u v       (2.1) ( ) ( ) ( ) ( , ) ( , ) ( , ) 1 2 (1 ( , )) pt AA pt pt z u v ptz z S u v u z v z Log z z             (2.2) ( ) ( ) ( ) ( ) ( , ) ( , ) 2( , ) ( , ) ( , ) pt pt z u v pt JC pt ptu u v v u z v z S u v u u v v                 (2.3) Trong đó, 𝜔𝑝𝑡(𝑢, 𝑣) được xác định bởi công thức (1.5) trong chương 1. 2.2. Các độ đo liên kết dựa trên nội dung bài báo Các độ đo liên kết dựa trên trọng số giới thiệu trong mục 1.1.3 và mục 2.1 đã phản ánh được mức độ liên kết giữa hai cặp tác giả thông qua số lượng tác giả, thứ tự của các tác giả và thời gian xuất bản các bài báo. Tuy nhiên, trong mạng đồng tác giả, mỗi một mối cộng tác giữa hai tác giả lại ẩn chứa nội dung của bài báo mà hai tác giả cộng tác, nội dung của các bài báo mà mỗi tác giả đã viết có thể cho chúng ta biết về chủ đề hay lĩnh vực họ đang nghiên cứu, từ đó có thể biết được liệu những tác giả nào có lĩnh vực hay nội dung nghiên cứu tương đồng (hoặc gần) với tác giả cần xem xét, từ đó có thêm thông tin để dự đoán xem hai tác giả nào sẽ có khả năng cộng tác với nhau trong tương lai. Một số nghiên cứu trước đó đã xem xét mức độ tương đồng giữa hai tác giả thông qua tập các từ khóa xuất hiện trong các bài báo hoặc tập các từ xuất hiện trong tên và nội dung tóm tắt của bài báo [5, 50, 75, 92], sử dụng véc-tơ trọng số TF-IDF [87] hoặc xem xét mức độ tương quan giữa các tác giả dựa trên các lĩnh vực mà các bài báo họ đã công bố được u v z Pu = {pu1, pu2, , pum} Puz = {puz1, , puzk} Pv = {pv1, pv2, , pvn} Pvz = {pvz1, , pvzq} Nz = {(x1, (x1, z)), , (xl, (xl, z))} (u, z) (v, z) Hình 2.1 Minh họa độ đo liên kết mở rộng 47 phân vào [54]. Với cách này, không xem xét được tính tương đồng ngữ nghĩa hai tập từ, bởi lẽ hai từ khác nhau vẫn có thể có nghĩa tương đồng hoặc cùng thuộc về một chủ đề nào đó hoặc có thể cùng một mảng nghiên cứu được phân vào các lĩnh vực khác nhau và một lĩnh vực nghiên cứu có thể được diễn đạt với các tên khác nhau. Vì vậy, trong luận án này đã sử dụng phương pháp phân tích chủ đề để xác định mức độ tương đồng giữa hai bài báo. Trên thực tế, có nhiều phương pháp phân tích theo chủ đề. Tuy nhiên, vì khuôn khổ luận án có hạn nên chỉ lựa chọn kỹ thuật LDA bởi kỹ thuật này khá trực quan, có nhiều mã nguồn đáng tin cậy được chia sẻ trên mạng Internet có thể sử dụng lại được và đã được sử dụng trong mô hình CTR [86] để khuyến nghị bài báo khoa học. Mặt khác, việc hai tác giả u, v đã từng cùng cộng tác với một tác giả z nào đó cũng sẽ là cầu nối để hai tác giả u, v sẽ cộng tác với nhau trong tương lai. Độ đo liên kết đã được đề xuất như KMC [92] hay AKMC [75] mới chỉ xem xét mức độ tương đồng giữa hai tác giả u, v thông qua hai tập bài báo (Pu, Pv) được công bố bởi họ (dựa trên hai tập từ khóa hoặc hai tập từ xuất hiện trong nội dung tóm tắt của các bài báo) mà chưa xem xét đến mức độ tương đồng giữa tập bài báo được viết bởi tác giả u, z (Puz) với tập bài báo được viết chung bởi tác giả v, z (Pvz). Nếu hai tập bài báo (Pu, Pv) chỉ có một vài bài báo liên quan đến nhau, nhưng nếu những bài báo liên quan này lại xuất hiện tương ứng trong hai tập bài báo (Puz, Pvz) thì khả năng cộng tác giữa u và v càng cao bởi họ đã từng cùng cộng tác với tác giả z trong một số lĩnh vực. Từ phân tích trên kết hợp với những khảo sát về sự ảnh hưởng của nội dung bài báo đến các độ đo liên kết trong công trình nghiên cứu CT3, độ đo liên kết mở rộng dựa trên nội dung bài báo trong mạng đồng tác giả được luận án đề xuất. Hình 2.1 sẽ minh họa cho độ đo liên kết đã đề xuất. Hình 2.1 xem xét sự tương tác giữa hai tác giả u và v thông qua một tác giả z có mối cộng tác với cả hai tác giả u và v. Pu và Pv lần lượt là tập các bài báo đã được công bố bởi tác giả u và v; Puz và Pvz là tập các bài báo được công bố bởi cặp tác giả (u, z) và (v, z) tương ứng; (u, z) và (v, z) là trọng số liên kết giữa u với z, và v với z tương ứng; Nz là tập các tác giả đã cộng tác với z cùng với trọng số liên kết với z. Để xác định mức độ tương đồng giữa hai tác giả, có thể kết hợp mức độ tương đồng giữa hai tập bài báo được công bố bởi hai tác giả u, v (S(Pu, Pv) có thể xem như là mức độ tương đồng về lĩnh vực nghiên cứu) với mức độ tương tự giữa hai tập bài báo được viết chung bởi hai tác giả (u, z) và (v, z) (S(Puz, Pvz)) dựa trên ý tưởng của độ đo liên kết trọng số theo láng giềng chung (𝑆𝐶𝑁 𝑛𝑝 ). 48 Có hai cách kết hợp là kết hợp tích và kết hợp tuyến tính. a) Kết hợp tích, ký hiệu là SP_LDAcosin(u, v) được tính theo công thức (2.4) [CT5] _ cos ( ) ( )1 ( , ) 1 ( , ) ( , ) 1 1 1 ( ) ( )u v uz vz P LDA in z u vS P P S P P S u v u ve e          (2.4) Trong đó, ( , )u v av avx x u vSP P P av avx x u v    (2.5) 1 1 ( ) ( ), 1: m av u ui i x j x j j K m    (2.6) ( , )uz vz av avx x uz vzSP P P av avx x uz vz    (2.7) 1 1 ( ) ( ), 1, k av uz uzi i x j x j j K k    (2.8) Xu = {xu1,,xum}, Xv = {xv1,,xvn}, Xuz = {xuz1,,xuzk}, Xvz = {xvz1,,xvzq} lần lượt là tập các véc-tơ trong không gian K chiều, biểu diễn các bài báo trong Pu, Pv và Pvz tương ứng; 𝑥𝑢 𝑎𝑣là véc-tơ trung bình từ tập các bài báo của tác giả u; m, n lần lượt là số lượng bài báo được công bố bởi tác giả u, v; k, q lần lượt là số bài báo được viết chung bởi tác giả u và z, và v và z. Trong công thức (2.4), mức độ tương đồng giữa hai tác giả càng cao nếu họ có nhiều tương đồng về lĩnh vực nghiên cứu và mức độ tương đồng trung bình giữa tập các bài báo của hai nút với láng giềng chung càng cao. b) Kết hợp tuyến tính, ký hiệu là SLDAcosin (u, v) Độ đo liên kết dựa trên nội dung bài báo (SLDAcosin) được xây dựng dựa trên sự kết hợp tuyến tính mức độ tương đồng giữa hai tập bài báo mà hai tác giả đã công bố (trong Hình 2.1 chính là hai tập Pu và Pv), và mức độ tương đồng giữa hai tập bài báo mà mỗi tác giả đã viết chung với tác giả láng giềng chung (trong Hình 2.1 là tập Puz và Pvz). SLDAcosin được xác định bởi công thức (2.9). ( ) ( ) ( , ) cos 1 ( , ) (1 ) ( , ) | ( ) ( ) | u v uz vz z u v S u v LDA in SP P P SP P P u v              (2.9) 49 Trong đó, hệ số kết hợp  (0, 1), S(Pu, Pv) được tính theo công thức (2.5) và S(Puz, Pvz) được tính theo công thức (2.7). Mức độ tương đồng giữa hai tác giả dựa trên nội dung bài báo được đề xuất trong công thức (2.9) có thể áp dụng cho hai tác giả bất kỳ, trong trường hợp hai tác giả không có láng giềng chung (tức là không có tác giả nào cùng viết chung với hai tác giả đó) thì thành phần thứ hai (chứa S(Puz, Pvz)) trong công thức (2.9) sẽ bằng 0. Như vậy, công thức (2.9) có tính phổ quát cao hơn công thức (2.4), đồng thời tham số  cho phép điều chỉnh sự ảnh hưởng của từng thành phần (thành phần thứ nhất chứa S(Pu, Pv), và thành phần thứ hai chứa S(Puz, Pvz)) tùy thuộc vào từng trường hợp cụ thể. Phương pháp LDA được sử dụng để phân tích mỗi bài báo vào K chủ đề khác nhau (K nguyên dương), thông tin của mỗi bài báo được sử dụng để phân tích chủ đề bao gồm tên và nội dung tóm tắt của bài báo với mong muốn xác định được một cách chính xác nhất và có tính tương đồng cao về ngữ nghĩa lĩnh vực nghiên cứu của mỗi tác giả thông qua nội dung của các bài báo. Sau khi áp dụng kỹ thuật LDA đối với tập các bài báo, sẽ nhận được một véc-tơ độ thuộc p trong không gian K chiều tương ứng với bài báo thứ p, các giá trị của mỗi phần tử jp trong p cho biết bài báo thứ p thuộc vào chủ đề thứ j với độ thuộc bằng bao nhiêu. Véc-tơ p được luận án sử dụng như là một véc-tơ đặc trưng cho bài báo thứ p, và dùng để tính các độ đo liên kết mở rộng mà luận án đã đề xuất. Trên cơ sở các độ đo liên kết trọng số đã được giới thiệu trong mục 1.1.3 và mục 2.1, và độ đo liên kết dựa trên nội dung bài báo (SLDAcosin) đã được đề xuất, có thể kết hợp các độ đo liên kết trọng với chỉ số SLDAcosin để tạo ra một độ đo liên kết mở rộng nhằm tăng cường (cải thiện) mức độ chính xác dự đoán khi áp dụng vào bài toán dự đoán liên kết trong mạng đồng tác giả. Trên cơ sở đó, việc kết hợp các độ đo liên kết trọng số với SLDAcosin đã được đề xuất trong luận án theo các công thức tổng quát từ (2.10) đến (2.12). Các đề xuất của luận án về việc kết hợp tuyến tính giữa các độ đo liên kết trọng số với độ đo liên kết dựa trên nội dung bài báo trên cơ sở việc phân tích sự ảnh hưởng của các độ đo liên kết trong mạng đồng tác giả đã được công bố trong công trình nghiên cứu CT2. _ cos cos( , ) ( , ) (1 ) ( , ) type type CN LDA in CN LDA inS u v S u v S u v      (2.10) type type AA_LDAcosin AA LDAcosin( , ) ( , ) (1 ) ( , )S u v S u v S u v      (2.11) type type JC_LDAcosin LDAcosin( , ) ( , ) (1 ) ( , )JCS u v S u v S u v      (2.12) Trong đó, type  {‘np’, ‘na’, ‘pt’} tương ứng với các kiểu trọng số liên kết, hệ số kết hợp   (0, 1) cho biết mức độ ảnh hưởng của độ đo liên kết trọng số đến độ đo liên kết kết 50 hợp, hệ số này cũng sẽ được tính thông qua thực nghiệm. Như vậy, ba kiểu trọng số liên kết và ba độ đo liên kết khi kết với hợp đô đo SLDAcosin sẽ cho ra được 9 cách kết hợp khác nhau. 2.3. Thuật toán tính độ đo liên kết và đánh giá độ phức tạp của thuật toán Trong mục này, luận án trình bày các thuật toán dưới dạng giả mã để tính toán giá trị độ đo liên kết dựa trên trọng số và dựa trên nội dung bài báo đã trình bày bày trong mục 1.1.3, 2.1 và 2.2. Ở đây, giả thiết mạng đồng tác giả được lưu dưới dạng danh sách kề. Do vậy, tập láng giềng ((u)) của một tác giả đã được xác định. Đầu tiên, luận án sẽ trình bày thuật toán 2.1 để xác định ba loại trọng số (type = {‘np’, ‘na’, ‘pt’}) làm cơ sở để tính toán các độ đo liên kết trọng số. Thuật toán 2.1 Weighted_based_type Đầu vào: Tập quan các hệ cộng tác E(T), tc thời gian hiện tại, tf là thời gian đầu tiên hai tác giả u, v cộng tác, loại trọng số cần tính type và tập các bài báo P(T). Đầu ra: Giá trị trọng số dựa trên type ứng với các cặp tác giả u, v có quan hệ cộng tác trong E(T) (𝜔𝑡𝑦𝑝𝑒). 1: For (u,v)  E(T) 2: (u,v) := 0 3: For p  Puv // tập các bài báo được viết chung bởi hai tác giả u, v 4: If type == ‘np’ 5: (u,v) := (u,v) + 1 6: Else 7: If type == ‘na’ 8: (u,v) := (u,v)+ 1/(p.numofauthors - 1) 9: Else // tính trọng số theo type = ’pt’ 10: tp := p.year; du := p.order(u); dv := p.order(v); t0 := tf - 1 11: (u,v) := (u,v) + DCL(du, dv)*(tp – t0)/(tc – t0) 12: End If 13: End If 14: End For 15: End For // DCL(du, dv) được xác định theo công thức (1.4) trong chương 1 51 Mệnh đề 2.1. Thuật toán 2.1 có độ phức tạp thời gian là O(NDQ). Trong đó, N là tổng số tác giả trong mạng, D và Q lần lượt là số láng giềng lớn nhất và số bài báo lớn nhất của một tác giả nào đó. Chứng minh. Dễ nhận thấy, thuật toán sẽ thực hiện hai vòng For lồng nhau (dòng 1, 3). - Xét vòng For thứ 2 (dòng 3): Dễ nhận thấy, cần phải duyệt vòng For theo tập số bài báo chung của hai tác giả u, v (Puv). Do vậy, độ phức tạp thời gian được xác định là T1 (Q) = O(Q). - Xét vòng For thứ 1 (dòng 1): Dễ nhận thấy, cần phải duyệt vòng For theo số lượng cộng tác trong E(T). Do vậy, độ phức tạp thời gian được xác định là T2 (|E(T)|, Q) = |E(T)|T1(Q) = O(|E (T)|Q). Mặt khác, do đồ thị biểu diễn mối quan hệ cộng tác giữa các tác giả là một đơn đồ thị vô hướng. Vì vậy, ta có mối quan hệ (tổng bậc của tất cả các nút bằng hai lần số cạnh) 2|E(T)| = ∑ |Γ(𝑣)|𝑣∈𝑉(𝑇) . Từ đó, |E (T)|  ND/2. Như vậy, độ phức tạp thời gian khi xét với vòng For thứ nhất là T2(N, D, Q) = O(NDQ). Tóm lại, độ phức tạp thời gian của thuật toán 2.1 là: T(N, D, Q) = T2 (N, D, Q) = O(NDQ). Do các độ đo liên kết trọng số dựa trên CN (bao gồm 𝑆𝐶𝑁 𝑡𝑦𝑝𝑒 , với type là kiểu trọng số liên kết) đều có cách tính tương tự nhau, chỉ khác biệt ở việc tính trọng số liên kết giữa hai tác giả. Nên để cho ngắn gọn, luận án sẽ trình bày một thuật toán chung để tính toán giá trị của các độ đo liên kết trọng số dựa trên CN thông qua Thuật toán 2.2 dưới đây. Mệnh đề 2.2. Thuật toán 2.2 có độ phức tạp thời gian là O(NDQ +ND2). Trong đó, N là tổng số tác giả trong mạng, D và Q lần lượt là số láng giềng lớn nhất và số bài báo lớn nhất của một tác giả nào đó. Chứng minh. Dễ nhận thấy, thuật toán sẽ thực hiện tính trọng số cho các quan hệ cộng tác (type) theo Thuật toán 2.1, sau đó thực hiện ba vòng For lồng nhau (dòng 1, 3, 4). - Để tính trọng số cho các quan hệ cộng tác theo Thuật toán 2.1 thì độ phức tạp thời gian được xác định là T1(N, D, Q) = O(NDQ). - Xét vòng For thứ 3 (dòng 4): cần duyệt theo số láng giềng của tác giả v ((v)), do đó độ phức tạp thời gian được xác định là T2(D) = O(D). - Xét vòng For thứ 2 (dòng 3): cần duyệt theo số láng giềng của tác giả u ((u)), do đó độ phức tạp thời gian được xác định là T3(D) = DT2(D) = O(D2). - Xét vòng For thứ nhất (dòng 1): cần duyệt theo tất cả các tác giả trong mạng (V(T)), do đó độ phức tạp thời gian được xác định là T4(N, D) = NT3(D) = O(ND2). 52 Tóm lại, độ phức tạp thời gian của thuật toán 2.2 là: T(N, Q, D) = T1(N, D, Q) + T4(N, D) = O(NDQ+ND 2). Thuật toán 2.2 Weighted_Metrics_based_CN Đầu vào: Tập các tác giả V(T), tập các cộng tác E(T ), tập các bài báo P(T) và type  {‘np’, ‘na’, ‘pt’} tương ứng với các kiểu trọng số liên kết. Đầu ra: Giá trị độ đo liên kết trọng số dựa trên CN ứng với các cặp tác giả có chung láng giềng (𝑆𝐶𝑁 𝑡𝑦𝑝𝑒 ). 1: type := Weighted_based_type(E(T ), P(T), type)// tính trọng số liên kết cho các quan hệ cộng tác 2: For u  V(T) 3: hset := new HashSet() 4: For v  (u) 5: For x  (v)\{u} 6: If (check(x) ==0 && hset.contains(x)) 7: 𝑆𝐶𝑁 𝑡𝑦𝑝𝑒(𝑢, 𝑥) := 𝑆𝐶𝑁 𝑡𝑦𝑝𝑒(𝑢, 𝑥) + (type(u, v) + type(v, x))/2 8: Else If (check(x) == 0) 9: hset.add(x) 𝑆𝐶𝑁 𝑡𝑦𝑝𝑒(𝑢, 𝑥) := (type(u, v) + type(v, x))/2 10: End If 11: End For 12: End For 13: Check(u) := 1 14: End For 53 Tương tự như các độ đo liên kết trọng số dựa trên CN, các độ đo liên kết trọng số dựa trên AA (bao gồm 𝑆𝐴𝐴 𝑡𝑦𝑝𝑒 ) cũng được trình bày trên một Thuật toán chung để tính toán giá trị của các độ đo liên kết dựa trên Thuật toán 2.3 dưới đây. Thuật toán 2.3 Weighted_Metrics_based_AA Đầu vào: Tập các tác giả V(T), tập các cộng tác E(T ), tập các bài báo P(T) và type  {‘np’, ‘na’, ‘pt’} tương ứng với các kiểu trọng số liên kết. Đầu ra: Giá trị độ đo liên kết trọng số dựa trên AA ứng với các cặp tác giả có láng giềng chung (𝑆𝐴𝐴 𝑡𝑦𝑝𝑒 ). 1: type := Weighted_based_type(E(T ), P(T), type)// tính trọng số liên kết cho các quan hệ cộng tác 2: For u  V(T) 3: For v  (u) // lần lượt xét các láng giềng của u 4: wv := 0 hset : = new HashSet() 5: For y  (v) // lần lượt xét các láng giềng của v 6: wv := wv + type(y, z) // tính tổng trọng số của v 7: End For 8: For x  (v)\{u} // lần lượt xét các láng giềng của v 9: If (check(x) ==0 && hset.contains(x)) 10: 𝑆𝐴𝐴 𝑡𝑦𝑝𝑒(𝑢, 𝑥) := 𝑆𝐴𝐴 𝑡𝑦𝑝𝑒(𝑢, 𝑥) + ( ( , ) ( , )) 2 (1 ) type typeu v v x Log wv    11: Else If (check(x) == 0) 12: hset.add(x) 13: 𝑆𝐴𝐴 𝑡𝑦𝑝𝑒(𝑢, 𝑥) := ( ( , ) ( , )) 2 (1 ) type typeu v v x Log wv    14: End If 15: End For 16: End For 17: Check(u) := 1 18: End For 54 Mệnh đề 2.3. Thuật toán 2.3 có độ phức tạp thời gian là O(NDQ +ND2). Trong đó, N là tổng số tác giả trong mạng, D và Q lần lượt là số láng giềng lớn nhất và số bài báo lớn nhất của một tác giả nào đó. Chứng minh. Dễ nhận thấy, thuật toán sẽ tính toán trọng số liên kết cho các quan hệ cộng tác (type), sau đó thực hiện hai vòng For lồng nhau (dòng 2, 3), đối với vòng For thứ hai thì thực hiện hai vòng For liên tiếp (dòng 5, 8). - Để tính trọng số cho các quan hệ cộng tác theo Thuật toán 2.1 thì độ phức tạp thời gian được xác định là T1(N, D, Q) = O(NDQ). - Xét vòng For dòng 5: cần duyệt theo số láng giềng của tác giả v ((v)), do đó độ phức tạp thời gian được xác định là T2(D) = O(D). - Xét vòng For dòng 8: cần duyệt theo số láng giềng của tác giả v ((v)), do đó độ phức tạp thời gian được xác định là T3(D) = O(D). - Xét vòng For thứ hai (dòng 3): cần duyệt theo số láng giềng của tác giả u ((u)), do đó độ phức tạp thời gian được xác định là T4(D) = D(T2(D)+T3(D)) = O(D2). - Xét vòng For thứ nhất (dòng 1): cần duyệt theo tất cả các tác giả trong mạng (V(T)), do đó độ phức tạp thời gian được xác định là T5 (N, D) = NT4(D) = O(ND2). Tóm lại, độ phức tạp thời gian của thuật toán 2.3 là: T(N, Q, D) = T1(N, D, Q) + T5(N, D) = O(NDQ+ND 2). Tương tự như hai Thuật toán 2.2 và 2.3, các độ đo liên kết trọng số dựa trên JC (bao gồm 𝑆𝐽𝐶 𝑡𝑦𝑝𝑒 ) cũng được trình bày trên một Thuật toán chung để tính toán giá trị của các độ đo liên kết theo Thuật toán 2.4 dưới đây. Mệnh đề 2.4. Thuật toán 2.4 có độ phức tạp thời gian O(NDQ +ND2). Trong đó, N là tổng số tác giả trong mạng, D và Q lần lượt là số láng giềng lớn nhất và số bài báo lớn nhất của một tác giả nào đó. Chứng minh. Dễ nhận thấy, thuật toán sẽ tính toán trọng số liên kết cho các quan hệ cộng tác (type), sau đó từ dòng 2 đến dòng 9 thuật toán sẽ thực hiện hai vòng For lồng nhau (dòng 2, 4), từ dòng 10 đến 23 thuật toán sẽ thực hiện ba vòng For lồng nhau (dòng 10, 12, 13). - Để tính trọng số cho các quan hệ cộng tác theo Thuật toán 2.1 thì độ phức tạp thời gian được xác định là T1(N, D, Q) = O(NDQ). - Xét vòng For dòng 4: cần duyệt theo số láng giềng của tác giả u ((u)), do đó độ phức tạp thời gian được xác định là T2(D) = O(D). - Xét vòng For dòng 2: cần duyệt theo tất cả các tác giả trong mạng (V(T)), do đó độ phức tạp thời gian được xác định là T3(N, D) = NT2(D) = O(ND). 55 - Xét vòng For dòng 13: cần duyệt theo số láng giềng của tác giả v ((v)), do đó độ phức tạp thời gian được xác định là T4(D) = O(D). - Xét vòng For dòng 12: cần duyệt theo số láng giềng của tác giả u ((u)), do đó độ phức tạp thời gian được xác định là T5(D) = DT4(D) = O(D2). - Xét vòng For dòng 10: cần duyệt theo tất cả các tác giả trong mạng (V(T)), do đó độ phức tạp thời gian được xác định là T6(N, D) = NT5(D) = O(ND2). Tóm lại, độ phức tạp thời gian của thuật toán 2.4 là: T(N, Q, D) = T1(N, D, Q)+T3(N, D)+T6(N, D) = O(NDQ)+ O(ND)+O(ND 2) = O(NDQ+ND2). Thuật toán 2.4 Weighted_Metrics_based_JC Đầu vào: Tập các tác giả V(T), tập các cộng tác E(T ), tập các bài báo P(T) và type  {‘np’, ‘na’, ‘pt’} tương ứng với các kiểu trọng số liên kết. Đầu ra: Giá trị độ đo liên kết trọng số dựa trên JC ứng với các cặp tác giả có chung láng giềng (𝑆𝐽𝐶 𝑡𝑦𝑝𝑒 ). 1: type := Weighted_based_type(E(T ), P(T), type)// tính trọng số liên kết cho các quan hệ cộng tác 2: For u  V(T) 3: w(u) := 0 5: For each y  (u) 7: w(u) := w(u) + type(u, y) 8: End For 9: End For 10: For u  V(T) 11: hset : = new HashSet() 12: For each v  (u) // lần lượt xét các láng giềng của u 13: For each x  (v)\{u} // lần lượt xét các láng giềng của v 14: If (check(x) ==0 && hset.contains(x)) 15: 𝑆𝐽𝐶 𝑡𝑦𝑝𝑒(𝑢, 𝑥)= 𝑆𝐽𝐶 𝑡𝑦𝑝𝑒(𝑢, 𝑥) + (type(u, v) + type(v, x))/2(w(u)+w(x)) 16: Else If (check(x) == 0) 17: hset.add(x) 18: 𝑆𝐽𝐶 𝑡𝑦𝑝𝑒(𝑢, 𝑥)= (type(u, v) + type(v, x))/2(w(u)+w(x)) 19: End If 20: End For 21: End For 22: Check(u) := 1 23: End For 56 Giá trị độ đo liên kết dựa trên nội dung bài báo P_LDAcosin và LDAcosin sẽ được xác định dựa trên Thuật toán 2