Chương 1 Kiến thức chuẩn bị 1. Các đại lượng cơ bản của đồ thị Đồ thị G = (V, E) được định nghĩa bởi tập đỉnh V và tập cạnh E. Trong trường hợp đồ thị đơn, giữa hai đỉnh i và j thuộc V chỉ có duy nhất một cạnh nối trực tiếp. Ngoài ra, những cạnh có điểm đầu và điểm cuối trùng nhau, tức là xuất phát và kết thúc tại cùng một đỉnh, được gọi là khuyên.
Các khái niệm cơ bản dưới đây sẽ được sử dụng xuyên suốt trong luận văn này. Đồ thị có hướng G = (V, E) là một bộ ba gồm một tập đỉnh V, một tập cạnh E, và một hàm ánh xạ mỗi cạnh thành một cặp đỉnh có thứ tự. Đỉnh đầu tiên của cặp có thứ tự là đuôi của cạnh, và đỉnh thứ hai là đầu; cùng nhau, hai đỉnh tạo thành điểm đầu cuối. Một cạnh được xác định là một cạnh từ đuôi của nó đến đầu của nó.
Những cạnh trong đồ thị có hướng được gọi là cạnh có hướng, có thể được biểu diễn bởi những đường thẳng có mũi tên chỉ hướng. Trong khi đó, đồ thị vô hướng được xác định khi cạnh không có hướng, tức mối quan hệ hai chiều, từ đây ta có định nghĩa của đồ thị vô hướng như sau: Định nghĩa 1. Một đồ thị vô hướng G = (V, E) là một bộ ba gồm một tập đỉnh V, một tập cạnh E, và một hàm ánh xạ mỗi cạnh tới một cặp đỉnh không có thứ tự. Ma trận kề là một công cụ toán học phổ biến dùng để biểu diễn đồ thị.
Nó cung cấp cách thức mô tả sự kết nối giữa các đỉnh trong đồ thị thông qua các 4 5 cạnh. Cụ thể, ma trận kề của một đồ thị được định nghĩa như sau: Định nghĩa 1. Ma trận kề A của đồ thị đơn G = (V, E) là một ma trận vuông kích thước n × n, trong đó n = |V | là số đỉnh của đồ thị. Các phần tử của ma trận A được xác định như sau: 1, nếu có cạnh từ đỉnh i đến đỉnh j, ∀i, j ∈ 1,.
Aij = 0, trong trường hợp ngược lại. Ngoài đồ thị đơn, trong thực tế tồn tại nhiều đồ thị với sự liên kết giữa các đỉnh không chỉ là các cạnh đơn mà có thể nhiều cạnh hoặc trọng số của cạnh, đồ thị có trọng số được định nghĩa như sau: Định nghĩa 1. Một đồ thị Gw có trọng số được biểu diễn thông qua 3 đại lượng Gw = (V, E, W ) trong đó W là ma trận biểu diễn trọng số cho mỗi cạnh với Wij là trọng số của cạnh nối giữa hai đỉnh i, j. Trong lý thuyết đồ thị, một khái niệm quan trọng là bậc của một đỉnh, thể hiện số lượng kết nối của đỉnh đó với các đỉnh khác trong đồ thị.
Để hiểu rõ hơn về mức độ liên kết của các đỉnh trong đồ thị, ta định nghĩa bậc của đỉnh như sau: Định nghĩa 1. Bậc của đỉnh i trong đồ thị G được tính dựa trên tổng các trọng số của các cạnh nối từ đỉnh i đến các đỉnh khác trong đồ thị. Đối với từng loại đồ thị, bậc của mỗi đỉnh được xác định cụ thể như sau: • Đồ thị vô hướng, không trọng số: Bậc của đỉnh i, ký hiệu là di , được tính bằng tổng số cạnh nối đến đỉnh i: n n di = ∑ Aij = ∑ A ji , j =1 j =1 trong đó Aij là phần tử của ma trận kề A, biểu thị sự tồn tại của cạnh giữa hai đỉnh i và j. • Đồ thị có hướng, không trọng số: Do cạnh có hướng, bậc của đỉnh i được chia thành hai loại: 6 – Bậc vào din i : là tổng số cạnh đi vào đỉnh i, n i = ∑ A ji , din j =1 – Bậc ra diout : là tổng số cạnh đi ra từ đỉnh i, n diout = ∑ Aij.
j =1 • Đồ thị có trọng số: Bậc của đỉnh i được tính tương tự, nhưng thay các giá trị Aij bằng trọng số của cạnh giữa hai đỉnh i và j. Cụ thể: n di = ∑ wij , j =1 trong đó wij là trọng số của cạnh giữa i và j. Từ đó, chúng ta sẽ định nghĩa ma trận bậc cho đồ thị vô hướng và có hướng như sau: Định nghĩa 1. • Trong đồ thị vô hướng, ma trận bậc D là ma trận đường chéo, trong đó phần tử Dii là bậc của đỉnh i, tức Dii = di.
dn • Trong đồ thị có hướng, ma trận bậc đi ra D out là một ma trận đường chéo, trong đó phần tử Diiout là bậc đi ra của đỉnh i, tức là Diiout = diout. dnout 7 Kể từ thời điểm này trong luận văn, với trường hợp đồ thị có hướng, ma trận bậc sẽ được hiểu là ma trận bậc đi ra. Tiếp theo, chúng tôi sẽ giới thiệu về ma trận Laplacian. Ma trận Laplacian trong đồ thị là một công cụ quan trọng trong lý thuyết đồ thị, giúp biểu diễn các thuộc tính kết nối và cấu trúc của đồ thị, từ đó hỗ trợ phân tích các đặc điểm như tính liên thông và phát hiện cộng đồng trong đồ thị.
Ma trận Laplacian L của đồ thị G được đinh nghĩa là: L = D − A, (1.3) trong đó A, D lần lượt là ma trận kề và ma trận bậc của đồ thị G. Quá trình ngẫu nhiên trên đồ thị Bước đi ngẫu nhiên trên đồ thị là một quá trình ngẫu nhiên mô tả sự di chuyển trên đồ thị, bắt đầu từ một đỉnh ban đầu, ở mỗi bước, ta chọn ngẫu nhiên một cạnh nối với đỉnh hiện tại và di chuyển đến đỉnh ở đầu kia của cạnh đó, sau đó tiếp tục lặp lại quá trình này. Từ đó, chúng ta có thể định nghĩa về ma trận xác suất chuyển trên đồ thị sau như sau (áp dụng cho cả đồ thị vô hướng và có hướng): Định nghĩa 1. Đồ thị G = (V, E) có ma trận kề A = ( Aij )n×n và ma trận bậc D, gọi Pij là xác suất di chuyển từ đỉnh i sang đỉnh j, xác suất này được xác định như sau: Aij Aij Pij = = n (1.1) Dii ∑ j=1 Aij Công thức trên có thể viết dưới dạng ma trận: P = D −1 A = ( Pij )n×n .2) Từ công thức 1.1, ta kí hiệu Pijt là xác suất đỉnh i di chuyển tới đỉnh j sau t bước; dưới dạng ma trận, ta có Pt = ( Pijt )n×n là ma trận xác suất chuyển với độ dài t bước.
8 Ta thấy, xác suất chuyển là xác suất có điều kiện khi từ đỉnh hiện tại, ta chuyển sang đỉnh khác với xác suất được tính dựa trên bậc của đỉnh hiện tại. Bên cạnh xác suất chuyển này, xác suất để bước đi rơi vào các đỉnh tại thời điểm ban đầu và sau t bước cũng được quan tâm. Xem xét thời điểm ban đầu, bước đi có thể bắt đầu từ đỉnh i với xác suất pi , bắt đầu tại đỉnh j với xác suất p j ,. Từ đây ta kí hiệu xác suất để sau t bước, bước đi rơi vào một đỉnh i cụ thể (t) (t) (t) (t) là pi (đặt p(0) = p, tổng hợp lại mọi đỉnh, ta được p(t) = ( p1 , p2 , ., pn ) là vector xác suất.
Dễ thấy n ∑ pi (t) = 1, (1.4) j hay p(t) = p(t−1) P dưới dạng ma trận. Từ đây, ta biểu diễn được p(t) theo p(0) và Pt : p ( t ) = p (0) P t , (1.5) Một trong các đại lượng quan trọng thể hiện xác suất bước đi ngẫu nhiên rơi vào các đỉnh chính là trạng thái dừng.6) t→∞ Đặc biệt với mọi cặp trạng thái i, j, ta cũng thu được xác suất chuyển giới hạn: lim Pijt = π j .7) t→∞ Nếu phân phối π tồn tại thì sẽ là nghiệm của phương trình: π = πP, (1.8) Để trạng thái dừng của bước đi ngẫu nhiên trên đồ thị tồn tại, cần thỏa mãn một số điều kiện cụ thể [6]: 9 • Đối với đồ thị vô hướng: Đồ thị phải liên thông, nghĩa là từ bất kỳ đỉnh nào cũng có thể đi đến mọi đỉnh khác. Hơn nữa, một điều kiện quan trọng là ước chung lớn nhất (UCLN) của số bước để một đỉnh i quay lại chính nó phải bằng 1, tức là UCLN ({t|t ∈ N∗ , Piit > 0}) = 1. Điều kiện này ngăn quá trình bước đi ngẫu nhiên rơi vào một chu kỳ cố định có độ dài lớn hơn 1, giúp đảm bảo rằng trạng thái dừng có thể đạt được với mọi t đủ lớn.
• Đối với đồ thị có hướng: Đồ thị cần liên thông mạnh, tức là có thể di chuyển từ mọi đỉnh đến tất cả các đỉnh khác theo hướng của các cạnh. Tương tự, UCLN của số bước để một đỉnh i quay lại chính nó cũng phải bằng 1, tức là UCLN ({t|t ∈ N∗ , Piit > 0}) = 1. Mạng và tìm kiếm cộng đồng mạng Mạng là cấu trúc có thể được hình dung một cách cơ bản nhất như một tập hợp các điểm được nối với nhau thành từng cặp bằng các đường thẳng. Trong ngôn ngữ toán học, các điểm này được gọi là đỉnh (hoặc nút), và các đường nối giữa chúng được gọi là cạnh.
Trong bối cảnh cấu trúc dữ liệu và thuật toán, đồ thị đại diện cho một cấu trúc dữ liệu phi tuyến, mô tả mối quan hệ giữa các đỉnh thông qua tập hợp các cạnh. Đồ thị được ứng dụng rộng rãi trong thực tế, đặc biệt trong nghiên cứu mối quan hệ giữa các đối tượng như mạng xã hội, mạng protein, và mạng lưới sân bay. Ví dụ, mạng Internet có thể được xem như một tập hợp các máy tính kết nối với nhau, trong khi xã hội con người là một mạng lưới các cá nhân gắn kết qua các mối quan hệ. Nghiên cứu đồ thị có thể tập trung vào đặc điểm của các đỉnh, như hoạt động của máy tính, hoặc các cạnh, như cách thức tương tác diễn ra.
Một khía cạnh quan trọng khác là cấu trúc kết nối giữa các đỉnh, quyết định đến đặc tính của mạng, khả năng lan truyền thông tin, tính bền vững trước các tấn công, và sự hình thành của các cấu trúc con. Cộng đồng mạng: là nhóm các đỉnh có liên kết chặt chẽ với nhau hơn khi so với các đỉnh bên ngoài. Những mối quan hệ này có thể được đo lường qua 10 các chỉ số như số đỉnh chung, số cạnh kết nối, số đường đi ngắn nhất, hoặc độ tương đồng dựa trên các đặc tính cụ thể.