Danh mục

Ứng dụng thuật toán PageRank đánh giá độ ảnh hưởng của người dùng trên mạng xã hội

Số trang: 7      Loại file: pdf      Dung lượng: 520.06 KB      Lượt xem: 25      Lượt tải: 0    
tailieu_vip

Xem trước 1 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

Bài toán đánh giá độ ảnh hưởng hay tầm quan trọng của người dùng mạng xã hội là một trong những lĩnh vực ứng dụng quan trọng trong sử dụng những kĩ thuật của phân tích mạng xã hội. Bài viết đặt vấn đề tìm hiểu thuật toán nổi tiếng PageRank dùng trong cỗ máy tìm kiếm Google để tính toán độ ảnh hưởng dựa trên mối quan hệ của người dùng mạng xã hội.
Nội dung trích xuất từ tài liệu:
Ứng dụng thuật toán PageRank đánh giá độ ảnh hưởng của người dùng trên mạng xã hội 254 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2020 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” Ứng Dụng Thuật Toán PageRank Đánh Giá Độ nh Hưởng Của Người Dùng Trên Mạng Xã Hội TS. Đoàn Trung Sơn, Nguyễn Ly Na Khoa An ninh thông tin H c vi n An ninh nhân dân son.doantrung@gmail.com Tóm tắt. Bài toán đ nh gi đ nh hư ng hay t m quan tr ng c a ngư i d ng m ng x h i là m t trong những l nh v c ng d ng quan tr ng s d ng những k thu t c a phân tích m ng x h i. Tuy nhiên, hi n nay c c nghiên c u còn nhi u h n ch v đ chính x c tính to n và đ đo đư c ch p nh n ph bi n b i c ng đ ng. Chính v l do đ , c c t c gi đ t v n đ t m hi u thu t to n n i ti ng PageRank d ng trong c m y t m ki m c a Google đ tính toán đ nh hư ng d a trên c c m i quan h c a ngư i d ng m ng x h i. Từ khóa: M ng x h i, đ nh hư ng ngư i d ng m ng x h i, PageRank. Abstract. The problem of evaluating the influence or the level of importance of social network users is one of the important areas of application using the techniques of social network analysis. However, there are currently limited researches on computational accuracy and measurement commonly accepted by the community. For that reason, authors decided to figure out the famous algorithm PageRank, which is used in the search engine of Google in order to calculate the influence based on the relationships of social network users. Keywords: Social Network Analysis, Influence of Social Network User, PageRank 1 Đặt vấn đề 1.1 Giới thiệu về mạng xã hội Trong những năm g n đây, c ng với s ph t m nh mẽ c a Web 2.0, m ng x h i tr c tuy n như Facebook, Twitter, Instagram... ngày càng tr nên ph bi n. Theo định ngh a c a SearchCIO of Techtarget [1]: “Mạng xã hội là website cho phép người dùng có chung sở thích chia sẻ các thông tin, hình ảnh, âm thanh” c ng c th theo t đi n Oxford [2] “Mạng xã hội là một mạng lưới các tương tác và quan hệ xã hội của con người. Là website dành riêng cho việc cung cấp các thông tin, tin nhắn, góp ý, chia sẻ hình ảnh, âm thanh”. M ng x h i là m t c u trúc x h i đư c t o lên t c c c nhân ho c t ch c đư c g i là c c “nút” đư c lên k t ho c k t n i b i m t ho c nhi u ki u ph thu c với nhau như: quan h b n bè, h hàng, c chung quy n l i, trao đ i tài chính, c ng v n đ quan tâm, quan h t nh c m, ho c quan h d a trên s tin tư ng, s hi u bi t lẫn nhau. M ng x h i đư c xem như th giới o cho phép k t n i c c thành viên c c ng s thích l i với nhau và c nhi u tính năng ph c v ngư i d ng. M ng x h i c c c tính năng chính sau: liên k t với c ng đ ng, tính đa phương ti n và kh năng lưu trữ, truy n t i thông tin. Trong bài b o này, m ng x h i đư c coi như m t đ thị trong đ c c nút c th là m t ngư i d ng, c th , t ch c, còn c c c nh c a đ thị là quan h x h i như b n bè, gia đ nh, công vi c. M ng xã h i ph n nh m t c u trúc xã h i đư c t o thành t các nút là c c ngư i d ng và các cung là c c m i quan h . Trong lý thuy t đ thị, m ng x h i đư c bi u diễn là m t đ thị = ( , , ) trong đ : - = , … : là m t t p h p c c nút t đ n bi u diễn ngư i d ng hay t c nhân, trong đ là s lư ng nút trong m ng. - ⊆ × : là m t t p c c c nh hay cung, liên k t đư c bi u diễn là m t c p { , } với ≠ Đoàn Trung Sơn, Nguyễn Ly Na 255 - : là t p h p c c tr ng s c nh { , }và đư c bi u diễn là ( , ) ∈ . Tr ng s c nh thư ng bi u hi n t m quan tr ng c a c nh đ ho c mô t m c đ , cư ng đ c a k t n i. C c c nh { , } c th c hướng ho c vô hướng t y theo thu c tính c a k t n i là m t chi u hay hai chi u. Bên c nh đ , t p c c nút l ng gi ng c a m t nút trong m t m ng c hướng đư c x c định b i: - T p c c nút c liên k t đi vào nút , kí hi u ( ) = ∈ |{ , } ∈ . - T p c c nút c liên k t đi ra t nút , kí hi u ( ) = ∈ |{ , }∈ . Với những bi u diễn cơ b n như trên, c c v n đ liên quan đ n bi u diễn, tính to n đ nh hư ng c a ngư i d ng m ng x h i tr c tuy n c th đư c mô h nh h a. 1.2 Phân tích mạng xã hội Ngoài các kỹ thu t th ng kê thông thư ng đ phân tích dữ li u, các m ng xã h i ngày nay đư c kh o sát bằng các bi n pháp phân tích m ng xã h i (Social Network Analysis). Đây là công c c ngh a trong vi c x c định s ph thu c giữa các ngư i d ng trong xã h i, mô t hành vi c a ngư i d ng c ng như đ nh hư ng theo th i gian. Phân tích m ng xã h i liên quan tr c ti p đ n c u trúc c a m ng x h i (Social Network Structure). Qua đ , các đ c đi m, thu c tính và kh năng k t n i giữa c c nút m ng c a đ thị đư c kh o sát. C 3 hướng ti p c n chính th c hi n phân tích m ng xã h i chính: - Phân tích d a trên nút (Node-based Analysis): S d ng c c k thu t đ nh gi đ nh hư ng, tính đ trung tâm (Centrality). Ví d d a trên thu t to n PageRank [3] ho c HITS [4] đ nghiên c u vị trí và vai trò c a c c nút trong m ng x h i. - Phân tích d a trên c u trúc (Structure-based Analysis): S d ng các thu t toán d đo n liên k t [5] và nghiên c u s phát tri n c a m ng [6, 7]. M c tiêu là khai ph c c liên k t trong m ng c ng như nghiên c u s phát tri n c u trúc theo th i gian. - Phân tích d a trên phát hi n c ng đ ng (Community Detection-based Analysis): S d ng thu t toán phân c m [8], đ x c định ho c nh n d ng các nhóm/c ng đ ng (Cluster/Community). Các nút trong cùng m t nhóm sẽ có m t s đ c trưng gi ng nhau. Đây c ng là m t đ c tính khá ph bi n trong m ng th c t . Ví d , với m ng xã h i, các nhóm/c ng đ ng đư c hình thành d a trên y u t vùng mi n, các v n đ quan tâm, yêu thích, công vi c... 1.3 Bài toán tính ...

Tài liệu được xem nhiều:

Gợi ý tài liệu liên quan: