Tổng quan về luận án

Trong kỷ nguyên chuyển đổi số và bùng nổ dữ liệu lớn, mạng xã hội (Social Networks - SN) đã phát triển theo cấp số nhân và trở thành hạ tầng kết nối thiết yếu trong đời sống kinh tế, chính trị và xã hội toàn cầu. Sự mở rộng quy mô của các nền tảng trực tuyến như Facebook, Twitter, Instagram hay LinkedIn đặt ra thách thức tính toán to lớn cho lĩnh vực Phân tích Mạng xã hội (Social Network Analysis - SNA). Trong đó, bài toán phát hiện cộng đồng (Community Detection) đóng vai trò then chốt nhằm khám phá cấu trúc vi mô và vĩ mô của mạng lưới, nhận diện các nhóm thực thể có mật độ liên kết nội bộ chặt chẽ và tương tác tương đồng.

Tuy nhiên, một rào cản căn bản trong văn hiến học thuật đương đại là: "Hầu hết các nghiên cứu tập trung giải quyết bài toán phát hiện cộng đồng trực tiếp trên đồ thị mà rất ít công trình nghiên cứu tính đến việc giảm thiểu không gian đỉnh và cạnh của đồ thị nhưng bảo toàn được các tính chất của đồ thị mạng xã hội ban đầu" (Nguyễn Xuân Dũng, 2021). Khi quy mô mạng lưới đạt mức hàng triệu đỉnh ($n = |V|$) và hàng tỷ cạnh ($m = |E|$), các thuật toán kinh điển dựa trên độ đo trung tâm trung gian (Betweenness Centrality) như Girvan-Newman với độ phức tạp $O(m^2n)$ hay thuật toán Brandes $O(mn)$ đều rơi vào điểm nghẽn nghiêm trọng về không gian và thời gian tính toán.

Luận án tiến sĩ kỹ thuật chuyên ngành Hệ thống thông tin (Mã số: 9.04) của nghiên cứu sinh Nguyễn Xuân Dũng, dưới sự hướng dẫn khoa học của PGS.TS Đoàn Văn Ban và TS. Đỗ Thị Bích Ngọc tại Học viện Công nghệ Bưu chính Viễn thông (2021), đã giải quyết trực diện khoảng trống nghiên cứu (research gap) mang tính then chốt này. Luận án đặt ra và giải quyết hai câu hỏi nghiên cứu cốt lõi:

  1. RQ1: Làm thế nào để xây dựng các thuật toán rút gọn không gian đồ thị mạng xã hội thông qua các lớp đỉnh tương đương mà vẫn bảo toàn chính xác giá trị độ đo trung tâm trung gian và động học lan truyền nhãn?
  2. RQ2: Làm thế nào để ứng dụng đồ thị rút gọn nhằm tăng tốc vượt bậc thời gian thực thi của các thuật toán phát hiện cộng đồng mà không làm suy giảm chất lượng phân hoạch theo các chuẩn đo mô đun hóa và lý thuyết thông tin?

Tương ứng với hai câu hỏi trên là hai giả thuyết nghiên cứu chính:

  • H1: Trên đồ thị mạng xã hội tồn tại các cấu trúc topo đặc thù tạo nên các lớp đỉnh treo, đỉnh sườn và đỉnh đồng nhất có cùng độ đo trung tâm trung gian hoặc cùng đặc trưng lan truyền nhãn; việc gộp các lớp này thành các đỉnh đại diện sẽ tạo ra đồ thị rút gọn có kích thước nhỏ hơn đáng kể nhưng bảo toàn nguyên vẹn tính chất cấu trúc gốc.
  • H2: Việc tính toán độ đo trung tâm trung gian và thực thi thuật toán phân cụm trên đồ thị rút gọn sẽ làm giảm độ phức tạp thời gian từ đa thức bậc cao xuống tiệm cận tuyến tính, trong khi bảo đảm độ đơn thể mô đun ($Q$) và độ đo tương hỗ chuẩn hóa ($NMI$) tương đương hoặc vượt trội so với các giải thuật tiên tiến trên thế giới.

Khung lý thuyết của luận án được xây dựng trên nền tảng Lý thuyết Đồ thị hình thức, Lý thuyết Tính trung tâm cấu trúc của Linton C. Freeman (1977, 1979), Mô hình Cấu trúc cộng đồng phân chia của Michelle Girvan & Mark E. J. Newman (2002), và Nguyên lý Động học Lan truyền nhãn của Usha N. Raghavan, Réka Albert & Soundar Kumara (2007). Phạm vi thực nghiệm của luận án bao quát từ các mạng lưới chuẩn kinh điển (Zachary Karate Club $n=34$, $m=78$; Santa Fe Institute $n=118$; Kite Network) đến các tập dữ liệu mạng xã hội quy mô lớn trích xuất từ kho dữ liệu SNAP (Stanford Large Network Dataset Collection).

Literature Review và Positioning

Lịch sử nghiên cứu phát hiện cộng đồng mạng xã hội trải qua nhiều thập kỷ phát triển với bốn dòng lý thuyết chủ đạo:

  1. Dòng thuật toán phân cụm truyền thống: Khởi nguồn từ thuật toán phân hoạch đồ thị nhị phân của Brian Kernighan & Shen Lin (1970) với hạn chế cố định kích thước phân vùng; kỹ thuật phân cụm phân cấp tích tụ Top-down BIRCH của Tian Zhang, Raghu Ramakrishnan & Miron Livny (1996); phân cụm dựa trên clique cực đại chồng lấp EAGLE của Huawei Shen et al. (2009); kỹ thuật phân cụm phân hoạch $K$-means và phân cụm phổ (Spectral Clustering) của Jianbo Shi & Jitendra Malik (2000), Andrew Ng, Michael Jordan & Yair Weiss (2002). Nhược điểm cố hữu của nhóm này là làm thất thoát thông tin cấu trúc vi mô và đòi hỏi tri thức tiên nghiệm về số lượng cộng đồng.
  2. Dòng thuật toán tối ưu hóa độ đo đơn thể ($Q$ - Modularity): Được dẫn dắt bởi công trình đột phá của Mark E. J. Newman (2004) với phương pháp tham lam tích tụ $O(n^2)$, sau đó được Vincent D. Blondel et al. (2008) tối ưu hóa thành thuật toán Louvain danh tiếng với độ phức tạp $O(n \log n)$. Bên cạnh đó là các hướng tiếp cận tối ưu hóa mở rộng (Extremal Optimisation) của Stefan Boettcher & Allon G. Percus (2001), Jordi Duch & Alex Arenas (2005) $O(n^2 \log n)$, cùng các giải thuật tiến hóa đa mục tiêu. Tranh luận lý thuyết lớn nhất ở nhóm này là "giới hạn phân giải" (resolution limit), khiến thuật toán bỏ qua các cộng đồng quy mô nhỏ trong mạng lưới khổng lồ.
  3. Dòng thuật toán dựa vào độ đo trung tâm trung gian (Betweenness Centrality): Dựa trên định đề của Linton C. Freeman (1977), Michelle Girvan & Mark E. J. Newman (2002) đề xuất thuật toán GN loại bỏ dần các cạnh có độ đo trung gian cao nhất nối giữa các cộng đồng. Ulrik Brandes (2001) đã tối ưu hóa việc tính toán khoảng cách trắc địa trên đồ thị phi chu trình có hướng (DAG) đưa độ phức tạp về $O(mn)$. Gần đây, nghiên cứu quốc tế tiêu biểu của Majid Arasteh & Alizadeh (2018) đã đề xuất thuật toán MAA đạt độ phức tạp $O(m^2)$ bằng cách tính toán tỷ lệ độ đo trung tâm và xóa đồng thời nhiều cạnh. Tuy nhiên, MAA vẫn phải thực thi trên toàn bộ không gian cạnh gốc.
  4. Dòng thuật toán dựa trên nguyên lý lan truyền nhãn (Label Propagation Algorithm - LPA): Usha N. Raghavan et al. (2007) thiết lập thuật toán LPA chạy trong thời gian gần tuyến tính $O(m+n)$. Các biến thể sau đó như LPAm của Michael J. Barber & John W. Clark (2009), LPAm+ của Xin Liu & Tsuyoshi Murata (2014), LPAp của Xiao-Dong Zhang et al. liên tục được cải tiến. Nghiên cứu quốc tế của Matin Pirouz et al. (2018) đề xuất giải thuật OLP (Optimized Label Propagation) đạt độ phức tạp $O(n)$ thông qua cơ chế chọn nhãn theo bậc đỉnh lân cận và kiểm soát điều kiện dừng hội tụ. Điểm yếu của dòng LPA là tính ngẫu nhiên cao và hiện tượng không hội tụ trên các đồ thị hai phía (bi-partite networks).

Luận án của NCS. Nguyễn Xuân Dũng định vị đột phá tại giao điểm giữa Lý thuyết Rút gọn đồ thị (Graph Reduction Theory) và Phân tích Cấu trúc Cộng đồng. Thay vì tìm kiếm cộng đồng trực tiếp trên không gian đồ thị nguyên bản như MAA (2018) hay OLP (2018), luận án thiết lập không gian đồ thị rút gọn đồng cấu về mặt độ đo, tạo ra bước nhảy vọt về hiệu năng tính toán.

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án đóng góp quan trọng vào sự phát triển của Lý thuyết Tính trung tâm Mạng lưới (Network Centrality Theory) và Mô hình Động học Lan truyền cấu trúc:

  • Mở rộng lý thuyết Betweenness Centrality của Freeman (1977): Luận án chứng minh một cách chặt chẽ về mặt toán học rằng độ đo trung tâm trung gian của một đỉnh $v$: $$C_B(v) = \sum_{s \neq v \neq t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}$$ có tính bất biến cấu trúc đối với các lớp đỉnh tương đương khi thực hiện phép co đồ thị (graph contraction). Luận án xác lập 3 mệnh đề hình thức chứng minh rằng việc gộp các đỉnh tương đương thành đỉnh đại diện không làm thay đổi tỷ lệ đường đi ngắn nhất $\frac{\sigma_{st}(v)}{\sigma_{st}}$ đi qua các đỉnh còn lại trong đồ thị mạng xã hội.
  • Phát triển định đề về sự bất biến nhãn (Label Invariance Proposition): Mở rộng nguyên lý lan truyền nhãn của Raghavan et al. (2007), chứng minh rằng các đỉnh có cùng cấu trúc lân cận tương đương sẽ luôn tiếp nhận cùng một nhãn trạng thái trong mọi bước lặp động học, do đó việc hợp nhất nhãn trước khi lan truyền bảo toàn nghiệm hội tụ của phân hoạch cộng đồng.

Khung phân tích độc đáo

Luận án xây dựng một khung phân tích tích hợp đa chiều, định nghĩa chính xác 3 lớp đỉnh tương đương trên đồ thị mạng xã hội vô hướng $G = (V, E)$:

  1. Lớp đỉnh treo tương đương (Leaf vertex equivalence classes): Tập các đỉnh có bậc $\deg(v) = 1$ cùng nối vào một đỉnh gốc $u$. Luận án chứng minh độ đo trung tâm trung gian của mọi đỉnh treo đều bằng 0 ($C_B(v) = 0$), vì chúng không nằm trên bất kỳ đường đi ngắn nhất nào nối giữa hai đỉnh bất kỳ khác trong mạng lưới.
  2. Lớp đỉnh sườn tương đương (Side vertex equivalence classes): Tập các đỉnh cùng liên kết với một đỉnh trung tâm $u$ đồng thời có các liên kết nội bộ giữa chúng nhưng không có liên kết nào ra bên ngoài. Các đỉnh này chia sẻ vai trò cầu nối phụ trợ cục bộ và có thể thu gọn thành một đỉnh sườn đại diện tổng hợp.
  3. Lớp đỉnh đồng nhất tương đương (Identical vertex equivalence classes): Tập các đỉnh có cùng tập hợp đỉnh lân cận hoàn toàn: $G(u) \setminus {u} = G(v) \setminus {v}$. Các đỉnh đồng nhất có vai trò kết nối đối xứng tuyệt đối trong toàn mạng.

Điều kiện biên (Boundary conditions): Khung phân tích phát huy hiệu quả tối đa trên các mạng xã hội có cấu trúc "thế giới nhỏ" (Small-world) và mạng phi tỷ lệ (Scale-free network) với hệ số phân cụm cao và phân bố bậc theo luật lũy thừa (Power-law), nơi xuất hiện dày đặc các cụm đỉnh treo và đỉnh sườn xung quanh các nút mạng trung tâm (hubs).

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Luận án tuân thủ chặt chẽ thế giới quan thực chứng (Positivism) kết hợp giữa phương pháp diễn dịch toán học hình thức (Formal Mathematical Deduction) và phương pháp kiểm chứng thực nghiệm đa cấp (Multi-level Empirical Validation). Quy trình nghiên cứu được thiết kế theo mô hình 2 pha khép kín:

[Đồ thị Mạng xã hội G = (V, E)]
   [PHA 1: GRAPH REDUCTION]
   [Đồ thị Rút gọn G* = (V*, E*)]  (|V*| << |V|, |E*| << |E|)
   [PHA 2: COMMUNITY DETECTION]
   [KHÔI PHỤC CỘNG ĐỒNG TOÀN VẸN TRÊN ĐỒ THỊ GỐC]
   [ĐÁNH GIÁ ĐỘ ĐO TOÀN DIỆN] (Modularity Q, NMI, F-measure, Runtime)
  • Pha 1: Rút gọn không gian topo đồ thị: Thiết kế giải thuật REG (Reduce Equivalence Graph) dựa trên độ đo trung tâm trung gian và giải thuật LREN (Label based Reduce Equivalence Nodes) dựa trên nguyên lý lan truyền nhãn để nén đồ thị $G = (V, E)$ thành $G^* = (V^, E^)$ với $|V^| \ll |V|$ và $|E^| \ll |E|$.
  • Pha 2: Khám phá cấu trúc cộng đồng và giải mã ngược: Phát triển giải thuật FBC (Fast Betweenness Centrality) và CDAB (Community Detection Algorithm based on Betweenness centrality) trên đồ thị rút gọn; đồng thời phát triển giải thuật LPAA (Label Propagation Algorithm on Abridged graph). Sau khi phân cụm hoàn tất trên $G^*$, thuật toán ánh xạ ngược nhãn cộng đồng về các đỉnh thành phần thuộc các lớp tương đương ban đầu.

Quy trình nghiên cứu rigorous và công thức toán học

Luận án thiết lập hệ thống công thức định lượng chuẩn xác nhằm mô tả mạng xã hội và đánh giá thuật toán:

  • Hệ số cố kết mạng (Density Cohesion - $D_G$): $$D_G = \frac{2k}{n(n-1)}$$ Trong đó $k = |E|$ là tổng số liên kết thực tế và $n = |V|$ là tổng số tác nhân. Luận án trích dẫn nguyên lý của John Scott (2000): "Khi hệ số cố kết của mạng càng lớn, mức độ gắn kết, sự chặt chẽ của các mối quan hệ giữa các thực thể, tác nhân trong mạng càng lớn, và do đó, sự tương trợ, hỗ trợ giữa các tác nhân cũng càng nhiều, càng hiệu quả hơn" (Nguyễn Xuân Dũng, 2021).
  • Hệ số trung tâm trực tiếp (Degree Centrality - $C_D(v)$): $C_D(v) = \deg(v)$.
  • Hệ số trung tâm lân cận (Closeness Centrality - $C_{Cl}(v)$): $$C_{Cl}(v) = \frac{1}{\sum_{t \in V \setminus {v}} d(v, t)}$$
  • Hệ số trung tâm trung gian (Betweenness Centrality - $C_B(v)$): $$C_B(v) = \sum_{s \neq v \neq t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}$$

Quá trình tính toán nhanh $C_B(v)$ trong giải thuật FBC được thực hiện thông qua việc duyệt đồ thị theo chiều rộng (Breadth-First Search - BFS) xây dựng đồ thị định hướng phi chu trình gốc $X$ ($DAG_X$), từ đó tích lũy độ phụ thuộc cặp đỉnh từ các nút lá ngược về gốc.

Data và phân tích thực nghiệm

Thực nghiệm được triển khai nghiêm ngặt trên môi trường máy tính tính toán hiệu năng cao, sử dụng ngôn ngữ lập trình C++/Python kết hợp thư viện phân tích mạng chuẩn quốc tế NetworKit và kho dữ liệu SNAP của Đại học Stanford. Luận án chia tập thực nghiệm thành hai nhóm dữ liệu:

  1. Nhóm dữ liệu mạng xã hội quy mô vừa và nhỏ có cấu trúc cộng đồng chuẩn (Ground Truth):
    • Đồ thị Câu lạc bộ Karate của Zachary ($n=34$, $m=78$).
    • Đồ thị Mạng lưới Viện Santa Fe ($n=118$ nhà khoa học).
    • Đồ thị Mạng xã hội Kite ($n=10$, $m=18$).
  2. Nhóm dữ liệu mạng xã hội quy mô lớn: Các mạng lưới cộng tác khoa học, mạng bạn bè trực tuyến từ Stanford SNAP với quy mô từ hàng chục nghìn đến hàng trăm nghìn đỉnh và cạnh.

Hệ thống chỉ số đánh giá đa chiều:

  • Độ đo đơn thể mô đun ($Q$ - Modularity): Đo lường mật độ liên kết nội bộ cộng đồng so với phân bố ngẫu nhiên kỳ vọng.
  • Độ tương hỗ chuẩn hóa ($NMI$ - Normalized Mutual Information): Đo mức độ trùng khớp giữa phân hoạch thuật toán tìm được và phân hoạch thực tế theo lý thuyết thông tin.
  • Độ đo $F\text{-measure}$: Đánh giá độ chính xác tổng hòa (Harmonic mean giữa Precision và Recall) của các cụm cộng đồng.
  • Thời gian thực thi ($T$ tính bằng giây/mili-giây): So sánh đối đầu trực tiếp giữa FBC với thuật toán Brandes gốc và NetworKit; so sánh CDAB với Girvan-Newman (GN) và MAA (2018); so sánh LPAA với LPA gốc và OLP (2018).

Phát hiện đột phá và implications

Những phát hiện then chốt

Kết quả thực nghiệm của luận án mang lại 4 phát hiện khoa học mang tính đột phá:

  1. Hiệu quả nén không gian đồ thị vượt trội của thuật toán REG và LREN: Thuật toán REG và LREN rút gọn từ 30% đến trên 60% số lượng đỉnh và cạnh trên các mạng xã hội thực tế mà không làm biến dạng cấu trúc cộng đồng. Đối với đồ thị Kite và Karate Club, tỷ lệ đỉnh treo và đỉnh sườn chiếm tới hơn 40%, cho phép co cụm không gian tính toán ngay từ pha tiền xử lý.
  2. Thuật toán FBC tạo bước nhảy vọt về tốc độ tính toán $C_B(v)$: So với thuật toán Brandes kinh điển, FBC giảm thời gian tính toán trung bình từ 2.5 đến 5.8 lần trên các tập dữ liệu thử nghiệm. Thời gian tính toán của FBC cạnh tranh trực tiếp và tiệm cận với tốc độ của thư viện tối ưu hóa mức hệ thống NetworKit viết bằng C++ đa luồng.
  3. Thuật toán CDAB phá vỡ giới hạn tính toán của họ giải thuật Girvan-Newman: Bằng việc thực hiện tính toán trên đồ thị rút gọn bởi REG và áp dụng FBC, CDAB giảm thời gian chạy từ mức $O(m^2n)$ xuống mức khả thi trên mạng lớn (giảm hàng chục lần thời gian chạy so với GN gốc). Khi đối sánh với thuật toán quốc tế MAA của Majid Arasteh & Alizadeh (2018), CDAB đạt chất lượng cộng đồng vượt trội thông qua độ đo đơn thể mô đun $Q$ cao hơn từ 0.03 đến 0.08 đơn vị, đồng thời ổn định hơn về số lượng cộng đồng phân hoạch.
  4. Thuật toán LPAA giải quyết triệt để sự mất ổn định của nguyên lý lan truyền nhãn: Luận án phát hiện hiện tượng phản trực giác (counter-intuitive): việc gộp các đỉnh tương đương theo LREN trước khi lan truyền nhãn giúp triệt tiêu hoàn toàn hiện tượng dao động nhãn không hội tụ trên các đồ thị chứa chu trình chẵn hoặc đồ thị hai phía. Khi so sánh với thuật toán OLP của Matin Pirouz et al. (2018), giải thuật LPAA đạt chỉ số $NMI$ và $F\text{-measure}$ cao hơn rõ rệt, chứng minh tính ưu việt của việc tiền cấu trúc hóa nhãn.

Implications đa chiều

  • Về mặt lý thuyết: Mở ra một hướng tiếp cận mới trong Lý thuyết Mạng phức tạp (Complex Networks Theory): tích hợp lý thuyết rút gọn đồ thị đại số vào các bài toán khai phá cấu trúc tô-pô. Đóng góp trực tiếp cho sự phát triển của lý thuyết phân cụm đồ thị quy mô cực lớn.
  • Về mặt phương pháp luận: Cung cấp bộ công cụ giải thuật hoàn chỉnh (REG, LREN, FBC, CDAB, LPAA) có thể chuyển giao và áp dụng phổ quát cho nhiều bài toán đồ thị khác như: tính toán độ đo Closeness, phân tích PageRank, tìm kiếm đường đi ngắn nhất nguồn đơn (SSSP).
  • Về mặt thực tiễn ứng dụng:
    • Quản trị Mạng xã hội và Kinh doanh số: Nhận diện chính xác cộng đồng khách hàng mục tiêu, tối ưu hóa hệ thống tư vấn/gợi ý sản phẩm (Recommender Systems), phát hiện các nhân tố có tầm ảnh hưởng (KOLs/Influencers) dựa trên độ đo trung tâm trung gian đã được tính toán nhanh.
    • An ninh mạng và Kiểm soát thông tin độc hại: Định vị các nhóm lan truyền tin giả, phát hiện sớm các chiến dịch truyền thông thao túng dư luận, hỗ trợ cơ quan quản lý đưa ra khuyến cáo kịp thời nhằm bảo đảm an ninh trật tự xã hội.
    • Y sinh học và Dịch tễ học: Áp dụng phát hiện các module chức năng trong mạng lưới tương tác protein-protein (PPI networks), phân tích cấu trúc mạng bệnh học Alzheimer và Parkinson (tương tự định hướng của Calderone), mô hình hóa và ngăn chặn chuỗi lây lan dịch bệnh trong cộng đồng dân cư.

Limitations và Future Research

Luận án thừa nhận một cách khách quan các giới hạn học thuật và điều kiện biên:

  1. Giới hạn về loại hình đồ thị: Luận án tập trung chủ yếu vào đồ thị đơn, vô hướng và không có trọng số. Việc mở rộng cho đồ thị có hướng (Directed Graphs) và đồ thị có trọng số phức tạp (Weighted Graphs) vẫn còn những thách thức nhất định trong việc định nghĩa các lớp đỉnh tương đương bảo toàn trọng số cạnh.
  2. Đặc trưng phụ thuộc cấu trúc mạng (Topology Sensitivity): Tỷ lệ rút gọn của thuật toán REG và LREN phụ thuộc vào mật độ xuất hiện của đỉnh treo, đỉnh sườn và đỉnh đồng nhất. Đối với các mạng lưới có cấu trúc siêu liên kết chính quy (Random Regular Graphs) hoặc đồ thị giãn nở (Expander Graphs) với hệ số cố kết $D_G$ rất cao nhưng không có cấu trúc phân cấp, tỷ lệ rút gọn sẽ bị suy giảm.
  3. Tính chất tĩnh của đồ thị (Static Graph Assumption): Nghiên cứu giải quyết bài toán trên đồ thị tĩnh tại một thời điểm. Trong khi đó, mạng xã hội thực tế là mạng động (Dynamic/Temporal Networks) với các đỉnh và cạnh liên tục xuất hiện và mất đi theo thời gian thực.

Chương trình nghiên cứu tương lai (Future Research Agenda):

  • Phát triển các phiên bản thuật toán rút gọn động (Incremental/Dynamic Graph Reduction) cho phép cập nhật tức thời các lớp đỉnh tương đương khi luồng dữ liệu mạng biến đổi mà không cần tính toán lại từ đầu.
  • Tích hợp kỹ thuật tính toán song song phân tán trên nền tảng Big Data (Apache Spark GraphX, GPU Computing với CUDA) để mở rộng khả năng xử lý của CDAB và LPAA lên mạng xã hội hàng tỷ thực thể.
  • Mở rộng khung phân tích để phát hiện các cộng đồng gối nhau (Overlapping Communities) và cộng đồng đa tầng (Multi-layer Networks).

Tác động và ảnh hưởng

Luận án tạo ra những giá trị tác động sâu rộng trên cả phương diện học thuật và kinh tế - xã hội:

  • Tác động học thuật (Academic Impact): Các công trình khoa học công bố từ luận án ([CT1], [CT2], [CT3], [CT4]) trên các tạp chí và hội thảo chuyên ngành trong nước và quốc tế khẳng định đóng góp tiên phong của tác giả. Luận án đặt nền móng cho các nghiên cứu tiếp theo về nén dữ liệu đồ thị trong phân tích dữ liệu lớn.
  • Chuyển đổi công nghiệp (Industry Transformation): Các doanh nghiệp cung cấp dịch vụ mạng xã hội, thương mại điện tử và viễn thông có thể tích hợp trực tiếp giải thuật REG-CDAB và LREN-LPAA vào hệ sinh thái quản trị dữ liệu lớn, giúp tiết kiệm hàng triệu USD chi phí máy chủ và điện năng tính toán định kỳ.
  • Lợi ích xã hội và hoạch định chính sách: Cung cấp cơ sở khoa học định lượng vững chắc cho các cơ quan quản lý nhà nước (Bộ Thông tin và Truyền thông, các đơn vị an ninh mạng) trong việc giám sát luồng thông tin trên không gian mạng, kịp thời ngăn chặn các cuộc khủng hoảng truyền thông và giữ vững an ninh thông tin quốc gia.

Đối tượng hưởng lợi

Nghiên cứu mang lại giá trị trực tiếp và thiết thực cho nhiều nhóm đối tượng trong hệ sinh thái khoa học và công nghệ:

  1. Nghiên cứu sinh và Giới học giả chuyên sâu: Tiếp cận một khung phương pháp luận hoàn chỉnh về rút gọn đồ thị bảo toàn độ đo, mở ra các đề tài nghiên cứu mở rộng trong lĩnh vực Lý thuyết Đồ thị và Phân tích Mạng phức tạp.
  2. Kỹ sư Khoa học Dữ liệu và R&D Công nghệ: Sở hữu các thuật toán mã nguồn mở hiệu năng cao (FBC, CDAB, LPAA) với độ phức tạp tiệm cận tuyến tính, dễ dàng cài đặt trong các hệ thống phân tích đồ thị thực tế.
  3. Doanh nghiệp Số và Nền tảng Mạng xã hội: Ứng dụng thuật toán để phân đoạn thị trường chính xác, tối ưu hóa các chiến dịch tiếp thị lan truyền (Viral Marketing) và gia tăng mức độ tương tác của người dùng.
  4. Cơ quan Quản lý Nhà nước và Hoạch định Chính sách: Sử dụng công cụ để phân tích cấu trúc mạng lưới xã hội, kiểm soát dịch bệnh truyền nhiễm và bảo vệ không gian mạng lành mạnh.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và đã mở rộng lý thuyết nào?

Đóng góp lý thuyết độc đáo nhất là việc thiết lập và chứng minh toán học tính bất biến của Độ đo Trung tâm Trung gian ($C_B(v)$) và Tính tương đương Động học Lan truyền nhãn trên các lớp đỉnh đặc thù (đỉnh treo, đỉnh sườn, đỉnh đồng nhất). Luận án đã mở rộng trực tiếp Lý thuyết Tính trung tâm cấu trúc của Linton C. Freeman (1977) và Mô hình Phân tích Cấu trúc Cộng đồng của Michelle Girvan & Mark E. J. Newman (2002) sang không gian đồ thị co đại số, tạo cơ sở lý thuyết vững chắc cho bài toán nén đồ thị bảo toàn tính chất phân cụm.

2. Sự đổi mới về phương pháp luận của luận án khi so sánh với ít nhất 2 nghiên cứu quốc tế tương đương?

So sánh với hai nghiên cứu quốc tế tiêu biểu:

  • So với thuật toán MAA của Majid Arasteh & Alizadeh (2018) ($O(m^2)$): MAA tìm cách xóa nhiều cạnh trên đồ thị gốc, trong khi giải thuật CDAB của luận án thực hiện nén không gian đỉnh và cạnh trước thông qua REG, giúp giảm bậc của bài toán từ không gian hàng trăm nghìn phần tử xuống không gian rút gọn, đạt thời gian thực thi nhanh hơn rõ rệt và độ đo $Q$ cao hơn từ 0.03 - 0.08 đơn vị.
  • So với thuật toán OLP của Matin Pirouz et al. (2018) ($O(n)$): OLP cải tiến việc chọn nhãn ngẫu nhiên trên đồ thị gốc nhưng vẫn chịu rủi ro phân mảnh nhãn trên đồ thị phức tạp; trong khi giải thuật LPAA của luận án tiền gộp các đỉnh tương đương qua LREN, triệt tiêu hoàn toàn hiện tượng dao động nhãn, cải thiện vượt bậc các chỉ số $NMI$ và $F\text{-measure}$.

3. Phát hiện nào trong luận án gây bất ngờ nhất và được chứng minh bằng dữ liệu thực nghiệm như thế nào?

Phát hiện bất ngờ nhất là: Việc rút gọn đồ thị không những không làm suy giảm chất lượng phát hiện cộng đồng mà trong nhiều trường hợp còn làm tăng độ chính xác ($Q$ và $NMI$) so với việc chạy thuật toán trên đồ thị gốc. Dữ liệu thực nghiệm trên mạng Kite và Zachary Karate Club chứng minh rằng việc loại bỏ sự nhiễu loạn của các đỉnh treo ($C_B=0$) và đỉnh sườn giúp thuật toán Girvan-Newman và Lan truyền nhãn xác định chính xác các cạnh cầu nối liên cụm thực sự mà không bị đánh lạc hướng bởi các kết nối thứ cấp cục bộ.

4. Luận án có cung cấp giao thức tái lập thực nghiệm (Replication Protocol) hoàn chỉnh không?

Luận án cung cấp đầy đủ và chi tiết giao thức tái lập thực nghiệm bao gồm: cấu trúc giả mã chi tiết của 5 thuật toán đề xuất (REG, LREN, FBC, CDAB, LPAA); mô tả chi tiết tập dữ liệu nguồn chuẩn hóa từ SNAP và các mạng kinh điển; định nghĩa toán học chính xác các tham số đầu vào/đầu ra; chỉ rõ công cụ phần mềm đối sánh (Brandes, NetworKit, GN, MAA, LPA, OLP); thiết lập môi trường phần cứng và phương thức đo đếm thời gian thực thi chính xác đến mili-giây.

5. Chương trình nghiên cứu 10 năm tiếp theo từ kết quả luận án được định hình như thế nào?

Chương trình nghiên cứu 10 năm tiếp theo tập trung vào 3 trụ cột:

  1. Nghiên cứu lý thuyết: Xây dựng khung lý thuyết rút gọn đồ thị động ngẫu nhiên (Dynamic Stochastic Graph Reduction) cho mạng siêu phức hợp đa chiều (Hypergraphs / Multi-layer Networks).
  2. Nghiên cứu giải thuật: Phát triển các thuật toán rút gọn đồ thị không mất mát (Lossless Graph Compression) tích hợp mạng nơ-ron đồ thị (Graph Neural Networks - GNNs) phục vụ học sâu tự giám sát (Self-supervised Graph Learning).
  3. Nghiên cứu ứng dụng: Triển khai hệ thống phân tích cộng đồng thời gian thực quy mô petabyte phục vụ giám sát không gian mạng quốc gia và dự báo dịch tễ học chính xác.

Kết luận

Công trình nghiên cứu luận án tiến sĩ của NCS. Nguyễn Xuân Dũng đã khẳng định những đóng góp học thuật và thực tiễn xuất sắc, giải quyết trọn vẹn điểm nghẽn tính toán trong phân tích mạng xã hội quy mô lớn:

  1. Đề xuất thuật toán REG: Rút gọn đồ thị dựa trên các lớp đỉnh tương đương theo độ đo trung tâm trung gian, cắt giảm từ 30% đến trên 60% kích thước không gian topo mà bảo toàn tuyệt đối giá trị trung tâm cấu trúc.
  2. Đề xuất thuật toán LREN: Rút gọn đồ thị dựa trên các lớp đỉnh tương đương theo nguyên lý lan truyền nhãn, khắc phục căn bản hiện tượng mất ổn định và không hội tụ nhãn.
  3. Phát triển thuật toán FBC: Tăng tốc độ tính toán Betweenness Centrality nhanh gấp 2.5 đến 5.8 lần so với thuật toán Brandes gốc, đạt hiệu năng tương đương các thư viện C++ mức thấp như NetworKit.
  4. Phát triển thuật toán CDAB: Phá vỡ giới hạn tính toán $O(m^2n)$ của họ thuật toán Girvan-Newman, vượt trội về cả thời gian thực thi và chất lượng phân hoạch $Q$ so với thuật toán quốc tế MAA (2018).
  5. Phát triển thuật toán LPAA: Hoàn thiện giải thuật lan truyền nhãn trên đồ thị rút gọn với thời gian tiệm cận tuyến tính, nâng cao rõ rệt độ chính xác theo các thang đo $NMI$ và $F\text{-measure}$ so với thuật toán OLP (2018).
  6. Xác lập hệ phương pháp luận nén đồ thị tiên phong: Mở ra phân ngành nghiên cứu giao thoa giữa Lý thuyết Rút gọn đồ thị và Khai phá dữ liệu lớn, để lại giá trị ứng dụng lâu dài cho khoa học tính toán và công nghệ thông tin nước nhà.