Ứ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
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 ꢋ ≠ ꢌ
255
Đoàn Trung Sơn, Nguyễn Ly Na
- ꢃ: 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
Page(i)
Rank(i)
Đꢗ thị web
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:
257
Đoàn Trung Sơn, Nguyễn Ly Na
ꢤ′ = ꢤ + ꢬ. ꢥ
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)
(2)
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
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
Betweenness Centrality
Closeness Centrality
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.
259
Đoàn Trung Sơn, Nguyễn Ly Na
Bảng 1. 10 ngưꢈi dꢉng cꢚ đꢃ đo cao nhꢕt ꢎng với tꢠng thuꢑt toꢂn
Degree
Centrality
107
1684
1912
3437
0
2543
2347
1888
1800
1663
Betweeness
Centrality
107
Closeness
Centrality
107
58
428
563
1684
171
348
483
#
PageRank
1
2
3
4
5
6
7
8
9
3437
107
1684
0
1912
348
686
3980
414
483
1684
3437
1912
1085
0
698
567
58
428
414
376
10
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 ꢹ
#
1
2
3
Phương phꢂp
Degree Centrality
Betweenness Centrality
Closeness Centrality
Đꢃ tương quan với thuꢑt toꢂn PageRank
0.678165247
0.764704741
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.
2.
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.
5.
Kleinberg, Jon M (1999), “Authoritative Sources in a Hyperlinked Environment”.
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.
7.
Prof William M.K. Trochim (1999), “Research Methods Knowledge Base”.
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.
M.E.J. Newman (2004), “Fast Algorithm for Detecting Community Structure in Networks”, Physical Review
E.
8.
9.
10.
Francisco Aparecido Rodrigue (2019), “Network centrality: an introduction”.
Sergey N Dorogovtsev, Alexander V Goltsev, and Jose Ferreira F Mendes (2006), “K-core organization of
complex networks”, Physical Review Letters.
11.
12.
D. T. Son (2017), “On Trustworthiness Recommendation”.
A.N. Langville and C.D. Meyer (2006), “Google’s PageRank and Beyond: The Science of Search Engine
Rankings”, Princenton University Press.
13.
14.
15.
J. Clement (2020), “Number of daily active Facebook users worldwide as of 1st quarter 2020 (in millions)”.
Prof William M.K. Trochim (1999), “Research Methods Knowledge Base”.
7 trang
19340
Free
Bạn đang xem 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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- ung_dung_thuat_toan_pagerank_danh_gia_do_nh_huong_cua_nguoi.pdf
