Tổng quan luận án

Luận án tiến sĩ "Một số kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội" được thực hiện bởi nghiên cứu sinh Nguyễn Hiền Trinh, thuộc ngành Khoa học máy tính (mã số: 9480101), dưới sự hướng dẫn khoa học của TS. Vũ Vinh Quang và PGS.TS Đoàn Văn Ban tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên (bảo vệ năm 2023).

Tính cấp thiết và khoảng trống nghiên cứu

Mạng xã hội được mô hình hóa dưới dạng đồ thị phức tạp $G = (V, E)$, trong đó các đỉnh $V$ đại diện cho các thực thể (người dùng, tổ chức) và các cạnh $E$ thể hiện mối quan hệ, tương tác giữa các thực thể. Khai phá cấu trúc cộng đồng (community detection) là bài toán phân rã mạng lưới thành các đồ thị con sao cho các đỉnh nội bộ liên kết chặt chẽ và các liên kết liên cộng đồng là thưa thớt.

Theo tác giả trình bày, bài toán phát hiện cấu trúc cộng đồng đối mặt với các thách thức kỹ thuật lớn:

  • Phần lớn các thuật toán truyền thống và thuật toán tối ưu hóa (như giải thuật phân tách cạnh trung gian Girvan-Newman với độ phức tạp $O(m^2n)$, thuật toán CONGA $O(m^3)$, hoặc thuật toán tìm kiếm tham lam tối ưu hóa Modularity $O(n^3)$) đòi hỏi chi phí tính toán rất cao khi xử lý đồ thị mạng xã hội quy mô lớn.
  • Thuật toán lan truyền nhãn (LPA) có ưu điểm thời gian tính toán gần tuyến tính $O(m+n)$, song lại phụ thuộc vào cơ chế ngẫu nhiên hóa (heuristic), không đảm bảo tìm ra nghiệm duy nhất và dễ bị mất ổn định.
  • Vấn đề phát hiện cộng đồng chồng chéo (overlapping communities) – khi một đỉnh có thể thuộc về nhiều hơn một nhóm – thường gặp khó khăn trong việc cân bằng giữa độ chính xác và hiệu năng tính toán trên các mạng mật độ cao; các thuật toán như COPRA khó xác định tham số cận trên số lượng cộng đồng trực thuộc ($\mu$).

Mục tiêu nghiên cứu

Mục tiêu tổng quát của luận án là nghiên cứu và đề xuất một số kỹ thuật nhằm nâng cao tốc độ tính toán và chất lượng phân cụm cấu trúc cộng đồng trên đồ thị mạng xã hội. Cụ thể bao gồm hai mục tiêu thành phần:

  1. Nghiên cứu, phát triển một số thuật toán phát hiện cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội (tập trung vào kỹ thuật phân cụm phổ cải tiến, lan truyền nhãn kết hợp tối ưu hàm mật độ - modul, và lan truyền nhãn kết hợp rút gọn đỉnh treo).
  2. Nghiên cứu, phát triển thuật toán phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội (dựa trên việc kết hợp lan truyền nhãn với hệ số thuộc về cộng đồng xuất phát từ hệ số phân cụm cải tiến).

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Các mô hình biểu diễn đồ thị mạng xã hội; các độ đo trung tâm và cấu trúc đồ thị (độ đo trung tâm theo bậc, độ đo trung gian, độ đo vector riêng, hệ số phân cụm); các độ đo đánh giá chất lượng phân cụm (độ đơn thể Modularity $Q$, thông tin tương hỗ chuẩn NMI); các giải thuật phát hiện cộng đồng rời nhau và chồng chéo.
  • Phạm vi nghiên cứu:
    • Về mặt lý thuyết: Tập trung vào kỹ thuật phân cụm phổ (Spectral Clustering) sử dụng ma trận Laplace và bài toán Min-cut; kỹ thuật lan truyền nhãn (LPA, COPRA) và các biến thể kết hợp rút gọn đồ thị (Reduce Leaf Vertex Graph - RLVG).
    • Về dữ liệu thực nghiệm: Thử nghiệm trên các tập dữ liệu mạng xã hội và mạng phức tạp thực tế chuẩn (Ground truth) từ các kho dữ liệu mở như Stanford Large Network Dataset Collection (SNAP) và Network Repository.

Tổng quan tài liệu và vị trí của luận án

Luận án hệ thống hóa các công trình nghiên cứu trong và ngoài nước về bài toán phân tích mạng xã hội và phát hiện cấu trúc cộng đồng theo 5 nhóm phương pháp chính:

Nhóm phương pháp Công trình và tác giả tiêu biểu Đặc điểm và hạn chế văn bản ghi nhận
1. Thuật toán truyền thống - Kernighan - Lin (1970)
- Phân cụm phân cấp BIRCH (Zhang et al., 1996)
- Phân cụm phân hoạch k-Means (MacQueen, 1967)
- Phân cụm phổ (Ulrike von Luxburg, 2007; Tang F et al., SpcSA)		 Cần xác định trước số cụm $k$ hoặc ngưỡng $T$; độ phức tạp lớn khi dữ liệu đa chiều; dễ mất mát thông tin trong quá trình chiếu không gian.
2. Tối ưu hóa độ đo đơn thể (Modularity) - Greedy Search (Newman, 2004)
- Louvain (Blondel et al., 2008)
- Mô phỏng luyện kim Simulated Annealing (Kirkpatrick et al., 1983)		 Thuật toán Newman có độ phức tạp $O(n^3)$; Louvain đạt $O(n \log n)$ nhưng dễ rơi vào cực trị địa phương; mô phỏng luyện kim phụ thuộc tham số nhiệt độ.
3. Dựa trên độ đo trung gian (Betweenness) - Girvan - Newman (GN, 2002/2004)
- CONGA (Gregory, 2007)
- CONGO (Gregory, 2008)
- Brandes (2001)		 Phải tính toán lại độ đo trung gian sau mỗi lần xóa cạnh; độ phức tạp GN là $O(m^2n)$, CONGA là $O(m^3)$; CONGO giảm xuống $O(m \log m + m^2 2^{h+2}/n)$ bằng trung gian cục bộ.
4. Lan truyền nhãn (Label Propagation) - LPA (Raghavan et al., 2007)
- COPRA (Gregory, 2010)
- PCB (Fu et al., 2018)
- OLP (Matin Pirouz et al., 2018)
- Saradha et al. (2020)		 LPA chạy gần tuyến tính $O(m+n)$ nhưng không hội tụ trên đồ thị hai phía (bipartite), kết quả không ổn định; COPRA khó kiểm soát tham số $\mu$.
5. Học sâu trên đồ thị (Deep Learning) - GCN (Kipf & Welling), GNN, Deep Autoencoder, Non-negative Matrix Factorization (NMF) Xử lý tốt các đặc trưng phi tuyến nhưng chi phí huấn luyện cao và cấu hình phức tạp.

Các nghiên cứu liên quan tại Việt Nam

Luận án điểm lại các công trình tiêu biểu trong nước:

  • Hồ Trung Thành (2017): Phân tích mạng xã hội dựa trên mô hình chủ đề có yếu tố thời gian.
  • Dư Phương Hạnh (2018): Tối ưu hóa truy vấn tương tranh trên đồ thị động và tính toán song song độ trung tâm.
  • Nguyễn Xuân Dũng (2021): Nghiên cứu kỹ thuật rút gọn đồ thị phục vụ phát hiện cấu trúc cộng đồng rời nhau.

Khoảng trống nghiên cứu luận án lựa chọn giải quyết

  1. Giảm số chiều không gian dữ liệu gốc trong phân cụm phổ nhằm hạ thấp độ phức tạp tính toán nhưng vẫn bảo toàn cấu trúc phân cụm thông qua tối ưu ma trận Laplace.
  2. Khắc phục tính bất định và nâng cao độ chính xác của thuật toán LPA bằng cách xây dựng hàm chọn nhãn kết hợp giữa độ đơn thể (Modularity) và mật độ liên kết cục bộ (Density).
  3. Giảm quy mô không gian tính toán trước khi lan truyền nhãn bằng phương pháp tách và gộp các đỉnh treo (Leaf vertices).
  4. Xác định cơ chế gán nhãn đa cộng đồng tự thích nghi cho bài toán cộng đồng chồng chéo thông qua hệ số phân cụm cải tiến thay cho việc gán tham số cố định.

Cơ sở lý thuyết và phương pháp nghiên cứu

Các khái niệm và mô hình lý thuyết

  • Đồ thị mạng xã hội: Được định nghĩa là đồ thị $G = (V, E)$ với $V$ là tập đỉnh ($|V| = n$) và $E$ là tập cạnh ($|E| = m$).
  • Cấu trúc cộng đồng rời nhau: Tập các đồ thị con $\mathcal{C} = {C_1, C_2, \dots, C_k}$ với $C_i = (V_i, E_i)$ thỏa mãn:
    1. $\bigcup_{i=1}^k V_i = V$ và $V_i \cap V_j = \emptyset$ với mọi $i \neq j$.
    2. $\bigcup_{i=1}^k E_i \subseteq E$, trong đó số liên kết nội bộ $|E_i| \to \max$, số liên kết liên cộng đồng $|E_{ij}| \to \min$, và thỏa mãn $|E_i| \gg |E_{ij}|$.
  • Cấu trúc cộng đồng chồng chéo: Tồn tại ít nhất một đỉnh $v \in V$ thỏa mãn $v \in V_i \cap V_j$ với $i \neq j$.

Các độ đo trung tâm và cấu trúc đồ thị

  • Độ đo trung tâm theo bậc chuẩn hóa (Degree Centrality): $$C_D(v) = \frac{\text{deg}(v)}{n - 1}$$
  • Độ đo trung gian (Betweenness Centrality): $$C_B(v) = \sum_{s \neq t \neq v} \frac{\sigma_{st}(v)}{\sigma_{st}}$$ Trong đó $\sigma_{st}$ là số đường đi ngắn nhất giữa $s$ và $t$, $\sigma_{st}(v)$ là số đường đi ngắn nhất đi qua đỉnh $v$. Luận án áp dụng phương pháp Brandes tính thông qua độ phụ thuộc kép $\tau_{st}(v) = \frac{\sigma_{st}(v)}{\sigma_{st}}$.
  • Độ đo trung tâm theo vector riêng (Eigenvector Centrality): $$x_v = \sum_{u \in \Gamma(v)} a_{uv} x_u \quad \Leftrightarrow \quad A^T x = \lambda x$$
  • Hệ số phân cụm của đỉnh (Clustering Coefficient):
    • Đối với đồ thị có hướng: $C(v) = \frac{|{e_{ij}}|}{n(n-1)}$ (với $i, j$ thuộc tập lân cận của $v$).
    • Được sử dụng làm cơ sở để tác giả xây dựng hệ số thuộc về cộng đồng (Belonging Coefficient).

Các tiêu chuẩn đánh giá chất lượng thuật toán

  1. Độ đo đơn thể (Modularity $Q$): Đánh giá độ đậm đặc của các cạnh bên trong cộng đồng so với mạng ngẫu nhiên có cùng phân bố bậc: $$Q = \sum_{i} (e_{ii} - a_i^2)$$ Trong đó $e_{ii}$ là tỷ lệ số cạnh nội bộ cộng đồng $i$, $a_i$ là tỷ lệ đầu mút các cạnh gắn với cộng đồng $i$.
  2. Thông tin tương hỗ chuẩn hóa (Normalized Mutual Information - NMI): Đánh giá độ tương đồng giữa cấu trúc cộng đồng phát hiện được $\mathcal{C}$ và cấu trúc chuẩn thực tế $\mathcal{C}^*$, nhận giá trị trong đoạn $[0, 1]$: $$\text{NMI}(X, Y) = \frac{2 I(X; Y)}{H(X) + H(Y)}$$
  3. Thời gian thực thi (Execution Time): Tính bằng giây (s).

Nguồn dữ liệu thực nghiệm

Luận án sử dụng các tập dữ liệu mạng thực tế được chuẩn hóa từ các công trình nghiên cứu và kho dữ liệu mở [46, 60]:

Nhóm bài toán Tập dữ liệu thực nghiệm kiểm chứng
Phân cụm phổ (SCN) AdjNoun, Caltech36, Simmons81, Pages tvshow, Lehigh96
Lan truyền nhãn cải tiến (LPAMD) Page-food, Hamsterster, Hepth, Oregon_2, Email-Enron, Brightkite, Musae-wiki
Rút gọn đỉnh treo (LPARLV) Dolphin Group, Les Misérables Group, Wiki-Vote, Youtube, Wiki-Elec
Cộng đồng chồng chéo (COPA-BC) Zachary's Karate Club, Dolphin Group, Email-Eu-core, DBLP, Amazon, Youtube

Nội dung chính theo từng chương

Chương 1: Tổng quan về đồ thị mạng xã hội và bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội

Chương 1 thiết lập khung lý thuyết hoàn chỉnh về mạng xã hội và các phương pháp phát hiện cộng đồng:

  • Trình bày 5 đặc tính cốt lõi của mạng xã hội: Dựa vào người dùng (User-based), Tương tác (Interactive), Hướng đến cộng đồng (Community-driven), Các mối quan hệ (Relationships), và Cảm xúc về nội dung (Emotion over content).
  • Định nghĩa toán học về đồ thị đơn vô hướng/có hướng, ma trận kề $A$, vector bậc $K$, ma trận Laplace $L = D - A$, cấu trúc cộng đồng rời nhau và chồng chéo.
  • Minh họa bài toán cộng đồng thông qua mạng lưới các nhân vật trong tác phẩm Những người khốn khổ (Les Misérables) gồm 77 nút và 254 cạnh (theo thu thập của D. Knuth, 1993).
  • Phân tích chi tiết nguyên lý hoạt động, độ phức tạp và hạn chế của các giải thuật: Kernighan-Lin, BIRCH, k-Means, phân cụm phổ của Ulrike von Luxburg, Newman Greedy, Louvain, Simulated Annealing, Girvan-Newman, CONGA, CONGO, LPA, COPRA, OLP và các mô hình học sâu.
  • Xác lập cơ sở lựa chọn 3 hướng tiếp cận chính: phân cụm phổ giảm số chiều, cải tiến hàm cập nhật nhãn trong LPA, và xây dựng hệ số phụ thuộc cộng đồng cho mạng chồng chéo.

Chương 2: Phát hiện cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội

Chương 2 trình bày 3 thuật toán đề xuất để phát hiện cấu trúc cộng đồng rời nhau:

1. Thuật toán phân cụm phổ mới SCN (Spectral Clustering New)

  • Cơ sở: Sử dụng ma trận Laplace chuẩn hóa để giải bài toán Min-cut, giảm số chiều dữ liệu từ dạng ma trận đa chiều xuống không gian vector thực dựa trên các vector riêng (eigenvectors).
  • So sánh thực nghiệm: So sánh SCN với hai thuật toán phân cụm phổ là SpcSA (Tang F et al.) và UVonLB (Ulrike von Luxburg) trên các bộ dữ liệu AdjNoun, Caltech36, Simmons81, Pages tvshow, Lehigh96.
  • Kết quả ghi nhận: SCN đạt giá trị Modularity $Q$ và chỉ số NMI cao hơn, đồng thời rút ngắn thời gian tính toán so với UVonLB và SpcSA trên các mạng thử nghiệm.

2. Thuật toán lan truyền nhãn LPAMD (Label Propagation Algorithm with Modularity and Density)

  • Cơ sở: Khắc phục nhược điểm chọn nhãn ngẫu nhiên của LPA chuẩn bằng cách đề xuất hàm xác định nhãn $f_{Tmax}$. Hàm này kết hợp đồng thời tiêu chí tối ưu hóa độ đơn thể (Modularity $Q$) của Newman và mật độ liên kết cục bộ (Density) của cộng đồng tại mỗi bước lặp $t$.
  • So sánh thực nghiệm: So sánh LPAMD với LPA nguyên bản, CLPA (Controlled LPA) và NLPPC (New LPA with Pairwise Constraints) trên 7 tập dữ liệu: Page-food, Hamsterster, Hepth, Oregon_2, Email-Enron, Brightkite, Musae-wiki.
  • Kết quả ghi nhận: LPAMD triệt tiêu hiện tượng dao động nhãn, cải thiện tính ổn định, đạt hệ số Modularity và NMI cao hơn hẳn so với LPA truyền thống.

3. Thuật toán lan truyền nhãn kết hợp rút gọn đỉnh treo LPARLV (LPA Reduce Leaf Vertex)

  • Cơ sở: Xây dựng mô hình đồ thị rút gọn RLVG (Reduce Leaf Vertex Graph). Thuật toán thực hiện loại bỏ có điều kiện các đỉnh treo (đỉnh bậc 1 - Leaf vertices) trước khi chạy quy trình lan truyền nhãn, sau khi các cộng đồng lõi hội tụ sẽ thực hiện bước gán nhãn ngược trở lại cho các đỉnh treo.
  • So sánh thực nghiệm: So sánh LPARLV với thuật toán gốc LPA và thuật toán OLP (Matin Pirouz et al., 2018) trên các tập dữ liệu: Dolphin Group, Les Misérables, Wiki-Vote, Youtube, Wiki-Elec.
  • Kết quả ghi nhận: LPARLV giảm rõ rệt số lượng nút tham gia quá trình lặp lan truyền, từ đó giảm thời gian thực thi tổng thể trong khi chất lượng Modularity và NMI vẫn duy trì tương đương hoặc tốt hơn OLP và LPA.

Chương 3: Phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội

Chương 3 giải quyết bài toán phát hiện cộng đồng chồng chéo trên các mạng có quy mô lớn:

Thuật toán đề xuất COPA-BC (Community Overlap Propagation Algorithm Based on New Belonging Coefficient)

  • Cơ sở lý thuyết: Cải tiến thuật toán COPRA của Gregory. Luận án đề xuất hệ số thuộc về cộng đồng (Belonging Coefficient) dựa trên sự biến đổi của hệ số phân cụm của đỉnh. Hệ số này cho phép định lượng mức độ gắn kết của một nút với nhiều cộng đồng lân cận khác nhau một cách tự động.
  • Đặc tính kỹ thuật: Dựa vào hệ số thuộc về cộng đồng mới, COPA-BC tự động xác định ngưỡng số lượng cộng đồng mà một đỉnh có thể trực thuộc (tham số $\mu$), tránh việc phải gán cứng tham số tiên nghiệm như ở COPRA, đồng thời cắt giảm các bước cập nhật nhãn không cần thiết.
  • Độ phức tạp tính toán: Thuật toán đạt độ phức tạp thời gian xấp xỉ tuyến tính, phù hợp cho mạng quy mô lớn.
  • Kết quả thực nghiệm: Đánh giá trên 6 bộ dữ liệu thực tế: Karate Club, Dolphin Group, Email-Eu-core, DBLP, Amazon, Youtube. So sánh đối chuẩn trực tiếp với COPRA và IVIC-COPRA (Improved Vertex Imitation Coefficient based COPRA). Kết quả chỉ ra COPA-BC vượt trội về độ chính xác NMI, Modularity mở rộng cho cộng đồng chồng chéo và tối ưu thời gian thực thi.

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và học thuật

  1. Đề xuất thuật toán SCN: Thiết lập quy trình phân cụm phổ mới dựa trên việc giảm số chiều không gian vector riêng kết hợp tối ưu hàm Min-cut trên ma trận Laplace, giúp tăng tốc độ hội tụ trong bài toán cộng đồng rời nhau.
  2. Xây dựng hàm chọn nhãn $f_{Tmax}$ và thuật toán LPAMD: Đóng góp một nguyên lý gán nhãn mới cho họ thuật toán lan truyền nhãn, kết hợp hai độ đo cấu trúc Modularity và Mật độ (Density), giải quyết bài toán bất định và tối ưu hóa chất lượng phân cụm cục bộ.
  3. Đề xuất mô hình RLVG và thuật toán LPARLV: Cung cấp giải pháp kết hợp giữa kỹ thuật rút gọn đồ thị (loại bỏ đỉnh treo bậc 1) và lan truyền nhãn, làm giảm không gian tính toán đối với các mạng thưa có cấu trúc phân nhánh phức tạp.
  4. Đề xuất thuật toán COPA-BC: Xây dựng công thức tính hệ số thuộc về cộng đồng dựa trên hệ số phân cụm cải tiến của đỉnh, giải quyết bài toán xác định ngưỡng tham gia cộng đồng trong phân tích cộng đồng chồng chéo.

Đóng góp về mặt thực tiễn và ứng dụng

  • Cung cấp các công cụ thuật toán đã được kiểm chứng thực nghiệm có hiệu năng tính toán cao, áp dụng trực tiếp cho việc xử lý các đồ thị mạng thực tế có kích thước hàng chục nghìn đến hàng triệu nút/cạnh (như DBLP, Amazon, Youtube).
  • Hỗ trợ xây dựng các hệ thống gợi ý (Recommendation Engines) trong thương mại điện tử (Amazon, Shopee, Tiki) dựa trên việc gom nhóm người dùng có hành vi tương đồng; phân tích mạng lưới cộng tác khoa học; hỗ trợ khoanh vùng và kiểm soát lan truyền thông tin hoặc dịch bệnh.

Hạn chế và hướng nghiên cứu tiếp

Dựa trên phạm vi và nội dung được tác giả trình bày trong luận án, các hạn chế và hướng phát triển mở rộng bao gồm:

  • Hạn chế:
    • Các thuật toán đề xuất chủ yếu tập trung khai thác cấu trúc liên kết hình học (topo đồ thị), chưa tích hợp sâu các thông tin thuộc tính ngữ nghĩa phong phú của nút người dùng (như văn bản bài đăng, thông tin nhân khẩu học).
    • Nghiên cứu tập trung vào mô hình đồ thị tĩnh, chưa mở rộng toàn diện cho các mạng xã hội động (Dynamic Graphs) có cấu trúc đỉnh và cạnh biến đổi liên tục theo thời gian thực.
  • Hướng nghiên cứu tiếp:
    • Phát triển các kỹ thuật phát hiện cộng đồng kết hợp đồng thời thông tin liên kết mạng và thuộc tính nội dung đa phương tiện của các đỉnh.
    • Nghiên cứu mở rộng các thuật toán LPAMD và COPA-BC trên môi trường tính toán phân tán/song song để xử lý các đồ thị quy mô siêu lớn.
    • Áp dụng các thuật toán vào các bài toán phân tích mạng xã hội động và hệ thống gợi ý tương thích theo thời gian.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu cho các nhóm đối tượng:

  1. Nghiên cứu sinh, học viên cao học, giảng viên ngành Khoa học máy tính, Công nghệ thông tin và Khoa học dữ liệu: Tham khảo hệ thống tổng quan toàn diện về lý thuyết đồ thị mạng xã hội, các kỹ thuật phân cụm phổ, giải thuật lan truyền nhãn và các công thức toán học về độ đo trung tâm đồ thị tại Chương 1 và Chương 2.
  2. Các nhà nghiên cứu về Khai phá dữ liệu (Data Mining) và Mạng phức tạp (Complex Networks): Tham khảo phương pháp xây dựng hàm heuristic chọn nhãn $f_{Tmax}$, kỹ thuật rút gọn đỉnh treo RLVG, và cách thiết lập hệ số thuộc về cộng đồng từ hệ số phân cụm tại Chương 2 và Chương 3.
  3. Kỹ sư phát triển hệ thống tại các doanh nghiệp công nghệ: Ứng dụng thuật toán SCN, LPAMD, COPA-BC vào việc xây dựng mô đun phân khúc khách hàng, hệ thống phát hiện gian lận và thuật toán gợi ý liên kết bạn bè/sản phẩm.

Câu hỏi thường gặp

1. Thuật toán SCN trong Chương 2 sử dụng kỹ thuật nền tảng nào để giảm độ phức tạp tính toán?

Thuật toán SCN (Spectral Clustering New) sử dụng kỹ thuật phân cụm phổ (Spectral Clustering) dựa trên ma trận Laplace của đồ thị. SCN tiếp cận theo hướng giảm số chiều dữ liệu từ ma trận biểu diễn liên kết đa chiều ban đầu xuống không gian vector thực (chuỗi số thực) thông qua các vector riêng (eigenvectors), kết hợp ý tưởng tối ưu hóa hàm Min-cut để rút gọn khối lượng tính toán phát hiện cộng đồng rời nhau.

2. Hàm $f_{Tmax}$ trong thuật toán LPAMD được xây dựng dựa trên nguyên lý nào?

Hàm $f_{Tmax}$ được tác giả đề xuất để thay thế cơ chế chọn nhãn ngẫu nhiên của thuật toán LPA truyền thống. Hàm này xác định nhãn cập nhật cho mỗi đỉnh dựa trên sự kết hợp đồng thời giữa tiêu chí độ đơn thể Modularity ($Q$) của Newman và tiêu chí Mật độ cộng đồng (Density), đo lường tính năng cấu trúc nội bộ cộng đồng tại mỗi bước lặp $t$.

3. Nguyên lý giảm kích thước đồ thị của thuật toán LPARLV là gì?

Thuật toán LPARLV (LPA Reduce Leaf Vertex) thực hiện tiền xử lý đồ thị ban đầu bằng cách tách và loại bỏ các đỉnh treo (đỉnh có bậc bằng 1 - Leaf vertices) để tạo thành đồ thị rút gọn RLVG (Reduce Leaf Vertex Graph). Quá trình lan truyền nhãn LPA chỉ thực hiện trên đồ thị rút gọn RLVG có kích thước nhỏ hơn, sau đó nhãn của các đỉnh treo sẽ được gán ngược lại từ các đỉnh láng giềng sau khi thuật toán hội tụ.

4. Điểm khác biệt cốt lõi giữa thuật toán COPA-BC và thuật toán COPRA của Gregory là gì?

Thuật toán COPRA chuẩn yêu cầu phải gán trước tham số $\mu$ (số lượng cộng đồng tối đa mà một nút có thể tham gia), điều này gây khó khăn khi mạng không có thông tin tiên nghiệm. COPA-BC khắc phục nhược điểm này bằng cách sử dụng hệ số thuộc về cộng đồng (Belonging Coefficient) được phát triển từ hệ số phân cụm của đỉnh để tự động xác định ngưỡng và hạn chế số lần cập nhật nhãn trong quá trình lan truyền.

5. Những độ đo chuẩn nào được sử dụng xuyên suốt luận án để đánh giá các thuật toán đề xuất?

Luận án sử dụng 3 tiêu chuẩn định lượng chính để so sánh thực nghiệm trên các tập dữ liệu chuẩn: Độ đơn thể (Modularity $Q$), Chỉ số thông tin tương hỗ chuẩn hóa (Normalized Mutual Information - NMI), và Thời gian thực thi (Execution Time, tính bằng giây).

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Hiền Trinh đã giải quyết có hệ thống bài toán phát hiện cấu trúc cộng đồng rời nhau và chồng chéo trên đồ thị mạng xã hội thông qua 4 thuật toán đề xuất: SCN, LPAMD, LPARLV và COPA-BC. Các đóng góp tập trung vào việc tối ưu hóa ma trận Laplace trong phân cụm phổ, kết hợp độ đơn thể với mật độ liên kết trong lan truyền nhãn, rút gọn đỉnh treo đồ thị và xây dựng hệ số phụ thuộc cộng đồng dựa trên hệ số phân cụm cải tiến. Toàn bộ các đề xuất lý thuyết đều được kiểm chứng thực nghiệm trên các bộ dữ liệu thực tế chuẩn quy mô từ nhỏ đến lớn, khẳng định tính hiệu quả về chất lượng phân cụm và thời gian thực thi của các giải thuật.