Nghiên cứu và ứng dụng các phương pháp xác định người có ảnh hưởng trên mạng xã hội thực tế (Facebook)

GIỚI THIỆU ĐỒ ÁN

Đặt vấn đề

Mạng xã hội hiện nay trở nên phổ biến với hơn 2,3 tỷ người dùng Facebook hàng tháng, cho phép chia sẻ câu chuyện, ý tưởng, hình ảnh và video Người dùng có thể cập nhật hoạt động của mình trên các nền tảng máy tính và điện thoại thông minh Việc khai thác dữ liệu từ mạng xã hội mang lại giá trị lớn, nhờ vào tính ứng dụng và tính cấp thiết của nó.

Với dân số khoảng 97 triệu người, Việt Nam hiện có hơn 145 triệu kết nối di động, đạt tỷ lệ thâm nhập 150% Trong số đó, 68.17 triệu người, tương đương 70% dân số, sử dụng internet, và 65 triệu người tham gia mạng xã hội, chiếm 67% tổng dân số, theo báo cáo năm gần đây.

Hình 1: Tổng quan về internet tại Việt Nam tính đến tháng 2/2021 [1]

Các số liệu hiện tại mở ra cơ hội lớn cho các nhà tiếp thị tại Việt Nam trong việc tối ưu hóa chiến lược tiếp cận khách hàng tiềm năng Tính đến tháng 4 năm 2021, Facebook vẫn dẫn đầu về tỉ lệ người dùng tương tác trên mạng xã hội, theo sau là YouTube, cùng với Instagram, TikTok và Twitter, tạo thành danh sách năm mạng xã hội được yêu thích nhất tại Việt Nam.

Thông tin này rất quan trọng cho các nhà tiếp thị khi xây dựng chiến lược cho kênh mạng xã hội, đặc biệt trong việc hoạch định và thực hiện các hoạt động truyền thông qua người ảnh hưởng Do đó, việc xác định các yếu tố liên quan là cần thiết.

Tổng quan về internet tại Việt Nam 2/2021

Tổng dân số Việt Nam đang tăng trưởng, với số lượng kết nối di động và người dùng Internet cũng không ngừng gia tăng Số lượng người dùng mạng xã hội hoạt động đóng vai trò quan trọng trong việc giúp các nhãn hàng xác định đúng đối tượng mục tiêu, từ đó nâng cao hiệu quả quảng cáo sản phẩm Hiện nay, tại Việt Nam có nhiều lĩnh vực người ảnh hưởng phát triển mạnh mẽ như Giải trí, Đời sống/Phong cách sống, Gaming, Gia đình-trẻ em và Âm nhạc.

Việc xác định người ảnh hưởng trên mạng xã hội rất quan trọng, nhưng cũng đối mặt với nhiều thách thức Mạng xã hội là một lĩnh vực nghiên cứu mới, nơi hành vi người dùng luôn biến đổi và cập nhật liên tục.

Có nhiều khó khăn trong việc xác định người ảnh hưởng

Việc thu thập dữ liệu trên Facebook hiện nay gặp nhiều khó khăn do cơ chế bảo mật nghiêm ngặt Facebook có khả năng phát hiện các truy cập bất thường, điều này dẫn đến việc khóa tài khoản của những người thu thập dữ liệu.

• Thứ hai, các phương pháp đánh giá hiện tại đơn giản, không đánh giá đúng sự ảnh hưởng và tầm quan trọng

• Thứ ba là tính toán trên đồ thị phức tạp khi mở rộng đồ thị về số lượng nút và cạnh

Hiện nay, nhiều phương pháp ứng dụng chỉ tập trung vào mạng lưới bạn bè để đánh giá mức độ ảnh hưởng, hoặc sử dụng các phương pháp thống kê để xác định những người có tầm ảnh hưởng trên mạng xã hội Tuy nhiên, điều này dẫn đến nhiều hạn chế về độ chính xác trong việc tính toán.

Phát biểu bài toán

Đồ án này nhằm phân tích dữ liệu mạng xã hội để xác định người dùng có tầm ảnh hưởng theo chủ đề cụ thể Qua việc xử lý dữ liệu tương tác của người dùng với các bài viết và tổ chức thành dữ liệu đồ thị, chúng tôi áp dụng các thuật toán và đo lường độ trung tâm cùng tầm ảnh hưởng của các nút trong đồ thị Kết quả sẽ giúp so sánh và xác định người dùng có ảnh hưởng trên mạng xã hội trong một chủ đề nhất định.

Nhiệm vụ của đồ án

Để giải quyết bài toán đặt ra, cần thực hiện các công việc sau:

Dựa trên dữ liệu thô đã thu thập, việc xử lý dữ liệu được thực hiện bằng cách xây dựng mối liên kết giữa các thực thể cá nhân trên mạng xã hội theo thời gian, tạo thành một mạng lưới tương tác giữa các cá nhân trong hệ thống mạng.

- Sử dụng các thuật toán về độ đo trung tâm và tầm ảnh hưởng của các nút trong đồ thị để phân tích dữ liệu

- So sánh và đánh giá hiệu năng các phương pháp.

Ý nghĩa của đồ án

Người ảnh hưởng là những cá nhân có tiếng nói mạnh mẽ trên mạng xã hội, có khả năng tác động đến cuộc sống của người khác Tuy nhiên, do sự phát triển mạnh mẽ của mạng xã hội, việc xác định những người này trở nên khó khăn hơn Hiện nay, các nhà nghiên cứu đang tìm cách hiểu rõ hơn về vai trò và ảnh hưởng của họ trong xã hội.

Mặc dù việc xác định người ảnh hưởng (KOL) thường dựa vào số lượng bạn bè và người theo dõi, nhưng những chỉ số này không hoàn toàn phản ánh tính chất động của tiếng nói và khả năng lan truyền thông tin mà các KOL tạo ra Để có cái nhìn sâu sắc hơn về sức ảnh hưởng thực sự của họ, cần áp dụng các giải pháp đa dạng và toàn diện hơn.

Đồ án này nghiên cứu tầm ảnh hưởng của người dùng trong ngành giải trí thông qua việc thu thập dữ liệu từ các bài viết trên Fanpage và trang cá nhân của những cá nhân trong danh sách đã có sẵn Dữ liệu sẽ được tổ chức dưới dạng đồ thị và áp dụng thuật toán xếp hạng nút để đánh giá mức độ ảnh hưởng của từng người dùng Kết quả mang đến cái nhìn tổng quan về các thuật toán xếp hạng ảnh hưởng và xác định những cá nhân có tầm ảnh hưởng trong lĩnh vực giải trí dựa trên dữ liệu thực tế.

CƠ SỞ LÝ THUYẾT

Tổng quan về mạng xã hội

Mạng xã hội (MXH) là một hệ thống mô tả sự tương tác giữa các cá nhân có cùng sở thích, kết nối họ qua internet với nhiều mục đích khác nhau, không bị giới hạn bởi không gian và thời gian Theo định nghĩa, MXH bao gồm các phần tử (nút) như cá nhân, tập thể hoặc tổ chức, được liên kết với nhau thông qua các mối quan hệ xã hội gọi là liên kết (links).

Hình 2: Mô hình mạng xã hội (Social Network) [3]

Trong lĩnh vực công nghệ thông tin, mạng xã hội trực tuyến đóng vai trò quan trọng trong việc kết nối những người có chung sở thích trên Internet, bất chấp không gian và thời gian Các dịch vụ như Email, chat và Internet Sharing đã tạo ra một nền tảng giao tiếp mạnh mẽ Sự xuất hiện của các trang mạng như Facebook, Twitter, Myspace, Youtube, Google+ và Flickr đã làm cho mạng xã hội trở nên đa dạng và ngày càng phổ biến hơn trong cộng đồng người dùng.

Mạng xã hội (MXH) là một hệ thống bao gồm nhiều công cụ và dịch vụ trực tuyến như email, diễn đàn thảo luận, blog, chat, và các nền tảng chia sẻ hình ảnh và video, nhằm tạo điều kiện thuận lợi cho sự tương tác giữa người dùng.

Lý thuyết về đồ thị

Đồ thị là một tập hợp các đối tượng được gọi là nút, liên kết với nhau thông qua các cạnh Thông thường, đồ thị được thể hiện dưới dạng các điểm nút được nối bằng những đoạn thẳng hoặc cạnh Một đồ thị có thể được biểu diễn bằng ký hiệu G = (V, E), trong đó V là tập hợp các nút và E là tập hợp các cạnh.

• G gọi là đồ thị được cấu thành

• V là tập hợp các nút hoặc các nút của đồ thị (vertices / node)

• E là tập hợp các cạnh kết nối các nút của đồ thị (edge)

• 𝑒ij = (𝑣𝑖, 𝑣𝑗)𝜖𝐸 là biểu diễn các cạnh 𝑒𝜖𝐸 nối từ nút 𝑣 𝑖 tới nút 𝑣 𝑗 của đồ thị

• 𝑁(𝑣) = {𝑢 ∈ 𝑉|(𝑣, 𝑢)𝜖𝐸 là các nút kề u hay nút làng giềng có chung cạnh với nút v

Biểu diễn ma trận của đồ thị

• Thông tin về các kết nối trong đồ thị được biểu diễn bởi một ma trận kề A (adjacency matrix) là một ma trận vuông có kích thước 𝑛𝑥𝑛 với 𝑛 = |𝐸|

Ma trận kề A cũng được gọi là một ma trận trọng số thể hiện trọng số các cạnh của đồ thị

Hình 3: Biểu diễn ma trận của đồ thị

Một số loại đồ thị

Đồ thị vô hướng (undirected graph) là một cấu trúc có các cạnh không có hướng, được định nghĩa bởi một cặp không có thứ tự G = (V, E) Trong đó, V là tập hợp các đỉnh hoặc nút, và E là tập hợp các cặp không thứ tự gồm các đỉnh phân biệt, được gọi là các cạnh Hai đỉnh nằm trong cùng một cạnh được gọi là các đỉnh đầu cuối của cạnh đó.

Đồ thị vô hướng cho phép biểu diễn mối quan hệ hai chiều, trong đó các cạnh có thể được truyền theo cả hai hướng Cạnh nối giữa hai nút 𝑣𝑖 và 𝑣𝑗 thể hiện sự kết nối không phân biệt chiều.

Hình 4: Đồ thị vô hướng (undirect graph)

Đồ thị có hướng (direct graph) là một cấu trúc gồm các cạnh có hướng, được định nghĩa bởi một cặp có thứ tự G = (V, A) Trong đó, V là tập hợp các đỉnh hoặc nút, còn A là tập hợp các cặp có thứ tự chứa các đỉnh, được gọi là các cạnh có hướng hoặc cung Mỗi cạnh e = (x, y) được xem là có hướng từ x tới y, trong đó x là điểm đầu (gốc) và y là điểm cuối (ngọn) của cạnh.

• Với đồ thị có hướng, có chiều xác định từ nút 𝑣𝑖 tới 𝑣𝑗 và tồn tại liên kết cạnh 𝑒 ij

Hình 5: Đồ thị có hướng (direct graph)

Phân tích mạng xã hội (Social Network Analysis - SNA)

Phân tích mạng xã hội (SNA) đang trở nên phổ biến hơn bao giờ hết, khi mà quan hệ xã hội và kết nối mạng đóng vai trò quan trọng trong cuộc sống con người Mặc dù internet có thể làm giảm số lượng và tần suất các mối quan hệ vật lý, nhưng sự phát triển của công nghệ Web 2.0 đã tạo điều kiện cho mọi người tự tổ chức vào các mạng xã hội ảo, tương tự như trong thế giới thực Sự khác biệt nằm ở cách giao tiếp, từ tương tác mặt-đối-mặt đến giao tiếp qua công nghệ thông tin và truyền thông (CNTT&TT).

Phân tích mạng xã hội (SNA) có nguồn gốc từ xã hội học và lý thuyết đồ thị, được các nhà khoa học máy tính áp dụng để nghiên cứu các trang web, lưu lượng truyền thông và mức độ phổ biến thông tin Mạng lưới phân tích mối quan hệ giúp xây dựng giải pháp cho các vấn đề trong cấu trúc mạng, thường được biểu diễn dưới dạng đồ thị Lý thuyết đồ thị cung cấp các khái niệm và phương pháp phân tích cần thiết, kết hợp với các công cụ và phương pháp phát triển đặc biệt, tạo thành nền tảng cho SNA.

SNA không phải là một phương pháp luận mà là một cái nhìn độc đáo về chức năng của mạng xã hội Thay vì chú trọng vào cá nhân và các thuộc tính của họ hay các cấu trúc vĩ mô, SNA tập trung vào mối quan hệ giữa các cá nhân, nhóm và tổ chức xã hội.

Phân tích mạng xã hội, dựa trên lý thuyết mạng, đã trở thành một kỹ thuật quan trọng trong xã hội học hiện đại và được áp dụng rộng rãi trong nhiều lĩnh vực như nhân chủng học, sinh học, nghiên cứu truyền thông, kinh tế, địa lý, khoa học thông tin, nghiên cứu tổ chức và tâm lý xã hội Kỹ thuật này không chỉ giúp hiểu rõ hơn về các mối quan hệ xã hội mà còn trở thành một chủ đề nghiên cứu phổ biến với nhiều ứng dụng thực tiễn.

Phân tích mạng xã hội – SNA, được ứng dụng trong nhiều lĩnh vực khác nhau:

Các doanh nghiệp áp dụng Phân tích Mạng Xã hội (SNA) để tối ưu hóa lưu lượng giao tiếp trong nội bộ tổ chức cũng như với các mạng lưới đối tác và khách hàng của họ.

• Phát hiện xu hướng cộng đồng và các nhóm đối tượng khách hàng

Cơ quan thực thi pháp luật và quân đội áp dụng Phân tích Mạng Xã hội (SNA) để phát hiện và phân tích các mạng lưới tội phạm và khủng bố thông qua các dấu vết truyền thông thu thập được, từ đó xác định các đối tượng chủ chốt trong những mạng lưới này.

• Gợi ý kết bạn, gợi ý theo dõi các trang trên nền tảng Facebook

• Phân tích sự tương tác ở cấp độ nguyên tử và phân tử cho các vấn đề sinh học như phân tích tác dụng phụ của thuốc

Xây dựng hệ thống kiến nghị sản phẩm cho các trang thương mại điện tử như Amazon có thể học hỏi từ những tương tác người dùng và hệ thống gợi ý của các nền tảng phim và video như Youtube và Netflix Việc áp dụng các thuật toán gợi ý thông minh sẽ giúp cải thiện trải nghiệm mua sắm, tăng cường sự hài lòng của khách hàng và tối ưu hóa doanh thu cho các trang thương mại điện tử.

Các nhà khai thác mạng điện thoại di động áp dụng phương pháp SNA nhằm tối ưu hóa cấu trúc và nâng cao năng lực trong hệ thống mạng của họ.

Các tổ chức xã hội dân sự áp dụng Phân tích Mạng Xã hội (SNA) để phát hiện xung đột lợi ích thông qua việc khám phá các mối liên hệ ẩn giữa các cơ quan chính phủ, các nhóm vận động hành lang và doanh nghiệp.

Hình 6: Các dạng dữ liệu đồ thị trong thực tế

Một số bài toán điển hình

Bài toán dự đoán liên kết (link prediction) liên quan đến việc xác định khả năng xuất hiện mối liên hệ mới giữa hai nút trong mạng Ví dụ, trong mạng xã hội, hệ thống có thể gợi ý kết bạn giữa những người chưa từng liên kết dựa trên các mối quan hệ hiện có Ngoài ra, các công ty cũng áp dụng dự đoán liên kết để xác định khách hàng có khả năng mua sản phẩm tiếp theo, tương tự như việc dự đoán kết nối giữa người tiêu dùng và sản phẩm.

Hình 7: Bài toán dự đoán liên kết trong đồ thị

Bài toán phân loại và dự đoán nút trên đồ thị là một thách thức phổ biến, trong đó chúng ta cần dự đoán các thuộc tính và phân loại các nút không có nhãn Mô hình đồ thị thường tận dụng thông tin từ các nút đã có nhãn để suy diễn và xác định các thuộc tính của những nút chưa được gán nhãn.

Hình 8:Phân loại nút trong đồ thị

Phân cụm và phát hiện cộng đồng

Bài toán phân cụm và phát hiện cộng đồng liên quan đến việc xác định các nhóm nút có mối liên hệ chặt chẽ với nhau hoặc chia sẻ một đặc điểm chung Ví dụ, các nhóm này có thể bao gồm các nhà toán học, nhà nghiên cứu hóa học, vật lý, sinh học, và nhiều lĩnh vực khác.

Hình 9: Phân cụm và phát hiện cộng đồng trong đồ thị [4]

Bài toán phân loại đồ thị sử dụng toàn bộ cấu trúc đồ thị để phân loại hoặc dự đoán một đặc tính cụ thể, và nó được áp dụng phổ biến trong lĩnh vực dữ liệu phân tử hóa học Ví dụ, một ứng dụng thực tiễn là xác định xem một phân tử có phù hợp để trở thành một loại thuốc hay không.

Hình 10: Đồ thị mô hình hóa tác dụng phụ của thuốc polypharmacy [5]

Phân tích độ ảnh hưởng của nút trong đồ thị

Từ góc độ phân tích mạng xã hội, việc xác định độ ảnh hưởng của người dùng mạng xã hội trực tuyến phụ thuộc vào vị trí và vai trò của các nút trong cấu trúc kết nối mạng Các phương pháp phân tích dựa trên độ trung tâm của nút được áp dụng để đo lường mức độ ảnh hưởng của các nút trong mạng.

Trong nghiên cứu và phân tích đối tượng trên mạng xã hội, việc trả lời các câu hỏi của khách hàng về ảnh hưởng trực tuyến và các nhân vật có tầm ảnh hưởng là rất quan trọng.

Các công ty nhận thức rằng họ không phải là lực lượng duy nhất định hình thương hiệu và cần tiếp cận những người khác để nâng cao hiệu quả chiến dịch xã hội Điều này yêu cầu xác định đúng các blogger và tài khoản có ảnh hưởng, những người đang tham gia vào cuộc trò chuyện về thương hiệu hoặc chủ đề cụ thể Tuy nhiên, việc xác định ai là người có ảnh hưởng không phải là điều đơn giản, vì ảnh hưởng là một hiện tượng phức tạp, phụ thuộc vào nhiều yếu tố như đặc điểm cá nhân, bối cảnh và mối quan hệ.

Dữ liệu liên kết giữa bài đăng trên mạng xã hội và các hành động của người tiêu dùng, như mua sản phẩm hoặc tẩy chay doanh nghiệp, hiện chưa có sẵn Thay vào đó, chúng ta có thể đánh giá "tiềm năng gây ảnh hưởng" thông qua phân tích đối tượng trên mạng xã hội, xác định ai đang tiếp cận khán giả lớn, thu hút sự chú ý và nhận được nhiều tương tác, cũng như ai thể hiện kiến thức chuyên môn nhất quán về một chủ đề Do đó, cần thiết phải có một chỉ số để phân tích thông điệp nào đang tiếp cận được đối tượng lớn nhất.

Những người có ảnh hưởng trên mạng xã hội là những cá nhân sở hữu lượng người dùng trung thành và có mức độ tương tác cao với nội dung của họ, bao gồm hình ảnh, blog, bài đăng và video Họ thường được xem là chuyên gia trong lĩnh vực của mình, có khả năng thuyết phục mạnh mẽ và có thể ảnh hưởng đến quyết định của người khác Việc hợp tác với những người có ảnh hưởng này rất hữu ích cho các chiến dịch tiếp thị lan truyền, quảng bá sản phẩm, thay đổi hành vi và phân tích sự lây lan của dịch bệnh Đặc biệt, đối với các thương hiệu nhỏ, việc tìm kiếm một người có ảnh hưởng với hàng nghìn người theo dõi trung thành để quảng bá sản phẩm sẽ tiết kiệm chi phí và hiệu quả hơn so với việc chi ngân sách cho quảng cáo truyền thống như bảng quảng cáo hay quảng cáo trên TV.

Trên mạng xã hội, không chỉ có những người nổi tiếng như PewDiePie hay Jamie Oliver mà còn nhiều người dùng khác với lượng khán giả từ 1.000 đến 100.000 người Những người này đã đạt được sự công nhận trong lĩnh vực của họ và mặc dù số lượng người theo dõi không lớn, họ vẫn có khả năng ảnh hưởng đáng kể đến hành vi và quyết định của một lượng lớn người.

Độ đo trung tâm dựa trên bậc (Degree Centrality) của một nút trong mạng xã hội được xác định bởi số lượng liên kết mà nút đó có Trong mạng có hướng, có hai loại trung tâm bậc: in-degree, là số liên kết từ các nút khác đến nút đang xem xét, và out-degree, là số liên kết mà nút đó hướng đến các nút khác Tổng của in-degree và out-degree tạo thành bậc của nút In-degree thường được xem như sự phổ biến, trong khi out-degree thể hiện sự hòa đồng Đối với đồ thị vô hướng, trung tâm bậc của một nút v được tính bằng bậc của nó Ví dụ, trong một đồ thị cụ thể, các nút 2 và 3 có mức trung tâm cao nhất.

Hình 12: Đồ thị vô hướng trong độ đo trung tâm dựa trên trung tâm bậc

Trung tâm bậc của nút 𝑣, một đồ thị được biểu diễn dưới dạng 𝐺 = (𝑉, 𝐸) với | 𝑉| nút và |𝐸| cạnh, được định nghĩa là (theo [7]):

Độ trung tâm bậc của một nút trong đồ thị được tính bằng cách sử dụng công thức 𝐶𝐷(𝑣) = deg (𝑣) Việc tính toán độ trung tâm cho tất cả các nút trong đồ thị sẽ tốn thời gian 𝛩(𝑉²) đối với đồ thị có ma trận kề dày đặc và 𝛩(𝐸) đối với đồ thị có ma trận kề thưa thớt Định nghĩa về tính trung tâm ở cấp độ nút có thể được mở rộng cho toàn bộ đồ thị, và trong trường hợp này, chúng ta gọi là đồ thị tập trung (graph centralization) Nếu 𝑣∗ là nút có mức độ trung tâm cao nhất trong G, thì 𝑋 được định nghĩa là (𝑌, 𝑍).

|Y|-đồ thị liên thông tối đa hóa số lượng (với 𝑦 ∗ là nút có độ trung tâm bậc cao nhất trong X):

Tương ứng, mức độ trung tâm bậc của đồ thị G như sau:

Giá trị của 𝐻 đạt tối đa khi đồ thị 𝑋 có một nút trung tâm kết nối tất cả các nút còn lại, tạo thành đồ thị sao.

Vì vậy, đối với bất kỳ đồ thị 𝐺 = (𝑉, 𝐸):

Ngoài ra, một độ đo toàn cục mở rộng mới cho trung tâm bậc có tên là Tendency to Make Hub (TMH) được định nghĩa như sau:

Trong đó, TMH tăng theo sự xuất hiện của mức độ trung tâm bậc trong đồ thị

Miền giá trị của độ đo này nằm trong khoảng [0 1] Khi giá trị càng gần tiến đến

Độ đo trung tâm của một nút trong mạng càng lớn khi nó nằm gần trung tâm của đồ thị Nút có độ đo trung tâm theo bậc cao nhất, gần bằng 1, được gọi là hệ số kết nối (hub) Hệ số hub phản ánh tầm ảnh hưởng của nút này trong đồ thị Độ đo trung tâm dựa trên sự lân cận (Closeness Centrality) là một yếu tố quan trọng trong việc đánh giá vai trò của các tác nhân trong mạng lưới.

Closeness centrality là một chỉ số đo lường khoảng cách từ một nút đến các nút khác trong đồ thị, cho thấy rằng nút càng ở trung tâm thì càng gần gũi với các nút còn lại Trung tâm lân cận của nút 𝑣 trong đồ thị G(V, E) với |V| nút và |E| cạnh có thể được tính bằng một trong hai công thức khác nhau.

Công thức (I) cho closeness centrality được xác định bằng cách lấy trị nghịch đảo của tổng khoảng cách ngắn nhất từ một nút đến tất cả các nút khác trong đồ thị.

• Công thức (II) : Closeness centrality được tính bằng bình quân của tổng số khoảng cách ngắn nhất từ một nút đến tất cả các nút còn lại

𝐶𝑐(𝑣) 𝑛 − 1 Với 𝑑𝐺(𝑣, 𝑡) là khoảng cách ngắn nhất từ nút 𝑣 đến 𝑡 của đồ thị

Công thức tính closeness centrality của nút 𝑣 theo dạng chuẩn:

Hình 13 dưới cho biết Rafael có giá trị closeness centrality tốt nhất vì có thể liên lạc với các nút khác thông qua đường đi ngắn nhất

Hình 13: Mô tả mức độ Closeness Centrality của đồ thị Độ đo trung tâm dựa trên trung gian (Betweennees Centrality)

Centrality giữa các nút trong mạng được xác định thông qua Betweenness Centrality, tính bằng tổng số đường đi ngắn nhất đi qua nút đó chia cho tổng số đường đi ngắn nhất trong toàn mạng Điều này cho thấy Betweenness Centrality là một chỉ số quan trọng để đánh giá vị trí của một tác nhân trong mạng, cũng như khả năng kết nối của nó với các cặp hoặc nhóm tác nhân khác.

Trung tâm dựa trên trung gian của nút 𝑣 của đồ thị được biểu diễn dưới dạng

𝐺 = (𝑉, 𝐸) với |𝑉| nút và |𝐸| cạnh có công thức như sau:

• 𝜎𝑠𝑡(𝑣) : Tổng số đường đi ngắn nhất từ nút s đến t và có qua nút 𝑣 (𝑠 ≠ 𝑣

• 𝜎𝑠𝑡 : Tổng số các đường đi ngắn nhất từ nút s đến t (𝑠 ≠ 𝑣 ≠ 𝑡)

Công thức tính Betweenness centrality của nút 𝑣 theo dạng chuẩn:

Độ đo 𝐶𝐵(𝑣) và 𝐶′𝐵(𝑣) được tính bằng công thức (𝑛 − 1)(𝑛 − 2)/2, với miền giá trị nằm trong khoảng [0 1] Giá trị của một nút càng lớn thì ảnh hưởng của nó đến việc phân bổ cấu trúc của các cụm hay nhóm trong mạng càng mạnh Nút có vai trò trung tâm lớn trong mạng sẽ có tác động lớn hơn đến cấu trúc tổng thể.

Trong mạng lưới thông tin, 23 tầm ảnh hưởng lớn có vai trò quan trọng trong việc kiểm soát thông tin trao đổi giữa các tác nhân Việc tính toán trung tâm dựa trên trung gian và sự lân cận có độ phức tạp Θ(|𝑉|^3) với thuật toán Floyd-Warshall Tuy nhiên, trên các đồ thị thưa thớt, thuật toán Johnson hoặc Brandes có thể mang lại hiệu quả cao hơn với độ phức tạp chỉ là Θ(|𝑉|^2 + |𝑉||𝐸|).

Hình 14: Mô tả mức độ Betweenness Centrality của đồ thị

John và Jame nằm giữa các nút khác nhưng Rafael có độ Betweenness Centrality cao nhất bởi vì:

• Nếu xóa John thì đồ thị không bị tách rời

• Nếu xóa Jame thì đồ thị mất hai nút là Alice và Bob

Mạng xã hội facebook

Facebook là một mạng xã hội miễn phí do công ty Facebook, Inc điều hành Người dùng có thể kết nối và giao tiếp với nhau thông qua các mạng lưới theo thành phố, nơi làm việc, trường học và khu vực.

Mọi người có thể kết bạn, gửi tin nhắn và cập nhật trang hồ sơ cá nhân để thông báo cho bạn bè về những điều mới mẻ trong cuộc sống của mình.

Hình 19: Giao diện chính của facebook

Với hơn 2,7 tỷ người dùng, Facebook là mạng xã hội phổ biến toàn cầu, thu hút người dùng ở mọi độ tuổi và nền văn hóa Nền tảng này không chỉ giúp doanh nghiệp kết nối với khách hàng dễ dàng mà còn tạo cơ hội xây dựng mối quan hệ và thu thập thông tin về sản phẩm, dịch vụ.

Hình 20: Lượng người sử dụng facebook trên thế giới tính đến tháng 2/2021.(Nguồn: https://bit.ly/3w16br5 )

Wall là trang cá nhân trên Facebook, nơi bạn có thể chia sẻ và cập nhật các trạng thái, bình luận, hình ảnh và video mới nhất của mình.

Status: Nó đồng nghĩa với "what's on your mind", bạn đang nghĩ gì, muốn chia sẻ điều gì với mọi người

Ghi chú là nơi bạn có thể tự do viết mọi thứ mà không bị giới hạn về số lượng, khác với trạng thái chỉ cho phép bạn viết ngắn gọn.

Comment: Bình luận của bạn hoặc người khác về một status, link, note

Nút "Like" trên Facebook cho phép người dùng thể hiện sự yêu thích đối với một trạng thái, bình luận hoặc liên kết từ các trang web khác Khi bạn nhấn vào nút này, bạn đang bày tỏ sự đồng tình hoặc thích thú với nội dung mà mình thấy.

Trên Facebook, bạn có thể kết bạn với nhiều người và nhận lời mời kết bạn từ họ Nền tảng này cũng cung cấp tính năng gợi ý bạn bè, giúp bạn dễ dàng tìm kiếm và kết nối với những người có thể bạn quen biết, đặc biệt hữu ích cho những người mới sử dụng.

New Feeds: This feature provides the latest updates, including information, statuses, and comments from your friends and social groups, continuously refreshed in real-time.

Tag: Tính năng này giúp nhận diện một cá nhân, thương hiệu trong một hình ảnh, video hoặc bài viết nào đó

Khó khăn trong việc thu thập dữ liệu facebook

Có 2 cách để thu thập dữ liệu trên facebook:

Cách 1: Sử dụng API chính thức của Facebook là phương pháp truyền thống, được hỗ trợ đầy đủ tại [đây](https://developers.facebook.com/docs/graph-api/) Mỗi API thực chất là một đường link, và Facebook sẽ trả về dữ liệu theo định dạng JSON.

Hình 21: Dữ liệu Graph API facebook (Nguồn: https://bit.ly/3tQaeop)

Kể từ sau scandal Cambridge Analytics, Facebook đã thắt chặt việc truy cập dữ liệu, siết chặt quyền và thông tin trả về khi sử dụng API Một số API đã bị cấm hoàn toàn, ví dụ như người dùng chỉ có thể xem bài viết của chính mình mà không thể thấy bài viết của bạn bè có bình luận.

 Do đó không thể sử dụng phương pháp này với bài toán cho số lượng lớn người dùng

Sử dụng phương thức scraping là một kỹ thuật hiệu quả để thu thập thông tin từ trang web, thông qua việc áp dụng các con "bot" hay "crawler" để đọc mã nguồn và trích xuất dữ liệu từ các thẻ HTML Một số công cụ phổ biến cho phương pháp này bao gồm scrapy và selenium.

Hiện nay, Facebook đang siết chặt việc phát hiện các tài khoản "bot" Nếu bị phát hiện, tài khoản crawler sẽ bị khóa vĩnh viễn và việc tạo tài khoản mới cho crawler cũng gặp nhiều khó khăn.

Phương pháp thu thập dữ liệu

Selenium WebDriver là công cụ kiểm thử phần mềm tự động, nhưng gặp khó khăn trong việc thu thập dữ liệu từ các trang lớn do sử dụng trình duyệt, dẫn đến quá tải RAM Ngược lại, Scrapy là framework thu thập dữ liệu hiệu quả mà không cần trình duyệt, giúp tiết kiệm bộ nhớ Nó bao gồm các thành phần để quản lý yêu cầu, duy trì phiên người dùng, theo dõi chuyển hướng và xử lý pipeline đầu ra.

Hình 22: Data flow của scrapy [19]

• Scrapy Engine : Engine chịu trách nhiệm điều khiển luồng giữa các

Component trong hệ thống và kích hoạt khi một số hành động nhất định xảy ra

• Scheduler : Có nhiệm vụ nhận request từ engine và đưa nó vào một queue để sắp xếp các URL theo một thứ tự Download

• Downloader : Có nhiệm vụ tải Source HTML của trang web và gửi nó về cho Engine

A Spider is a class created by a developer that analyzes responses, extracts items, generates new URLs, and reloads them into the Scheduler via the Engine.

• Item Pipeline : Có nhiệm vụ xử lí các Item sau khi được extract bằng spider, sau đó lưu vào cơ sở dữ liệu

• Downloader middlewares : Là móc nối giữa Engine và Downloader, chúng xử lí các request được đẩy từ engine và các response tạo ra từ Downloader

• Spider middlewares : Là móc nối giữa Engine và Spider, chúng có nhiệm vụ xử lí input (response) của Spider và đầu ra (items và request)

Quy trình thu thập của hệ thống :

1 Engine khởi tạo Request để bắt đầu crawl từ Spider

2 Engine lên lịch trình cho Request từ Spider và yêu cầu cho Request tiếp theo để crawl

3 Scheduler gửi request tiếp theo đến Engine

4 Engine gửi Request đến Downloader, đi qua Downloader Middleware

5 Sau khi tải source HTML hoàn tất, Downloader khởi tạo một Object Response trả về qua Engine, quá trình này đi qua Downloader MiddleWare

6 Engine nhận Response từ Downloader, và gửi về Spider để xử lí, quá trình này đi qua Spider Middleware

7 Spider xử lí Response và trả về các Item đã được scrape, sau đó khởi tạo Request đến Engine, thông qua Spider Middleware

8 Engine gửi các Item đã được xử lí đến Item pipelines, sau đó gửi các Request đã được xử lí đến Scheduler và yêu cầu Request tiếp theo để crawl

9 Tiến trình lặp lại như bước 1, cho đến khi không còn Request nào từ Scheduler Để tránh vấn đề phát hiện “bot” của Facebook, qua quá trình thực nghiệm em rút ra một số phương pháp giải quyết như sau:

• Tăng độ tin cậy của tài khoản bằng các hành động như người sử dụng

• IP của mỗi tài khoản crawler sẽ là khác nhau (việc đổi IP này sẽ dùng DCOM 3G)

• Thay đổi User Agent (UA - là một chuỗi nhận diện của trình duyệt web khi gửi yêu cầu đến máy chủ web)

Việc thu thập dữ liệu theo thời gian không chỉ phản ánh đúng xu hướng mà còn đảm bảo có được thông tin đầy đủ nhất, với số lượng bình luận trên một bài viết của một số người nổi tiếng có thể lên đến 10.000 bản ghi.

Mô tả về dữ liệu thu thập

Hiện nay, số lượt thích trên trang cá nhân và fanpage không còn phản ánh chính xác sự nổi tiếng thực sự do sự xuất hiện của like ảo Những lượt thích này đến từ các tài khoản Facebook ảo, được lập ra nhanh chóng mà không có người sử dụng thực sự, chỉ nhằm mục đích like chéo giữa các trang fanpage Do đó, like ảo không phải là đối tượng mà cá nhân hay fanpage mong muốn hướng đến.

Người dùng Facebook thường có mối quan hệ bạn bè, phản ánh sự tương tác giữa họ Tuy nhiên, mỗi người chỉ có tối đa 5000 bạn bè, khiến cho chỉ số này ít biến động và ảnh hưởng đến độ chính xác trong việc xác định người có sức ảnh hưởng.

Em quyết định thu thập dữ liệu bình luận từ các bài viết trên trang cá nhân và fanpage của những người hoạt động trong lĩnh vực ca nhạc và giải trí Dữ liệu sẽ được thu thập theo từng tài khoản trong danh sách những người làm việc trong ngành này.

Hình 23: Các bình luận trên một bài viết

ĐÁNH GIÁ THỬ NGHIỆM

Thực nghiệm và đánh giá với bộ dữ liệu ego-facebook

Bộ dữ liệu ego-Facebook chứa 4.039 nút, được đánh số từ 0 đến 4038, cùng với 88.234 cạnh thể hiện mối quan hệ bạn bè giữa các người dùng Dữ liệu này được thu thập từ những người tham gia khảo sát, cung cấp cái nhìn sâu sắc về mạng lưới kết nối trong cộng đồng Facebook.

J McAuley and J Leskovec thay thế số định danh nội bộ (UID) của Facebook cung cấp cho từng người dùng bằng một giá trị mới, điều này đảm bảo tính riêng tư của người dùng Bộ dữ liệu được khai phá liên quan quan hệ bạn bè giữa những người dùng Các mối quan hệ này được trực quan hóa và biểu diễn dưới dạng đồ thị với các nút là các người dùng và các cạnh là các quan hệ bạn bè

Thực nghiệm sử dụng các thuật toán

• Thời gian tính toán : 0.006 giây

• 15 người có độ đo cao nhất :

Hình 24: Đồ thị theo độ đo trung tâm dựa trên trung tâm bậc

Thời gian tính toán : 195 giây

15 người có độ đo cao nhất :

Hình 25: Đồ thị theo độ đo trung tâm dựa trên trung gian

Hình 26: Đồ thị theo độ đo trung tâm dựa theo sự lân cận

Hình 27: Đồ thị theo độ đo trung tâm dựa trên trị vector đặc trưng

Thời gian tính toán : 1.006 giây

Hình 28: Đồ thị theo độ đo trung tâm dựa theo PageRank

15 người có độ đo cao nhất (theo authority) :

Hình 29: Đồ thị theo độ đo trung tâm dựa theo HITS

Kết quả đánh giá và so sánh độ ảnh hưởng của từng nút được trình bày qua biểu đồ cột trong hình 33 và hình 34, cho thấy các nút cùng với giá trị độ ảnh hưởng tương ứng Thực nghiệm này được thực hiện trên bộ dữ liệu ego-Facebook.

Hình 30: Đồ thị đường biểu diễn kết quả tính toán độ ảnh hưởng của 4039 người dùng được đánh số từ 0 đến 4038 trên mạng xã hội Facebook bằng PageRank

Phân tích kết quả từ 4039 người dùng trong bộ dữ liệu bằng thuật toán PageRank cho thấy người dùng có độ ảnh hưởng cao nhất được đánh số.

3437 (𝑟𝑎𝑛𝑘3437 = 0.007614), kết quả này cao gấp 186 lần độ ảnh hưởng của người dùng được đánh số 2079, 2195, 2269, 2457, 2470 (đều có 𝑟𝑎𝑛𝑘 0.000041) Và tổng của tất cả độ ảnh hưởng bằng 1 ( 𝑟𝑎𝑛𝑘𝑖 = 1)

Tính trung tâm của Eigenvector đánh giá tầm quan trọng của một nút thông qua sự ảnh hưởng của các nút lân cận Chẳng hạn, một nút với 300 bạn bè ít nổi tiếng sẽ có mức độ trung tâm thấp hơn so với một nút có 300 bạn bè nổi tiếng như Sơn Tùng hay Jack Trong mạng egofacebook, một nút có ít bạn nhưng bạn bè của nó lại rất nổi tiếng vẫn có giá trị eigenvalue cao Điều này cho thấy khác biệt so với các chỉ số trung tâm khác, mà chủ yếu dựa vào số lượng bạn bè Đối với phương pháp HITS, giá trị thẩm quyền 𝑎𝑢𝑡ℎ𝑜𝑟𝑖𝑡𝑦 phụ thuộc vào giá trị trung tâm của các nút liên kết, khác với các phương pháp đo lường khác Để so sánh, các chỉ số trung tâm dựa trên bậc, trung gian và sự lân cận được tính toán từ dữ liệu ego-facebook, và kết quả của ba phương pháp này được biểu đồ hóa.

Hình 31: Đồ thị đường biểu diễn kết quả tính toán độ ảnh hưởng của 4039 người dùng được đánh số từ 0 đến 4038 trên mạng xã hội Facebook bằng Closeness Centrality

Hình 32: Đồ thị đường biểu diễn kết quả tính toán độ ảnh hưởng của 4039 người dùng được đánh số từ 0 đến 4038 trên mạng xã hội Facebook bằng Degree Centrality

Hình 33: Đồ thị đường biểu diễn kết quả tính toán độ ảnh hưởng của 4039 người dùng được đánh số từ 0 đến 4038 trên mạng xã hội Facebook bằng Betweenness Centrality

Biểu đồ đường cho thấy sự tương quan giữa các thuật toán thông qua giá trị độ đo của các nút Dựa trên kết quả, 10 người dùng có độ đo cao nhất trong các thuật toán được xác định như sau:

Bảng 1: Thứ hạng 10 người dùng có độ đo cao nhất theo các thuật toán trung tâm

Bảng dữ liệu cho thấy rằng, bất chấp việc áp dụng các thuật toán khác nhau để đo lường độ ảnh hưởng, những người dùng có mã số {0, 107, 1684, 1912, 3437} vẫn nằm trong top 10 người dùng có ảnh hưởng lớn nhất Để có cái nhìn tổng quát về toàn bộ kết quả, phép tính độ tương quan 𝜌 (𝑃𝑒𝑎𝑟𝑠𝑜𝑛 𝐶𝑜𝑟𝑟𝑒𝑙𝑎𝑡𝑖𝑜𝑛) giữa kết quả của thuật toán Quantum PageRank và bốn phương pháp khác đã được thực hiện Cách tính độ tương quan này được tiến hành nhằm đánh giá mức độ tương đồng giữa các phương pháp.

Để so sánh hai bộ dữ liệu X và Y, chúng ta tiến hành tính toán độ tương quan giữa chúng Kết quả của phép tính này được trình bày trong bảng dưới đây.

# Phương pháp Độ tương quan với thuật toán PageRank

Bảng 2: Độ tương quan giữa thuật toán PageRank và các thuật toán degree, betweenness và closeness

Sự tương quan giữa thuật toán PageRank và các thuật toán độ trung tâm như độ trung tâm trung gian và độ trung tâm dựa trên bậc của nút đạt khoảng 67% sự tương đồng Mặc dù mỗi phương pháp tính có những đặc trưng riêng, nhưng PageRank cho thấy sự tác động tổng thể của các nút trong mạng, mang lại kết quả tốt hơn khi so sánh với các phương pháp đơn giản khác Để xác nhận tính đúng đắn của thuật toán PageRank, chúng ta sẽ tiến hành kiểm tra trên bộ dữ liệu đã thu thập.

Thực nghiệm và đánh giá với bộ dữ liệu thực

Hình 34: Các bước thực hiện xử lý dữ liệu thu thập được

Bộ dữ liệu em thu thập được như mô tả tại phần 3.1 và 3.2, dữ liệu bao gồm

141923 nút (người dùng) được thu thập từ 1714 bài viết được trong khoảng thời gian từ ngày 11/04/2021 đến 15/05/2021

Thu thập và trích rút dữ liệu

Dữ liệu thu thập bao gồm:

• Source : Tên tài khoản bình luận

• Reply_to : Tên, đường dẫn đến tài khoản trả lời bình luận của tài khoản bình luận trên bài viết gốc (nếu có)

• Text : Nội dung bình luận

• Source_url : Đường dẫn đến trang cá nhân của tài khoản bình luận trên bài viết gốc

• Url : ID của bài viết gốc

• Page_id : đường dẫn đến trang cá nhân của người sở hữu bài viết gốc

Hình 35: Nội dung dữ liệu thô thu thập được

Mô tả dữ liệu thu thập:

Số lượng page/person thu thập

Bảng 3: Mô tả dữ liệu thu thập từ Facebook

Quá trình thu thập dữ liệu có thể gặp phải vấn đề trùng lặp, do đó, các tập dữ liệu cần được xử lý và làm sạch Việc này là cần thiết để tổ chức cấu trúc dữ liệu một cách hợp lý cho bài toán cụ thể.

Hình 36: Dữ liệu một bản ghi trên bài viết gốc

Hình 37: Dữ liệu một bản ghi trả lời một bình luận trên bài viết gốc

Mô hình hóa sang đồ thị đồng nhất

Dữ liệu mạng xã hội trong đồ án này chủ yếu từ Facebook, bao gồm các thực thể như Người, Trang, Bài Viết và Bình Luận Đồ án tập trung vào phân tích bình luận trên các bài viết, sử dụng dữ liệu mạng xã hội để thể hiện các nút trạng thái trong biểu đồ đồng nhất Ý tưởng chính là các bài viết từ cá nhân hoặc trang đại diện cho một người thường xoay quanh cùng một chủ đề như giải trí hay âm nhạc trong một khoảng thời gian nhất định.

Input: Person (P), Page (Pg), Comment(C), Status(S)

N For Pi in set (P, Pg) do:

Where Pi write a status Sj:

If Pk comment status Sj:

Add Pk in N Create a connection Cik from Pk to Pi Else Pm reply to a comment Cjk of Pk in Status j:

Create a connection Cmk and Cmi End for Return G, N

Dữ liệu sau khi xử lý thành đồ thị:

Số nút người sau khi xử lý 141923

Bảng 4: Dữ liệu sau khi mô hình hóa sang đồ thị đồng nhất

Hình 38: Đồ thị đồng nhất sau khi xử lý

Thực nghiệm sử dụng các thuật toán

Bước 1: Thu thập dữ liệu theo tuần

Bước 2: Xử lý đưa dữ liệu về đồ thị đồng nhất

Bước 3: Thực nghiệm và so sánh các phương pháp xếp hạng nút ảnh hưởng trong đồ thị

Dữ liệu sau đây được tính toán theo 1 tuần từ 11/04/2021-17/04/2021

Hình 39: Đồ thị theo độ đo trung tâm dựa theo bậc với dữ liệu thực

Bảng 5: Xếp 7 người có hạng cao nhất theo dữ liệu thực từ ngày 11/04/2021 đến

Từ ngày 11/4/2021 đến 17/4/2021, Jack 97 ghi nhận sự ảnh hưởng mạnh mẽ khi thông báo ra mắt bài hát mới "laylalay", thu hút lượng tương tác cao từ người hâm mộ Tương tự, Sơn Tùng M-TP cũng chuẩn bị phát hành ca khúc mới mang tên "Muộn rồi mà sao còn", hứa hẹn tạo nên sự chú ý trong cộng đồng yêu nhạc.

Hình 40: Đồ thị theo độ đo trung tâm dựa theo trung gian với dữ liệu thực

Hình 41: Đồ thị theo độ đo trung tâm dựa theo sự lân cận với dữ liệu thực

Hình 42: Đồ thị theo độ đo trung tâm dựa theo PageRank với dữ liệu thực

Phân tích kết quả từ 45374 người dùng dựa trên thuật toán PageRank cho thấy người dùng có độ ảnh hưởng cao nhất được đánh số 1 với giá trị 𝑟𝑎𝑛𝑘1 = 0.1393, cao gấp nhiều lần so với các người dùng khác Tổng độ ảnh hưởng của tất cả người dùng là 1 (𝑟𝑎𝑛𝑘𝑖 = 1).

Hình 43: Đồ thị theo độ đo trung tâm dựa theo Quantum PageRank với dữ liệu thực

Kết quả tính độ tương quan được biểu diễn trong bảng dưới đây:

# Phương pháp Độ tương quan với thuật toán PageRank

Bảng 6: Độ tương quan giữa thuật toán PageRank và các thuật toán degree, betweenness và closeness theo dữ liệu thực

Bảng so sánh các phương pháp :

Bảng 7: Bảng kết quả xếp hạng theo từng tuần với dữ liệu thực

Nhận xét: Ta nhận thấy 4 tuần đầu tiên Jack 97 (số 4600) và Sơn Tùng MTP (số

1) luôn xếp đầu, nhưng đến tuần thứ 5 thì hạng bị tụt xuống (Sơn Tùng MTP vị trí thứ 5 và Jack 97 vị trí số 23 ) do đây là thời điểm sau sự kiện ra bài hát mới nên các bài giới thiệu và cập nhật trạng thái giảm đi Thay vào đó là Trấn Thành phát hành phim điện ảnh “Bố già”, và Mỹ Tâm (số 90255) mở liveshow “Tri Âm” Số thứ tự 20346 (Thủy Tiên) và 23806 (Hồ Ngọc Hà) là những tài khoản có lượng tương tác cao vì họ có những bài viết quảng cáo cho các nhãn hàng như: MOI cosmetics, 82XPlacenta, Guccimulticolor,…

Định dạng
Số trang	59
Dung lượng	3,61 MB