Chương 1 Kiến thức chuẩn bị 1. Sơ lược về đồ thị có hướng 1. Các khái niệm cơ bản Định nghĩa 1. Một đồ thị có hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là một tập con của tích Đề các V × V, tức là E là một quan hệ hai ngôi trên V.
Các phần tử của V được gọi là các đỉnh, còn các phần tử của E được gọi là các cạnh (cung) của đồ thị có hướng G. Cụ thể hơn, nếu (i, j) ∈ E thì (i, j) được gọi là cạnh (cung) của G với đỉnh đầu là i, đỉnh cuối là j và có hướng đi từ i tới j. Giả sử G = (V, E) là một đồ thị có hướng. Khi đó i và j cũng được gọi là kề nhau.
Hai cạnh bất kỳ của G được gọi là kề nhau nếu chúng có đỉnh chung. Mỗi đồ thị G = (V, E) có thể được biểu diễn bằng ma trận kề A của nó. Ma trận kề A của một đồ thị G = (V, E) là một ma trận cỡ Hình 1.1: Đồ thị có hướng 3 4 |V | × |V |, với 1, nếu (i, j) ∈ E, ∀ i, j ∈ 1,. , |V |; Aij = 0, trong trường hợp ngược lại.
Giả sử G = (V, E) là một đồ thị có hướng và v ∈ V. Khi đó, diout =| N + (i )| được gọi là bậc đi ra, còn din − i =| N (i )| được gọi là bậc đi vào của đỉnh i. Ma trận bậc của đồ thị có hướng được định nghĩa là D = Dout = diag[d1out ,. Giả sử G = (V, E) là một đồ thị có hướng.
Một hành trình có hướng trong G là một dãy i0 e1 i1 e2 i2. en in sao cho với mọi m = 0, 1,. , n, im ∈ V, còn với mọi m = 1, 2,. , n, em ∈ E và em = (im−1 , im ).
Khi đó n được gọi là độ dài, đỉnh i0 được gọi là đỉnh đầu, còn in được gọi là đỉnh cuối của hành trình có hướng trên. Một hành trình có hướng, trong đó các đỉnh đều khác nhau được gọi là một đường có hướng. Trong đồ thị có hướng, có nhiều định nghĩa về tính liên thông: liên thông mạnh, liên thông, và liên thông yếu. Trong luận văn này, chúng ta chỉ cần quan tâm đến định nghĩa về liên thông mạnh.
Đồ thị có hướng G = (V, E) được gọi là liên thông mạnh, nếu với hai đỉnh bất kỳ khác nhau i và j, luôn tồn tại cả hành trình có hướng với đỉnh đầu là i và đỉnh cuối là j và hành trình có hướng với đỉnh đầu là j và đỉnh cuối là i. Bước đi ngẫu nhiên trên đồ thị có hướng Cho G = (V, E) là một đồ thị có hướng n đỉnh, A = [ Aij ]i,j=1,n , là ma trận kề của G. Một bước đi ngẫu nhiên trên đồ thị có hướng là quá trình di chuyển từ một đỉnh đến các đỉnh kề đi ra với nó một cách ngẫu nhiên với xác suất như nhau. Với mỗi Aij đỉnh i có bậc đi ra diout , xác suất chuyển từ đỉnh i đến đỉnh j là pij = out.
Từ đó ta di có định nghĩa ma trận chuyển xác suất P của bước đi ngẫu nhiên là P = pij i,j=1,n 5 (chúng ta có thể xem trong [6]). Định nghĩa Pt là ma trận mà mỗi phần tử Pt ij là xác suất đi từ i đến j sau t bước. Với G là đồ thị liên thông mạnh, xét bước đi ngẫu nhiên không tuần hoàn trên G, nghĩa là ước số chung lớn nhất của độ dài các đường đi từ mọi đỉnh quay lại chính nó bằng 1 (xem [7]), theo định lý về sự hội tụ trong [8], ma trận chuyển xác suất P thỏa mãn limt→∞ Pt = P∞ , với ( P∞ )ij = ϕj là thành phần thứ j của phân phối dừng ϕ = (ϕ1 , ϕ2 ,. Điều này có nghĩa là, khi độ dài của bước đi ngẫu nhiên (t) tiến đến vô cùng, ma trận chuyển xác suất P sẽ hội tụ về một ma trận giới hạn P∞ , trong đó mỗi phần tử ( P∞ )ij của ma trận giới hạn này bằng ϕj , là phân phối dừng tại đỉnh j.
√ √ Đối với một đồ thị có hướng liên thông mạnh G, đặt Φ1/2 = diag [ ϕ1 ,. Trong [9], các tác giả đã định nghĩa ma trận Laplacian chuẩn hóa cho đồ thị có hướng (gọi tắt là Diplacian) Γ = Γij cho đồ thị G như sau: Định nghĩa 1. Ma trận Diplacian Γ được định nghĩa như sau: Γ = Φ1/2 ( I − P)Φ−1/2. Với 1 ≤ i, j ≤ n, 1 − pii khi i = j; Γij = −ϕ1/2 pij ϕ−1/2 khi (i, j) ∈ E; i j 0 trong các trường hợp còn lại.
Phân tích giá trị kỳ dị (SVD) Định nghĩa 1. Với m và n là các số tự nhiên bất kì, m không nhất thiết lớn hơn n. Xét ma trận A ∈ Cm×n , một phép phân tích giá trị kì dị (SVD) của A là phân tích: A = UΣV T với U ∈ Cm × m là ma trận unita; V ∈ Cn × n là ma trận unita; Σ ∈ Rm × n là ma trận đường chéo. 6 các phần tử đường chéo σj của ma trận Σ không âm và được sắp xếp theo thứ tự không tăng, tức là: σ1 ≥ σ2 ≥ · · · ≥ σp ≥ 0, p = min{m, n}.
Ta có nhận xét rằng ma trận đường chéo Σ có cùng kích thước với A, A không nhất thiết là ma trận vuông, còn U và V luôn là các ma trận vuông unita. Định lý sau đây khẳng định rằng mọi ma trận đều có phân tích SVD. Mọi ma trận A ∈ Cm×n đều có phân tích giá trị kỳ dị (SVD). Các giá trị kỳ dị σj j=1,p (p = min{m, n}) được xác định duy nhất, và nếu A là ma trận vuông và các σj là các giá trị khác nhau, thì các vector kỳ dị trái và phải u j j=1,m và v j j=1,n cũng được xác định duy nhất bỏ qua sai khác về dấu phức (sai khác nhau một số phức có module bằng 1).
Cộng đồng mạng và tìm kiếm cộng đồng mạng Mạng là một tập hợp các đối tượng, trong đó các đối tượng được kết nối với nhau bởi các liên kết. Các đối tượng được kết nối thường được gọi là đỉnh (hoặc nút), và các kết nối giữa chúng được gọi là cạnh (hoặc liên kết). Mạng có thể được sử dụng để mô hình hoá các hệ thống trong đời sống thực, bao gồm mạng xã hội, hệ thống giao thông, mạng sinh học, và hệ thống thông tin liên lạc. Mạng có thể là vô hướng hoặc có hướng, và thường được biểu diễn bằng đồ thị.
Trong luận văn này, mạng và đồ thị là các từ sử dụng thay thế tương đương cho nhau. Trong mạng có hướng, các cạnh có hướng, chỉ ra mối quan hệ một chiều giữa hai nút. Mỗi liên kết là một cặp có thứ tự, hướng từ một nút (nguồn) đến nút khác (đích). Mạng có hướng được sử dụng để biểu diễn các hệ thống trong đó hướng của tương tác là quan trọng, chẳng hạn như các liên kết trang web (trong đó một trang liên kết đến một trang khác), mạng trích dẫn (một bài báo trích dẫn một bài khác), mối quan hệ săn mồi trong hệ sinh thái, liên kết người theo dõi trên một số mạng xã hội như Instagram, bản đồ các đường truyền trong một trận đấu bóng đá.
Tính có hướng của mạng là một đặc trưng có nhiều ứng dụng trong thực tế [5]. Một cụm hay một cộng đồng trong một mạng là một tập hợp các đỉnh (nút) có những đặc trưng tương tự hoặc giống nhau, hay gần nhau về mặt khoảng cách. Tìm kiếm cộng đồng mạng là bài toán phân chia các đỉnh một mạng (thường là 7 Hình 1.2: Mạng lưới trích dẫn giữa các blog chính trị ở Mỹ trước cuộc bầu cử 2004. một mạng lớn) thành nhiều cụm đỉnh nhỏ hơn, sao cho các đỉnh trong cùng một cụm có có những đặc trưng tương tự hoặc giống nhau, hay gần nhau về mặt khoảng cách.
Nhờ thế, chúng ta có thể tìm hiểu cấu trúc của một mạng lớn bằng cách xem xét sự liên kết giữa các cụm này, thay vì phải xem xét từng đỉnh một cách riêng lẻ. Sự đơn giản hóa này giúp chúng ta dễ dàng nắm bắt và hiểu rõ các quy luật hoặc mô hình quan trọng trong mạng [11].2 là minh hoạ của mạng có hướng các blog chính trị ở Mỹ trước cuộc bầu cử 2004 [12]. Mạng này có 1490 đỉnh, 19090 cạnh, được phân thành hai cộng đồng lớn, mỗi cộng đồng đại diện cho một quan điểm chính trị chủ đạo trong truyền thống chính trị Hoa Kỳ: tự do cánh tả (màu xanh- màu truyền thống của Đảng Dân chủ) và bảo thủ cánh hữu (màu đỏ- màu truyền thống của Đảng Cộng hòa). Sự phân cụm của mạng này cho thấy truyền thống chính trị lưỡng cực tại Mỹ, ngày càng thể hiện rõ rệt hơn qua các cuộc bầu cử trong thế kỷ 21.
Thuật toán K-Means Thuật toán K-Means là một thuật toán dùng để phân cụm N điểm dữ liệu trong một không gian I chiều thành K cụm. Mỗi cụm được đại diện bởi một vector m(k) , được gọi là tâm của cụm. n o Các điểm dữ liệu được ký hiệu là x(n). Mỗi vector x có dạng x = ( x1 , x2 ,.
n=1,N Giả sử rằng trên không gian các điểm dữ liệu có thể định nghĩa một hàm khoảng 8 cách, chẳng hạn khoảng cách Euclid: 1 2∑ d(x, y) = ( x i − y i )2 i Đầu tiên, Thuật toán K-Means khởi tạo K tâm cụm. Việc khởi tạo tâm có thể thực hiện theo nhiều cách, trong đó cách đơn giản nhất là chọn ngẫu nhiên K điểm từ tập dữ liệu để làm tâm. Sau đó, Thuật toán K-Means lặp lại hai bước chính. Trong bước gán nhãn, mỗi điểm dữ liệu x(n) được gán vào cụm có tâm gần nhất.
Trong bước cập nhật, các tâm cụm được điều chỉnh lại sao cho tâm mới là trung bình của các điểm dữ liệu trong mỗi cụm đã được phân hoạch ở bước trước. Dưới đây là thuật toán K-Means [1]: Thuật toán 1: Thuật toán K-Means 1 Bước khởi tạo: Chọn ngẫu nhiên K tâm cụm {m(k) }kK=1 .