Ứ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
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 ...
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ìm kiếm theo từ khóa liên quan:
Thuật toán PageRank Mạng xã hội Người dùng mạng xã hội Mối quan hệ xã hội Liên kết vô hướngGợi ý tài liệu liên quan:
-
11 trang 406 0 0
-
Truyền thông mạng xã hội: Vị trí nào?
3 trang 209 0 0 -
67 trang 199 0 0
-
21 trang 179 0 0
-
Bài văn mẫu: Nghị luận xã hội về tình bạn
3 trang 163 0 0 -
Xu hướng và tác động của cách mạng công nghiệp lần thứ tư đến môi trường thông tin số
9 trang 161 0 0 -
Thực trạng sử dụng ngôn ngữ của sinh viên hiện nay
3 trang 158 0 0 -
15 trang 135 0 0
-
11 trang 133 0 0
-
Mạng xã hội có liên hệ thế nào với quảng cáo?
4 trang 131 0 0