Chương 1: Cơ sở lý thuyết về đồ thị và mạng xã hội Nội dung cơ bản của chương: Trình bày một số kiến thức tổng quan liên quan đến nội dung đề tài. Chương 2: Một số thuật toán nhanh tìm k-core trong mạng xã hội Tìm hiểu một số thuật toán tìm Cores trong phân tích mạng xã hội, mổ tả thuật toán, đánh giá độ phức tạp của thuật toán. Ứng dụng của core trong phân tích mạng xã hội c 4 Nội dung cơ bản trong chương này: Tìm hiểu một số ứng dụng của core trong phân tích mạng xã hội và xây dựng chương trình ứng dụng. Phần kết luận: Trình bày kết quả mà luận văn đạt được và phương hướng đề xuất.
CƠ SỞ LÝ THUYẾT ĐỒ THỊ VÀ MẠNG XÃ HỘI Phân tích mạng xã hội được xem là các mối quan hệ xã hội về lý thuyết mạng lưới bao gồm các nút và các mối quan hệ (còn gọi là các cạnh, liên kết, hoặc kết nối). Nút là các cá nhân trong mạng lưới, và các mối quan hệ là những mối liên kết với các cá nhân. Kết quả là các cấu trúc dựa trên đồ thị rất phức tạp. Nội dung cơ bản của chương trình bày các khái niệm cơ sở về đồ thị, các loại đồ thị, một số khái niệm về phân tích mạng xã hội cũng như khái niệm về thuật toán tìm core để làm tiền đề trình bày trong chương 2 và 3.
Một số khái niệm liên quan đến đồ thị Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều những ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế kỷ XVIII bởi nhà toán học người Thụy Sỹ - Leonhard Euler 1. Định nghĩa đồ thị [1] Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối giữa các đỉnh đó. Người ta thường ký hiệu đồ thị G = (V, E), V là tập các đỉnh (Verterx), E là tập ác cạnh (Edge).
Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh của V. Một số hình ảnh về đồ thị: Sơ đồ mạng giao thông Sơ đồ mạng Internet Sơ đồ mạng xã hội Hình 1.1: Ví dụ về mô hình đồ thị [1] 1. Các loại đồ thị Có thể phân loại đồ thị ở đặc tính và số lượng của tập các cạnh E: Cho đồ thị G = (V, E). Định nghĩa một cách hình thức.
G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1 c 6 cạnh trong E nối từ u tới v. G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v (Hiển nhiên đơn đồ thị cũng là đa đồ thị). G được gọi là đồ thị vô hướng nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự (u, v) và (v, u).
G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v tới đỉnh u. Nói cách khác tập E gồm các cặp (u, v) có tính thứ tự: (u, v) ≠ (v, u). Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, v bất kỳ tương đương với hai cung (u, v) và (v, u).
Đồ thị Đơn đồ thị Đa đồ thị 2 4 2 4 Có hướng 1 6 1 6 3 5 3 5 2 4 2 4 Vô hướng 1 6 1 6 3 5 3 5 Hình 1.2: Phân loại về đồ thị [1] Một số dạng đồ thị đơn vô hướng đặc biệt: Đồ thị đầy đủ Kn (compelte graph): Là đơn đồ thị vô hướng mà giữa hai đỉnh bất kì của nó luôn tồn tại cạnh nối. Đồ thị vòng Cn (cycle graph): Là đơn đồ thị vô hướng G = (V, E) với tập đỉnh V + {1, 2, 3,…, n} và tập cạnh E = {(1, 2); (2, 3); …. Đồ thị bánh xe Wn (wheel graph): là đơn đồ thị vô hướng thu được từ đồ c 7 thị Cn-1 bằng cách thêm một đỉnh n nối với n-1 đỉnh của đồ thị Cn-1. Đồ thị hai phía Km, n (bipartite graph): là đồ thị có tập đỉnh phân hoạch thành hai tập con không giao nhau V=X Y sao cho mọi cạnh nối một đỉnh thuộc X với một đỉnh thuộc Y.3: Các dạng đồ thị đặc biệt [1] 1.
Các khái niệm liên quan Cho đồ thị G = (V, E): trong đó có các tập đỉnh V = {1, 2, 3, ., n} và các tập cạnh E = {e1, e2, …, en}. là một cấu trúc rời rạc, tức là các tập V và E hoặc là tập hữu hạn, hoặc là tập đếm được, có nghĩa là ta có thể đánh số thứ tự 1, 2, 3. cho các phần tử của tập V và E. Hơn nữa, đứng trên phương diện người lập trình cho máy tính thì ta chỉ quan tâm đến các đồ thị hữu hạn (V và E là tập hữu hạn), chính vì vậy nếu không chú thích thì khi nói tới đồ thị, ta hiểu rằng đó là đồ thị hữu hạn.4: Các khái niệm liên quan đến đồ thị [1] Cạnh (edge) Nếu (u, v) là một cặp đỉnh thuộc E thì nói có một cạnh nối u và v.
Khi đó v được gọi là kề của u. Bậc của đỉnh Gọi bậc của đỉnh trong đồ thị vô hướng là số cạnh liên thuộc với chính đỉnh đó và được kí hiệu là deg(v). Bán bậc của đỉnh Bậc ra (vào) của đỉnh trong đồ thị có hướng là số cạnh của đồ thị đi ra (vào) đỉnh đó và kí hiệu là deg+(v) hay deg-(v). Ví dụ trong hình 1.4 đỉnh 2 của G1 có bán bậc vào là 1: hay deg--(2)=1 và bán bậc ra là 2: deg2--(2) = 2.
Đường đi (path) Một đường đi từ đỉnh u đến đỉnh v trên đồ thị G là một dãy đỉnh từ u1, u2,…, ui. Trong đó v có các cạnh (u, u1), (u1, u2), …, (ui, v) ∈ E, và i là số lượng cung trên đường đi được gọi là độ dài của đường đi. Đường đi đơn Một đường đi đơn trên đồ thị là một đường đi mà trên đó không có cạnh nào lặp lại. Chu trình (cycle) Một chu trình trên đồ thị G là một đường đi đơn có đỉnh đầu và đỉnh cuối trùng nhau.
Ví dụ trong hình 1.2 (Đơn đồ thị vô hướng ta có): - Đường đi: a bcfebc - Đường đi đơn: abcfeb c 9 - Chu trình: bcfeb. Hai đỉnh liên thông Đỉnh p và q được gọi là liên thông với nhau trên đồ thị G nếu có một đường đi từ p đến q trên đồ thị đó. Đồ thị liên thông Một đồ thị được gọi là liên thông nếu mọi cặp đỉnh của đồ thị đều liên thông. Thành phần liên thông Đồ thị G không liên thông sẽ phân rã thành một số đồ thị con hữu hạn liên thông không có đỉnh chung.
Các đồ thị con này được gọi là các thành phần liên thông của đồ thị. Đỉnh rẽ nhánh và bắc cầu [1] Đỉnh rẽ nhánh Đỉnh u được gọi là đỉnh rẽ nhánh của đồ thị G nếu việc loại bỏ đỉnh đó cùng các cạnh liên thuộc với nó làm tăng số thành phần liên thông của đồ thị. Cầu Cạnh e được gọi là cầu của đồ thị G nếu việc loại bỏ cạnh đó làm tăng số thành phần liên thông của đồ thị. Đồ thị con và đồ thị đẳng cấu [1] c 10 Đồ thị con Đồ thị H= (W, F) được gọi là đồ thị con của đồ thị G = (V, E) nếu W⊆ V và F ⊆ E.
Đồ thị đẳng cấu Hai đồ thị G1= (V1, E1) và G2= (V2, E2) được gọi là đẳng cấu nếu tồn tại một song ánh f: E1E2 sao cho (u, v) E1 khi và chỉ khi (f(u), f(v)) E2. Một số khái niệm liên quan về mạng xã hội Mạng xã hội xuất hiện trong nhiều lĩnh vực như: Xã hội học, Công nghệ thông tin (khai phá dữ liệu), khoa học hành vi, toán học, thống kê và nhiều lĩnh vực khác. Mạng xã hội (Social network sites), mạng xã hội trên Internet, mạng xã hội trực tuyến, hay còn gọi là mạng xã hội ảo, là một khái niệm mới được hình thành trong thập niên cuối thế kỷ XX, bắt đầu bằng sự ra đời của Classmates.com (1995), SixDegrees (1997), kế đến là sự nở rộ của một loạt các trang mạng khác như Friendster (2002), Facebook (2004), Twitter (2006) và tại Việt Nam Zing me (2009) [2]… với sự phát triển nhanh chóng của các hình thức xã hội ảo này nên mạng xã hội được định nghĩa rất khác nhau tùy theo hướng tiếp cận. Một cách chung nhất mạng xã hội là tập hợp các cá nhân với các mối quan hệ về một hay nhiều mặt gắn kết với nhau.
Mạng xã hội là một bản đồ của tất cả các mối quan hệ liên quan giữa tất cả các nút đang được nghiên cứu, mạng cũng có thể được sử dụng để đo vốn xã hội – giá trị mà các cá nhân có từ mạng xã hội, được hiển thị trong một sơ đồ mạng xã hội, nơi mà các nút là các điểm và quan hệ là các đường. Về mặt toán học, mạng xã hội có thể xem như một hệ thống các điểm (node) gắn với nhau thành một mạng gồm các liên kết (hoặc các cung). Theo hướng tiếp cận này mạng xã hội được xem như mạng phức hợp, hay nói cách khác là một tập các hệ thống được tạo bởi các yếu tố đồng nhất hoặc không đồng nhất kết nối với nhau thông qua sự tương tác khác nhau giữa các yếu tố này và được trải ra trên diện rộng. Mạng phức hợp có 2 thuộc tính quan trọng là “hiệu ứng thế giới nhỏ” (small – world effect) và “đặc trưng co giãn tự do” (Scale – free feature).7: Ma trận mạng xã hội (https://upload.org/wikipedia/commons/9/94/Six_degrees_of_separation.
Phân tích cấu trúc mạng xã hội Một mạng xã hội là một bản đồ của các mối quan hệ nhất định chẳng hạn mối qua hệ giữa các nút như tính liên kết giữa các nút đang được nghiên cứu. Các mối quan hệ mà cá nhân như là các nút các kết nối là những quan hệ xã hội của cá nhân đó. Mạng lưới này cũng có thể được sử dụng để đo lường vốn xã hội những giá trị mà một cá nhân nhận được từ các mạng xã hội.