Một Số Kỹ Thuật Phát Hiện Cấu Trúc Cộng Đồng Trên Đồ Thị Mạng Xã Hội

Tìm hiểu các kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội. Luận án nghiên cứu chuyên sâu về thuật toán và ứng dụng thực tiễn.

• Tác giả: Nguyễn Hiền Trinh
• Người hướng dẫn: PTS. Đoàn Văn Ban
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Một Số Kỹ Thuật Phát Hiện Cấu Trúc Cộng Đồng Trên Đồ Thị Mạng Xã Hội
• Loại tài liệu: Luận Án Tiến Sĩ
• Năm xuất bản: 2023
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
• DANH MỤC CÁC THUẬT NGỮ
• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ ĐỒ THỊ MẠNG XÃ HỘI VÀ BÀI TOÁN PHÁT HIỆN CẤU TRÚC CỘNG ĐỒNG TRÊN ĐỒ THỊ MẠNG XÃ HỘI
• 1.1. Giới thiệu chung
• 1.2. Mạng xã hội và đồ thị mạng xã hội
• 1.3. Một số đặc tính của mạng xã hội
• 1.4. Đồ thị mạng xã hội và cấu trúc cộng đồng của mạng xã hội
• 1.5. Một số độ đo quan trọng trên đồ thị mạng xã hội
• 1.5.1. Độ đo trung tâm theo bậc
• 1.5.2. Độ đo trung tâm theo vector riêng
• 1.5.3. Hệ số phân cụm của đỉnh trên đồ thị
• 1.6. Bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội
• 1.6.1. Nhóm thuật toán phát hiện cấu trúc cộng đồng truyền thống
• 1.6.2. Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa trên tối ưu hóa độ đo đơn thể
• 1.6.3. Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa vào độ đo trung gian
• 1.6.4. Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa trên lan truyền nhãn
• 1.6.5. Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa vào mạng học sâu
• 1.6.6. Đánh giá chung về bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội và lựa chọn hướng nghiên cứu
• 1.7. Các độ đo đánh giá thuật toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội
• 1.7.1. Thông tin tương hỗ chuẩn NMI
• 1.8. Tổng kết chương 1
• 2. CHƯƠNG 2: PHÁT HIỆN CẤU TRÚC CỘNG ĐỒNG RỜI NHAU TRÊN ĐỒ THỊ MẠNG XÃ HỘI
• 2.1. Phát hiện cấu trúc cộng đồng rời nhau bằng phương pháp phân cụm phổ (Spectral)
• 2.1.1. Những vấn đề cơ bản trong phương pháp phân cụm phổ (Spectral Clustering)
• 2.1.2. Bài toán và phương pháp phân cụm phổ
• 2.1.3. Thuật toán đề xuất
• 2.1.4. Các kết quả thực nghiệm
• 2.2. Cải tiến thuật toán lan truyền nhãn LPA
• 2.2.1. Thuật toán lan truyền nhãn LPA
• 2.2.2. Thuật toán lan truyền nhãn LPAMD với hàm f đề xuất
• 2.2.3. Kết quả thực nghiệm thuật toán LPAMD
• 2.3. Kết hợp rút gọn đồ thị và thuật toán lan truyền nhãn
• 2.3.1. Thuật toán LPARLV (LPA Reduce Leaf Vertex)
• 2.3.2. Kết quả thực nghiệm
• 2.4. Tổng kết chương 2
• 3. CHƯƠNG 3: PHÁT HIỆN CẤU TRÚC CỘNG ĐỒNG CHỒNG CHÉO TRÊN ĐỒ THỊ MẠNG XÃ HỘI
• 3.1. Khái quát về vấn đề cộng đồng chồng chéo
• 3.2. Hệ số phân cụm của đỉnh trên đồ thị và hệ số thuộc về cộng đồng
• 3.2.1. Hệ số phân cụm của đỉnh trên đồ thị
• 3.2.2. Hệ số thuộc về cộng đồng
• 3.3. Phát hiện cấu trúc cộng đồng chồng chéo theo lan truyền nhãn và dựa vào hệ số thuộc về cộng đồng
• 3.4. Độ phức tạp thuật toán COPA-BC
• 3.5. Kết quả thực nghiệm
• 3.6. Tổng kết chương 3
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA LUẬN ÁN
• DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CÓ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phát Hiện Cấu Trúc Cộng Đồng 55 Ký Tự

Mạng xã hội là tập hợp các thực thể kết nối với nhau, tạo thành đồ thị mạng xã hội. Các thực thể này có thể là cá nhân, tổ chức, hoặc thậm chí là các khái niệm trừu tượng. Các liên kết biểu diễn mối quan hệ giữa chúng, ví dụ như bạn bè, quan hệ kinh doanh, hoặc sự tương tác trên nền tảng trực tuyến. Phát hiện cộng đồng trên các đồ thị này là một bài toán quan trọng trong phân tích mạng xã hội. Nó giúp ta hiểu rõ hơn về cấu trúc và động lực của mạng. Mục tiêu chính là xác định các nhóm (cộng đồng) mà các thành viên có liên kết chặt chẽ với nhau hơn so với các thành viên bên ngoài nhóm. Kỹ thuật này có nhiều ứng dụng thực tế, từ ứng dụng trong marketing đến ứng dụng trong an ninh mạng. Các thuật toán phát hiện cộng đồng ngày càng phát triển, đáp ứng nhu cầu phân tích các mạng ngày càng lớn và phức tạp.

1.1. Khái niệm cấu trúc cộng đồng trong mạng xã hội

Cấu trúc cộng đồng, hay còn gọi là cộng đồng, là một nhóm các thực thể trong mạng có những đặc tính tương tự nhau và liên kết chặt chẽ với nhau. Các thành viên trong một cộng đồng thường có chung sở thích, mục tiêu, hoặc mối quan hệ. Theo Nguyễn Hiền Trinh, việc phân tích cấu trúc cộng đồng sẽ cung cấp những thông tin giá trị để hiểu sâu hơn về cấu trúc của mạng. Việc xác định được các cấu trúc này giúp chúng ta dự đoán hành vi, lan truyền thông tin, và đưa ra các quyết định phù hợp.

1.2. Vai trò của phát hiện cộng đồng trong phân tích đồ thị

Phát hiện cộng đồng đóng vai trò then chốt trong phân tích đồ thị, mở ra cánh cửa để hiểu rõ hơn về cách thức các thực thể tương tác và hình thành các nhóm liên kết chặt chẽ. Điều này có ý nghĩa quan trọng trong việc dự đoán hành vi, khám phá các mối quan hệ tiềm ẩn, và tối ưu hóa chiến lược kinh doanh. Chẳng hạn, trong marketing, việc xác định các cộng đồng giúp doanh nghiệp target quảng cáo hiệu quả hơn.

II. Thách Thức Trong Phát Hiện Cấu Trúc Cộng Đồng 59 Ký Tự

Mặc dù có nhiều thuật toán phát hiện cộng đồng, vẫn còn nhiều thách thức cần vượt qua. Độ phức tạp tính toán là một vấn đề lớn, đặc biệt đối với các đồ thị mạng xã hội cực lớn. Nhiều thuật toán có độ phức tạp cao, khiến việc áp dụng trên các mạng thực tế trở nên khó khăn. Bên cạnh đó, việc đánh giá chất lượng của các thuật toán phát hiện cộng đồng cũng là một thách thức. Cần có các độ đo phù hợp để so sánh và đánh giá hiệu quả của các thuật toán khác nhau. Ngoài ra, các mạng xã hội thường có cấu trúc phức tạp, với các cộng đồng chồng lấp và động, đòi hỏi các thuật toán phải có khả năng xử lý những tính chất này.

2.1. Khó khăn khi xử lý đồ thị mạng xã hội kích thước lớn

Các đồ thị mạng xã hội thường có số lượng nút và cạnh rất lớn, gây khó khăn cho việc tính toán. Các thuật toán truyền thống có thể không đủ khả năng xử lý các mạng này trong thời gian hợp lý. Do đó, cần có các thuật toán hiệu quả hơn hoặc các kỹ thuật xử lý song song để giải quyết vấn đề này. Theo Nguyễn Xuân Dũng, cần nghiên cứu rút gọn đồ thị để áp dụng vào phát hiện cấu trúc cộng đồng mạng xã hội rời nhau.

2.2. Vấn đề đánh giá độ chính xác của thuật toán

Việc đánh giá độ chính xác của thuật toán phát hiện cộng đồng là một vấn đề nan giải do thiếu các bộ dữ liệu chuẩn và các độ đo phù hợp. Các độ đo như Modularity và NMI thường được sử dụng, nhưng chúng có những hạn chế nhất định. Cần có các độ đo mới và các phương pháp đánh giá toàn diện hơn để đánh giá chính xác hiệu quả của các thuật toán.

2.3. Cấu trúc phức tạp của mạng xã hội chồng lấp và động

Cấu trúc của các mạng xã hội thường phức tạp, với các cộng đồng chồng lấp và thay đổi theo thời gian. Các thuật toán phải có khả năng xử lý những tính chất này để có thể phát hiện chính xác các cộng đồng thực tế. Các phương pháp phát hiện mô hình cộng đồng chồng lấp và cộng đồng động đang được nghiên cứu và phát triển.

III. Cách Phát Hiện Cộng Đồng Bằng Phân Cụm Phổ 58 Ký Tự

Phân cụm phổ (Spectral Clustering) là một phương pháp hiệu quả để phát hiện cộng đồng trên đồ thị mạng xã hội. Phương pháp này dựa trên việc phân tích các vector riêng của ma trận kề hoặc ma trận Laplacian của đồ thị. Các vector riêng này biểu diễn cấu trúc của đồ thị, và chúng có thể được sử dụng để phân cụm các nút thành các cộng đồng khác nhau. Phân cụm phổ có nhiều ưu điểm so với các phương pháp phân cụm truyền thống, đặc biệt là khả năng xử lý các đồ thị có cấu trúc phức tạp. Tuy nhiên, phương pháp này cũng có một số hạn chế, như độ phức tạp tính toán cao và khó khăn trong việc lựa chọn số lượng cụm.

3.1. Cơ sở lý thuyết của phân cụm phổ trong mạng xã hội

Phân cụm phổ dựa trên lý thuyết đồ thị phổ, sử dụng các vector riêng và giá trị riêng của ma trận liên kết để biểu diễn cấu trúc đồ thị. Theo Nguyễn Hiền Trinh, các vector riêng này cho phép ánh xạ các nút trên đồ thị vào không gian chiều thấp, trong đó các nút có liên kết chặt chẽ với nhau sẽ nằm gần nhau hơn. Từ đó, các thuật toán phân cụm truyền thống có thể được sử dụng để phân chia các nút thành các cộng đồng.

3.2. Các bước thực hiện phân cụm phổ trên đồ thị

Các bước cơ bản của phân cụm phổ bao gồm: (1) Xây dựng ma trận liên kết (ma trận kề, ma trận Laplacian), (2) Tính toán các vector riêng và giá trị riêng của ma trận, (3) Chọn k vector riêng tương ứng với k giá trị riêng lớn nhất, (4) Ánh xạ các nút vào không gian k chiều, (5) Sử dụng thuật toán phân cụm (ví dụ: k-means) để phân chia các nút thành các cộng đồng.

IV. Thuật Toán Lan Truyền Nhãn LPA Và Cải Tiến 57 Ký Tự

Thuật toán lan truyền nhãn (LPA) là một phương pháp đơn giản và hiệu quả để phát hiện cộng đồng. LPA gán cho mỗi nút một nhãn, và sau đó lặp đi lặp lại việc lan truyền nhãn cho các nút lân cận. Mỗi nút sẽ cập nhật nhãn của mình thành nhãn phổ biến nhất trong số các nút lân cận. Quá trình này lặp lại cho đến khi nhãn của tất cả các nút ổn định. LPA có ưu điểm là thời gian tính toán nhanh và dễ cài đặt. Tuy nhiên, LPA cũng có một số nhược điểm, như tính không ổn định và độ chính xác không cao. Nhiều cải tiến đã được đề xuất để khắc phục những nhược điểm này.

4.1. Nguyên lý hoạt động của thuật toán lan truyền nhãn

LPA hoạt động dựa trên nguyên tắc: các nút có liên kết chặt chẽ với nhau có xu hướng thuộc cùng một cộng đồng và do đó có nhãn giống nhau. Thuật toán bắt đầu bằng cách gán cho mỗi nút một nhãn duy nhất. Sau đó, các nút lặp đi lặp lại việc cập nhật nhãn của mình thành nhãn phổ biến nhất trong số các nút lân cận. Quá trình này lặp lại cho đến khi các nhãn ổn định.

4.2. Các cải tiến của thuật toán lan truyền nhãn LPA

Để khắc phục nhược điểm của LPA, nhiều cải tiến đã được đề xuất, như sử dụng các hàm trọng số để đánh giá mức độ ảnh hưởng của các nút lân cận, hoặc sử dụng các ràng buộc để hướng dẫn quá trình lan truyền nhãn. Một số thuật toán cải tiến LPA bao gồm LPAMD, LPARLV. Các cải tiến này giúp cải thiện tính ổn định và độ chính xác của thuật toán.

4.3. Ưu điểm và hạn chế của thuật toán LPA và các biến thể

LPA và các biến thể của nó có ưu điểm là thời gian tính toán nhanh và dễ cài đặt. Tuy nhiên, chúng cũng có một số hạn chế, như tính không ổn định, độ chính xác không cao và khó khăn trong việc xử lý các cộng đồng chồng lấp. Cần lựa chọn thuật toán phù hợp với từng bài toán cụ thể.

V. Ứng Dụng Của Phát Hiện Cộng Đồng Trong Thực Tế 53 Ký Tự

Phát hiện cộng đồng có nhiều ứng dụng trong thực tế, từ ứng dụng trong marketing và nghiên cứu xã hội đến ứng dụng trong an ninh mạng. Trong marketing, phát hiện cộng đồng có thể được sử dụng để xác định các nhóm khách hàng mục tiêu và phát triển các chiến dịch quảng cáo hiệu quả hơn. Trong nghiên cứu xã hội, phát hiện cộng đồng có thể được sử dụng để hiểu rõ hơn về cấu trúc và động lực của các cộng đồng trực tuyến. Trong an ninh mạng, phát hiện cộng đồng có thể được sử dụng để phát hiện các nhóm người dùng có hành vi đáng ngờ.

5.1. Ứng dụng trong marketing và quảng cáo trực tuyến

Trong marketing, phát hiện cộng đồng giúp doanh nghiệp xác định các phân khúc khách hàng mục tiêu dựa trên sở thích, hành vi và mối quan hệ. Điều này cho phép doanh nghiệp tạo ra các chiến dịch quảng cáo được cá nhân hóa, tăng hiệu quả tiếp cận và tương tác với khách hàng. Ví dụ, một công ty bán đồ thể thao có thể sử dụng phát hiện cộng đồng để xác định các nhóm người dùng thích chạy bộ, đạp xe hoặc tập gym.

5.2. Ứng dụng trong an ninh mạng và phát hiện gian lận

Trong an ninh mạng, phát hiện cộng đồng có thể được sử dụng để xác định các nhóm người dùng có hành vi đáng ngờ, chẳng hạn như các nhóm hacker hoặc các nhóm phát tán tin giả. Bằng cách phân tích cấu trúc liên kết và hành vi của các người dùng trong mạng, các chuyên gia an ninh mạng có thể phát hiện và ngăn chặn các cuộc tấn công mạng hoặc các hoạt động gian lận.

5.3. Ứng dụng trong nghiên cứu xã hội và khoa học thông tin

Trong nghiên cứu xã hội, phát hiện cộng đồng được sử dụng để hiểu rõ hơn về cấu trúc và động lực của các cộng đồng trực tuyến, chẳng hạn như các cộng đồng người dùng trên mạng xã hội hoặc các diễn đàn trực tuyến. Trong khoa học thông tin, phát hiện cộng đồng có thể được sử dụng để cải thiện các hệ thống gợi ý và tìm kiếm thông tin.

VI. Kết Luận Và Hướng Nghiên Cứu Phát Triển 56 Ký Tự

Phát hiện cộng đồng trên đồ thị mạng xã hội là một lĩnh vực nghiên cứu quan trọng và đầy tiềm năng. Mặc dù đã có nhiều tiến bộ trong lĩnh vực này, vẫn còn nhiều thách thức cần vượt qua. Các hướng nghiên cứu trong tương lai bao gồm phát triển các thuật toán hiệu quả hơn cho các đồ thị lớn, xây dựng các độ đo đánh giá chất lượng toàn diện hơn, và nghiên cứu các phương pháp xử lý các cộng đồng chồng lấp và động. Đồng thời, cần tập trung vào việc ứng dụng phát hiện cộng đồng vào các lĩnh vực thực tế khác nhau.

6.1. Tóm tắt các kỹ thuật và ứng dụng đã trình bày

Bài viết đã trình bày tổng quan về phát hiện cộng đồng trên đồ thị mạng xã hội, bao gồm các khái niệm cơ bản, các thuật toán phổ biến (phân cụm đồ thị, LPA và các biến thể), và các ứng dụng thực tế trong marketing, an ninh mạng và nghiên cứu xã hội. Các thuật toán này có thể được sử dụng để giải quyết nhiều bài toán thực tế khác nhau.

6.2. Các hướng nghiên cứu tiềm năng trong tương lai

Các hướng nghiên cứu trong tương lai bao gồm phát triển các thuật toán hiệu quả hơn cho các đồ thị mạng xã hội lớn, xây dựng các độ đo đánh giá chất lượng toàn diện hơn, nghiên cứu các phương pháp xử lý các cộng đồng chồng lấp và động, và ứng dụng phát hiện cộng đồng vào các lĩnh vực thực tế khác nhau. Đặc biệt, cần chú trọng đến việc phát triển các thuật toán có khả năng xử lý big data analytics và tận dụng sức mạnh của machine learning cho mạng xã hội.

Trích đoạn nội dung tài liệu

Chương 1 Tổng quan về đồ thị mạng xã hội và bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội Đồ thị là công cụ phổ biến và quan trọng để biểu diễn mạng xã hội. Chương này giới thiệu một cách tổng quan những vấn đề lý thuyết liên quan đến đồ thị, đồ thị mạng xã hội, đến cấu trúc cộng đồng của mạng xã hội, các phương pháp phát hiện cấu trúc cộng đồng, các độ đo thường sử dụng trong quá trình phân tích, các tiêu chuẩn thường được áp dụng để đánh giá chất lượng cấu trúc cộng đồng, làm cơ sở cho việc đánh giá hiệu quả của các thuật toán đề xuất ở các chương sau.1 Giới thiệu chung Dữ liệu lớn tạo ra một sự bùng nổ các phương pháp, các kỹ thuật, các công nghệ khai phá dữ liệu và phát hiện tri thức, một phần bởi kích thước thông tin rất lớn, một phần bởi thông tin đa dạng, mở rộng hơn về các chủng loại phi cấu trúc và nội dung của dữ liệu. Đồ thị là công cụ đơn giản và hiệu quả giúp đặc tả thế giới vô cùng phong phú xung quanh ta. Ta có thể gặp hình thức biểu diễn bằng đồ thị cho hầu hết các sự vật, hiện tượng trong tự nhiên và xã hội.

Cấu trúc dữ liệu đồ thị là một tập hợp 9 các nút có dữ liệu và được kết nối với các nút khác. Đồ thị chứa đỉnh (đại diện cho các đối tượng) và các cạnh nối các đỉnh (đại diện cho mối quan hệ giữa các đối tượng). Đồ thị được sử dụng trong vô vàn lĩnh vực nghiên cứu, từ khai phá dữ liệu, xử lý ngôn ngữ tự nhiên, mô phỏng thế giới thực, đến phân tích mạng xã hội và khai thác thông tin,. Về mặt lý thuyết, người ta thường đồng nhất mô hình dữ liệu đồ thị với khái niệm hệ thống mạng và mạng xã hội.1 Cấu trúc dữ liệu đồ thị có mặt ở khắp nơi: Mạng đồng biểu hiện; mạng xã hội; các luồng chương trình; trong hợp chất hóa học và cấu trúc protein,.

Bản thân mỗi đồ thị còn có thể hàm chứa rất nhiều thông tin giá trị cho các ứng dụng thực tiễn, vì vậy khai phá dữ liệu thực hiện tìm kiếm tri thức từ đó cũng là đòi hỏi đặt ra hết sức hấp dẫn và cấp thiết, đặc biệt 10 trong những thập kỷ gần đây. Khai phá đồ thị là một nhánh nghiên cứu trong khai phá dữ liệu. Đó là một trong những cách tiếp cận mới để khai thác tập dữ liệu được biểu thị bằng cấu trúc đồ thị. Khai phá đồ thị xuất hiện trong nhiều ứng dụng của các lĩnh vực xã hội, tự nhiên, bao gồm: tin sinh học, phản ứng hóa học, cấu trúc dòng chương trình, mạng máy tính, mạng xã hội,.

Trong khai phá dữ liệu đồ thị, việc phát hiện cấu trúc cộng đồng là một nhiệm vụ phổ biến và quan trọng bậc nhất, song cũng đầy thách thức, đặc biệt khi quy mô của đồ thị mạng xã hội ngày càng trở nên to lớn. Đã có nhiều thuật toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội được đề xuất, nhưng hầu hết chưa thực sự mang lại hiệu quả đối với các đồ thị mạng xã hội quy mô lớn. Luận án thực hiện đề xuất một số thuật toán mới phát hiện cấu trúc cộng đồng, bao gồm cả phát hiện cấu trúc cộng đồng rời nhau và cấu trúc cộng đồng chồng chéo.2 Mạng xã hội và đồ thị mạng xã hội 1.1 Mạng xã hội Theo Fortunato và các cộng sự [24] 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ụ,.

Khi nghiên cứu về mạng xã hội, người ta còn gọi các thực thể này là các tác nhân (agent), bởi tính tương tác và ảnh hưởng của chúng đối với môi trường xung quanh (ít nhất là với các láng giềng của chúng). Các tác nhân luôn có xu hướng liên kết với nhau (có thể dựa trên tính tương đồng trong sự lựa chọn nào đó, hoặc mối quan hệ khăng khít về một lĩnh vực nào đó, hoặc sự đồng cảm theo sở thích/không thích, .) trong một nền tảng được chia sẻ và tạo thành các cụm ảo hoặc cộng đồng.2 Một số đặc tính của mạng xã hội Mạng xã hội có những đặc tính cơ bản [10, 11, 103] sau: • Dựa vào người dùng (User-based): Các mạng xã hội trực tuyến (Face- book, Twitter, Youtube,. ) đượ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 mở rộng các nội dung trao đổi, thảo luận với nhau trên mạng.

Nội dung đó được xác định bởi bất kỳ ai có tham gia vào tổ chức. • Tương tác (Interactive): Mạng xã hội hiện đại gồm các tác nhân thường xuyên tương tác thông qua các mối liên kết với nhau. 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,. mà còn chứa các dịch vụ, chơi trò chơi, quảng cáo, tiếp thị, bán hàng online, quảng bá thông tin,.

Vì vậy, mạng xã hội càng ngày càng trở nên chuẩn mực, phổ biến, hấp dẫn và thu hút người dùng nhiều hơn bởi tính năng tương tác vượt trội so với sử dụng Internet thông thường. • Hướng đến cộng đồng (Community-driven): Mạng xã hội thể hiện hiệu ứng cộng đồng mạnh mẽ. Đó là, một nhóm những người có xu hướng tương tác với nhau nhiều hơn những người bên ngoài nhóm. Phát hiện các nhóm gắn kết trong một mạng xã hội (được gọi là phát hiện cấu trúc cộng đồng, gọi tắt là cộng đồng) là một vấn đề quan trọng và cốt lõi trong phân tích mạng xã hội.

• Các mối quan hệ (Relationships): Các mạng xã hội phát triển mạnh mẽ về các mối quan hệ. Càng có nhiều mối quan hệ trong mạng, các tác nhân càng thiết lập được vai trò trung tâm của mạ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ý, 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. • Cảm xúc về nội dung (Emotion over content): Đặc điểm độc đáo của mạng xã hội là yếu tố cảm xúc và nhạy cảm.

Ngày nay, các trang web 12 thực sự mang đến cho người dùng về mặt cảm xúc và cảm giác rằng mối quan hệ, như bạn bè của họ luôn ở trong phạm vi kiểm soát. Khi mạng xã hội ngày càng trở nên phổ biến và nổi bật, câu hỏi rõ ràng đầu tiên đặt ra là: làm thế nào để trích xuất được những thông tin, tri thức có ý nghĩa từ những dữ liệu này? Để tìm kiếm câu trả lời, đòi hỏi phải có những phương pháp nghiên cứu và kỹ thuật phân tích phù hợp, hiệu quả nhất.3 Đồ thị mạng xã hội và cấu trúc cộng đồng của mạng xã hội Mạng xã hội thường được biểu diễn dưới dạng đồ thị liên thông, trong đó các tác nhân (cá nhân hoặc một tổ chức) được biểu diễn bằng các nút (đỉnh) và các kết nối giữa các tác nhân được thể hiện bằng liên kết hoặc các cạnh (cung) [37, 92, 80, 81]. Đồ thị mạng xã hội là đồ thị G = (V, E) [92], trong đó V là tập các nút (đỉnh) 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, tập E thể hiện mối quan hệ xã hội giữa các thành viên với nhau.

Đồ thị G = (V, E) là vô hướng nếu các cạnh (u, v) ∈ E không phân biệt thứ tự, ngược lại là đồ thị có hướng. Hai nút u và v trong đồ thị G được gọi là liền kề (lân cận) nếu (u, v) ∈ E , hoặc (v, u) ∈ E. Nếu e = (u, v) thì e gọi là cạnh liên thuộc với các nút u và v. Thông thường, đồ thị mạng xã hội là đồ thị đơn vô hướng và liên thông, ví dụ đồ thị mạng bạn bè trên 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 trên Twitter hoặc Google+. Việc phân tích đặc điểm tính chất của mỗi đồ thị mạng xã hội dựa nhiều vào lý thuyết đồ thị, bao gồm việc phân tích, xác định vai trò các nút và các cạnh trong đồ thị. Trong luận án có sử dụng một số định nghĩa và khái niệm cơ bản của lý thuyết đồ thị, cũng như hệ thống ký hiệu và cách biểu diễn thông thường cho một mạng xã hội theo các tài liệu tham khảo [92, 40, 66, 5]. Theo lý thuyết đồ thị, với đồ thị mạng xã hội G = (V, E), cấu trúc cộng đồng (community structure) [5] là một đồ thị con của G, có tập 13 đỉnh C là tập con các đỉnh của V, sao cho với mỗi đỉnh v ∈ C , có nhiều cạnh kết nối v với những đỉnh khác trong C (liên thông mạnh) và ít cạnh kết nối v với những đỉnh w khác thuộc V-C (liên thông yếu).

Định nghĩa rõ hơn về mặt hình thức cho cấu trúc cộng đồng mạng xã hội [92]: Với đồ thị mạng xã hội G = (V, E); V là tập các đỉnh, E là tập các cạnh E = {(u, v)|u, v ∈ V }. Các cấu trúc cộng đồng (cộng đồng) là tập các đồ thị con của G, kí hiệu là C = {C1 , C2 ,. , Ck }, trong đó Ci = (Vi , Ei ); i = 1. k thỏa mãn: (i) ∪ki=1 Vi = V và Vi ∩ Vj = ∅ với ∀i ̸= j = 1.

k ; (ii) ∪ki=1 Ei ⊆ E và |Ei | → max, |Eij | → min và |Ei | ≫ |Eij |, trong đó i, j = 1. k; Ei tập các cạnh của cộng đồng Ci ; Eij : Tập các cạnh nối các đỉnh của cộng đồng Ci với cộng đồng Cj ; kí hiệu ≫: lớn hơn rất nhiều. Nói cách khác một cấu trúc cộng đồng (gọi tắt là cộng đồng) được tạo ra bởi một tập hợp các tác nhân có tương tác thường xuyên với nhau hơn so với những tác nhân khác ngoài cộng đồng. Thực tế, cộng đồng có thể là một tập hợp các tác nhân như: bạn bè, đồng nghiệp, nhóm những người có cùng sở thích, cùng chuyên môn, cùng mối quan tâm,.

trên mạng xã hội.