Chương 1 KIẾN THỨC CHUẨN Bà 1. Một số khái niệm về lý thuyết ồ thị ịnh nghĩa 1. ồ thị vô hướng ồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở ây V là một tập hợp các ßnh hoặc nút, còn E là tập các cặp không có thứ tự chứa các ßnh phân biệt, ược gọi là cạnh. Hai ßnh thuộc một cạnh ược gọi là các ßnh ầu cuối của cạnh ó.
ồ thị có hướng ồ thị có hướng G là một cặp có thứ tự G = (V, E), ở ây V là một tập hợp các ßnh hoặc nút, còn E là tập các cặp có thứ tự chứa các ßnh phân biệt, ược gọi là cạnh. Cụ thể hơn nếu (a, b) ∈ E thì (a, b) là cạnh của G với ßnh ầu là a, ßnh cuối là b và có hướng i từ a ến b. ồ thị hai phần Một ồ thị hai phần xác ịnh bởi: G = (U, V, E) trong ó U ∪ V là tập ßnh của ồ thị; U, V rời nhau. U là tập hợp các ßnh trái, V là các ßnh phải và không có cạnh nối hai ßnh bất kỳ thuộc cùng một tập hay E ¦ U × V là tập hợp các cạnh liên kết giữa U và V.
Hành trình; chu trình G(V, E) là một ồ thị vô hướng. Một hành trình trong G là một dãy các ßnh v0 v1 v2 .vn sao cho với mọi i = 0, 1, ., n − 1, {vi , vi+1 } là một cạnh của G. Các cạnh {vi , vi+1 }, i = 0, 1, ., n − 1, cũng ược gọi là các cạnh của hành trình v0 v1. Khi ó n ược gọi là ộ dài, v0 ược gọi là ßnh ầu, vn ược gọi là ßnh cuối của hành trình trên.
Một hành trình ược gọi là khép kín nếu ßnh ầu và ßnh cuối của nó trùng nhau. Một hành trình ược gọi là ường nếu các ßnh của hành trình ó ều khác nhau. Một hành trình khép kín ược gọi là chu trình, nếu nó có ộ dài ít nhất là 3 và khi xoá 4 i ßnh cuối thì trờ thành ường. Khoa học mạng và cộng ồng mạng 1.
Khoa học mạng Khoa học mạng ã phát triển thành một ngành học khổng lồ. Trong phần này, chúng tôi sẽ giải thích một số kiến thức cơ bản về khoa học mạng. Hiện nay có một số sách giáo trình tốt về khoa học mạng; trong số ó, chúng tôi ề cập ến tài liệu [1] với phạm vi bao phủ rộng và [2] tập trung duy nhất vào mô hình hóa, giải thích và chất lượng dữ liệu. Có nhiều ịnh nghĩa khoa học mạng và ta có thể tìm ược một ịnh nghĩa về khoa học mạng trong [3]: Khoa học mạng là nghiên cứu về các mạng sử dụng lý thuyết toán học, tập trung vào phân tích và mô tả ặc iểm và trạng thái của mạng.
Nghiên cứu về các mạng ã thấy những nghiên cứu quan trọng, với trọng tâm là tìm hiểu và ánh giá các ặc tính thống kê của các mạng quy mô lớn (Newman, 2003). Cộng ồng Trong mục này chúng tôi chủ yếu tham khảo phần trình bày về cộng ồng ở trong tài liệu [4] và [5]. CẤU TRÚC CỘNG ỒNG Các mạng thường ược biểu diễn bằng các ồ thị trong ó một nhóm các nút (ßnh) có các liên kết giữa chúng (các cạnh) [4]. Lý thuyết ồ thị là toán học của các mạng ang ược sử dụng ể mô hình hóa ồ thị (Stam, 2014).
Erdös và Rényi (1959) ã giới thiệu các ồ thị ngẫu nhiên trong ó xác suất cạnh giữa hai ßnh là như nhau ối với bất kỳ cặp nào khác. Nhưng các mạng trong thế giới thực không phải là ồ thị ngẫu nhiên vì chúng có một trật tự tốt của các mẫu. Một trong những ặc iểm thích hợp của các mạng trong thế giới thực là chúng có cấu trúc cộng ồng, có thể ược mô hình hóa một cách tương ối chính xác bằng cách sử dụng ồ thị (Fortunato, 2010; Singh, 2014). Nói chung, cộng ồng hoặc cụm ược ịnh nghĩa là một nhóm các ßnh có các liên kết chặt chẽ khác với phần còn lại của mạng (Yang và cộng sự, 2010).
Xác ịnh cấu trúc cộng ồng là một bước tiến tới sự hiểu biết về các cấu trúc mạng khác nhau (Newman và Girvan, 2004) với các ứng dụng trong một số lĩnh vực như mạng xã hội trực tuyến và tất cả các ngành khoa học vật lý và ời sống (Lewis, 2011). Phát hiện cộng ồng ề cập ến việc xác ịnh các nhóm ßnh có nhiều liên kết trong mạng tùy thuộc vào thuộc tính cấu trúc của chúng (Yang và cộng sự, 2013; Kelley và cộng 5 sự, 2012). Nhiều thuật toán ể phát hiện cộng ồng ã ược phát triển, sử dụng các kỹ thuật và công cụ từ các ngành khác nhau như sinh học, vật lý, khoa học xã hội, toán học ứng dụng và khoa học máy tính (Lancichinetti và Fortunato, 2009). Tuy nhiên, một thuật toán phát hiện cộng ồng duy nhất không hoạt ộng trong tất cả các loại mạng (Plantié và Crampes, 2013; Yang và cộng sự, 2016) vì có rất nhiều mạng phức tạp ược tạo từ các cách khác nhau [4].
Vì vậy bài toán phát hiện cộng ồng vẫn ang ược quan tâm và ngày càng có nhiều thuật toán phát hiện cồng ồng ược ề xuất. Nhiều hệ thống phức tạp trong tự nhiên và xã hội có thể ược mô tả dưới dạng ồ thị (mạng lưới) giới hạn mạng lưới kết nối phức tạp giữa các ơn vị mà chúng ược tạo thành [4]. ồ thị ã nổi lên như một mô hình mạnh mẽ ể biểu diễn các loại dữ liệu khác nhau. Ví dụ: dữ liệu không có cấu trúc (ví dụ: tài liệu văn bản), dữ liệu bán cấu trúc (ví dụ: cơ sở dữ liệu XML) và dữ liệu có cấu trúc (ví dụ: cơ sở dữ liệu quan hệ) ều có thể ược mô hình hóa dưới dạng ồ thị, trong ó các ßnh (nút) tương ứng và các cạnh, tương ứng, có thể là siêu liên kết, mối quan hệ cha-con và mối quan hệ chính-khóa ngoại.
Ngoài ra, các biểu ồ tự nhiên phát sinh trong các lĩnh vực ứng dụng như mạng sinh học, mạng xã hội mạng thông tin. Cấu trúc cộng ồng tồn tại một cách tự nhiên trong nhiều mạng lưới trong thế giới thực như mạng xã hội, mạng sinh học, mạng cộng tác và truyền thông chß là một vài ví dụ [4]. Một câu hỏi ược quan tâm là làm thế nào ể giải thích cấu trúc của các mạng như vậy về sự cùng tồn tại của các tiểu ơn vị cấu trúc của chúng (cộng ồng) gắn với các bộ phận có liên kết với chúng cao hơn. Việc xác ịnh các cộng ồng chưa biết trước này (ví dụ, các nhóm người, các ngành công nghiệp và các protein liên quan ến chức năng) là rất quan trọng ối với sự hiểu biết về các ặc tính cấu trúc và chức năng của các mạng.
ể minh họa, chúng tôi giới thiệu ba ví dụ áng chú ý về các cộng ồng [5]. • Mạng xã hội trực tuyến. Một loại mạng mà cộng ồng thường xuyên ược quan sát là mạng xã hội trực tuyến. ược kích hoạt bởi Internet và ược thúc ẩy bởi sự ra ời gần ây của các trang mạng xã hội trực tuyến như Facebook, Google+ và Twitter, nghiên cứu về khám phá cộng ồng trên các mạng xã hội trực tuyến ã và ang bùng nổ.
Với sự sẵn có của dữ liệu mạng xã hội quy mô lớn, nghiên cứu ã dẫn ến sự phát triển của nhiều ứng dụng thú vị, ví dụ: khám phá vòng kết nối xã hội và tìm kiếm cộng ồng có ảnh hưởng. • Ngoài ra, do sự phát triển của các thiết bị iện thoại thông minh, các mạng xã hội 6 trực tuyến ã dẫn ến sự phát triển nhanh chóng của các mạng xã hội ịa lý (còn ược gọi là mạng xã hội dựa trên vị trí), chẳng hạn như Foursquare, Yelp, Google+ và Facebook Places. Trong mạng xã hội ịa lý, người dùng ược liên kết với thông tin vị trí (ví dụ: quê quán và ịa iểm ăng ký) và cộng ồng bao gồm những người dùng ược kết nối chặt chẽ trong lớp xã hội cũng như gần nhau về mặt không gian trong lớp không gian. • Mạng cộng tác học thuật.
Mạng cộng tác học thuật nổi tiếng là mạng DBLP, trong ó một ßnh ại diện cho một tác giả và một cạnh giữa hai tác giả biểu thị mối quan hệ cộng tác, tức là họ có (các) ấn phẩm ồng tác giả. Ngoài ra, các ßnh có thể có các thuộc tính ại diện cho lĩnh vực chuyên môn của tác giả như ấn phẩm, bài báo, sách. Các cộng ồng trong mạng DBLP có thể ại diện cho một nhóm tác giả thường xuyên cộng tác với nhau và làm việc về các chủ ề tương tự. Mạng cộng tác học thuật trong ví dụ 3 là một mạng thông tin không ồng nhất [5].
Mạng không ồng nhất bao gồm các ßnh và các cạnh của cả hai loại khác nhau. Ví dụ, trong một mạng lưới chăm sóc sức khỏe, các ßnh có thể là bệnh nhân, bác sĩ, xét nghiệm y tế, bệnh tật, thuốc men, bệnh viện, phương pháp iều trị,. Một mặt, việc coi tất cả các ßnh cùng loại có thể bỏ sót thông tin quan trọng. Mặt khác, việc coi mọi ßnh là một kiểu riêng biệt có thể bỏ sót bức tranh lớn.
ây là một ví dụ cổ iển về một mạng không ồng nhất. Nhiều loại ối tượng như vậy, các mạng thông tin liên kết với nhau, không ồng nhất nhưng thường là bán cấu trúc, làm cho các cộng ồng trên các mạng thông tin không ồng nhất trở nên phức tạp và thú vị. Trong luận văn này ngoài việc giải quyết các bài toán phát hiện cộng ồng thông thường có tất cả các ßnh cùng loại (chương 2) thì luận văn còn tìm hiểu về cách phát hiện cộng ồng trên các ồ thị hai phần ể giải quyết cho các mạng mà có hai loại ßnh khác nhau (chương 3). Ngoài ví dụ về mạng các tác giả và các sản phẩm của họ thì trong thực tế ta cũng bắt gặp rất nhiều các mạng gồm hai loại ßnh khác nhau chẳng hạn như: • ồ thị biểu diễn một số diễn viên và một số phim họ tham gia óng.
Khi ó tập các diễn viên và tập các bộ phim ược liên kết bởi các cạnh nếu diễn viên tham gia óng bộ phim nào thì sẽ có cạnh nối giữa chúng. • ồ thị biểu diễn các công ty sản xuất và người tiêu dùng. Trong ó tập ßnh gồm hai tập con là công ty sản xuất và người tiêu dùng. Nếu người tiêu dùng sử dụng sản phẩm của công ty thì sẽ có cạnh liên kết giữa chúng.