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

á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à 푆 , 푆 , 푆퐽 . 
 45 
 Các công thức từ (2.1) đến (2.3) đã được công bố trong nghiên cứu CT5. 
 (,)(,)u z v z
 Spt ( u , v )  pt pt (2.1) 
 CN z ()() u  v 2
 pt
 SAA ( u , v )
 pt(,)(,)u z pt v z 1 (2.2) 
 z ()() u  v
 2Log (1 zz  ()pt ( z , z ))
 pt(,)(,)u z pt v z
 z ()() u  v
 pt 2 (2.3) 
 SJC ( u , v ) 
 u ()() upt(,)(,)u u v  v pt v v
 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. 
 Pu = {pu1, pu2, , pum} Pv = {pv1, pv2, , pvn} 
 u v 
 Puz = {puz1, , puzk} (v, z) 
 (u, z) Pvz = {pvz1, , pvzq} 
 z 
 Nz = {(x1, (x1, z)), , (xl, (xl, z))} 
 Hình 2.1 Minh họa độ đo liên kết mở rộng 
 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 
 46 
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 (푆 ). 
 47 
 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] 
 SP_ LDA cos in (,) u v 
 1 1 1 (2.4) 
 z ()() u  v
 1 SPPSPP (u , v ) 1 ( uz , vz )
 ee()()uv  
Trong đó, 
 xxav av
 uv
 SP(,) Puv P (2.5) 
 xxav av
 uv 
 m
 av 1
 xu( j )  x ui ( j ), j 1: K (2.6) 
 m i 1
 xxav av
 uz vz
 SP(,) Puz P vz (2.7) 
 xxav av
 uz vz
 k
 av 1
 xuz( j )  x uzi ( j ), j 1, K (2.8) 
 k i 1
 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). 
 S(,) u v 
 LDAcos in
 1 (2.9) 
  SP( Pu , P v ) (1 )  SP ( P uz , P vz )
 | (uv )  ( ) | z ()() u  v
 48 
 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 
 j
phần tử  p 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. 
 type type
 SCN_ LDA cos in(,) u v S CN (,)(1) u v S LDA cos in (,) u v (2.10) 
 type type
 SAA_LDAcosin(,) u v S AA (,)(1) u v S LDAcosin (,) u v (2.11) 
 type type
 SJC_LDAcosin(,) u v SJC (,)(1) u v S LDAcosin (,) 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 
 49 
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 
 (T)
 Đầu vào: Tập quan các hệ cộng tác E , tc thời gian hiện tại, tf là thời gian đầu tiên 
 (T)
 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 . 
 Đầ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)
 tác trong E (휔푡 푒). 
 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 
 50 
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 
 (T) (T)
 cộng tác trong E . Do vậy, độ phức tạp thời gian được xác định là T2 (|E |, Q) = 
 (T) (T)
 |E |T1(Q) = O(|E |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) 
 (T) (T)
 2|E | = ∑푣∈ ( ) |Γ(푣)|. Từ đó, |E | 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 đó 
 2
 độ phức tạp thời gian được xác định là T3(D) = DT2(D) = O(D ). 
 - 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)), 
 2
 do đó độ phức tạp thời gian được xác định là T4(N, D) = NT3(D) = O(ND ). 
 51 
Tóm lại, độ phức tạp thời gian của thuật toán 2.2 là: 
 2
 T(N, Q, D) = T1(N, D, Q) + T4(N, D) = O(NDQ+ND ). 
 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 (푆 ). 
 (T ) (T)
 1: type := Weighted_based_type(E , P , 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 
 52 
 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 (푆 ). 
 (T ) (T)
 1: type := Weighted_based_type(E , P , 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: ( (u , v ) ( v , x ))
 푆푡 푒( , ) := 푆푡 푒( , ) + type type 
 2Log (1 wv )
 11: Else If (check(x) == 0) 
 12: hset.add(x) 
 13: 푡 푒
 푆 ( , ) := 
 14: End If 
 15: End For 
 16: End For 
 17: Check(u) := 1 
 18: End For 
 53 
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 
 2
 đó độ phức tạp thời gian được xác định là T4(D) = D(T2(D)+T3(D)) = O(D ). 
 - 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)), 
 2
 do đó độ phức tạp thời gian được xác định là T5 (N, D) = NT4(D) = O(ND ). 
Tóm lại, độ phức tạp thời gian của thuật toán 2.3 là: 
 2
 T(N, Q, D) = T1(N, D, Q) + T5(N, D) = O(NDQ+ND ). 
 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