Đề xuất mô hình sử dụng cơ chế biểu quyết kết hợp với độ đo trung tâm cho bài toán xác định các nút ảnh hưởng trên mạng xã hội

Chuyên khảo toán học phân tích Đề xuất mô hình sử dụng cơ chế biểu quyết kết hợp với độ đo trung tâm cho bài toán xác định các nút, đánh giá các khía cạnh quan trọng, đề xuất

• Tác giả: Phạm Văn Dương
• Người hướng dẫn: PGS. Phạm Văn Hải
• Trường học: Đại học Bách Khoa Hà Nội
• Chuyên ngành: Khoa học máy tính
• Đề tài: Mô Hình Biểu Quyết Kết Hợp Đo Trung Tâm Xác Định Nút Ảnh Hưở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: 2022
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. GIỚI THIỆU
• 1.1. Mục đích của luận văn
• 1.2. Phạm vi nghiên cứu
• 1.3. Nội dung luận văn
• 1.3.1. Lý thuyết về đồ thị
• 1.3.1.1. Một số loại đồ thị
• 1.3.1.2. Biểu diễn đồ thị
• 1.3.1.3. Một số khái niệm khác
• 1.3.2. Tổng quan về các bài toán phân tích mạng xã hội
• 1.3.2.1. Các bài toán nghiên cứu trong phân tích mạng xã hội
• 1.3.3. Một số phương pháp xác định nút ảnh hưởng
• 1.3.3.1. Độ đo trung tâm dựa trên bậc
• 1.3.3.2. Độ đo trung tâm dựa trên sự lân cận
• 1.3.3.3. Phân rã k-shell và cải tiến k-shell
• 1.3.3.4. Hệ số phân cụm
• 1.3.3.5. Cải tiến mô hình lực hấp dẫn
• 1.3.3.6. Độ đo trung tâm kết hợp nhiều thông tin cục bộ có trọng số dựa trên thông tin entropy (LWC)
• 1.3.3.7. Độ đo kết hợp vị trí, hệ số bậc và Entropy (MCDE)
• 1.3.3.8. Thuật toán EnRenew
• 1.3.3.9. Thuật toán VoteRank
• 1.3.3.10. Thuật toán WVoteRank
• 1.3.3.11. Thuật toán cải tiến WVoteRank
• 1.3.3.12. Thuật toán VoteRank++
• 1.3.4. Một số lý thuyết liên quan
• 1.3.4.1. Đồ thị tri thức
• 1.3.4.2. Thông tin Entropy
• 1.3.5. Phương pháp đánh giá thuật toán
• 1.3.5.1. Mô hình Nhạy cảm – Bị nhiễm – Phục hồi
• 1.3.5.2. Trung bình đường đi ngắn nhất giữa các nút
• 2. MÔ HÌNH ĐỀ XUẤT
• 2.1. Mô hình hóa dữ liệu đồ thị trên mạng xã hội
• 2.2. Thuật toán đề xuất EAVoteRank++
• 2.2.1. Xây dựng độ đo và trọng số tương ứng
• 2.2.2. Khởi tạo điểm khả năng biểu quyết
• 2.2.3. Xác định điểm ảnh hưởng (điểm biểu quyết)
• 2.2.4. Giảm nhiễu thông tin với các lân cận của nút hạt giống và cập nhật điểm khả năng biểu quyết
• 2.2.5. Tính toán lại điểm ảnh hưởng và điểm khả năng biểu quyết và lựa chọn nút hạt giống
• 2.3. Mô tả thuật toán
• 3. THỰC NGHIỆM, ĐÁNH GIÁ
• 3.1. Bộ dữ liệu
• 3.1.1. Mô hình hóa dữ liệu mạng xã hội
• 3.1.2. Mô tả bộ dữ liệu
• 3.2. Thực nghiệm thuật toán
• 3.3. Kết quả thực nghiệm
• 3.3.1. Kết quả đạt được
• 3.3.2. Hướng phát triển
• DANH MỤC HÌNH VẼ
• DANH MỤC BẢNG
• DANH MỤC TỪ VIẾT TẮT
• DANH MỤC KÍ HIỆU

Tóm tắt

I. Tổng quan về Mô Hình Biểu Quyết Kết Hợp Đo Trung Tâm

Mô hình biểu quyết kết hợp đo trung tâm là một phương pháp tiên tiến trong việc xác định các nút ảnh hưởng trên mạng xã hội. Mô hình này không chỉ giúp phân tích các mối quan hệ giữa người dùng mà còn tối ưu hóa việc truyền tải thông tin. Việc áp dụng mô hình này trong phân tích mạng xã hội đang trở thành xu hướng quan trọng, đặc biệt trong bối cảnh bùng nổ thông tin hiện nay.

1.1. Định nghĩa Mô Hình Biểu Quyết Kết Hợp

Mô hình biểu quyết kết hợp là sự kết hợp giữa các phương pháp đo lường trung tâm và cơ chế biểu quyết. Nó cho phép xác định các nút ảnh hưởng dựa trên nhiều yếu tố khác nhau như hệ số bậc và vị trí trong mạng.

1.2. Tầm quan trọng của Mô Hình trong Phân Tích Mạng Xã Hội

Mô hình này giúp các nhà nghiên cứu và doanh nghiệp hiểu rõ hơn về cách thức lan truyền thông tin và ảnh hưởng của các nút trong mạng xã hội, từ đó đưa ra các chiến lược truyền thông hiệu quả.

II. Vấn đề và Thách thức trong Xác Định Nút Ảnh Hưởng

Việc xác định nút ảnh hưởng trên mạng xã hội gặp nhiều thách thức, bao gồm sự phức tạp trong mối quan hệ giữa người dùng và sự thay đổi liên tục của dữ liệu. Những vấn đề này cần được giải quyết để tối ưu hóa hiệu quả của các chiến dịch truyền thông.

2.1. Sự Phức Tạp của Mối Quan Hệ Người Dùng

Mối quan hệ giữa người dùng trên mạng xã hội thường rất phức tạp và chồng chéo, điều này gây khó khăn trong việc xác định chính xác các nút ảnh hưởng.

2.2. Thay Đổi Liên Tục của Dữ Liệu

Dữ liệu trên mạng xã hội thay đổi liên tục, điều này đòi hỏi các mô hình phân tích phải linh hoạt và có khả năng cập nhật thường xuyên để đảm bảo tính chính xác.

III. Phương Pháp Đề Xuất Mô Hình Biểu Quyết Kết Hợp

Phương pháp đề xuất mô hình biểu quyết kết hợp sử dụng các thuật toán hiện đại để xác định các nút ảnh hưởng. Mô hình này kết hợp nhiều yếu tố như độ đo trung tâm và cơ chế biểu quyết để đưa ra kết quả chính xác hơn.

3.1. Thuật Toán EAVoteRank

Thuật toán EAVoteRank++ là một trong những thuật toán chính được sử dụng trong mô hình này, giúp xác định điểm ảnh hưởng của các nút dựa trên nhiều thông tin khác nhau.

3.2. Kết Hợp Đo Trung Tâm và Biểu Quyết

Mô hình kết hợp giữa độ đo trung tâm và cơ chế biểu quyết giúp tối ưu hóa việc xác định các nút ảnh hưởng, từ đó nâng cao hiệu quả của các chiến dịch truyền thông.

IV. Ứng Dụng Thực Tiễn của Mô Hình

Mô hình biểu quyết kết hợp đo trung tâm đã được áp dụng thành công trong nhiều lĩnh vực, từ quảng cáo đến kiểm soát thông tin. Những ứng dụng này chứng minh tính hiệu quả của mô hình trong việc xác định các nút ảnh hưởng.

4.1. Ứng Dụng trong Chiến Dịch Quảng Cáo

Mô hình này giúp các doanh nghiệp xác định những người có ảnh hưởng lớn để tối ưu hóa chiến dịch quảng cáo, từ đó tăng cường khả năng tiếp cận khách hàng.

4.2. Kiểm Soát Thông Tin và Tin Đồn

Mô hình cũng có thể được sử dụng để kiểm soát thông tin và ngăn chặn sự lan truyền của tin đồn, đặc biệt trong các tình huống nhạy cảm như dịch bệnh.

V. Kết Luận và Tương Lai của Mô Hình

Mô hình biểu quyết kết hợp đo trung tâm đang mở ra nhiều cơ hội mới trong việc phân tích mạng xã hội. Tương lai của mô hình này hứa hẹn sẽ mang lại nhiều cải tiến và ứng dụng mới trong các lĩnh vực khác nhau.

5.1. Hướng Phát Triển Mới

Các nghiên cứu tiếp theo có thể tập trung vào việc cải thiện độ chính xác của mô hình và mở rộng ứng dụng của nó trong các lĩnh vực khác nhau.

5.2. Tác Động Đến Ngành Công Nghiệp

Mô hình này có thể tạo ra những thay đổi lớn trong cách thức các doanh nghiệp tiếp cận và tương tác với khách hàng trên mạng xã hội.

Nội dung chính

## Tổng quan nghiên cứu

Trong bối cảnh bùng nổ thông tin trên mạng xã hội, việc xác định các nút ảnh hưởng trở thành một bài toán quan trọng trong lĩnh vực phân tích mạng xã hội. Tính đến tháng 6/2021, Việt Nam có gần 76 triệu người dùng Facebook, chiếm hơn 70% dân số, tạo ra một môi trường dữ liệu phong phú nhưng cũng đầy thách thức trong việc khai thác và phân tích. Bài toán xác định các nút ảnh hưởng nhằm tìm ra nhóm người dùng có khả năng lan tỏa thông tin rộng rãi nhất, từ đó hỗ trợ các chiến dịch quảng cáo, truyền thông, kiểm soát tin đồn và dịch bệnh hiệu quả hơn.

Mục tiêu nghiên cứu là đề xuất một mô hình kết hợp cơ chế biểu quyết và độ đo trung tâm để xác định các nút ảnh hưởng trên mạng xã hội, đồng thời xây dựng phương pháp mô hình hóa dữ liệu thu thập từ Facebook thành đồ thị đồng nhất dựa trên đồ thị tri thức. Phạm vi nghiên cứu bao gồm dữ liệu thu thập từ Facebook và các bộ dữ liệu mạng phức hợp khác, với thời gian thực nghiệm và đánh giá thuật toán trong năm 2022. Ý nghĩa nghiên cứu được thể hiện qua việc nâng cao độ chính xác và hiệu quả trong việc xác định nút ảnh hưởng, giúp tối ưu hóa phạm vi lan truyền thông tin và giảm chi phí cho các chiến dịch truyền thông.

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

### Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

- **Lý thuyết đồ thị**: Đồ thị đồng nhất được sử dụng để mô hình hóa mạng xã hội, trong đó các nút đại diện cho người dùng và các cạnh biểu thị mối quan hệ giữa họ. Các khái niệm chính bao gồm độ đo trung tâm (degree centrality, closeness centrality), phân rã k-shell, hệ số phân cụm cục bộ, và các thuật toán xác định nút ảnh hưởng như VoteRank, EnRenew.

- **Cơ chế biểu quyết (Voting mechanism)**: Thuật toán VoteRank và các biến thể như VoteRank++ sử dụng điểm khả năng biểu quyết và điểm ảnh hưởng được biểu quyết để lựa chọn các nút hạt giống có tầm ảnh hưởng cao, phân phối rộng rãi trên mạng.

- **Thông tin Entropy**: Áp dụng để xác định trọng số cho các độ đo trung tâm, giúp cân bằng đóng góp của từng chỉ số trong việc tính điểm khả năng biểu quyết, nâng cao hiệu quả thuật toán.

- **Mô hình lan truyền thông tin SIR (Susceptible-Infected-Recovered)**: Mô phỏng quá trình lan truyền thông tin trên mạng xã hội, dùng để đánh giá hiệu quả của thuật toán qua các chỉ số quy mô lan truyền, quy mô lan truyền cuối và trung bình khoảng cách giữa các nút hạt giống.

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

- **Nguồn dữ liệu**: Thu thập dữ liệu từ mạng xã hội Facebook, bao gồm các tương tác người dùng, được xử lý và mô hình hóa thành đồ thị đồng nhất dựa trên đồ thị tri thức. Bổ sung thêm 7 bộ dữ liệu mạng phức hợp phổ biến trong nghiên cứu xác định nút ảnh hưởng như mạng máy bay Mỹ năm 2010, mạng nhạc sĩ Jazz.

- **Phương pháp phân tích**: Đề xuất thuật toán EAVoteRank++ kết hợp cơ chế biểu quyết với độ đo trung tâm có trọng số dựa trên entropy. Thuật toán tính điểm khả năng biểu quyết dựa trên hệ số bậc, vị trí trong mạng và hệ số phân cụm cục bộ, đồng thời áp dụng cơ chế giảm nhiễu thông tin với các lân cận cấp 1 và cấp 2.

- **Timeline nghiên cứu**: Thu thập và xử lý dữ liệu trong năm 2021-2022, phát triển và hoàn thiện thuật toán trong năm 2022, thực nghiệm và đánh giá trên các bộ dữ liệu trong cùng năm.

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

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

- Thuật toán EAVoteRank++ đạt hiệu quả vượt trội trên 8 bộ dữ liệu thử nghiệm, bao gồm 7 bộ dữ liệu mạng phức hợp và 1 bộ dữ liệu Facebook. Cụ thể, quy mô lan truyền cuối tăng trung bình 15-20% so với các thuật toán VoteRank, EnRenew và WVoteRank.

- Thời gian thực thi thuật toán giảm khoảng 25% so với các phương pháp truyền thống nhờ cơ chế cập nhật điểm khả năng biểu quyết một phần, không phải toàn bộ nút trong mỗi vòng lặp.

- Trung bình khoảng cách giữa các nút hạt giống được chọn bởi EAVoteRank++ lớn hơn 10% so với các thuật toán khác, cho thấy sự phân bố rộng rãi và đa dạng hơn trong mạng, góp phần tối đa hóa phạm vi lan truyền.

- Trọng số các độ đo trung tâm được xác định bằng phương pháp entropy giúp cân bằng đóng góp của từng chỉ số, nâng cao độ chính xác trong việc đánh giá tầm ảnh hưởng của các nút.

### Thảo luận kết quả

Kết quả cho thấy việc kết hợp cơ chế biểu quyết với độ đo trung tâm có trọng số là hướng đi hiệu quả trong bài toán xác định nút ảnh hưởng. Việc xem xét đồng thời thông tin cục bộ (hệ số bậc, hệ số phân cụm) và vị trí trong mạng giúp thuật toán đánh giá chính xác hơn tầm ảnh hưởng thực tế của các nút. So với các nghiên cứu trước đây chỉ tập trung vào một hoặc hai yếu tố, mô hình đề xuất giảm thiểu sự chồng chéo vùng ảnh hưởng giữa các nút hạt giống, từ đó tăng phạm vi lan truyền thông tin.

Việc áp dụng mô hình SIR để mô phỏng lan truyền thông tin cung cấp cơ sở đánh giá khách quan và thực tiễn cho hiệu quả thuật toán. Các biểu đồ quy mô lan truyền theo thời gian và bảng so sánh thời gian thực thi minh họa rõ ràng ưu thế của EAVoteRank++ so với các thuật toán khác. Kết quả này phù hợp với các nghiên cứu gần đây về tối đa hóa ảnh hưởng trong mạng xã hội, đồng thời mở rộng ứng dụng cho các mạng phức hợp đa dạng.

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

- **Triển khai thuật toán EAVoteRank++ trong các chiến dịch quảng cáo số** nhằm tối ưu hóa việc lựa chọn nhóm người có sức ảnh hưởng, tăng hiệu quả lan truyền thông điệp, giảm chi phí quảng cáo. Thời gian thực hiện: 6 tháng; chủ thể: các doanh nghiệp, công ty quảng cáo.

- **Phát triển hệ thống thu thập và mô hình hóa dữ liệu mạng xã hội tự động** dựa trên đồ thị tri thức để cập nhật liên tục dữ liệu người dùng, đảm bảo tính chính xác và kịp thời cho thuật toán. Thời gian: 12 tháng; chủ thể: các tổ chức nghiên cứu, công ty công nghệ.

- **Áp dụng mô hình SIR và các chỉ số đánh giá để giám sát hiệu quả lan truyền thông tin trong thời gian thực**, hỗ trợ điều chỉnh chiến lược truyền thông linh hoạt. Thời gian: liên tục; chủ thể: các cơ quan truyền thông, tổ chức y tế.

- **Nâng cao khả năng mở rộng thuật toán cho các mạng xã hội lớn và phức tạp hơn**, bao gồm tích hợp thêm các yếu tố trọng số cạnh, đa dạng loại mối quan hệ. Thời gian: 18 tháng; chủ thể: nhóm nghiên cứu khoa học máy tính, phát triển phần mềm.

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

- **Nhà nghiên cứu và sinh viên ngành Khoa học máy tính, Mạng xã hội**: Nắm bắt các phương pháp tiên tiến trong phân tích mạng xã hội, thuật toán xác định nút ảnh hưởng, ứng dụng mô hình SIR.

- **Doanh nghiệp và chuyên gia marketing số**: Áp dụng thuật toán để lựa chọn nhóm người ảnh hưởng hiệu quả, tối ưu hóa chiến dịch quảng cáo trên mạng xã hội.

- **Cơ quan quản lý truyền thông và y tế công cộng**: Sử dụng mô hình để kiểm soát tin giả, lan truyền thông tin dịch bệnh, xác định các nút ảnh hưởng trong cộng đồng.

- **Phát triển phần mềm và công nghệ dữ liệu lớn**: Tham khảo mô hình và thuật toán để xây dựng các công cụ phân tích mạng xã hội, hệ thống thu thập và xử lý dữ liệu.

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

1. **Thuật toán EAVoteRank++ khác gì so với các thuật toán VoteRank truyền thống?**  
EAVoteRank++ kết hợp cơ chế biểu quyết với độ đo trung tâm có trọng số dựa trên entropy, xem xét cả hệ số bậc, vị trí trong mạng và hệ số phân cụm cục bộ, giúp đánh giá chính xác hơn tầm ảnh hưởng của nút và giảm sự chồng chéo vùng ảnh hưởng.

2. **Phương pháp mô hình hóa dữ liệu mạng xã hội như thế nào?**  
Dữ liệu thu thập từ Facebook được chuyển đổi thành đồ thị đồng nhất dựa trên đồ thị tri thức, biểu diễn các mối quan hệ chi tiết giữa người dùng, thuận lợi cho việc áp dụng thuật toán xác định nút ảnh hưởng.

3. **Mô hình SIR được sử dụng để làm gì trong nghiên cứu?**  
Mô hình SIR mô phỏng quá trình lan truyền thông tin trên mạng xã hội, giúp đánh giá hiệu quả thuật toán qua các chỉ số quy mô lan truyền, quy mô lan truyền cuối và khoảng cách giữa các nút hạt giống.

4. **Thuật toán có thể áp dụng cho các mạng xã hội khác ngoài Facebook không?**  
Có thể, thuật toán và mô hình có tính tổng quát cao, phù hợp với các mạng xã hội được mô hình hóa dưới dạng đồ thị đồng nhất, tuy nhiên cần điều chỉnh phù hợp với đặc thù dữ liệu từng nền tảng.

5. **Làm thế nào để đảm bảo thuật toán hoạt động hiệu quả trên mạng xã hội có quy mô lớn?**  
Thuật toán sử dụng cơ chế cập nhật điểm khả năng biểu quyết một phần, giảm thiểu chi phí tính toán, đồng thời áp dụng trọng số entropy để cân bằng các độ đo, giúp mở rộng hiệu quả trên mạng lớn và phức tạp.

## Kết luận

- Đã đề xuất thành công mô hình kết hợp cơ chế biểu quyết và độ đo trung tâm có trọng số để xác định các nút ảnh hưởng trên mạng xã hội.  
- Thuật toán EAVoteRank++ cho hiệu quả cao hơn về độ chính xác và thời gian thực thi so với các phương pháp hiện có.  
- Mô hình hóa dữ liệu mạng xã hội thành đồ thị đồng nhất dựa trên đồ thị tri thức giúp khai thác hiệu quả các mối quan hệ người dùng.  
- Mô hình SIR và các chỉ số đánh giá cung cấp cơ sở thực nghiệm khách quan cho hiệu quả thuật toán.  
- Đề xuất các hướng phát triển mở rộng và ứng dụng thực tiễn trong lĩnh vực truyền thông, y tế và công nghệ dữ liệu lớn.

Khuyến nghị các nhà nghiên cứu và doanh nghiệp tiếp tục ứng dụng và phát triển mô hình để nâng cao hiệu quả truyền thông trên mạng xã hội, đồng thời mở rộng nghiên cứu cho các mạng phức hợp đa dạng hơn.

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

Đặt vấn đề Bùng nổ thông tin trong thời đại công nghệ 4.0 là một vấn đề không còn xa lạ trong những năm gần đây. Nguồn thông tin đa dạng cũng đang và sẽ là cơ hội và thách thức cho các nhà nghiên cứu trong việc phân tích và xử lý dữ liệu. Một trong số đó là nguồn thông tin đền từ nền tảng Internet. Sự phát triển nhanh chóng của internet dẫn đến các tiện ích và cụ thể là mạng xã hội ngày càng phong phú.

Ta có thể kể đến các trang mạng xã hội trực tuyến như Facebook, Twitter, Instagram. Chúng đã và đang trở nên vô cùng phổ biến với hầu hết mọi lứa tuổi [1]. Theo đó, mạng xã hội trở thành một nền tảng quan trọng, hữu ích cho các chiến dịch truyền thông và quảng cáo [2]. Ở trên không gian mạng xã hội hiện có rất nhiều thông tin được trao đổi và tiếp cận mỗi ngày.

Riêng đối với việc sử dụng mạng xã hội Facebook, theo số liệu thống kê tính tới tháng 6/2021 của NapoleonCat 1 (công cụ đo lường các chỉ số mạng xã hội), tổng số người dùng Facebook tại Việt Nam là gần 76 triệu người, chiếm hơn 70% dân số toàn quốc, tăng 31 triệu người dùng so với năm 2019 và vẫn dẫn đầu danh sách các mạng xã hội phổ biến tại Việt Nam. Mô tả chi tiết về các thông tin người dùng mạng xã hội Facebook được mô tả ở biểu đồ Hình 0.1: Thống kê người dùng Facebook tại Việt Nam năm 2021 2 Đây là những điều kiện mang đến cơ hội to lớn cho các nhà bán hàng gia tăng việc tìm kiếm và tiếp cận hiệu quả với đối tượng khách hàng tiềm năng tại Việt Nam 1 https://napoleoncat.com/ 2 https://hr1tech.com/vi/news/cap-nhat-so-lieu-moi-nhat-2021-ve-nguoi-dung-mang-xa-hoi-tai-viet-nam- 158.html 1 trên nền tảng mạng xã hội. Do đó, có thể khẳng định rằng mạng xã hội đã, đang và sẽ là một nền tảng quan trọng cho các chiến dịch truyền thông và quảng cáo. Tuy nhiên, việc phổ biến các thông tin đến mọi người dùng trên mạng xã hội hiện không hiệu quả và tốn kém chi phí rất nhiều.

Một giải pháp hợp lý là nhắm mục tiêu vào một số lượng người dùng nhất định với mong muốn truyền bá thông điệp quảng cáo càng rộng rãi càng tốt, nghĩa là tìm một nhóm người nhất định trên mạng xã hội (hay còn gọi là người có sức ảnh hưởng trên mạng xã hội - KoLs) để thực hiện các chiến dịch quảng bá sản phẩm, lan tỏa thông điệp giúp tiếp cận đến càng nhiều người dùng càng tốt. Giả sử rằng một công ty có một sản phẩm mới và có kế hoạch bắt đầu một chiến dịch quảng cáo, tiếp thị đến với người dùng trên mạng xã hội. Công ty này muốn chọn một nhóm người nhất định có khả năng truyền bá sản phẩm của họ đến với những người dùng khác trên mạng lưới của những người này. Việc lựa chọn nhóm người này là rất quan trọng vì nếu lựa chọn không hợp lý có thể khiến toàn bộ chiến dịch quảng cáo này thất bại.

Do đó, công ty nên chọn một nhóm người có ảnh hưởng lớn để đảm bảo rằng sản phẩm của họ sẽ tiếp tục được tiếp thị đến những người dùng khác. Việc xếp hạng theo mức độ ảnh hưởng của những nhóm người này sẽ giúp doanh nghiệp linh hoạt hơn trong việc lựa chọn những người có ảnh hưởng cho chiến dịch tiếp thị của mình. Cụ thể như, nếu thuật toán chỉ tìm thấy 𝑘𝑘 người có tầm ảnh hưởng hàng đầu và hầu hết trong số họ từ chối hợp tác hoặc yêu cầu một mức giá rất cao không thể chi trả được, thì chiến dịch tiếp thị của công ty có thể bị dừng hoàn toàn. Do đó, thuật toán đề xuất cho phép có nhiều cơ hội hơn để tìm những người dùng có ảnh hưởng khác vì nó sắp xếp các nút của mạng xã hội theo mức độ ảnh hưởng của họ.

Bằng cách này, doanh nghiệp có thể lựa chọn những người ảnh hưởng phù hợp hơn, ví dụ, lựa chọn nhiều người dùng có tầm ảnh hưởng ở mức trung bình để dẫn đầu chiến dịch quảng cáo thay vì chỉ lựa chọn một người có tầm ảnh hưởng nhất, nếu điều này phù hợp hơn với yêu cầu của họ. Không chỉ với các thông tin trên mạng xã hội mà nhiều dữ liệu trong thực tế cũng được biểu diễn dưới các mạng đồ thị được gọi chung là các mạng phức hợp. Có thể kể đến như mạng bao hàm sự hợp tác nghiên cứu khoa học giữa các tác giả [3], mạng email biểu thị thông tin liên lạc email giữa người dùng [4], mạng protein- DNA giúp chúng ta có cái nhìn đa chiều về các phản ứng sinh hóa [5] hay mạng đường sắt biểu diễn cấu trúc của đường sắt qua các trạm đỗ [6]. Những dữ liệu này được mô hình hóa thành các mạng phức hợp, tạo điều kiện thuận lợi cho việc nghiên cứu các hệ thống.

Sự hiểu biết sâu sắc về các mạng phức hợp nói chung và mạng xã hội nói riêng trong việc xác định các nút ảnh hưởng có ý nghĩa vô cùng to lớn trong việc truyền bá thông tin và kiểm soát các kết nối giữa các thành phần trong mạng. Một mặt, bằng cách xác định các nút có ảnh hưởng trong mạng, chúng ta có thể thực hiện các chiến dịch quảng bá truyền thông cho các sản phẩm đưa ra thị trường, hỗ trợ truyền bá thông tin đến các người dùng trên nền tảng mạng xã hội như đã trình bày ở phần trên hay trong lĩnh vực sinh học, bài toán còn có thể giúp phát hiện các protein thiết yếu trong đời sống [7]. Mặt khác, bằng cách loại bỏ một số nút ảnh 2 hưởng quan trọng trong mạng, nó có thể hạn chế tốc độ lan truyền thông tin nhanh gây ảnh hưởng trên quy mô lớn của tin giả ví dụ như thông tin giả từ các tài khoản mạng xã hội về tin trong việc phòng, chống dịch bệnh Covid-19 ở Việt Nam. Hay trong quá trình lây lan dịch bệnh, việc xác định vị trí và tạo miễn dịch cho những cá nhân có ảnh hưởng nhất có thể ngăn chặn sự lây lan thêm của vi rút.

Điều này là vô cùng cấp thiết vì những mối nguy thường bắt đầu với một số lượng nhỏ các nút và có thể nhanh chóng lan rộng ra toàn bộ mạng [6]. Hoặc trong một hệ thống mạng máy tính quy mô lớn, việc phải thiết kế một kiến trúc mạnh mẽ và an toàn là một điều bắt buộc vì hệ thống thực tế sẽ không được xảy việc gián đoạn đột ngột, vậy nên việc tạo ra các máy chủ dự phòng và các liên kết dự phòng với các máy chủ trong hệ thống chính tùy theo mức độ quan trọng là một giải pháp khá hiệu quả [8]. Từ những ý nghĩa thực tiễn và lợi ích đã trình bày ở trên, việc xác định các nút có ảnh hưởng trong mạng là một bài toán hữu ích, có ý nghĩa to lớn và đang được nhiều nhà khoa học quan tâm và nghiên cứu. Việc xác định các nút ảnh hưởng thực chất là bài toán tối đa hóa ảnh hưởng (Influence Maximization - IM) trong mạng xã hội [9, 10].

Về mặt hình thức, vấn đề tối đa hóa ảnh hưởng được định nghĩa là việc tối đa hóa phạm vi tiếp cận của thông tin bằng cách ban đầu gửi thông tin đến một nhóm các nút có ảnh hưởng. Ở đây, bài toán xác định nút ảnh hưởng với yêu cầu đầu vào là một mạng đồ thị đồng nhất, thông qua các thuật toán và mô hình khác nhau sẽ đưa ra được một danh sách các nút trong mạng có tầm ảnh hưởng nhất. Bài toán có thể được mô tả bằng công thức toán học như sau: 𝑓𝑓 PT 0.1 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) → 𝑆𝑆 với 𝐺𝐺 là đồ thị đồng nhất, 𝑉𝑉 là tập hợp các nút và 𝐸𝐸 là tập hợp các cạnh có trong đồ thị. 𝑓𝑓 ở đây biểu thị thuật toán xác định được tập hợp 𝑙𝑙 nút ảnh hưởng 𝑆𝑆.

Trong thực tế, như ta đã biết, mạng xã hội là một nền tảng chia sẻ thông tin vô cùng hữu ích, nó mô tả các hoạt động của người dùng trên đây như chính các hoạt động trong thế giới thực. Người dùng có thể dễ dàng thể hiện các cảm xúc hay những quan điểm của mình trên đây, tuy nhiên việc thu thập thông tin này lại vô cùng khó khăn do các chính sách bảo mật, riêng tư của mỗi người dùng. Hơn nữa, mối quan hệ phức tạp, chồng chéo của mỗi người dùng cũng khiến cho việc mô hình hóa dữ liệu này gặp rất nhiều khó khăn. Một trong những phương pháp gần đây được nhiều nhà khoa học áp dụng để giải quyết khó khăn này là việc xây dựng đồ thị tri thức.

Đây là một trong những mô hình quan hệ hữu ích có thể được áp dụng trong thế giới thực. Đặc biệt đối với mạng xã hội, đồ thị tri thức cơ bản được xây dựng bởi các thực thể và các cạnh là mối quan hệ giữa chúng. Mối quan hệ này chúng ta sẽ định nghĩa bởi các yếu tố khác nhau, tuy nhiên bên trong chúng sẽ ẩn chứa các mối quan hệ trong thế giới thực. Từ các nhận định trên, ta có thể thấy mạng xã hội là nền tảng dữ liệu mới, nơi mà dữ liệu thay đổi và cập nhật liên tục từ người dùng.

Do vậy, việc thu thập dữ liệu vô cùng khó khăn do việc cá nhân hóa của mỗi người dùng và các cơ chế phát hiện bất thường trên Facebook từ các 3 tài khoản được sử dụng để thu thập dữ liệu rất gắt gao, dễ dàng bị chặn hoặc khóa các tài khoản này. Ngoài ra, việc bảo mật thông tin với các tài khoản trên Facebook để biết được mối liên hệ giữa những người dùng cũng là một vấn đề đáng lưu tâm do các tài khoản thường để dưới dạng riêng tư, không công khai các thông tin cá nhân. Đối với bài toán xác định các nút ảnh hưởng trên mạng xã hội, các nhà khoa học đã nghiên cứu và đề xuất nhiều thuật toán với các hướng tiếp cận khác nhau để giải quyết [11]. Một trong số những hướng tiếp cận được nhiều nhà nghiên cứu áp dụng đó là việc xác định tập hợp các nút ảnh hưởng trong mạng dựa trên việc xếp hạng các nút trong mạng theo điểm được xác định bằng độ đo trung tâm của mỗi nút.

Dựa trên các nghiên cứu từ các thực nghiệm khác nhau, có rất nhiều độ đo trung tâm được đề xuất. Các độ đo theo hướng tiếp cận này được chia thành 4 loại bao gồm: độ đo trung tâm dựa trên thông tin cục bộ, độ đo trung tâm dựa trên thông tin bán cục bộ, độ đo trung tâm dựa trên thông tin toàn cục và độ đo kết hợp.