ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
----------

BÁO CÁO ĐỒ ÁN

MÔN HỌC: MẠNG XÃ HỘI
Năm học: 2020 - 2021

ĐỀ TÀI:

SO SÁNH HIỆU NĂNG VÀ TÌM HIỂU
THUẬT TỐN PHÂN CỤM
Lớp: IS353.L12.HTCL
Giảng viên hướng dẫn: Nguyễn Thị Kim Phụng
Nhóm thực hiện:
18520872 – Lê Võ Đình Kha
18521018 – Bùi Cảnh Long
19522247 – Vũ Phú Thành
18520864 – Nguyễn Thu Huyền
17520589 – Trầm Thanh Huy
TP. Hồ Chí Minh, tháng 11 năm 2020


MỤC LỤC
Lời nói đầu .....................................................................................................................
Lời cảm ơn .....................................................................................................................
Nhận xét của giảng viên ................................................................................................
1. Lý do chọn đề tài ..................................................................................................... 1
2. Độ đo VoteRank ...................................................................................................... 1
2.1 Gới thiệu về thuật toán VoteRank.................................................................. 1

2.2 Ý tưởng thuật toán VoteRank ........................................................................ 2
2.3 Các bước trong thuật tốn VoteRank ............................................................. 2
2.4 Ví dụ về VoteRank ......................................................................................... 3
3. Betweenness Centrality .......................................................................................... 5
4. Closeness Centrality ............................................................................................... 6
5. PageRank ................................................................................................................. 6
5.1 Giới thiệu về thuật toán PageRank ................................................................. 6
5.2 Ý tưởng thuật toán PageRank ........................................................................ 6
6. Girvan-Newman ...................................................................................................... 8
7. Thuật tốn Louvain community ............................................................................ 9
8. Mơ hình dịch bệnh SIR ........................................................................................ 10
8.1 Các khái niệm trong mô hình SIR ................................................................ 10
8.2 Lý do chọn mơ hình SIR ............................................................................... 10
9. Đánh giá hiệu quả ................................................................................................. 11
10. Thực hiện chương trình trên Python ................................................................ 15
10.1 Nội dung con thằn lằn .................................................................................. 15
10.2 Nội dung con chim én .................................................................................. 16
Phụ lục ...........................................................................................................................
1. Tài liệu tham khảo ..........................................................................................
2. Phân công công việc.......................................................................................


LỜI NÓI ĐẦU
Việc xác định các phần tử lan truyền có ảnh hưởng (influential spreaders) trong
một mạng xã hội đóng vai trị quan trọng trong việc lan truyền thơng tin một cách hiệu
quả. Ta có thể chọn được những phần tử có tính ảnh hưởng lớn nhất bằng cách dựa vào
các độ đo như PageRank, Closeness, Betweenness,... Tuy nhiên phương pháp dựa vào
các độ đo đã liệt kê trên gặp phải hạn chế khi xảy ra trường hợp các phần tử lan truyền
ở quá gần nhau dẫn đến ảnh hưởng của chúng bị trùng lắp làm giảm hiệu quả lan truyền.
Trong báo cáo này nhóm muốn giới thiệu độ đo VoteRank vốn được thiết kế để

khắc phục vấn đề mà các độ đo ở trên gặp phải. Trong thuật toán VoteRank tất cả các
phần tử (nodes) sẽ tham gia vào bầu chọn phần tử có ảnh hưởng lớn nhất (spreader) tại
mỗi lượt và khả năng bầu cử của các láng giềng của node được chọn sẽ giảm đi tại lượt
tiếp theo.
Theo báo cáo của nhóm tác giả VoteRank: Dựa trên mơ hình SIR (SusceptibleInfected-Recovered) và SI (Susceptible-Infect) phương pháp dùng VoteRank vượt trội
hơn các độ đo truyền thống cả về tốc độ lây lan trong mạng lẫn quy mô ảnh hưởng cuối
cùng (final affected scale). Ngồi ra VoteRank cịn có hiệu quả tính tốn tốt về mặt tốc
độ.
Báo cáo này được viết dựa trên bài báo khoa học của nhóm tác giả VoteRank:
Jian-Xiong Zhang, Duan-Bing Chen, Qiang Dong & Zhi-Dan Zhao. Bài báo gốc có thể
được tìm thấy tại địa chỉ: />

LỜI CẢM ƠN
Trên thực tế khơng có sự thành cơng nào mà không gắn liền với những sự hỗ
trợ, giúp đỡ dù ít hay nhiều, dù trực tiếp hay gián tiếp của người khác. Trong suốt học
kỳ này khi bắt đầu làm đồ án mơn Mạng xã hội, nhóm em đã nhận được rất nhiều sự
quan tâm, giúp đỡ của q Thầy Cơ, các anh chị khóa trên và bạn bè trong và ngồi
lớp.
Với lịng biết ơn sâu sắc nhất, nhóm em xin chân thành cảm ơn Cơ Nguyễn Thị
Kim Phụng đã tận tâm hướng dẫn chúng em qua từng buổi học trên lớp, giải đáp kịp
thời các thắc mắc của chúng em. Nếu khơng có những lời hướng dẫn của Cơ thì nhóm
em nghĩ bài báo cáo của nhóm rất khó để hồn thành được.
Đồ án được thực hiện trong vịng hai tuần, bước đầu sử dụng ngơn ngữ Python
để xử lý các thuật tốn. Do vậy, khơng tránh khỏi những thiếu sót là điều chắc chắn,
nhóm em rất mong nhận được những ý kiến đóng góp quý báu của Cô để cho bài làm
cũng như kiến thức của nhóm em được hồn thiện.
Sau cùng, kính chúc Cơ thật nhiều sức khỏe, niềm tin để tiếp tục thực hiện sứ
mệnh cao đẹp của mình là truyền đạt kiến thức cho thế hệ mai sau.



NHẬN XÉT CỦA GIẢNG VIÊN:
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................
....................................................................................................................................................

-------------------------------------------------------


1. Lý do chọn đề tài
Trong thế giới thực, nhiều hệ thống phức tạp có thể được biểu diễn dưới dạng các
mạng phức tạp. Trong đó, nhiều hoạt động như quảng cáo trên phương tiện truyền thông
và truyền miệng trên các mạng xã hội có thể được mơ tả bằng thông tin lan truyền trên các
mạng phức tạp. Tối đa hóa quy mơ lan rộng là một mục tiêu phổ biến.
Với cấu trúc liên kết không thay đổi hoặc thay đổi một chút, vị trí của các nút gốc
xác định quy mô lan truyền cuối cùng ở mức độ lớn. Vấn đề chọn các nút ban đầu làm nút
lan truyền để đạt được quy mô lan truyền tối đa được xác định là vấn đề tối ưu hóa ảnh
hưởng. Nghiên cứu của chúng em tập trung vào chiến lược chọn một tập hợp các nút quan
trọng làm công cụ lan truyền nguồn tin trong báo cáo này.
2. Độ đo VoteRank
2.1 Giới thiệu về thuật toán VoteRank
VoteRank là thuật toán được nhóm tác giả Jian-XiongZhang, Duan-BingChen,
Qiang Dong và Zhi-DanZhao thuộc trung tâm khoa học Web và trung tâm nghiên cứu
BigData của Đại học Khoa học và Công nghệ Điện tử Trung Quốc đề xuất. Bài báo khoa
học của nhóm này được hội đồng khoa học chấp nhận ngày 23 tháng 5 năm 2016 và được
xuất bản ngày 14 tháng 6 năm 2016.
Bài báo có tựa đề “Identifying a set of influential spreaders in complex networks”
tạm dịch ra “Việc xác định tập hợp các node có tính ảnh hưởng cao trong mạng lưới phức
tạp”. Bài báo chỉ ra rằng để xác định tính ảnh hưởng của node ta có thể sử dụng các độ đo
như closeness, betweenness, PageRank, ClusterRank. Tuy nhiên, những độ đo trên gặp
phải hạn chế là có khả năng một số node có ảnh hưởng lớn lại quá gần nhau, dẫn đến phạm
vi ảnh hưởng của các node này dễ bị trùng lặp.
Thuật tốn leo đồi (hill-climbing) có thể giải quyết được những vấn đề đề cập trên,
tuy nhiên nó rất tốn thời gian, đặc biệt trong mạng có tỉ lệ scale lớn. Ngoài ra, Narayanam
and Narahari cũng đề xuất thuật toán SPIN, nhưng cũng khá tốn thời gian cho mạng lưới
lớn, thời gian chạy của CPU là 28.25 phút để tìm ra 30 node quan trọng nhất trong mạng

có 1589 node.
Vì vậy, thuật tốn VoteRank được ra đời, các node trong mạng lưới sẽ tiến hành bỏ
phiếu cho các node láng giềng (khởi tạo chỉ số bầu cử của các node là như nhau), sau khi
bầu cử sẽ chọn ra được node có số điểm cao nhất, đồng thời giảm đi khả năng bầu cử của
So sánh hiệu năng và tìm hiểu các thuật tốn phân cụm

Trang 1


các node láng giềng của node cao nhất vừa rồi. Cứ tiếp tục thực hiện n – 1 lần bầu cử tiếp
theo thì sẽ tìm ra được n node có tính ảnh hưởng cao nhất mạng lưới mà phạm vi ảnh
hưởng của chúng không bị trùng lặp đồng thời phương pháp này có thể áp dụng cho mạng
với hàng triệu node nhưng lại ít tốn thời gian vì nó chỉ cập nhật thông tin nội bộ (local)
sau khi chọn một node ảnh hưởng.
Nhóm tác giả phát biểu rằng, qua bốn lần thử nghiệm trên mạng lưới thực tế (real
networks) theo mơ hình lây lan dịch bệnh Susceptible-Infected-Recovered (SIR) và mơ
hình Susceptible-Infected (SI), VoteRank vượt trội so với các phương pháp điểm chuẩn
truyền thống trên cả tỉ lệ lan truyền và thang đo ảnh hưởng cuối cùng. Hơn nữa, VoteRank
có hiệu quả tính tốn vượt trội.
2.2 Ý tưởng thuật tốn VoteRank
Trong thế giới thực, nếu người A hỗ trợ người B thì khả năng hỗ trợ của người A
đối với những người khác sẽ bị giảm đi.
Dựa vào quan sát đó, nhóm tác giả đã đưa ra ý tưởng về thuật tốn VoteRank.
Ý tưởng chính của VoteRank là chọn ra những node có ảnh hưởng lớn nhất dựa
trên điểm bỏ phiếu (voting scores) nhận được từ các láng giềng. Node có điểm bỏ phiếu
lớn nhất sẽ được xem là node có ảnh hưởng lớn nhất. Những node láng giềng sẽ bị giảm
khả năng bỏ phiếu.
Giả sử ta cần chọn ra N node có ảnh hưởng lớn nhất thì tất cả các node sẽ phải bỏ
phiếu N lần.
Trong mỗi lần bỏ phiếu, node có điểm lớn nhất sẽ được chọn vào một trong số N

node có ảnh hưởng lớn nhất.
Nếu một node đã được chọn ở những lần bỏ phiếu trước node đó sẽ bị loại bỏ trong
những lần chọn sau. Đồng thời những láng giềng của node được chọn sẽ bị giảm khả năng
bầu chọn (giảm điểm) tại những lượt chọn sau.
Chúng ta cứ tiếp tục lặp lại các bước cho đến khi tìm được N node có sức ảnh hưởng
lớn nhất.
2.3 Các bước trong thuật toán VoteRank
Trong VoteRank một node được gán một bộ (su, vau) trong đó su là điểm mà node
u nhận được từ láng giềng, vau là số điểm mà node u có thể bầu cho các láng giềng của u.
Thuật toán bao gồm các bước sau:
Bước 1: Khởi tạo tất cả các node với bộ (0, 1).
So sánh hiệu năng và tìm hiểu các thuật tốn phân cụm

Trang 2


Bước 2: Thực hiện bầu cử. Các node nhận điểm từ các láng giềng đồng thời
cho điểm các láng giềng.
Bước 3: Chọn ra node có su lớn nhất và gán cho node được chọn (0, 0) trong
các lượt bầu cử sau.
Bước 4: Làm yếu khả năng bầu cử của các node láng giềng của node được
chọn trong bước 3. Các node láng giềng đó sẽ được gán (su, vau – f). Với f được
tính bằng cơng thức:

𝑓=

1
𝑘

Với k là số bậc trung bình.

2.4 Ví dụ về VoteRank
- u cầu: Giả sử ta có một mạng như sau với yêu cầu tìm 2 nodes có sức ảnh
hưởng lớn nhất.

- Các bước thực hiện:
Khởi tạo tất cả các node với bộ (0,1)

So sánh hiệu năng và tìm hiểu các thuật tốn phân cụm

Trang 3


Thực hiện bầu cử lượt 1. Các node nhận điểm từ các láng giềng, đồng thời cho
điểm các láng giềng. Chọn ra node có điểm bầu cử lớn nhất (node 0 với 5 điểm)

Thực hiện bầu cử lượt 2. Node 0 được gán (0, 0) và các láng giềng bị giảm điểm
bầu cử đi f = 1/2.4 (2.4 là số bậc trung bình của mạng). Chọn ra node 7 có điểm bầu cử
lớn nhất (2.583)

So sánh hiệu năng và tìm hiểu các thuật toán phân cụm

Trang 4


3. Betweenness Centrality
Betweenness centrality của một đỉnh được tính
bằng tổng số các đường đi ngắn nhất ngang qua đỉnh đang
xét chia cho tổng số các đường đi ngắn nhất của tồn
mạng.
Nói cách khác, Betweenness Centrality là độ đo dùng để xác định vị tri của tác nhân

trong mạng mà nó có khả năng kết nối đến những cặp tác nhân hay những nhóm tác nhân
khác.
Betweeness Centrality của một đỉnh u, ký hiệu là CB (u), độ đo này dùng để xem
xét khả năng chi phối các quan hệ giữa các nút khác trong mạng.
Một node có độ đo Betweenness Centrality càng cao thì:
+ Giữ một vị trí đặc biệt quan trọng và một tầm ảnh hưởng rất lớn trong mạng.
+ Nếu node này bị loại bỏ thì sẽ gây ra sự tan rã cấu trúc của mạng, tức là các node
sẽ khơng cịn có thể trao đơi thơng tin liên lạc với nhau.
Cơng thức tính Betweenness centrality:

𝐶𝐵 𝑣 =
𝑠 ≠𝑣 ≠𝑡 ∈ 𝑉

So sánh hiệu năng và tìm hiểu các thuật toán phân cụm

𝜎𝑠𝑡 (𝑣)
𝜎𝑠𝑡
Trang 5


Với:
σst(v) là số lượng đường đi ngắn nhất từ s đến t và đi qua v.
σst là số lượng đường đi ngắn nhất từ s đến t.

4. Closeness Centrality
Closeness Centrality là độ đo trung tâm theo sự lân
cận.
Closeness Centrality được tính bằng trị nghịch đảo
của tổng số khoảng cách ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại của đồ thị.
Closeness Centrality được tính bằng bình qn của tổng số khoảng cách ngắn nhất

từ một đỉnh đến tất cả các đỉnh cịn lại.
Một thực thể có giá trị Closeness Centrality tốt nhất:
+ Có thể truy xuất nhanh chóng đến các thực thể khác trong mạng.
+ Có một đường đi ngắn nhất đến nhiều thực thể khác.
Công thức tính Closeness Centrality:

𝐶𝑐 𝑣𝑖 =

𝑛−1
𝑛
𝑗 ≠ 𝑖 𝑔(𝑣𝑖 , 𝑣𝑗 )

Với:
n là số phần tử (node) trong mạng
g(vi, vj) là khoảng cách ngắn nhất từ vi đến vj

5. PageRank
5.1 Giới thiệu về thuật tốn PageRank
Pagerank là thuật tốn phân tích được dùng để đánh giá xếp hạng giá trị của các
trang web thông qua việc xem xét số lượng và chất lượng của các liên kết truy cập đến
trang web đó.
Giá trị Pagerank hình thành từ thuật tốn tốn học dựa trên webgraph: các trang
world wide web được coi như các đỉnh và các đường link là các cạnh. Khi hình thành
webgraph người ta có tính đến những trang của các cơ quan có thẩm quyền như cnn.com
hay usa.gov. Giá trị xếp hạng cho thấy tầm quan trọng của từng trang cụ thể. Mỗi đường
link tới trang web sẽ được tính như 1 sự hỗ trợ làm tăng thêm giá trị Pagerank. Giá trị
So sánh hiệu năng và tìm hiểu các thuật toán phân cụm

Trang 6



Pagerank của trang được định nghĩa đệ quy và phụ thuộc vào số lượng và giá trị của các
trang mà có link dẫn đến trang đó (incoming links). Một trang web có chứa nhiều link liên
kết từ các trang web có giá trị PageRank cao thì giá trị PageRank của trang đó cũng sẽ
cao. Có rất nhiều bài viết đã được xuất bản ra công chúng dựa trên nghiên cứu gốc của
Page và Brin. Trên thực tế khái niệm PageRank rất khó để thao tác. Đã có nhiều nghiên
cứu tiến hành xác định những ảnh hưởng sai tới PageRank ranking. Mục đích là tìm một
cách loại bỏ hiệu quả những link từ các văn bản với những ảnh hưởng sai tới PageRank.
5.2 Ý tưởng thuật toán PageRank
Thuật toán toán học PageRank đối với một hệ thống liên kết đơn giản sẽ được hiển
thị tỷ lệ bằng %. Trang C có một PageRank cao hơn so với trang E, mặc dù có ít liên kết
(links) đến trang C; một link duy nhất dẫn tới C từ một trang quan trọng và chính vì thế
mà C có giá trị cao. Nếu như một người lướt web bắt đầu từ một trang bất kỳ thì có 85%
xác suất chọn một link ngẫu nhiên trên trang mà họ đang xem, và 15% họ sẽ chọn chuyển
sang một trang web bất kỳ từ toàn bộ hệ thống các liên kết. Người dùng sẽ truy cập vào
trang E với xác suất 8.1%. (Xác suất 15% truy cập tới một trang bất kỳ tương ứng với yếu
tố damping là 85%.) Nếu khơng có yếu tố damping, người dùng cuối cùng cũng sẽ kết
thúc quá trình lướt web tại trang A, B, hoặc C, và các trang khác sẽ có PageRank bằng 0.
Nếu như tính cả yếu tố damping, trang A vẫn liến kết đến tất cả các trang trong hệ thống,
mặc dù chỉ có 1 link trỏ đi.
Giả sử một nhóm gồm 4 trang web: A, B, C, D. những liên kết từ một trang đến
chính nó khơng được tính, mỗi trang web có 1 đường dẫn duy nhất đến 1 trang web khác.
Giá trị Pagerank của các trang ban đầu được cho là bằng nhau. Tổng giá trị Pagerank trên
tất cả các trang là tổng số trang web tại thời điểm đó, do đó mỗi trang trong ví dụ này sẽ
có một pagerank ban đầu tương đương với 1. Tuy nhiên trong phần còn lại và các ví dụ
của bài này sẽ có giá trị tương đối từ 0 đến 1. Do đó giá trị ban đầu cho mỗi trang là 0.25.
Pagerank chuyển từ một trang đến các trang khác bằng các đường link, trong những bước
tính tiếp theo giá trị sẽ được chia đều cho tất cả các liên kết đi. Nếu các liên kết duy nhất
trong hệ thống từ các trang B, C và D tới A, mỗi liên kết sẽ chuyển giá trị bằng 0.25
Pagerank A khi tính trong


lần tiếp theo, tổng

cộng là 0,75.

So sánh hiệu năng và tìm hiểu các thuật tốn phân cụm

Trang 7


Khác với ví dụ trên, B có liên kết đến trang C và A, trong khi D có các link đến cả
ba trang. Như vậy trong bước tiếp theo, trang B sẽ chuyển tải một nửa giá trị của mình,
tương đương với 0.125 tới trang A và 0.125 tới trang C. Khi trang D có 3 liên kết trỏ đi,
có nghĩa nó sẽ chuyển 1/3 giá trị của mình, tương đương với 0.083 tới A.

PageRank được tính cho 1 outbound link sẽ bằng số score pagerank của document
đó chia cho số outbound link L()

Công thức chung, giá trị Pagerank đối với bất kỳ trang u có thể tính như sau:

Giá trị PageRank đối với trang u phụ thuộc vào giá trị Pagerank của từng trang v có
chứa trong set Bu (tập hợp có chứa các trang có link đến trang u), chia cho số L (v) các link
từ trang v.
6. Girvan-Newman
Thuật tốn Girvan-Newman dùng để phát hiện và
phân tích cấu trúc cộng đồng phụ thuộc vào việc loại bỏ
lặp đi lặp lại các cạnh có số lượng đường ngắn nhất đi qua
chúng cao nhất.
Thuật toán Girvan-Newman khá đơn giản, nội dung
chính của nó chỉ là xác định cạnh có độ trung gian lớn nhất

và loại bỏ nó. Sau đó độ trung gian được tính lại và lại thực hiện loại bỏ dần các cạnh tiếp
tục như vậy cho đến khi khơng cịn cạnh nào trong đồ thị.Nếu trong trường hợp có 2 cạnh
với độ trung gian như nhau, ta có thể loại bỏ một cạnh bất kỳ, hoặc loại bỏ cả 2 cạnh cùng
một lúc. Tồn bộ thuật tốn có thể được biểu diễn trong một dendrogram,ở đây ta có thể
hiểu là thuật toán đi từ gốc đến các lá .Các nhánh của cây biểu diễn cho các phép loại bỏ
cạnh để chia đồ thị thành các cộng đồng riêng rẽ.
Thuật tốn: Lặp lại cho đến khi khơng cịn cạnh nào:
+ Tính độ lân cận giữa cho mọi cạnh trong biểu đồ.
+ Loại bỏ cạnh có độ giữa cạnh cao nhất.
So sánh hiệu năng và tìm hiểu các thuật tốn phân cụm

Trang 8


+ Tính độ dài giữa các cạnh cho các cạnh còn lại.
+ Các thành phần được kết nối là các cộng đồng.
7. Thuật toán Louvain community
Louvain là một thuật toán không giám sát
(không yêu cầu đầu vào số lượng cộng đồng cũng
như kích thước của chúng trước khi thực hiện) được
chia thành 2 giai đoạn: Tối ưu hóa mơ-đun và Tổng
hợp cộng đồng. Sau khi bước đầu tiên hoàn thành,
bước thứ hai tiếp theo. Cả hai sẽ được thực thi cho
đến khi khơng cịn thay đổi nào trong mạng và đạt
được mô đun tối đa.

Với:

𝐴𝑖𝑗 là mục nhập ma trận kề biểu thị trọng số của cạnh nối các nút 𝑖 và 𝑗,
𝑘𝑖 = ∑𝑗 𝐴𝑖𝑗 là bậc của nút 𝑖, 𝑐𝑖 là cộng đồng mà nó thuộc về.

𝛿-hàm 𝛿 (𝑢, 𝑣) là 1 nếu 𝑢 = 𝑣 và 0 nếu không.
𝑚 = 1 ∑𝑖𝑗 𝐴𝑖𝑗 2 là tổng trọng số của tất cả các cạnh trong đồ thị.
Louvain sẽ sắp xếp ngẫu nhiên tất cả các nút trong mạng trong Tối ưu hóa mơ-đun.
Sau đó, từng nút một, nó sẽ loại bỏ và chèn từng nút vào một cộng đồng khác nhau 𝐶 cho
đến khi khơng có sự gia tăng đáng kể về mô-đun (tham số đầu vào) được xác minh:

Gọi 𝛴𝑖𝑛 là tổng trọng số của các liên kết bên trong 𝐶, 𝛴𝑡𝑜𝑡 tổng trọng số của tất cả
các liên kết tới các nút trong 𝐶, 𝑘𝑖 tổng trọng số của tất cả các liên kết ngẫu nhiên trong
nút 𝑖, 𝑘𝑖, weight tổng trọng số của các liên kết từ nút 𝑖 đến các nút trong cộng đồng 𝐶 và
𝑚 là tổng trọng số của tất cả các cạnh trong đồ thị.
Trong khi 𝑘𝑖, 𝑖𝑛 và Σ𝑡𝑜𝑡 cần được tính tốn cho mỗi cộng đồng thử nghiệm, k𝑖 /
(2m) là cụ thể của nút đang được phân tích. Bằng cách này, biểu thức sau chỉ được tính
tốn lại khi một nút khác được xem xét trong Tối ưu hóa mơ-đun.

So sánh hiệu năng và tìm hiểu các thuật toán phân cụm

Trang 9


8. Mơ hình dịch bệnh SIR (Susceptible-Infected-Recovered)
8.1 Các khái niệm trong mơ hình SIR
Mơ hình SIR là một mơ hình toán học cơ bản về dịch bệnh, được giới thiệu trong
bài báo kinh điển của Kermack và McKendrick. Trong mô hình này, dân số được chia
thành 3 nhóm, dựa theo trạng thái đối với bệnh:
Nhóm 1: Những người có khả năng mắc bệnh (Susceptible)
Nhóm 2: Những người đang nhiễm bệnh và có thể lây cho người khác
(Infected)
Nhóm 3: Những người khơng cịn khả năng mắc bệnh (Removed hay
Recovered). Trong mơ hình này, trạng thái của một người chỉ có thể chuyển từ S
sang I (nhiễm bệnh), hoặc từ I sang R (bình phục hoặc chết, nhưng khơng thể nhiễm

lại).
Số người thuộc mỗi nhóm tại một thời điểm t được ký hiệu lần lượt là S(t), I(t) và
R(t). Trong mơ hình SIR đơn giản, tổng dân số được coi là không đổi, có nghĩa
S(t)+I(t)+R(t) = N khơng phụ thuộc vào t. Đại lượng được quan tâm nhất là I(t): chiều tăng
hay giảm (theo t) và độ lớn của nó cho biết xu hướng lây lan và quy mô của dịch bệnh.
Một trong những đại lượng quan trọng nhất đối với một mơ hình dịch bệnh là hệ số
lây nhiễm cơ bản, hay thường gọi là “hệ số R0”. Nếu R0 < 1, dịch sẽ tắt trước khi kịp bùng
phát, còn nếu R0 > 1, dịch sẽ bùng phát. Thí dụ, trong mơ hình SIR đơn giản ở trên, R0 =
β/γ, trong đó β là số người khỏe mạnh trung bình mà một người mắc bệnh có thể lây cho
trong khoảng thời gian mắc bệnh 1/γ.
Theo cảm tính, điều này khá hợp lý:
nếu trung bình một người mắc bệnh lây
cho nhiều hơn một người thì số người
mắc bệnh phải tăng (theo cấp số nhân),
cịn nếu trung bình một người mắc
bệnh lây cho ít hơn một người khác thì số người mắc bệnh phải giảm dần.
8.2 Lý do chọn mơ hình SIR
Để mơ phỏng sự lan truyền của thông tin trong mạng cần đến một mơ hình lan
truyền mà điển hình ở đây là SIR. Do đây là mơ hình căn bản nhất về việc lan truyền vì
thế chúng em dùng mơ hình SIR để kiểm thử độ chính sác của các thuật tốn voterank,

So sánh hiệu năng và tìm hiểu các thuật toán phân cụm

Trang 10


closeness và betweenness trên các tập dữ liệu mẫu chúng em tìm được và xem kết quả so
sánh chúng.
9. Đánh giá hiệu quả
Do các phương pháp đánh giá sau dựa vào mơ hình SIR hoặc SI và việc mơ phỏng

trên các mơ hình này có thể bị ảnh hưởng bởi yếu tố ngẫu nhiên nên ta không thể dùng kết
quả chạy của một lần để đánh giá được. Thay vào đó mơ hình sẽ được chạy một cách độc
lập trong nhiều lần và kết quả trung bình của các lần chạy đó sẽ được dùng để đánh giá
hiệu quả.
Để đánh giá hiệu quả lan truyền của VoteRank, ta định nghĩa hàm F(t) như sau:

𝐹 𝑡 =

𝑛𝐼

𝑡

+ 𝑛𝑅(𝑡)
𝑛

Trong đó:
- nI(t) và 𝑛R(t) lần lượt là số lượng nodes bị nhiễm và số lượng nodes đã phục hồi
trong mơ hình SIR.
- n là tổng số nodes trong mạng.
Ý nghĩa của F(t) là tỉ lệ số nodes đã từng nhiễm trên tổng số nodes trong mạng
Trong bài báo khoa học, nhóm tác giả VoteRank đã thực hiện kiểm tra hiệu năng
trên 4 bộ dữ liệu thực tế: YOUTUBE, COND-MAT, BERKSTAN, NOTRE DAME
Hình dưới là kết quả khi mơ phỏng và chạy mơ hình SIR với λ = 1.5 và p = 0.002
(λ là tốc độ lây nhiễm và p là tỉ lệ số node được chọn làm spreader)

So sánh hiệu năng và tìm hiểu các thuật toán phân cụm

Trang 11



Có thể thấy các nodes chọn bởi VoteRank cho kết quả lan truyền tốt hơn so với các
thuật tốn khác.
Ngồi hàm F(t) nhóm tác giả cịn sử dụng hàm F(tc) để đánh giá quy mô ảnh hưởng
cuối cùng (final scale of affected nodes) với công thức như sau:

𝐹 𝑡𝑐 =

𝑛𝑅(𝑡 𝑐 )
𝑛

Với:
nR(tc) là số lượng nodes đã hồi phục khi dịch bệnh bước vào trạng thái ổn định
(steady state).
n là số lượng nodes trong mạng.
Hình sau là kết quả thử nghiệm của nhóm tác giả VoteRank thể hiện giá trị của hàm
F(tc) khi p (tỉ lệ số nodes nhiễm bệnh ban đầu) tăng dần (với λ=1.5).

So sánh hiệu năng và tìm hiểu các thuật tốn phân cụm

Trang 12


Kết quả cho thấy VoteRank đạt được phạm vi ảnh hưởng lớn hơn các phương pháp
khác trong thử nghiệm này.
Bên cạnh đó nhóm tác giả VoteRank cịn thực hiện thử nghiệm khi λ thay đổi và p
cố định như trong hình dưới (p = 0.002).

So sánh hiệu năng và tìm hiểu các thuật toán phân cụm

Trang 13



Có thể thấy từ kết quả trên rằng VoteRank đạt được phạm vi ảnh hưởng lớn hơn
các phương pháp khác khi λ thay đổi và p cố định.
Cuối cùng, nhóm tác giả VoteRank dùng một phương pháp đánh giá khác là trung
bình độ dài đường đi ngắn nhất Ls giữa các node lan truyền (spreader), phương pháp này
được dùng để đo đạc sự phân tán của các node lan truyền. Ls được định nghĩa bởi công
thức sau:
𝐿𝑠 =

1
𝑆 ( 𝑆 − 1)

𝑙𝑢,𝑣
𝑢,𝑣 ∈ 𝑆
𝑢 ≠𝑣

Với:
lu,v là khoảng cách ngắn nhất từ u đến v
S là tập các node lan truyền
Nhóm tác giả VoteRank cũng đã thực hiện thử nghiệm trên phương pháp đánh giá
Ls với kết quả như trong hình sau:

So sánh hiệu năng và tìm hiểu các thuật tốn phân cụm

Trang 14


Do VoteRank được thiết kế với ý tưởng giảm thiểu trường hợp các node gần nhau
có phạm vi ảnh hưởng trùng lặp, nên Ls của VoteRank có xu hướng lớn hơn các phương

pháp khác. Điều này cho thấy các node lan truyền chọn bởi VoteRank sẽ có sự phân tán
lớn hơn và điều này được chỉ ra là sẽ đem đến hiệu quả lan truyền tốt hơn như tài liệu tham
khảo “Hu, Z.-L., Liu, J.-G., Yang, G.-Y. & Ren, Z.-M. Effects of the distance among
multiple spreaders on the spreading. EPL106, 18002 (2014).” đã đề cập.
10. Thực hiện chương trình trên Python
10.1 Nội dung con thằn lằn
Nguồn: />Loại mạng xã hội: Animal networks.
Loại cạnh: Sự tương tác giữa các con vật.
Định nghĩa sự tương tác: Khoảng cách vật lí hai con thằn lằn được cho là đã giao
tiếp xã hội với nhau nếu chúng cách nhau trong vòng phạm vi 2m tại bất kì vị trí GPS nào
được đồng bộ hóa trong 10 phút.
Loại đồ thị: Vô hướng.
Loại động vật nghiên cứu cụ thể: Tiliqua rugosa (lớp bò sát, bộ thằn lằn).
Vị trí nghiên cứu: Kungara, South Australia.

So sánh hiệu năng và tìm hiểu các thuật tốn phân cụm

Trang 15


Thời gian nghiên cứu: 24 tiếng/120 ngày.
Bao gồm: 60 node và 318 cạnh.
Link mô tả cạnh Small Graph:
/>_weighted
10.2 Nội dung con chim én
Nguồn: />Loại mạng xã hội: Animal networks.
Loại cạnh: Sự tương tác giữa các con vật.
Định nghĩa sự tương tác: Tiếp xúc vật lí trong phạm vi 0.1m hoặc gần hơn.
Loại đồ thị: Vô hướng.
Trọng số: Số tần suất gặp của các con chim (frequency).


Loại động vật nghiên cứu cụ thể: AVES-BARN-SWALLOW (Nhạn bụng trắng).
Vị trí nghiên cứu: Boulder Country, Colorado, USA.
Thời gian nghiên cứu: 6 tiếng/11 ngày.
Bao gồm: 17 node và 53 cạnh.
Link mô tả cạnh Small Graph:
/>iation_weighted
10.3 Ý nghĩa bài tốn:
-Về dataset: Tìm hiểu đơn giản về tổ chức xã hội của 1 vài loại động vật.
-Sử dụng dataset để tìm hiểu trực quan về các thuật toán và ứng dụng vào thực tế.
-Sử dụng gephi để thể hiện rõ hơn mơ hình mạng xã hội.

So sánh hiệu năng và tìm hiểu các thuật tốn phân cụm

Trang 16