Luận văn thạc sĩ: Tìm người dùng có tầm ảnh hưởng trên mạng xã hội

Luận văn thạc sĩ khoa học máy tính nghiên cứu phương pháp xác định người dùng có tầm ảnh hưởng trong mạng xã hội, ứng dụng công nghệ hiện đại.

• Tác giả: Lương Văn Minh
• Người hướng dẫn: TS. Quản Thành Thơ
• Trường học: Đại học Bách Khoa, Đại học Quốc gia TP. HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Tìm những người dùng có tầm ảnh hưởng trong mạng xã hội
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu

Luận văn tập trung vào việc tìm kiếm người dùng có tầm ảnh hưởng trong mạng xã hội, một bài toán quan trọng trong lĩnh vực khoa học máy tính. Mục tiêu chính là đề xuất và hiện thực hóa các giải thuật để xác định những người dùng có sức ảnh hưởng lớn dựa trên dữ liệu từ các mạng xã hội. Mạng xã hội được mô hình hóa thành đồ thị, trong đó người dùng là các nút và các tương tác là các cạnh. Giải thuật PageRank, được cải tiến để làm việc với đồ thị có trọng số, là công cụ chính được sử dụng. Trọng số của các cạnh được tính toán dựa trên EdgeRank, một công thức do Facebook đề xuất.

1.1. Mục đích nghiên cứu

Mục đích của luận văn là xây dựng một giải thuật hiệu quả để xác định người dùng có tầm ảnh hưởng trong mạng xã hội. Điều này không chỉ có ý nghĩa học thuật mà còn ứng dụng thực tiễn trong các hệ thống mạng xã hội. Giải thuật được đề xuất dựa trên PageRank và EdgeRank, kết hợp để đánh giá mức độ ảnh hưởng của người dùng.

1.2. Phạm vi nghiên cứu

Luận văn giới hạn trong việc nghiên cứu các mạng xã hội nhỏ tại Việt Nam và so sánh với các mạng xã hội lớn như Facebook và Twitter. Đối tượng nghiên cứu bao gồm các người dùng, hoạt động tương tác, và nhóm hội trong mạng xã hội.

II. Tổng quan

Chương này trình bày các độ đo và nghiên cứu học thuật liên quan đến việc xác định người dùng có tầm ảnh hưởng. Klout, một chuẩn công nghiệp, được sử dụng để đo lường mức độ ảnh hưởng dựa trên các tương tác như like, comment, và retweet. Các nghiên cứu học thuật tập trung vào việc mô hình hóa sự lan truyền ảnh hưởng và tối đa hóa sự trải rộng ảnh hưởng trong mạng xã hội.

2.1. Các độ đo công nghiệp

Klout là một trong những chuẩn công nghiệp phổ biến nhất để đo lường mức độ ảnh hưởng trong mạng xã hội. Nó sử dụng hơn 400 tín hiệu từ các mạng như Facebook, Twitter, và LinkedIn để tính toán điểm số. Điểm Klout phản ánh khả năng dẫn dắt hành động của người dùng trên mạng xã hội.

2.2. Nghiên cứu học thuật

Các nghiên cứu học thuật tập trung vào việc mô hình hóa sự lan truyền ảnh hưởng thông qua các mô hình như Linear Threshold và Independent Cascade. Các phương pháp heuristic và xác suất cũng được sử dụng để cải thiện độ chính xác trong việc xác định người dùng có tầm ảnh hưởng.

III. Cơ sở lý thuyết

Chương này trình bày các mô hình lan truyền ảnh hưởng cơ bản và độ quan trọng của các nút trong mạng xã hội. PageRank, một giải thuật nổi tiếng, được sử dụng để xác định các nút quan trọng trong đồ thị. Giải thuật này dựa trên mô hình lướt web ngẫu nhiên, trong đó thứ hạng của một nút được lan truyền thông qua các liên kết.

3.1. Mô hình lan truyền ảnh hưởng

Hai mô hình lan truyền ảnh hưởng chính là Linear Threshold và Independent Cascade. Các mô hình này giúp hiểu cách ảnh hưởng lan truyền trong mạng xã hội và cách tối đa hóa sự trải rộng của ảnh hưởng.

3.2. PageRank và EdgeRank

PageRank được sử dụng để xác định các nút quan trọng trong đồ thị, trong khi EdgeRank được sử dụng để tính toán trọng số của các cạnh dựa trên các tương tác như like, comment, và wall post. Sự kết hợp của hai giải thuật này giúp cải thiện độ chính xác trong việc xác định người dùng có tầm ảnh hưởng.

IV. Phương pháp và kết quả

Chương này trình bày chi tiết về phương pháp và kết quả thực nghiệm của luận văn. Giải thuật PageRank được cải tiến để làm việc với đồ thị có trọng số, và EdgeRank được sử dụng để tính toán trọng số của các cạnh. Kết quả thực nghiệm cho thấy sự kết hợp của hai giải thuật này mang lại độ chính xác cao hơn so với việc sử dụng riêng lẻ.

4.1. Phương pháp thực nghiệm

Phương pháp thực nghiệm bao gồm việc xây dựng đồ thị có hướng từ dữ liệu mạng xã hội và tính toán trọng số của các cạnh dựa trên EdgeRank. Giải thuật PageRank được áp dụng để xác định các nút quan trọng trong đồ thị.

4.2. Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy rằng việc kết hợp PageRank và EdgeRank mang lại độ chính xác cao hơn trong việc xác định người dùng có tầm ảnh hưởng. Các thí nghiệm được thực hiện trên tập dữ liệu thực từ mạng xã hội của một công ty.

V. Kết luận và hướng phát triển

Luận văn kết luận rằng việc kết hợp PageRank và EdgeRank là một phương pháp hiệu quả để xác định người dùng có tầm ảnh hưởng trong mạng xã hội. Hướng phát triển trong tương lai bao gồm việc mở rộng nghiên cứu sang các mạng xã hội lớn hơn và cải thiện độ chính xác của giải thuật.

5.1. Kết luận

Luận văn đã thành công trong việc đề xuất và hiện thực hóa một giải thuật kết hợp PageRank và EdgeRank để xác định người dùng có tầm ảnh hưởng. Kết quả thực nghiệm cho thấy phương pháp này mang lại độ chính xác cao.

5.2. Hướng phát triển

Hướng phát triển trong tương lai bao gồm việc áp dụng giải thuật trên các mạng xã hội lớn hơn và tích hợp thêm các yếu tố như thời gian và ngữ cảnh để cải thiện độ chính xác.

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

Chương 1: Giới thiệu 1.1 Giới thiệu đề tài Mạng xã hội là một cấu trúc trên internet, trong đó gồm có những thực thể là những người dùng của mạng xã hội, các hoạt động xảy ra của người dùng (như hoạt động cập nhật trạng thái, hoạt động like, chia sẻ hình ảnh, .) và mối quan hệ giữa các người dùng (kết bạn, cùng tham gia một nhóm hội, cùng bàn về một đề tài,. Một người dùng có ảnh hưởng trong mạng xã hội là một người dùng mà các hoạt động của người dùng này thu hút được nhiều mối quan hệ và các hoạt động tương tác từ người dùng khác đến người dùng này. Đề tài tìm người dùng có tầm ảnh hưởng đến những người dùng khác trong mạng xã hội là phương thức tìm kiếm một thuật giải suy luận từ cơ sở dữ liệu người dùng trong mạng xã hội dựa vào các yếu tố của mạng xã hội (như số lượng comment, số lượng like, .) để suy luận ra những người dùng nào có tầm ảnh hưởng đến những người dùng khác trong mạng xã hội. Một ví dụ điển hình là tìm ra những người dùng có tầm ảnh hưởng trong mạng xã hội của một công ty, từ đó ta có thể biết được những người dùng nào có tầm ảnh hưởng trong công ty đó.

Trước yêu cầu trên, vấn đề đặt ra là phải làm sao xây dựng được một thuật giải tương đối chính xác, có khả năng trích xuất từ cơ sở dữ liệu người dùng để tìm ra những người dùng có tầm ảnh hưởng đến những người dùng khác trong mạng xã hội. Đây là mục tiêu cốt lõi của đề tài mà chúng ta sẽ nghiên cứu.2 Mục đích nghiên cứu và giới hạn của đề tài Mục đích cơ bản của đề tài là tìm ra những người dùng có tầm ảnh hưởng đến những người dùng khác trong mạng xã hội dựa vào các hoạt động tương tác giữa các người dùng trong mạng xã hội. Điều này không những thiết thực mà còn là yếu tố nền tảng cho các hệ thống mạng xã hội trong và ngoài nước. Mục đích nghiên cứu của đề tài này là xây dựng một thuật giải thông minh tìm ra các những người dùng có tầm ảnh hưởng đến những người dùng khác trong mạng xã hội.

Tuy nhiên, thuật giải cũng chỉ là mang tính chất tương đối, độ đo mức độ ảnh hưởng phân biệt giữa những người dùng còn phụ thuộc vào các yếu tố mà chúng ta chọn lựa để so sánh. 1 Tìm những người dùng có tầm ảnh hưởng trong mạng xã hội   Đề tài chỉ đặt trọng tâm nghiên cứu vào giải thuật nhằm xác định người dùng có tầm ảnh hưởng trong mạng xã hội. Chính vì thế, đề tài sẽ bỏ qua các yếu tố khách quan như sự ảnh hưởng do yếu tố của mạng internet, các vấn đề về an toàn dữ liệu trong lưu trữ. Đề tài chỉ giới hạn trong việc xác định tập người dùng có mức độ ảnh hưởng trong mạng xã hội dựa trên các mối tương tác qua lại giữa những người dùng trong mạng xã hội.3 Đối tượng và phạm vi nghiên cứu 1.1 Đối tượng nghiên cứu Trong quá trình nghiên cứu, tìm hiểu thuật giải xác định ra những người dùng có tầm ảnh hưởng với những người dùng khác trong mạng xã hội, chúng ta cần nhắm đến những đối tượng nghiên cứu sau: § Các mạng xã hội trong và ngoài nước bao gồm: các đặc điểm đặc điểm đặc trưng của các mạng xã hội này, các yếu tố cấu thành nên nó,… Điều này sẽ bổ trợ cho chúng ta trong quá trình tìm ra những người dùng ảnh hưởng.

§ Các thực thể trong các mạng xã hội như: những người dùng trong mạng xã hội, những hoạt động trong mạng xã hội, những nhóm hội trong mạng xã hội,. § Những hệ thống đo lường mức độ ảnh hưởng trong các mạng xã hội hiện có.2 Phạm vi nghiên cứu § Hiện nay, lĩnh vực mạng xã hội đang phát triển không ngừng, các hệ thống mạng xã hội trong và ngoài nước tăng trưởng rất mạnh, mạng xã hội đã dần là phương tiện kết nối cho đời sống con người. Trong phạm vi nghiên cứu của đề tài, chúng ta sẽ nghiên cứu các mạng xã hội của các cộng đồng nhỏ ở Việt Nam. Hiểu và có những đánh giá phù hợp với mạng xã hội của chúng ta.

§ Trong phạm vi mở rộng hơn, chúng ta sẽ nghiên cứu các mạng xã hội lớn trên thế giới (như Facebook, Twitter,…). Chúng ta sẽ so sánh đánh giá các kết quả của chúng ta với các mạng xã hội lớn trên thế giới.4 Phương pháp tiến hành Trong đề tài này, học viên dựa vào đề xuất mà [6] đã tiến hành thử nghiệm. Ngoài cách tiếp cận được đề xuất, học viên còn đề xuất thêm cách kết hợp độ đo mức độ quan trọng của một cạnh của [9] dựa vào các hành động tương tác giữa những người dùng trong mạng xã 2 Tìm những người dùng có tầm ảnh hưởng trong mạng xã hội   hội. Trong đó, các hành động này là mention, like, comment, wall post,.

nhằm đánh giá trọng số của một cạnh trong mối quan hệ tương quan giữa những người dùng trong mạng xã hội. Đề tài tiến hành thực nghiệm đánh giá hiệu quả của phương pháp này trong việc đánh giá độ đo sự quan trọng của một nút trong một đồ thị xã hội dựa trên giải thuật PageRank, cải tiến giải thuật PageRank kết hợp với độ đo EdgeRank xác định mức độ quan trọng của một cạnh nhằm tìm ra những người dùng có tầm ảnh hưởng trong mạng xã hội. Chi tiết của phương pháp tiến hành sẽ được trình bày trong Chương 4, phần đánh giá kết quả thực nghiệm sẽ được trình bày trong Chương 5.5 Những đóng góp của đề tài Trong đề tài này, học viên đã thử nghiệm cách xác định người dùng có tầm ảnh hưởng trong mạng xã hội dựa trên giải thuật PageRank xác định mức độ quan trọng của một nút trong một đồ thị liên kết. Đối với các cạnh của đồ thị, đề tài đã tính toán mức độ quan trọng của một cạnh dựa trên giải thuật EdgeRank với các hành động tương tác qua lại giữa những người dùng trong mạng xã hội (like, comment, wall post).

Đề tài đã tiến hành thực nghiệm trên tập dữ liệu thật và so sánh các kết quả của đề tài với kết quả thực tế. Từ đó, đề tài phân tích được mức độ chính xác của giải thuật so với kết quả thực tế. Đề tài cung cấp một mã nguồn mở để xác định độ quan trọng của một cạnh trong một mạng xã hội và tính toán độ quan trọng của một nút, kết hợp độ đo quan trọng của một nút PageRank và độ đo quan trọng của một cạnh EdgeRank thành độ đo mức độ quan trọng của một người dùng trong một mạng xã hội. Như vậy, đóng góp của đề tài là xác định được người dùng có tầm ảnh hưởng trong mạng xã hội dựa trên số cạnh tới một nút (các cạnh tới này chính là các tương tác của người dùng này đến người dùng kia) và mức độ quan trọng của cạnh tới đó (mức độ quan trọng của một cạnh tới dựa vào hành động cụ thể đó là gì).

Đóng góp này cụ thể bao gồm hai đóng góp nhỏ đó là: - Áp dụng giải thuật PageRank nhằm xác định các nút quan trọng trong một đồ thị mạng xã hội. 3 Tìm những người dùng có tầm ảnh hưởng trong mạng xã hội   - Cải tiến giải thuật PageRank nhằm giúp cho giải thuật này có thể hoạt động được với đồ thị có trọng số. Trong đó, trọng số của một cạnh của đồ thị mạng xã hội sẽ được xác định dựa vào giải thuật EdgeRank. 4 Tìm những người dùng có tầm ảnh hưởng trong mạng xã hội   Chương 2: Tổng quan 2.1 Các độ đo được dùng trong công nghiệp 2.1 Klout Klout [10] là một chuẩn công nghiệp dùng để đo lường mức độ ảnh hưởng trong mạng xã hội.

Điểm hạng của nó là từ 1 đến 100. Mức độ ảnh hưởng của nó dựa vào khả năng mà thông điệp từ một người dùng sẽ được thực hiện lại từ người dùng khác (ví dụ như retweets, like, comments hoặc trong thông điệp của người nào đó có chứa từ khóa @messages). Dựa vào cách thức mà chuẩn Klout đưa ra, ta có thể xác định rằng: "Yếu tố quyết định đến độ ảnh hưởng của một người dùng là dựa vào số lượng like, comment, retweet của người dùng đó". Vì vậy, ta có thể xác định mức độ ảnh hưởng của một người dùng sẽ dựa vào các yếu tố đó.

Klout cho phép mọi người có thể mức độ ảnh hưởng của mình trên thế giới. Với sự gia tăng của các phương tiện truyền thông xã hội, khả năng ảnh hưởng đến những người khác đã được tính chính xác hơn. Klout đo lường sự ảnh hưởng của bạn dựa trên khả năng dẫn dắt hành động của bạn trên mạng xã hội. Điểm Klout là một số duy nhất đại diện cho sự tập hợp của nhiều phần dữ liệu về hoạt động của các phương tiện truyền thông xã hội của người dùng.

Điểm số của Klout được tính bằng cách áp dụng một mô hình điểm của những tín hiệu. Điểm số của Klout được kết hợp từ hơn 400 tín hiệu từ bảy mạng khác nhau (Facebook, Twitter, Google+, LinkedIn, Klout, Foursqure, Wikipedia). Klout sử dụng dữ liệu hàng ngày từ bảy mạng này để cập nhật liên tục giá trị điểm số của người dùng. Đa số các tín hiệu được sử dụng để tính toán điểm Klout được bắt nguồn từ sự kết hợp các thuộc tính, chẳng hạn như tỷ lệ của các phản ứng người dùng tạo ra so với số lượng nội dung mà người dùng chia sẻ.

Ví dụ, tạo ra 100 retweets từ 10 tweet của những người dùng đầu sẽ đóng góp nhiều hơn điểm của người dùng hơn là tạo ra 100 retweets từ 1.000 tweet của người dùng. Klout cũng xem xét các yếu tố như cách chọn lọc những người tương tác với nội dung của bạn. Thêm một người thích và retweets trong một ngày nhất định, ít hơn các tương tác cá nhân góp phần vào số điểm của người khác. Ngoài ra, Klout đánh giá điểm số cao những người dùng dẫn dắt nhằm lái các luồng sự kiện đến những cá nhân khác.

Một trăm retweets từ 100 người khác nhau đóng góp nhiều điểm hơn là 100 retweets xuất phát từ một người duy nhất. 5 Tìm những người dùng có tầm ảnh hưởng trong mạng xã hội   Klout biết mức độ quan trọng thế nào để duy trì tính toàn vẹn của điểm Klout, vì vậy cách tính điểm của Klout giám sát chặt chẽ hoạt động trên các tín hiệu mà Klout cho là những hành động giả. Điểm của Klout sẽ tiếp tục được tính toán và cải thiện.