chương 1 là trình bày tổng quan về mạng xã hội, cộng đồng mạng xã hội và các phân tích, đánh giá về các thuật toán rút gọn đồ thị, thuật toán phát hiện cộng đồng trên mạng xã hội và các ứng dụng trong các lĩnh vực khác nhau. Một số các độ đo được giới thiệu để sử dụng đánh giá tính hiệu quả của thuật toán rút gọn đồ thị và thuật toán phát hiện cộng đồng trên mạng xã hội. Thuật toán rút gọn đồ thị mạng xã hội dựa vào độ đo trung tâm trung gian và nguyên lý lan truyền nhãn. Chương 2 nghiên cứu các tính chất của lớp đỉnh tương đương dựa vào độ đo trung tâm trung gian, đề xuất thuật toán REG rút gọn đồ thị dựa trên thay thế các lớp đỉnh tương đương theo độ đo trung tâm trung gian, đề xuất này nhằm mục tiêu giảm thiểu không gian tính toán của đồ thị, từ đó giảm thiểu độ phức tạp tính toán của bài toán so với các phương pháp trước đây.
Đồng thời trong chương này cũng nghiên cứu các tính chất của lớp đỉnh tương đương dựa vào nguyên lý lan truyền nhãn, từ đó đề xuất thuật toán LREN rút gọn đồ thị dựa trên thay thế các lớp đỉnh tương đương. Các thực nghiệm khẳng định hiệu quả của thuật toán đề xuất trong bài toán rút gọn đồ thị mạng xã hội. Nội dung trình bày trong chương được công bố trong [CT1], [CT3], [CT4]. Áp dụng thuật toán rút gọn đồ thị để phát hiện cộng đồng trên mạng xã hội.
Chương 3 đề xuất thuật toán FBC cải tiến thời gian tính độ đo trung tâm trung gian trên đồ thị mạng xã hội. Đề xuất này nhằm mục tiêu giảm thiểu thời gian tính toán độ đo khoảng cách trên đồ thị mạng xã hội phục vụ cho thuật toán đề xuất phát hiện cấu trúc cộng đồng CDAB trên đồ thị mạng xã hội rút gọn. Đồng thời trong chương này cũng đề xuất thuật toán LPAA phát hiện các cộng đồng trên đồ thị mạng xã hội rút gọn. Đề xuất này nhằm mục tiêu giảm thiểu thời gian tính toán cho thuật toán phát hiện các cộng đồng trên đồ thị mạng xã hội rút gọn.
7 Các thực nghiệm khẳng định hiệu quả của thuật toán đề xuất trong bài toán phát hiện cộng đồng mạng xã hội. Nội dung trình bày trong chương được công bố trong [CT2], [CT3]. Cuối cùng là kết luận và các hướng phát triển tiếp theo. TỔNG QUAN RÚT GỌN ĐỒ THỊ VÀ PHÁT HIỆN CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI Chương này giới thiệu tổng quan về mạng xã hội, cộng đồng trên mạng xã hội, các thuật toán phát hiện cộng đồng mạng xã hội và các thuật toán rút gọn đồ thị cho nhiều ứng dụng khác nhau.
Trong nội dung chương cũng thực hiện phân tích, đánh giá rõ những mặt hạn chế, tồn tại của mỗi phương pháp từ đó xác định hướng phát triển thuật toán rút gọn đồ thị và ứng dụng để cải tiến thuật toán phát hiện cộng đồng trên mạng xã hội. Cuối chương trình bày một số độ đo phổ biến được sử dụng để đánh giá hiệu quả của các thuật toán rút gọn đồ thị và thuật toán phát hiện cộng đồng trên mạng xã hội. Mạng xã hội Mạng xã hội là một cấu trúc xã hội được tạo ra từ các thực thể, các tác nhân hoặc các tổ chức được liên kết, kết nối bởi một hoặc nhiều quan hệ với nhau [8], [42], [102]. Theo Fortunato và các cộng sự [31] mạng xã hội là một tập hợp các thực thể được kết nối với nhau bằng một tập hợp các mối quan hệ, liên kết, như quan hệ bạn bè, gia đình, cộng sự hay trao đổi thông tin, … Các mối quan hệ giữa các thực thể có thể mang nhiều nội dung khác nhau từ sự tương trợ, trao đổi thông tin cho đến việc trao đổi hàng hóa, dịch vụ, … Mạng xã hội cung cấp nhiều cách khác nhau để các tổ chức thu thập thông tin, cạnh tranh với nhau trong việc thiết lập giá kinh doanh hoặc chính sách, … Mạng xã hội thường có những đặc tính như sau [9], [34], [68], [102]: • Dựa vào người dùng (User-based): Trước khi các mạng xã hội như Facebook, Twitter, MySpace, … phổ biến trở thành chuẩn mực, các trang web dựa trên nội dung được cập nhật bởi người dùng và được người sử dụng truy cập trên mạng Internet để đọc, tham khảo thông tin.
Các mạng xã hội trực tuyến được xây dựng và định hướng bởi chính người dùng. Người dùng thực hiện các cuộc hội thoại và các nội dung trao đổi với nhau trên mạng. Hướng của nội dung đó được xác định bởi bất kỳ ai tham gia vào cuộc thảo luận. Vì vậy, mạng xã hội trở nên rất 9 hấp dẫn, thu hút bởi tính năng tương tác nhiều hơn đối với người dùng Internet thông thường.
• Tương tác (Interactive): Một đặc điểm khác của các mạng xã hội hiện đại là các thực thể thường xuyên tương tác thông qua các mối liên kết. Điều này có nghĩa là một mạng xã hội không chỉ là một bộ sưu tập các phòng chat, diễn đàn, …, trang web như Facebook mà còn chứa các ứng dụng chơi trò chơi, quảng cáo, bán hàng online, tin tức, … Các mạng xã hội ngày nay đang phát triển nhanh chóng và được người dùng lựa chọn nhiều hơn so với truyền hình bởi vì nó không chỉ là giải trí, học tập, trao đổi công việc mà đó còn là cách thức để mọi người kết nối, tương tác với nhau. • Hướng đến cộng đồng (Community-driven): Mạng xã hội được xây dựng và phát triển từ các khái niệm về cộng đồng. Điều này có nghĩa là các cộng đồng hoặc các nhóm xã hội trên toàn thế giới được thành lập dựa trên thực tế là các thành viên có những sở thích, những quan điểm chung,.
• Các mối quan hệ (Relationships): Không giống như các trang web trong quá khứ, các mạng xã hội phát triển mạnh về các mối quan hệ. Càng có nhiều mối quan hệ trong mạng, các thực thể càng thiết lập được vai trò trung tâm của mạng đó. Mối quan hệ giữa các thực thể như mối quan hệ hai người có thể là bạn bè hoặc không quen biết nhau. Tồn tại tính địa phương, mối quan hệ giữa các thực thể có xu hướng tạo thành các cụm (cộng đồng).
Mạng xã hội cung cấp tiềm năng rất lớn về tương tác và giao tiếp giữa rất nhiều các thành viên trong mạng ở khắp mọi nơi, không phụ thuộc vào không gian địa lý. Đồng thời tạo môi trường cho việc tương tác và chia sẻ thông tin giữa các thành viên trong mạng như người thân, đồng nghiệp, gia đình, bạn bè, người hâm mộ, … [68]. • Cảm xúc về nội dung (Emotion over content): Một đặc điểm độc đáo khác của mạng xã hội là yếu tố cảm xúc. Mặc dù các trang web trong quá khứ tập trung chủ yếu vào việc cung cấp thông tin cho người truy cập, nhưng mạng xã hội ngày nay thực sự mang đến cho người dùng sự an toàn về mặt cảm xúc và cảm giác rằng dù có chuyện gì xảy ra, bạn bè của họ vẫn ở trong tầm kiểm soát.
10 Hiện nay, mạng xã hội đang phát triển nhanh chóng, với số lượng người dùng và số lượng các mối quan hệ giữa các thành viên trong mạng rất lớn. Từ đó, yêu cầu khách quan đặt ra đòi hỏi phải có những phương pháp nghiên cứu và kỹ thuật phân tích mạng xã hội phù hợp. Một số hệ đo quan trọng trên đồ thị mạng xã hội Phân tích mạng xã hội (Social Network Analysis) [8], [9], [28], [42], [102], [105] dựa vào lý thuyết đồ thị là một tập hợp các phương pháp lựa chọn mẫu, thu thập và xử lý dữ liệu, phân tích các khái niệm, sử dụng lý thuyết đồ thị để mô tả và phân tích các mối quan hệ giữa các thực thể, các tác nhân trong mạng, xác nhận các quy luật hình thành và biến đổi của những mối quan hệ đó, và nhất là làm sáng tỏ những ảnh hưởng của các mối quan hệ xã hội (hay cấu trúc của mạng) đối với hành vi của các tác nhân. Mục tiêu chính của phân tích mạng xã hội là: • Xác định những thực thể, tác nhân quan trọng nhất trong mạng xã hội: Độ đo trung tâm (centrality) là một độ đo điển hình để xác định tầm quan trọng của một tác nhân trong mạng, đồng thời giúp chúng ta hiểu được tầm ảnh hưởng và quyền lực của một cá nhân trong xã hội.
• Phát hiện các cộng đồng trên mạng xã hội: Một số thực thể trong mạng xã hội có liên kết chặt chẽ với nhau tạo thành từng cụm, và giữa các cụm đó được nối với nhau chỉ bằng một số ít cạnh khác. Nhiệm vụ xác định các cộng đồng mạng xã hội được thực hiện thông qua nghiên cứu cấu trúc mạng xã hội và cấu trúc liên kết giữa các thực thể trên mạng xã hội. Mục này trình bày khái niệm đồ thị mạng xã hội và một số hệ đo quan trọng được sử dụng phổ biến trên đồ thị mạng xã hội. Mạng xã hội thường được mô hình hóa, trực quan hóa và biểu diễn dưới dạng một đồ thị, chỉ giữ lại các thành viên và mối quan hệ giữa các thành viên trên mạng có tồn tại hay không.
Thông thường đồ thị mạng xã hội là đồ thị vô hướng, ví dụ như đồ thị mạng bạn bè trên mạng xã hội Facebook, … Nhưng chúng cũng có thể là đồ thị có hướng như đồ thị mạng xã hội những người theo dõi nhau (followers) trên mạng xã hội Twitter hoặc Google +. Đồ thị mạng xã hội là đồ thị G = (V, E), trong đó V là tập các đỉnh (nút) và E là tập các cạnh (cung). Tập V biểu diễn cho các thành viên (tác nhân) của mạng xã hội, còn tập E thể hiện mối quan hệ xã hội giữa các thành viên với nhau. Dựa vào lý thuyết đồ thị, cấu trúc mạng xã hội cũng có thể được biểu diễn thông qua ma trận liền kề A = (Aij) ∈ Rn×n, với n = |V|, R = {0, 1} và Aij = 1 nếu hai đỉnh i và j có cạnh nối giữa chúng (có liên kết - quan hệ trực tiếp với nhau), ngược lại thì Aij = 0.
Để áp dụng được kỹ thuật khai phá dữ liệu trong phân tích mạng xã hội, thì trước tiên phải định nghĩa được độ đo khoảng cách (distance measure) giữa các đỉnh, cạnh của đồ thị. Khi các cạnh của đồ thị được gắn nhãn thì các nhãn này có thể được sử dụng như là độ đo khoảng cách, tùy thuộc vào những gì mà chúng đại diện. Nhưng khi các cạnh không có nhãn, như đồ thị “bạn bè” thì cần phải định nghĩa độ đo khoảng cách giữa các đỉnh.