Ứ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

Chia sẻ: ViSteveballmer ViSteveballmer | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

56
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Ứ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 độ ảnh hưởng T g c đ phân tích m ng x h i, vi c x c định đ nh hư ng ho c t m quan tr ng c a ngư i d ng m ng x h i tr c tuy n liên quan đ n vị trí, vai trò c a c c nút trong c u trúc k t n i m ng. M t s phương ph p phân tích d a trên nút tính đ trung tâm đư c s d ng đ đo đ nh hư ng c a c c nút trên m ng. Đ trung tâm d a trên b c c a nút (Degree Centrality) [9] là đ đo chỉ d a vào b c c a nút và đư c x c định bằng s c nh hay s k t n i mà m t nút c , đư c tính thông qua tính s k t n i t nút c n tính đi ra c c nút l ng gi ng. Tuy nhiên, đ đo Degree Centrality chỉ nh hư ng trong ph m vi c c b [9]. M t định ngh a t ng qu t hơn Degree Centrality là phương ph p k-Core [10], đư c th c hi n bằng vi c x c định các đ thị con trong đ t t c c c đỉnh đ u có b c lớn hơn ho c bằng . H n ch c a phương pháp này là nhi u nút c th đư c g n c ng gi trị, do đ vi c so s nh đ nh hư ng hay m c đ truy n t i thông tin c a c c nút này không mang nhi u ngh a [9]. Đ trung tâm giữa (Betweenness Centrality) [9] chỉ ra vị trí c nút trong m ng và kh năng k t n i c c thành ph n ho c nh m trong m ng, đư c tính bằng t ng s đư ng đi ngắn nh t t hai nút b t k mà đi qua nút c n tính. Đ trung tâm d a trên s g n g i (Closeness Centrality) [9] chỉ ra m t nút trong m ng c th truy c p nhanh tới nhi u nút khác trong m ng, đư c tính bằng t ng s đư ng đi ngắn nh t t nút c n tính tới c c nút còn l i. Đ trung tâm d a trên giá trị riêng (Eigenvalue Centrality) [9] x c định đ nh hư ng c a m t nút bằng c ch xem xét đ nh hư ng c a c c nút lân c n d a trên l thuy t ph đ thị và đư c tính to n d a trên vector riêng c a ma tr n li n k trong đ thị c tr ng s . M t hướng ti p c n kh c đ tính đ nh hư ng là s d ng thu t to n PageRank [3] và c c bi n th đ tính đ nh hư ng c ng trong đ thị c tr ng s . Trong mô h nh m ng phân t n, ti p c n thu t to n Random Walks đư c ch ng minh tương đương thu t to n PageRank trong [11] đư c s d ng. Trong bài b o này, nh m t c gi mu n th c nghi m và ch y m t s đ đo như đ đo trung tâm d a trên b c c a nút, đ trung
256 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” tâm giữa, đ trung tâm d a trên s g n g i và so s nh với c c k t qu thu đư c khi th c hi n thu t to n PageRank. 2 Thuật toán PageRank Thu t to n PageRank đư c đ xu t b i Larry Page và Sergey Brin vào năm 1998 và đư c Google s d ng đ x p h ng c c trang Web trong công c t m ki m Google Search. Trong đ , các trang Web đư c coi là các nút và và c nh giữa chúng là c c siêu liên k t (Hyperlink). Chỉ s PageRank c a m t trang Web đ i di n cho m c đ nh hư ng, t m quan tr ng trong t p h p t t c c c trang Web trên toàn th giới. Truy v n Quá trình truy v n Đ thị web Page(i) Rank(i) Trực tuyến PageRank ( ) Ngoại tuyến Hình 1. Sơ đồ biểu diễn hoạt động của PageRank Thu t to n PageRank ho t đ ng m c ngo i tuy n, t c là n “trong su t” và không ph thu c vào những truy v n t m ki m mà ngư i d ng đưa ra m c tr c tuy n. Công th c bi u diễn thu t to n PageRank như sau: () 1− () = . + (1) ∈ () () Trong đ là s trang có trong m ng, ( ) là h ng PageRank tương ng với trang , ( ) là t p các trang có liên k t đ n trang , ( ) là s liên k t ra ngoài c a trang , là h s h m nh n gi trị trong kho ng [0, 1]. Theo Page và Brin [12], h s h m thư ng đư c ch n là 0.85. Kh i t o ban đ u, các trang Web đ u có gi trị PageRank bằng 1. Sau c c vòng l p tính theo công th c (1), gi trị PageRank sẽ thay đ i và d n h i t t i m t gi trị x c định. Áp d ng l thuy t ma tr n, đ t: vector = [ (1), (2), (3), … , ( )] trong đ c c thành ph n (1), (2), … , ( ) tương ng là th h ng PageRank c a các trang th 1, 2,…, n. Theo quy ước, ban đ u t t c các ph n t c a vector có t ng bằng 1. Ma tr n = với , = 1. . . là ma tr n kích thước × trong đ c c ph n t đư c x c định như sau: 1 ế ( , )∈ = () 0 ế ượ ạ Chú ý: các ph n t trong m i c t c a ma tr n A có t ng bằng 1 hay nói cách khác mang tính ch t m t ma trận ngẫu nhiên cột. Tuy nhiên, trên th c t luôn t n t i các trang Web không có liên k t ra ngoài (thư ng là các trang web chỉ ch a m t b c nh, m t file, m t b ng dữ li u), đi u này dẫn đ n hi n tư ng t t c các ph n t trên cùng m t c t c a ma tr n (gi s trang là trang đ c l p) đ u có giá trị bằng 0, k t qu thu đư c không thỏa m n đi u ki n là ma tr n ngẫu nhiên c t. Page và c ng s đ xu t x lý v n đ này bằng cách thay th các c t chỉ toàn s 0 trong b i m t vector n×1 x c định x c su t phân ph i v = [1/ ,1/ ,…,1/ ]T . Khi đ g i a là vector 1×n với: 1 ế () =0 = 0 ế ượ ạ Ma tr n đư c bi n đ i thành ma tr n ′ theo công th c như sau:
Đoàn Trung Sơn, Nguyễn Ly Na 257 ′ = + . (2) Vi c thêm h s hãm vào công th c (1) đ ng th i bi n đ i ma tr n ′ thành ma tr n mới c d ng: ′′ = . ′ + (1 − ). . (3) Trong đ là vector hàng có n ph n t đ u bằng 1. Khi đ ngư i ta ch ng minh đư c rằng công th c (4) đư c bi u diễn dưới d ng phương tr nh ma tr n tuy n tính: = . (4) Lúc này vi c tính toán h ng trang quay v bài toán tìm vector riêng c a ma tr n . Đ gi i quy t bài to n này ngư i ta c ng s d ng phương ph p l p. Cha đẻ c a thu t to n PageRank c ng đ chỉ ra rằng bài to n này c th h i t kh nhanh, trong kho ng 50-100 vòng l p. 3 Thực nghiệm và đánh giá 3.1 Dữ liệu và cài đặt thuật toán Trong m ng x h i, ngư i d ng m ng c nhi u lo i quan h x h i kh c nhau như b n bè, đ ng nghi p, b n c ng s thích, b n h c c ... trong đ quan h b n bè là đư ng liên k t c t lõi nh t ph n nh đư c s liên quan c ng như kh năng tương t c giữa hai ngư i d ng trong m ng. Khi xây d ng đ thị bi u diễn, c nh c a đ th đư c l a ch n bi u diễn quan h b n bè và đây là m t liên k t vô hướng. C r t nhi u b dữ li u c a m ng x h i đư c cung c p công khai trên Internet. T c gi l a ch n khai ph và phân tích m ng x h i Facebook – đây đư c coi là m ng x h i lớn nh t trong s các m ng xã h i hi n có hơn 1,73 tỷ ngư i d ng tính đ n qu I năm 2020 theo [13]. Do h n ch v chính sách b o m t và riêng tư c a m ng x h i này, nên nh m nghiên c u chỉ s d ng b dữ li u ego-Facebook là m t ph n nhỏ c a m ng x h i Facebook đư c cung c p b i J. McAuley and J. Leskovec c a Đ i h c Stanford [14] dùng cho vi c phân tích. 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è. H nh 2. M t ph n quan h b n bè trên Faceboook B dữ li u ego-Facebook bao g m 4.039 nút đư c đ nh s t 0 đ n 4.038 và 88.234 c nh đ i di n cho 4.039 ngư i d ng và 88.234 liên k t b n bè giữa c c ngư i d ng này. Dữ li u đư c thu th p t những ngư i tham gia kh o s t, sau đ 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. Dữ li u đ u vào c a c c thu t to n đư c bi u diễn dưới d ng danh s ch k . Kh i t o ban đ u c c tham s như sau: h s hãm = 0.85 và đi u ki n d ng = 0.001. Trong qu tr nh th c thi, chương tr nh sẽ chuy n đ i danh sách k v ma tr n k ( ’’) và làm vi c ch y u với ma tr n này đ t m gi trị PageRank c a t ng nút.
258 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” 3.2 Đánh giá kết quả và so sánh Đ nh hư ng c a t ng nút đư c tính to n và tr c quan h a dưới d ng bi u đ c t trên H nh 3 và Hình 4, trong đ bi u diễn c c nút và gi trị đ nh hư ng tương ng. Th c nghi m trên b dữ li u ego-Facebook s d ng thu t to n PageRank cho ra k t qu trong H nh 3. PageRank 0 1016 1143 1397 1524 1651 1905 2032 2159 2413 2540 2667 2921 3048 3175 3429 3556 3683 3810 3937 1270 1778 2286 2794 3302 254 762 127 381 508 635 889 Hình 3. Đ 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.com bằng thu t to n PageRank. Phân tích k t qu đ nh hư ng c a 4039 ngư i d ng t b dữ li u n i trên cho ra b i thu t to n Pag- eRank, đ nh hư ng cao nh t là ngư i d ng đư c đ nh s 3437 ( = 0.007579), k t qu này cao g p 185 l n đ nh hư ng th p nh t c a các ngư i d ng đư c đ nh s 2079, 2195, 2269, 2457, 2470, 2569, 2596 ( = = = = = = = = 0.000041). Bên c nh đ , k t qu nh n đư c đ đ m b o t ng c a t t c đ nh hư ng bằng 1 (∑ = 1). Sau đ đ c dữ li u so s nh, đ trung tâm d a trên b c c a nút, đ trung tâm giữa và đ trung tâm d a trên s g n g i đư c tính c ng trên c ng b dữ li u đ thu th p. K t qu đ đo ng với 3 phương ph p đư c bi u đ h a trong H nh 4. Degree Centrality 3729 226 113 339 452 565 678 791 904 0 1017 1130 1243 1356 1469 1582 1695 1808 1921 2034 2147 2260 2373 2486 2599 2712 2825 2938 3051 3164 3277 3390 3503 3616 3842 3955 Betweenness Centrality 3729 1017 1130 1243 1356 1469 1582 1695 1808 1921 2034 2147 2260 2373 2486 2599 2712 2825 2938 3051 3164 3277 3390 3503 3616 3842 3955 226 0 113 339 452 565 678 791 904 Closeness Centrality 3729 226 1017 1130 1243 1356 1469 1582 1695 1808 1921 2034 2147 2260 2373 2486 2599 2712 2825 2938 3051 3164 3277 3390 3503 3616 3842 3955 113 339 452 565 678 791 904 0 Hình 4 . C c đ 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 c c thu t to n tính đ đo trung tâm. Qua quan s t, bi u đ gi trị đ đo c c nút ph n nh s tương quan nh t định trong k t qu đ u ra giữa 3 thu t to n: PageRank, Degree Centrality và Betweeness Centrality. Đ phân tích k t qu thu đư c, 10 ngư i d ng c c c đ đo cao nh t trong c c thu t to n đư c trích rút ra trong B ng 1.
Đoàn Trung Sơn, Nguyễn Ly Na 259 Bảng 1. 10 ngư i d ng c đ đo cao nh t ng với t ng thu t to n Degree Betweeness Closeness # PageRank Centrality Centrality Centrality 1 3437 107 107 107 2 107 1684 1684 58 3 1684 1912 3437 428 4 0 3437 1912 563 5 1912 0 1085 1684 6 348 2543 0 171 7 686 2347 698 348 8 3980 1888 567 483 9 414 1800 58 414 10 483 1663 428 376 B ng dữ li u cho th y m c d s d ng c c thu t to n kh c nhau tính đ nh hư ng nhưng những ngư i dùng trong danh s ch {0, 107, 1684, 1912, 3437} vẫn trong danh s ch 10 ngư i d ng c đ nh hư ng lớn nh t. Đ c m t c i nh n bao qu t trên toàn b d i k t qu , phép tính đ tương quan (Correlation) trong [15] giữa k t qu đ u ra c a thu t to n PageRank và 3 phương ph p tính còn l i đư c th c hi n. Đ tương quan đư c tính như sau: ∑ ∑ ∑ = (với N là s c p dữ li u) ( ∑ (∑ ) )( ∑ (∑ ) ) Trong đ , X và Y là hai b dữ li u c n so s nh khi đ đ tương quan đư c tính. K t qu tính to n đ tương quan đư c bi u diễn trong B ng 2 như sau: Bảng 2. Tính tương quan # Phương ph p Đ tương quan với thu t to n PageRank 1 Degree Centrality 0.678165247 2 Betweenness Centrality 0.764704741 3 Closeness Centrality 0.147999445 Như v y s tương quan giữa thu t to n PageRank và thu t to n đ trung tâm giữa c ng như đ trung tâm d a trên b c c a nút kh cao, kho ng trên 67% s tương đ ng. M i phương ph p tính c những đ c trưng riêng nhưng rõ ràng chúng ta th y s t c đ ng t ng th c c nút trong m ng trong thu t to n PageRank cho k t qu t t khi so s nh với c c phương ph p ph bi n đơn gi n kh c. Tính đúng đắn c a thu t to n PageRank c n đư c ki m tra trên m t m ng th c. 4 Kết luận và hướng phát triển Vi c phân tích c c m ng ph c t p n i chung và c c m ng x h i n i riêng là m t l nh v c quan tr ng. G n đây lý thuy t đ thị đư c ng d ng nhi u đ phân tích c c m ng này. Trong bài b o, t c gi tr nh bày ti p c n thu t to n PageRank cho vi c tính đ nh hư ng c a ngư i d ng trên m ng x h i tr c tuy n. K t qu thu đư c ph n nh m c đ tương quan kh cao so với c c thu t to n đ trung tâm d a trên b c c a nút, đ trung tâm giữa. Thu t to n PageRank đư c d ng tính s nh hư ng c a ngư i d ng trong s t c đ ng c a toàn b c u trúc m ng, gi trị c ngh a ph n nh t t hơn vai trò c a m i ngư i d ng trong m ng. M c d còn nhi u h n ch v kích thước m ng khai ph đư c do c c chính s ch v b o m t và riêng tư c a nhà qu n l m ng x h i, tuy nhiên, c c k t qu tính to n và phân tích đư c đ chỉ ra ti m năng c a vi c ng d ng l thuy t đ thị trong phân tích m ng x h i, trong đ c thu t to n PageRank. Hướng nghiên c u trong th i gian tới, t c gi mu n cài đ t th c nghi m c c bi n th c a thu t to n PageRank như HITS, SALSA và m r ng kích thước lớn dữ li u đư c th c nghi m. Ngoài ra, khía c nh hành vi c a ngư i d ng trong m ng x h i c n đư c xem xét, thay v những m i quan h x h i thông thư ng như b n bè.
260 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” Tài liệu tham khảo 1. SearchCIO of Techtarget (2020), https://searchcio.techtarget.com/definition/social-network. 2. Oxford Learner's Dictionaries (2020), https://www.oxfordlearnersdictionaries.com/definition/english/social- network. 3. L. Page, S. Brin, R. Motwani and T. Winograd (1998), “The PageRank Citation Ranking: Bringing order to the Web”, Stanford Digital Library Technologies Project. 4. Kleinberg, Jon M (1999), “Authoritative Sources in a Hyperlinked Environment”. 5. N. Benchettara, R. Kanawati, and C. Rouveirol (2010), “A Supervised Machine Learning Link Prediction Approach for Academic Collaboration Recommendation”, Proceedings of the fourth ACM conference on Recommender systems. 6. Prof William M.K. Trochim (1999), “Research Methods Knowledge Base”. 7. R. Kumar, J. Novak, and A. Tomkins (2006), “Structure and Evolution of Online Social Networks”, Pro- ceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. 8. M.E.J. Newman (2004), “Fast Algorithm for Detecting Community Structure in Networks”, Physical Review E. 9. Francisco Aparecido Rodrigue (2019), “Network centrality: an introduction”. 10. Sergey N Dorogovtsev, Alexander V Goltsev, and Jose Ferreira F Mendes (2006), “K-core organization of complex networks”, Physical Review Letters. 11. D. T. Son (2017), “On Trustworthiness Recommendation”. 12. A.N. Langville and C.D. Meyer (2006), “Google’s PageRank and Beyond: The Science of Search Engine Rankings”, Princenton University Press. 13. J. Clement (2020), “Number of daily active Facebook users worldwide as of 1st quarter 2020 (in millions)”. 14. Stanford Large Network Dataset Collection, https://snap.stanford.edu/data. 15. Prof William M.K. Trochim (1999), “Research Methods Knowledge Base”.