Luận Văn Thạc Sĩ: Nghiên Cứu Độ Đo Trung Gian Và Thuật Toán Phát Hiện Cộng Đồng Trên Mạng Xã Hội

Luận văn thạc sĩ khám phá độ đo trung gian và thuật toán phát hiện cộng đồng trên mạng xã hội, ứng dụng trong phân tích mạng lưới hiệu quả.

• Tác giả: Dương Thị Tình
• Người hướng dẫn: PGS. Đoàn Văn Ban
• Trường học: Đạ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: Nghiên cứu độ đo trung gian và thuật toán phát hiện cộng đồng trên mạng xã hội
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Thái Nguyên

Tóm tắt

I. Mạng xã hội và các độ đo trên đồ thị mạng xã hội

Mạng xã hội là một cấu trúc xã hội được hình thành từ các thực thể kết nối với nhau qua các mối quan hệ. Phân tích mạng xã hội dựa trên lý thuyết đồ thị, trong đó các đỉnh đại diện cho các cá nhân hoặc nhóm, và các cạnh thể hiện mối quan hệ giữa họ. Cấu trúc cộng đồng trong mạng xã hội là một yếu tố quan trọng, giúp xác định cách mà các cá nhân tương tác và hình thành các nhóm. Việc hiểu rõ về cấu trúc cộng đồng và các độ đo trên đồ thị mạng xã hội là cần thiết để phát hiện và phân tích các cộng đồng. Các độ đo như hệ số cố kết, độ trung gian, và độ trung tâm của đỉnh là những công cụ hữu ích trong việc đánh giá tính chất của mạng xã hội. Theo Fortunato và các cộng sự, mạng xã hội không chỉ là một tập hợp các thực thể mà còn là một hệ thống phức tạp với nhiều mối quan hệ đa dạng. Việc phân tích các mối quan hệ này giúp hiểu rõ hơn về hành vi của người dùng trong mạng xã hội.

1.1 Cấu trúc cộng đồng mạng xã hội

Cấu trúc cộng đồng mạng xã hội được định nghĩa là một tập hợp các tác nhân tương tác với nhau thông qua các phương tiện truyền thông. Cộng đồng mạng xã hội có thể được mô tả như một nhóm các đỉnh trong đồ thị, nơi mà các đỉnh này có mật độ liên kết cao với nhau và ít liên kết với phần còn lại của mạng. Việc phát hiện các cộng đồng trong mạng xã hội không chỉ giúp hiểu rõ hơn về cấu trúc tổng thể mà còn cung cấp thông tin quý giá về hành vi của người dùng. Các ứng dụng của việc phát hiện cộng đồng bao gồm việc tư vấn thông tin, hiểu cấu trúc mạng xã hội, và ngăn chặn thông tin độc hại. Điều này cho thấy tầm quan trọng của việc nghiên cứu và phát hiện các cộng đồng trong mạng xã hội, đặc biệt trong bối cảnh hiện đại khi mà mạng xã hội ngày càng phát triển mạnh mẽ.

1.2 Các độ đo trên đồ thị mạng xã hội

Các độ đo trên đồ thị mạng xã hội là những công cụ quan trọng để phân tích và đánh giá các mối quan hệ trong mạng. Đồ thị mạng xã hội có thể được mô hình hóa dưới dạng G = (V, E), trong đó V là tập hợp các đỉnh và E là tập hợp các cạnh. Các độ đo như hệ số cố kết, độ trung gian, và độ trung tâm giúp xác định mức độ gắn kết và vai trò của từng thực thể trong mạng. Hệ số cố kết cho biết mức độ chặt chẽ của các mối quan hệ trong mạng, trong khi độ trung gian cho thấy vai trò của một đỉnh trong việc kết nối các đỉnh khác. Việc áp dụng các độ đo này không chỉ giúp phân tích cấu trúc mạng xã hội mà còn hỗ trợ trong việc phát hiện các cộng đồng và hiểu rõ hơn về hành vi của người dùng trong mạng xã hội.

II. Thuật toán phát hiện cộng đồng mạng xã hội

Phát hiện cộng đồng trong mạng xã hội là một lĩnh vực nghiên cứu quan trọng, với nhiều thuật toán được phát triển để giải quyết bài toán này. Các thuật toán như Girvan-Newman và k-clique là những phương pháp phổ biến trong việc phát hiện cộng đồng. Thuật toán Girvan-Newman hoạt động dựa trên việc loại bỏ các cạnh có độ trung gian cao, từ đó xác định các cộng đồng trong mạng. Trong khi đó, thuật toán k-clique tìm kiếm các nhóm có k đỉnh kết nối với nhau. Việc áp dụng các thuật toán này giúp phát hiện các cộng đồng có cấu trúc mạnh mẽ và cung cấp cái nhìn sâu sắc về cách mà các cá nhân tương tác trong mạng xã hội. Các nghiên cứu cho thấy rằng việc phát hiện cộng đồng không chỉ có giá trị trong lĩnh vực khoa học máy tính mà còn có ứng dụng rộng rãi trong các lĩnh vực khác như xã hội học, kinh tế và sinh học.

2.1 Bài toán phát hiện cộng đồng trên đồ thị mạng xã hội

Bài toán phát hiện cộng đồng trên đồ thị mạng xã hội liên quan đến việc xác định các nhóm các đỉnh có mối liên hệ chặt chẽ với nhau. Các thuật toán phát hiện cộng đồng thường được phân loại thành hai nhóm chính: dựa trên độ đo và dựa trên tối ưu hóa. Các thuật toán dựa trên độ đo sử dụng các chỉ số như độ trung gian và độ cố kết để xác định các cộng đồng, trong khi các thuật toán tối ưu hóa tìm kiếm cấu trúc cộng đồng bằng cách tối ưu hóa một hàm mục tiêu. Việc phát hiện cộng đồng giúp hiểu rõ hơn về cấu trúc mạng xã hội và hành vi của người dùng, từ đó có thể áp dụng vào các lĩnh vực như marketing, phân tích dữ liệu và nghiên cứu xã hội.

2.2 Đánh giá thuật toán phát hiện cộng đồng

Đánh giá hiệu quả của các thuật toán phát hiện cộng đồng là một phần quan trọng trong nghiên cứu. Các tiêu chí đánh giá thường bao gồm độ chính xác, độ nhạy và khả năng mở rộng của thuật toán. Việc so sánh các thuật toán khác nhau giúp xác định phương pháp nào là hiệu quả nhất trong việc phát hiện cộng đồng trong các mạng xã hội khác nhau. Các nghiên cứu đã chỉ ra rằng không có một thuật toán nào hoàn hảo cho tất cả các loại mạng, do đó việc lựa chọn thuật toán phù hợp với đặc điểm của mạng là rất quan trọng. Điều này cho thấy sự cần thiết phải phát triển các phương pháp mới và cải tiến các thuật toán hiện có để đáp ứng nhu cầu ngày càng cao trong việc phân tích mạng xã hội.

III. Ứng dụng thuật toán Girvan Newman trong phát hiện cộng đồng mạng xã hội

Thuật toán Girvan-Newman là một trong những phương pháp nổi bật trong việc phát hiện cộng đồng mạng xã hội. Thuật toán này hoạt động bằng cách loại bỏ các cạnh có độ trung gian cao, từ đó xác định các cộng đồng trong mạng. Việc áp dụng thuật toán này cho phép phát hiện các nhóm có mối liên hệ chặt chẽ, giúp hiểu rõ hơn về cấu trúc mạng xã hội. Các nghiên cứu thực nghiệm cho thấy rằng thuật toán Girvan-Newman có thể áp dụng hiệu quả trên nhiều loại dữ liệu khác nhau, từ mạng xã hội đến mạng sinh học. Điều này chứng tỏ giá trị thực tiễn của thuật toán trong việc phân tích và phát hiện cộng đồng.

3.1 Mô tả bài toán phát hiện cộng đồng mạng xã hội

Bài toán phát hiện cộng đồng mạng xã hội liên quan đến việc xác định các nhóm các đỉnh có mối liên hệ chặt chẽ với nhau. Thuật toán Girvan-Newman cung cấp một cách tiếp cận hiệu quả để giải quyết bài toán này. Bằng cách loại bỏ các cạnh có độ trung gian cao, thuật toán giúp xác định các cộng đồng trong mạng. Việc áp dụng thuật toán này không chỉ giúp phát hiện các cộng đồng mà còn cung cấp cái nhìn sâu sắc về cách mà các cá nhân tương tác trong mạng xã hội.

3.2 Chương trình phát hiện cộng đồng mạng xã hội

Chương trình phát hiện cộng đồng mạng xã hội dựa trên thuật toán Girvan-Newman đã được triển khai và thử nghiệm trên nhiều bộ dữ liệu khác nhau. Kết quả cho thấy rằng chương trình có khả năng phát hiện các cộng đồng một cách chính xác và hiệu quả. Việc sử dụng chương trình này không chỉ giúp phát hiện cộng đồng mà còn hỗ trợ trong việc phân tích hành vi của người dùng trong mạng xã hội. Điều này mở ra nhiều cơ hội nghiên cứu mới trong lĩnh vực phân tích mạng xã hội.

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

CHƯƠNG 1 MẠNG XÃ HỘI VÀ CÁC ĐỘ ĐO TRÊN ĐỒ THỊ MẠNG XÃ HỘI 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 thông qua các mối quan hệ, mối liên kết,. Phân tích mạng xã hội là xem xét các mối quan hệ xã hội dựa vào lý thuyết đồ thị bao gồm các đỉnh và các cạnh (còn được gọi là các liên kết hoặc kết nối). Các đỉnh được xem là những cộng đồng riêng lẻ trên mạng, và các cạnh là các mối quan hệ giữa các cộng đồng. Cộng đồng mạng xã hội là một tập hợp các cá nhân (tác nhân, thực thể) tương tác với nhau thông qua các phương tiện truyền thông cụ thể, có khả năng vượt qua những ranh giới địa lý và chính trị để theo đuổi lợi ích hay mục tiêu chung.

Chương này giới thiệu khái quát về mạng xã hội và các độ đo phúc vụ cho phân tích, phát hiện cộng đồng trên đồ thị 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 xã hội được tạo ra từ các thực thể, tác nhân (actor) 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 [3], [4], [27]. Theo Fortunato và các cộng sự [25] 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, các dịch vụ, … Mạng 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 [11], [25], [26]:  Dựa vào người dùng (User-based): Trước khi các mạng xã hội như Facebook hoặc MySpace 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 các khách truy cập Internet 5 để đọc, tham khảo thông tin. Không có người dùng, mạng sẽ là một không gian trống chứa đầy các diễn đàn, ứng dụng và phòng trò chuyện trố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. Đây là những gì làm cho các mạng xã hội trở nên thú vị và năng động hơn nhiều đố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, …, các trang web như Facebook còn chứa đầy các ứng dụng chơi trò chơi, quảng cáo, bán hàng online, phổ biến tin tức, … Các mạng xã hội trở thành trò tiêu khiển mà nhiều người dùng lựa chọn nhiều hơn trên 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 và đó 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à giống như 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ó niềm tin hoặc sở thích chung, có chung đ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 đó.

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). Đồ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ộ, …  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ứ 6 tập trung chủ yếu vào việc cung cấp thông tin cho khách 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. Trong mạng có nhiều kiểu liên kết như liên kết vô hướng, liên kết một chiều, liên kết hai chiều, … Ta có thể biểu diễn mạng mạng xã hội bằng một đồ thị (được gọi là đồ thị mạng xã hội) mà các thực thể được biểu diễn bởi các đỉnh, còn các liên kết được biểu diễn bởi các cạnh.

Trong đó với hai đỉnh A và B có cạnh nối với nhau là thể hiện mối quan hệ giữa chúng. Ngoài ra, các liên kết này còn có thể đánh trọng số để biểu diễn độ mạnh yếu của mối liên kết. Mạng xã hội phát triển rất nhanh chóng, với số lượng người tham gia và mối quan hệ với nhau rất lớn đòi hỏi phải có những phương pháp nghiên cứu phù hợp về mạng xã hội. Mạng xã hội Facebook là mạng xã hội được coi là phổ biến nhất hiện nay, Facebook là mạng xã hội miễn phí do công ty Facebook Inc điều hành.

Người sử dụng có thể tham gia các mạng lưới được tổ chức theo thành phố, nơi làm việc, trường học và khu vực để liên kết và giao tiếp với người khác trên thế giới. mọi người đều có thể kết bạn và gửi tin nhắn cho nhau, và cập nhật thông tin của mình cho bạn bè biết. Tên của Facebook nhắc tới những cuốn sổ lưu niệm dùng để ghi tên những thành viên của cộng đồng campus mà một số trường đại học và cao đẳng tại Mỹ đưa cho các sinh viên mới vào trường, phòng ban, và nhân viên để có thể làm quen với nhau trong khuôn viên trường. Mạng xã hội Facebook Zing me là một trong những mạng xã hội phố biến hiện nay tại Việt Nam, nó có khả năng kết nối người dùng trên phạm vi rộng lớn, đồng thời khi sử dụng bạn có thể tham gia các trò chơi, tiện ích, tính năng kết nối cộng đồng mà ứng dụng đang sở hữu.

Ngoài ra ở Việt Nam còn có thể kể đến mạng xã hội Zalo. Mạng xã hội Zing me 8 Trên mạng, một số đỉnh 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 vài cạnh khác. Tính chất đó của các mạng trên thực tế được gọi là tính cộng đồng (community) [1], [9]. Đây là một tính chất quan trọng của mạng xã hội và đang ngày càng được nhiều người quan tâm nghiên cứu, phân tích cấu trúc cộng đồng của mạng xã hội bởi tần quan trọng của chúng.

Khả năng phát hiện và phân tích các cộng đồng sẽ cung cấp cho chúng ta những sự giúp đỡ vô giá để hiểu biết và hình dung được những cấu trúc, tính chất đặc trưng của mạng xã hội. Cấu trúc cộng đồng mạng xã hội Cấu trúc cộng đồng mạng xã hội (Community social structure) gọi tắt là cộng đồng mạng xã hội là một tập hợp các tác nhân tương tác thông qua các phương tiện truyền thông cụ thể, có khả năng vượt qua những ranh giới địa lý và chính trị để theo đuổi lợi ích hay mục tiêu chung. Cộng đồng là một nhóm các thực thể có những tính chất tương tự nhau, liên kết chặt chẽ với nhau hơn và cùng đóng một vai trò nhất định trong mạng xã hội. Một cộng đồng được mô tả như một nhóm các đỉnh (đồ thị con) cùng chia sẻ các thuộc tính chung hoặc đóng vai trò tương tự trong một mạng.

Một cộng đồng có thể được định nghĩa là một tập hợp các đỉnh có mật độ liên kết giữa các đỉnh cao và mật độ liên kết thấp với phần còn lại của mạng. Nói một cách khác một 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 cá nhân khác ngoài cộng đồng. Do vậy, nó thường là một tập hợp 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, mối quan tâm, … [1], [3], [9], [14], [26],. hiển thị các thành phần kết nối lớn nhất trong mạng lưới các cộng tác nghiên cứu của các nhà khoa học làm việc tại Viện Santa Fe (SFI).

Đồ 9 thị bao gồm 118 đỉnh đại diện cho các nhà khoa học làm việc tại SFI và các cộng tác viên của họ. Các cạnh được liên kết giữa các nhà khoa học khi họ đã công bố cùng với nhau ít nhất một bài báo. Ở mạng này ta quan sát được một số cộng đồng, mỗi cộng đồng biểu hiện cho những tác giả đã cùng nhau công bố một hay nhiều bài báo khoa học. Mặt khác ta cũng thấy giữa các cộng đồng trong mạng trên chỉ có một số ít mối liên kết.

Các đỉnh cùng màu là cùng một cộng đồng theo các lĩnh vực nghiên cứu của SFI. Mô hình mạng lưới cộng tác của các nhà khoa học làm việc tại SFI Trong mạng xã hội, việc trích xuất, phát hiện được những cấu trúc cộng đồng là rất hữu ích vì nó giúp chúng ta nghiên cứu được cấu trúc tổng thể của mạng. Khái niệm của khám phá, phát hiện cộng đồng tương tự như phân vùng (phân cụm) đồ thị nhưng có một số khác biệt như trong phân vùng đồ thị, số lượng nhóm và kích thước của chúng đã được biết trước, nhưng trong trường hợp phát hiện ra cộng đồng, chúng ta không biết về số lượng cộng đồng trong mạng và cộng đồng cũng có thể không cùng kích cỡ với nhau. 10 Một số ứng dụng chính của bài toán phát hiện cộng đồng mạng xã hội [1], [3], [4] , [14], [25] là: - Phát hiện cộng đồng có thể được sử dụng trong tư vấn thông tin và xác định được những cộng đồng có cùng một số quan tâm, sở thích tương tự.

- Cộng đồng cũng sẽ giúp chúng ta hiểu cấu trúc của mạng xã hội, làm rõ các thuộc tính và chức năng của mạng. - Phát hiện các cộng đồng để hiểu hành vi của mạng xã hội trong quy mô lớn vì nó sẽ làm rõ các quá trình chia sẻ thông tin và truyền bá thông tin. - Các phương pháp phát hiện cộng đồng có lợi thế lớn trong việc định tuyến nhận thức trong xã hội và ngăn chặn thông tin độc hại trên mạng xã hội.