Luận văn thạc sĩ về độ đo trung gian và thuật toán phát hiện cộng đồng trong mạng xã hội

Khám phá luận văn thạc sĩ về độ đ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 và ý nghĩa trong nghiên cứu.

• Tác giả: Dương Thị Tình
• Người hướng dẫn: PGS. Đ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: 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

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỞ ĐẦU
• 0.1. Lý do chọn đề tài
• 0.2. Mục đích nghiên cứu
• 0.3. Đối tượng nghiên cứu
• 0.4. Phạm vi nghiên cứu
• 0.5. Ý nghĩa khoa học
• 0.6. Phương pháp nghiên cứu
• 0.7. Cấu trúc đề tài
• 1. CHƯƠNG 1: MẠNG XÃ HỘI VÀ CÁC ĐỘ ĐO TRÊN ĐỒ THỊ MẠNG XÃ HỘI
• 1.1. Cấu trúc cộng đồng mạng xã hội
• 1.2. Mạng xã hội
• 1.3. Cấu trúc cộng đồng mạng xã hội
• 1.4. Các độ đo trên đồ thị mạng xã hội
• 2. CHƯƠNG 2: THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI
• 2.1. Bài toán phát hiện cộng đồng trên đồ thị mạng xã hội
• 2.2. Thuật toán phân cụm phân cấp
• 2.3. Thuật toán phát hiện cộng đồng dựa trên tối ưu hóa độ đo đơn thể
• 2.4. Thuật toán phát hiện cộng đồng dựa vào độ đo trung gian
• 2.5. Phát hiện các cộng đồng gối nhau
• 2.5.1. Phát hiện các k-cliques trong mạng xã hội
• 2.5.2. Thuật toán phát hiện k-clique. Thuật toán EAGLE
• 2.5.3. Đánh giá thuật toán
• 2.6. Kết luận chương 2
• 3. CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN GIRVAN-NEWMAN TRONG PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI
• 3.1. Mô tả bài toán phát hiện cộng đồng mạng xã hội
• 3.2. Chương trình phát hiện cộng đồng mạng xã hội
• 3.2.1. Bộ cơ sở dữ liệu
• 3.2.2. Môi trường thử nghiệm
• 3.2.3. Thử nghiệm và đánh giá
• 3.3. Kết luận chương 3
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về nghiên cứu độ đo trung gian và phát hiện cộng đồng trên mạng xã hội

Nghiên cứu độ đo trung gian và phát hiện cộng đồng trên mạng xã hội là một lĩnh vực đang thu hút sự quan tâm lớn từ các nhà khoa học. Mạng xã hội không chỉ là nơi kết nối con người mà còn là một nguồn dữ liệu phong phú cho việc phân tích hành vi và tương tác. Độ đo trung gian giúp xác định vai trò của các nút trong mạng, trong khi phát hiện cộng đồng giúp nhận diện các nhóm có mối quan hệ chặt chẽ. Việc hiểu rõ về cấu trúc này có thể mang lại nhiều lợi ích cho các lĩnh vực như marketing, xã hội học và khoa học máy tính.

1.1. Định nghĩa và vai trò của độ đo trung gian trong mạng xã hội

Độ đo trung gian là một chỉ số quan trọng trong phân tích mạng xã hội. Nó giúp xác định mức độ ảnh hưởng của một nút trong việc kết nối các nút khác. Cụ thể, độ đo trung gian của một nút càng cao, nó càng có khả năng kiểm soát thông tin trong mạng. Điều này có thể được áp dụng trong nhiều lĩnh vực như truyền thông, marketing và nghiên cứu xã hội.

1.2. Khái niệm cộng đồng trong mạng xã hội và tầm quan trọng của nó

Cộng đồng trong mạng xã hội được định nghĩa là nhóm các cá nhân có mối quan hệ chặt chẽ với nhau. Việc phát hiện cộng đồng giúp hiểu rõ hơn về cấu trúc mạng và hành vi của người dùng. Các cộng đồng này có thể ảnh hưởng đến cách thức thông tin được chia sẻ và lan truyền trong mạng xã hội.

II. Các thách thức trong nghiên cứu độ đo trung gian và phát hiện cộng đồng

Mặc dù nghiên cứu độ đo trung gian và phát hiện cộng đồng mang lại nhiều lợi ích, nhưng cũng gặp phải không ít thách thức. Một trong những thách thức lớn nhất là sự phức tạp của dữ liệu mạng xã hội. Dữ liệu này thường không đồng nhất và có thể chứa nhiều thông tin không chính xác. Hơn nữa, việc xác định các cộng đồng trong mạng xã hội cũng không đơn giản, vì các cộng đồng có thể chồng chéo và thay đổi theo thời gian.

2.1. Sự phức tạp của dữ liệu mạng xã hội

Dữ liệu mạng xã hội thường rất lớn và đa dạng, bao gồm nhiều loại thông tin khác nhau. Điều này tạo ra khó khăn trong việc phân tích và khai thác thông tin. Các nhà nghiên cứu cần phát triển các phương pháp mới để xử lý và phân tích dữ liệu này một cách hiệu quả.

2.2. Vấn đề xác định cộng đồng trong mạng xã hội

Việc xác định cộng đồng trong mạng xã hội là một thách thức lớn. Các cộng đồng có thể không rõ ràng và có thể chồng chéo lên nhau. Điều này đòi hỏi các thuật toán phát hiện cộng đồng phải có khả năng xử lý các mối quan hệ phức tạp giữa các nút trong mạng.

III. Phương pháp nghiên cứu độ đo trung gian trong mạng xã hội

Để nghiên cứu độ đo trung gian, có nhiều phương pháp khác nhau được áp dụng. Một trong những phương pháp phổ biến là sử dụng các thuật toán đồ thị để tính toán độ đo trung gian cho từng nút trong mạng. Các thuật toán này giúp xác định vai trò của các nút trong việc kết nối các phần khác nhau của mạng xã hội.

3.1. Thuật toán tính độ đo trung gian

Có nhiều thuật toán khác nhau để tính độ đo trung gian, như thuật toán Betweenness Centrality. Thuật toán này tính toán số lượng đường đi ngắn nhất giữa các cặp nút đi qua một nút cụ thể. Điều này giúp xác định mức độ trung gian của nút trong mạng.

3.2. Ứng dụng của độ đo trung gian trong phân tích mạng xã hội

Độ đo trung gian có thể được áp dụng trong nhiều lĩnh vực khác nhau, từ marketing đến nghiên cứu xã hội. Nó giúp các nhà nghiên cứu hiểu rõ hơn về cách thức thông tin được truyền tải và ảnh hưởng của các nút trong mạng đến hành vi của người dùng.

IV. Phương pháp phát hiện cộng đồng trong 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. Có nhiều phương pháp khác nhau được phát triển để xác định các cộng đồng trong mạng. Các phương pháp này thường dựa trên lý thuyết đồ thị và các thuật toán phân cụm.

4.1. Các thuật toán phát hiện cộng đồng phổ biến

Một số thuật toán phát hiện cộng đồng phổ biến bao gồm thuật toán Girvan-Newman và Louvain. Các thuật toán này giúp xác định các nhóm có mối quan hệ chặt chẽ trong mạng xã hội, từ đó giúp hiểu rõ hơn về cấu trúc của mạng.

4.2. Đánh giá hiệu quả của các 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à rất quan trọng. Các nhà nghiên cứu thường sử dụng các chỉ số như độ chính xác và độ bao phủ để đánh giá khả năng của các thuật toán trong việc phát hiện các cộng đồng thực sự trong mạng.

V. Ứng dụng thực tiễn của nghiên cứu độ đo trung gian và phát hiện cộng đồng

Nghiên cứu độ đo trung gian và phát hiện cộng đồng có nhiều ứng dụng thực tiễn trong đời sống. Các ứng dụng này không chỉ giúp cải thiện các chiến lược marketing mà còn hỗ trợ trong việc quản lý thông tin và phân tích hành vi người dùng trên mạng xã hội.

5.1. Ứng dụng trong marketing và quảng cáo

Các doanh nghiệp có thể sử dụng độ đo trung gian để xác định các influencer trong mạng xã hội. Điều này giúp họ tối ưu hóa chiến lược marketing và quảng cáo, từ đó tăng cường hiệu quả tiếp cận khách hàng.

5.2. Ứng dụng trong nghiên cứu xã hội

Nghiên cứu độ đo trung gian và phát hiện cộng đồng cũng có thể được áp dụng trong các nghiên cứu xã hội. Nó giúp các nhà nghiên cứu hiểu rõ hơn về hành vi và mối quan hệ giữa các cá nhân trong xã hội, từ đó đưa ra các giải pháp phù hợp.

VI. Kết luận và hướng phát triển tương lai trong nghiên cứu

Nghiên cứu độ đo trung gian và phát hiện cộng đồng trên mạng xã hội đang ngày càng trở nên quan trọng. Với sự phát triển không ngừng của công nghệ thông tin, các phương pháp và công cụ mới sẽ tiếp tục được phát triển để cải thiện khả năng phân tích và khai thác dữ liệu mạng xã hội. Hướng phát triển tương lai có thể bao gồm việc áp dụng trí tuệ nhân tạo và học máy trong phân tích mạng xã hội.

6.1. Xu hướng phát triển công nghệ trong nghiên cứu mạng xã hội

Công nghệ trí tuệ nhân tạo và học máy đang mở ra nhiều cơ hội mới trong nghiên cứu mạng xã hội. Các phương pháp này có thể giúp cải thiện độ chính xác và hiệu quả trong việc phát hiện cộng đồng và tính toán độ đo trung gian.

6.2. Tương lai của nghiên cứu độ đo trung gian và phát hiện cộng đồng

Nghiên cứu độ đo trung gian và phát hiện cộng đồng sẽ tiếp tục phát triển và đóng vai trò quan trọng trong việc hiểu rõ hơn về hành vi người dùng trên mạng xã hội. Các nhà nghiên cứu cần tiếp tục khám phá và phát triển các phương pháp mới để đáp ứng nhu cầu ngày càng cao trong lĩnh vực này.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của kỷ nguyên số đã thúc đẩy mạng xã hội phát triển với tốc độ trên 25% mỗi năm, tạo ra những cấu trúc đồ thị khổng lồ với hàng triệu thực thể và liên kết phức tạp. Trong bối cảnh nguồn dữ liệu trực tuyến tăng trưởng không ngừng, việc phân tích và khai phá các thuộc tính mạng lưới trở thành bài toán cấp thiết nhưng gặp nhiều thách thức do hạn chế về thuật toán xử lý dữ liệu quy mô lớn. Đặc trưng bản chất nhất của mạng xã hội chính là tính cộng đồng, nơi các cá nhân tương tác chặt chẽ vượt qua rào cản địa lý để chia sẻ mối quan tâm chung.

Nghiên cứu của tác giả Dương Thị Tình tại Trường Đại học Công nghệ Thông tin và Truyền thông thuộc Đại học Thái Nguyên (năm 2020) tập trung giải quyết bài toán phát hiện cấu trúc cộng đồng mạng xã hội thông qua việc phân tích chuyên sâu các độ đo đồ thị. Mục tiêu trọng tâm của đề tài gồm ba phần: khảo sát bản chất cấu trúc cộng đồng trên đồ thị mạng xã hội, nghiên cứu hệ thống các độ đo trung tâm và độ đo trung gian, và hiện thực hóa chương trình phát hiện cộng đồng dựa trên thuật toán phân tách Girvan-Newman cùng các kỹ thuật nhận diện cộng đồng gối nhau như k-clique và EAGLE.

Phạm vi thực nghiệm của luận văn bao quát từ các mạng lưới mô phỏng nhỏ từ 7 đỉnh đến các bộ dữ liệu thực tế kinh điển có quy mô hơn 1.000 liên kết. Kết quả nghiên cứu mang lại ý nghĩa khoa học và thực tiễn sâu sắc, cung cấp giải pháp nhận diện chính xác 100% các cụm cộng đồng chuẩn, đồng thời tối ưu hóa hơn 60% thời gian xử lý khi tích hợp thuật toán tính nhanh độ đo trung gian của Brandes, tạo tiền đề vững chắc cho các ứng dụng định tuyến thông tin, phân khúc người dùng và ngăn chặn tin tức độc hại trên không gian mạng.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng lý thuyết đồ thị vô hướng G = (V, E), trong đó tập đỉnh V biểu diễn các tác nhân mạng xã hội và tập cạnh E biểu diễn các mối quan hệ tương tác. Cấu trúc mạng được mô hình hóa toán học qua ma trận kề A kích thước n x n với n = |V|. Để định lượng đặc trưng mạng lưới, luận văn áp dụng hệ thống 5 độ đo then chốt:

Hệ số cố kết mạng (Cohesion Density) xác định mức độ gắn kết tổng thể qua tỷ lệ giữa số liên kết thực tế k và tổng số liên kết lý thuyết tối đa, tính theo công thức DG = 2k / (n(n - 1)) với giá trị dao động từ 0.00 đến 1.00.

Độ đo trung tâm vector đặc trưng (Eigenvector Centrality) đánh giá vị thế và tầm ảnh hưởng của một đỉnh dựa trên mức độ quan trọng của các đỉnh lân cận theo phương trình đệ quy tuyến tính.

Độ đo trung tâm trung gian của đỉnh (Node Betweenness Centrality) do Freeman đề xuất, đo lường tần suất một nút xuất hiện trên các đường đi ngắn nhất giữa tất cả các cặp đỉnh khác trong đồ thị, thể hiện năng lực kiểm soát dòng chảy thông tin.

Độ đo trung gian của cạnh (Edge Betweenness Centrality), giữ vai trò nòng cốt trong việc xác định các cầu nối (bridges) huyết mạch liên kết giữa các phân vùng cộng đồng khác nhau.

Lý thuyết cộng đồng gối nhau (Overlapping Communities) mở rộng với các khái niệm k-clique, k-club, k-clan và hàm mục tiêu đơn thể mở rộng EQ, cho phép một thực thể có thể đồng thời thuộc về 2 hoặc nhiều nhóm xã hội khác nhau.

Phương pháp nghiên cứu

Nghiên cứu sử dụng nguồn dữ liệu thử nghiệm chuẩn quốc tế (Benchmark Datasets) gồm 5 tập dữ liệu đa dạng về quy mô: mạng đơn giản Simple Network (7 đỉnh), đồ thị phân cấp mô phỏng (23 đỉnh), mạng quan hệ xã hội loài cá heo Dolphin (62 đỉnh), câu lạc bộ Karate của Zachary (34 đỉnh, 78 cạnh), mạng lưới các đội bóng bầu dục đại học Mỹ Football (115 đỉnh, 613 cạnh) và tập dữ liệu thương mại điện tử Amazon Small.

Phương pháp chọn mẫu có chủ đích được áp dụng nhằm bao quát đầy đủ các hình thái mạng từ cấu trúc đồ thị thưa, đồ thị có phân cụm rõ ràng đến mạng có tính chất chồng lấn phức tạp. Về phương pháp phân tích, tác giả lựa chọn thuật toán duyệt theo chiều rộng BFS cải tiến của Brandes (Faster Algorithm for Betweenness Centrality - FABC). Lý do lựa chọn là vì thuật toán này sử dụng kỹ thuật tích lũy phụ thuộc (dependency accumulation), giúp tối ưu hóa không gian bộ nhớ ở mức O(|V| + |E|) và giảm độ phức tạp thời gian từ mức O(|V|^3) xuống O(|V| * |E|). Trên cơ sở đó, thuật toán Girvan-Newman tiến hành loại bỏ lặp các cạnh có độ trung gian lớn nhất để chia cắt đồ thị thành các cộng đồng riêng biệt. Toàn bộ quy trình nghiên cứu lý thuyết, thiết kế thuật toán và kiểm thử thực nghiệm được triển khai đồng bộ trong giai đoạn 2019 - 2020.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đã mang lại 3 phát hiện khoa học mang tính đột phá:

Thứ nhất, thuật toán Girvan-Newman đạt độ chính xác phân tách 100% trên bộ dữ liệu chuẩn Zachary Karate Club. Thuật toán đã phát hiện chính xác sự phân rã của câu lạc bộ thành 2 nhóm độc lập gồm 16 và 18 thành viên sau các biến cố nội bộ, hoàn toàn trùng khớp với dữ liệu thực tế lịch sử. Đối với tập dữ liệu giải đấu Football gồm 115 đỉnh, thuật toán phân chia chuẩn xác mạng lưới thành 12 cụm thi đấu với độ tương đồng đạt trên 95%.

Thứ hai, việc ứng dụng thuật toán Brandes (FABC) để tính toán độ trung gian cạnh đã rút ngắn thời gian tính toán hơn 60% so với phương pháp vét cạn cổ điển. Cấu trúc lưu trữ ngăn xếp và hàng đợi tối ưu giúp chương trình thực thi mượt mà trên các tập dữ liệu có hơn 600 liên kết mà không gây quá tải bộ nhớ RAM.

Thứ ba, nghiên cứu chứng minh rằng trên các mạng có tính chất chồng chéo phức tạp, thuật toán EAGLE vượt trội hơn hẳn so với thuật toán Girvan-Newman và thuật toán đơn thể hóa Newman. Cụ thể, trên đồ thị thực nghiệm 23 đỉnh, EAGLE với ngưỡng k = 3 và k = 4 đã bóc tách thành công các đỉnh giao thoa (như đỉnh 10, 11 và 12 cùng thuộc 2 cộng đồng khác nhau), trong khi các phương pháp phân cụm phân cấp truyền thống hoàn toàn thất bại trong việc mô tả hiện tượng đa vai trò này.

Thảo luận kết quả

Cơ chế hoạt động của thuật toán dựa trên nguyên lý: các cạnh nối giữa các cộng đồng luôn có mật độ các đường đi ngắn nhất đi qua cao hơn hẳn so với các cạnh nội bộ. Ví dụ, trên đồ thị 7 nút, cạnh nối B-D có độ trung gian đạt cực đại với 12 đường đi ngắn nhất đi qua (chiếm tỷ trọng áp đảo), do đó việc loại bỏ cạnh này ngay lập tức phân lập đồ thị thành 2 cụm hoàn chỉnh.

Quá trình phân cụm và kết quả nghiên cứu được trực quan hóa sinh động thông qua biểu đồ cây phân cấp (Dendrogram). Mỗi nhánh cắt trên cây thể hiện một bước loại bỏ cạnh cầu nối, giúp người phân tích quan sát rõ ràng quá trình tách cụm ở từng mức độ chi tiết. Đồng thời, các bảng số liệu so sánh chỉ số đơn thể Modularity Q (đạt giá trị từ 0.38 đến 0.65) khẳng định cấu trúc cộng đồng tìm được có mật độ liên kết nội cụm dày đặc hơn nhiều lần so với liên kết ngẫu nhiên.

So với thuật toán phân cụm Louvain hay thuật toán phân cụm phân cấp BIRCH, phương pháp Girvan-Newman tuy có chi phí thời gian O(m^2 * n) cao hơn nhưng mang lại độ tin cậy tuyệt đối về mặt cấu trúc và khả năng giải thích trực quan cao. Trong khi đó, việc kết hợp thuật toán EAGLE giúp bù đắp hoàn hảo hạn chế của Girvan-Newman trong việc xử lý các quan hệ gối nhau trong thực tế.

Đề xuất và khuyến nghị

Dựa trên kết quả thực nghiệm, luận văn đưa ra 4 khuyến nghị hành động cụ thể nhằm nâng cao hiệu quả phân tích dữ liệu mạng xã hội:

Nâng cấp hiệu năng tính toán thuật toán: Đội ngũ kỹ sư dữ liệu và các nhóm nghiên cứu cần tái cấu trúc thuật toán Girvan-Newman bằng kỹ thuật tính toán song song trên GPU và nền tảng tính toán phân tán Spark GraphX. Mục tiêu là xử lý mạng lưới quy mô trên 100.000 đỉnh trong thời gian dưới 120 giây, hoàn thành triển khai trong vòng 6 tháng.

Tích hợp thuật toán cộng đồng gối nhau vào hệ thống gợi ý: Các doanh nghiệp công nghệ và sàn thương mại điện tử cần ứng dụng thuật toán EAGLE và k-clique vào các công cụ gợi ý bạn bè và sản phẩm chéo. Giải pháp này giúp tăng độ chính xác của các thuật toán đề xuất thêm ít nhất 25%, với lộ trình thực hiện từ quý 1 đến quý 3 trong năm kế tiếp.

Xây dựng hệ sinh thái giám sát an ninh và ngăn chặn tin giả: Các trung tâm điều hành an toàn thông tin cần triển khai công cụ phát hiện cạnh trung gian để nhanh chóng cô lập các tài khoản cầu nối chuyên phát tán thông tin sai lệch, nâng tỷ lệ kiểm soát vùng lây nhiễm mã độc hoặc tin giả lên trên 90% trong vòng 12 tháng.

Chuẩn hóa bộ công cụ đánh giá thuật toán phân cụm đồ thị: Các trường đại học và viện nghiên cứu chuyên ngành khoa học máy tính cần ban hành khung kiểm thử tự động kết hợp giữa độ đo Modularity Q và chỉ số tương hỗ NMI, áp dụng đồng bộ cho 100% các đề tài nghiên cứu đồ thị từ năm 2021 trở đi.

Đối tượng nên tham khảo luận văn

Tài liệu luận văn là nguồn tư liệu học thuật và thực tiễn giá trị cao cho 4 nhóm đối tượng:

Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học máy tính: Luận văn cung cấp hệ thống công thức toán học chặt chẽ về lý thuyết đồ thị, kèm theo mã nguồn cài đặt chi tiết thuật toán FABC và Girvan-Newman phục vụ trực tiếp cho việc phát triển các đề tài luận văn thạc sĩ và tiến sĩ.

Kỹ sư dữ liệu và chuyên gia phân tích mạng xã hội (Social Network Analysts): Hỗ trợ trực tiếp trong việc phân khúc tự động hàng triệu người dùng trên Facebook, Zalo hoặc LinkedIn thành các nhóm khách hàng mục tiêu theo sở thích và hành vi tương tác thực tế.

Chuyên gia an ninh mạng và điều tra số: Cung cấp phương pháp luận sắc bén để nhận diện các nút trọng yếu, các mắt xích liên lạc ngầm trong mạng lưới viễn thông hoặc các kênh thông tin độc hại cần ngăn chặn kịp thời.

Nhà phát triển hệ thống gợi ý và khai phá dữ liệu (Recommendation System Developers): Giúp ứng dụng cấu trúc k-clique và thuật toán EAGLE để giải quyết triệt để bài toán phân tích người dùng có nhiều vai trò xã hội phức tạp.

Câu hỏi thường gặp

Độ đo trung gian của cạnh khác gì so với độ đo trung gian của đỉnh? Độ đo trung gian của đỉnh đo lường số lượng đường đi ngắn nhất đi qua một nút mạng cụ thể, phản ánh quyền lực điều phối thông tin của cá nhân. Trong khi đó, độ đo trung gian của cạnh tính toán số lượng đường đi ngắn nhất đi qua một liên kết, giúp phát hiện chính xác các cầu nối huyết mạch giữa các phân vùng cộng đồng độc lập (ví dụ cạnh nối B-D có 12 đường đi ngắn nhất chạy qua).

Tại sao thuật toán Girvan-Newman phải tính toán lại độ trung gian sau mỗi lần xóa cạnh? Sau khi loại bỏ một cạnh có độ trung gian lớn nhất, cấu trúc liên thông của toàn mạng bị thay đổi, dẫn đến sự chuyển hướng của hàng loạt các đường đi ngắn nhất còn lại. Việc tính toán lại độ trung gian đảm bảo xác định chính xác cầu nối tiếp theo, tránh việc xóa nhầm các cạnh nội bộ quan trọng.

Thuật toán EAGLE giải quyết hiện tượng cộng đồng chồng lấn như thế nào? EAGLE khởi tạo từ các cụm clique cực đại (đồ thị con đầy đủ có khoảng cách từ 1 đến k) thay vì từng đỉnh riêng lẻ. Thuật toán sử dụng hàm mục tiêu mở rộng EQ để hợp nhất các cụm và cho phép một đỉnh (như đỉnh 10, 11 trên đồ thị 23 nút) có thể thuộc về nhiều cộng đồng cùng lúc.

Thuật toán Girvan-Newman có áp dụng trực tiếp cho mạng xã hội hàng triệu người dùng được không? Do độ phức tạp thời gian đạt mức O(m^2 * n), thuật toán nguyên bản sẽ chạy rất chậm trên mạng hàng triệu nút. Trong thực tế, các chuyên gia sẽ áp dụng thuật toán Louvain để gom cụm thô trước, sau đó mới chạy Girvan-Newman trên từng phân vùng nhỏ để tinh chỉnh cấu trúc.

Làm thế nào để xác định điểm dừng tối ưu khi chia cắt đồ thị trong thuật toán Girvan-Newman? Người nghiên cứu theo dõi sự biến thiên của chỉ số đơn thể Modularity Q sau mỗi bước lặp loại bỏ cạnh. Quá trình chia tách sẽ dừng lại tại bước lặp mà giá trị Q đạt cực đại (thường nằm trong khoảng từ 0.3 đến 0.7), đảm bảo cấu trúc cộng đồng thu được là tối ưu nhất.

Kết luận

Nghiên cứu của tác giả Dương Thị Tình đã giải quyết toàn diện bài toán phát hiện cộng đồng mạng xã hội thông qua các đóng góp nổi bật:

• Hệ thống hóa toàn diện cơ sở lý thuyết về 5 độ đo đồ thị quan trọng và các mô hình phân cụm cộng đồng mạng xã hội hiện đại.
• Cài đặt thành công thuật toán tính nhanh độ trung gian FABC (Brandes), giúp tiết kiệm hơn 60% chi phí tính toán so với cách tiếp cận truyền thống.
• Ứng dụng xuất sắc thuật toán Girvan-Newman trên 5 bộ dữ liệu chuẩn, đạt độ chính xác phân tách 100% trên mạng câu lạc bộ Karate.
• Làm rõ cơ chế nhận diện cộng đồng gối nhau và phân cấp thông qua việc phân tích chuyên sâu thuật toán EAGLE và k-clique trên đồ thị 23 đỉnh.
• Đề xuất khung giải pháp thực tiễn ứng dụng trong phân khúc người dùng, tối ưu hệ thống gợi ý và tăng cường an ninh mạng xã hội.

Trong giai đoạn 2021 - 2025, hướng nghiên cứu tiếp theo sẽ tập trung vào việc song song hóa thuật toán trên nền tảng dữ liệu lớn và mở rộng sang đồ thị mạng xã hội có trọng số và hướng động. Độc giả và các nhà nghiên cứu quan tâm có thể liên hệ trực tiếp với tác giả hoặc thư viện Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên để tiếp cận toàn văn công trình nghiên cứu giá trị này.

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 LUAN VAN CHAT LUONG download : add [e-mail] 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ứ LUAN VAN CHAT LUONG download : add [e-mail] 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

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 LUAN VAN CHAT LUONG download : add [e-mail] 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). Đồ LUAN VAN CHAT LUONG download : add [e-mail] 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.

LUAN VAN CHAT LUONG download : add [e-mail] 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.