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,...
Độ đo VoteRank
Ý tưởng thuật toá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 trên quan sát, nhóm tác giả phát triển thuật toán VoteRank, tập trung vào việc xác định các node có ảnh hưởng lớn nhất thông qua điểm bỏ phiếu từ các láng giềng Node nhận được điểm bỏ phiếu cao nhất sẽ được coi là node có ảnh hưởng lớn nhất, trong khi khả năng bỏ phiếu của các node láng giềng sẽ bị giảm thiể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
Khi một node đã được chọn trong các lần bỏ phiếu trước, nó sẽ bị loại bỏ trong những lần chọn tiếp theo Đồng thời, khả năng bầu chọn của các láng giềng của node được chọn cũng sẽ bị giảm trong các 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.
Các bước trong thuật toán VoteRank
Trong VoteRank, mỗi node được gán một cặp giá trị (su, vau), trong đó su đại diện cho điểm số mà node u nhận được từ các láng giềng, còn vau là số điểm mà node u có khả năng bỏ phiếu cho các láng giềng của mình.
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 toán phân cụm Trang 3
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: Giảm khả năng bầu cử của các node láng giềng của node đã chọn trong bước 3 Các node này sẽ được gán giá trị (su, vau – f), trong đó f được tính theo một công thức cụ thể.
Với k là số bậc trung bình.
Ví dụ về VoteRank
- Yê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
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 toán phân cụm Trang 4
Trong quá trình bầu cử lượt 1, các node nhận và cho điểm từ các láng giềng của mình Kết quả, node có điểm bầu cử cao nhất được chọn, cụ thể là node 0 với 5 điểm.
Trong quá trình bầu cử lượt 2, Node 0 được gán giá trị (0, 0) và các láng giềng của nó bị giảm điểm bầu cử với f = 1/2.4, trong đó 2.4 là số bậc trung bình của mạng Kết quả cho thấy Node 7 có điểm bầu cử cao nhất, đạ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 5
Betweenness Centrality
Betweenness centrality của một đỉnh được xác định bằng cách tính tổng số các đường đi ngắn nhất đi qua đỉnh đó và chia cho tổng số các đường đi ngắn nhất trong toàn bộ mạng.
Betweenness Centrality là một chỉ số quan trọng trong mạng xã hội, giúp xác định vị trí của một tác nhân dựa trên khả năng kết nối của nó với các cặp tác nhân hoặc 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ì:
Node này giữ vai trò quan trọng và có tầm ảnh hưởng lớn trong mạng Việc loại bỏ node này sẽ dẫn đến sự tan rã cấu trúc mạng, khiến các node không còn khả năng 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 6
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.
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 quân 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:
Với: n là số phần tử (node) trong mạng g(v i , v j ) là khoảng cách ngắn nhất từ v i đến v j
PageRank
Giới thiệu về thuật toán PageRank
PageRank là một thuật toán phân tích được sử dụng để đánh giá giá trị xếp hạng của các trang web, dựa trên số lượng và chất lượng các liên kết trỏ đến trang web đó.
Giá trị Pagerank được xác định bởi một thuật toán dựa trên webgraph, trong đó các trang web được xem như các đỉnh và các liên kết là các cạnh Khi xây dựng webgraph, các trang từ các cơ quan uy tín như cnn.com hay usa.gov được xem xét Giá trị xếp hạng phản ánh tầm quan trọng của từng trang cụ thể, với mỗi liên kết tới trang web được coi là một sự hỗ trợ, giúp tăng cường giá trị Pagerank.
So sánh hiệu năng và tìm hiểu các thuật toán phân cụm Trang 7
PageRank là một thuật toán được định nghĩa đệ quy, phụ thuộc vào số lượng và giá trị của các trang web có liên kết đến trang đó Trang web nhận nhiều liên kết từ các trang có PageRank cao sẽ có giá trị PageRank cao hơn Nhiều nghiên cứu đã được thực hiện dựa trên công trình của Page và Brin, tuy nhiên, khái niệm PageRank lại rất khó thao tác Các nghiên cứu cũng đã chỉ ra những ảnh hưởng sai lệch đến thứ hạng PageRank, với mục tiêu tìm ra phương pháp hiệu quả để loại bỏ các liên kết không đáng tin cậy.
Ý tưởng thuật toán PageRank
Thuật toán PageRank đánh giá giá trị của các trang web dựa trên hệ thống liên kết, với tỷ lệ hiển thị bằng % Trang C có PageRank cao hơn trang E mặc dù số lượng liên kết đến C ít hơn, nhờ vào một liên kết từ một trang quan trọng Khi người dùng lướt web, có 85% xác suất họ chọn một liên kết ngẫu nhiên trên trang hiện tại và 15% xác suất chuyển đến một trang bất kỳ trong hệ thống Trang E có xác suất truy cập là 8.1% Nếu không tính yếu tố damping, người dùng sẽ dừng lại ở các trang A, B, hoặc C, trong khi các trang khác sẽ có PageRank bằng 0 Tuy nhiên, khi 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ó một liên kết trỏ đi.
Trong một nhóm gồm 4 trang web A, B, C, D, mỗi trang có một liên kết duy nhất đến một trang khác và liên kết từ một trang đến chính nó không được tính Ban đầu, giá trị Pagerank của tất cả các trang là như nhau, tổng giá trị Pagerank tương đương với số lượng trang web, do đó mỗi trang có giá trị Pagerank ban đầu là 1 Tuy nhiên, trong các ví dụ tiếp theo, giá trị này sẽ dao động từ 0 đến 1, với giá trị ban đầu cho mỗi trang là 0.25 Giá trị Pagerank được chuyển từ một trang đến các trang khác thông qua các liên kết, và trong các bước tính tiếp theo, giá trị sẽ được chia đều cho tất cả các liên kết Nếu chỉ có các liên kết từ 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 toán phân cụm Trang 8
Khác với ví dụ trước, trang B có liên kết đến cả trang C và A, trong khi trang D liên kết đến tất cả ba trang Do đó, trang B sẽ chuyển 0.125 giá trị của mình tới trang A và 0.125 tới trang C Trang D, với ba liên kết, sẽ chuyển 1/3 giá trị của mình, tương đương với 0.083 tới trang 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 của trang u phụ thuộc vào giá trị PageRank của các trang v trong tập hợp Bu, được tính bằng cách chia tổng giá trị PageRank của các trang v cho số lượng liên kết L(v) từ trang v đến trang u.
Girvan-Newman
Thuật toán Girvan-Newman là phương pháp hiệu quả để phát hiện và phân tích cấu trúc cộng đồng trong mạng lưới, dựa trên việc loại bỏ các cạnh có số lượng đường đi ngắn nhất cao nhất.
Thuật toán Girvan-Newman là phương pháp đơn giản nhằm xác định và loại bỏ cạnh có độ trung gian lớn nhất trong đồ thị Quá trình này lặp lại, tính toán lại độ trung gian và loại bỏ các cạnh cho đến khi không còn cạnh nào Nếu có hai cạnh có độ trung gian giống nhau, có thể chọn loại bỏ một trong hai hoặc cả hai Toàn bộ thuật toán được biểu diễn qua một dendrogram, mô tả quá trình từ gốc đến các lá, với các nhánh thể hiện các phép loại bỏ cạnh để phân chia đồ thị thành các cộng đồng riêng biệt.
Thuật toá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 toán phân cụm Trang 9
+ 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.
Thuật toán Louvain community
Louvain là một thuật toán không giám sát
Quá trình này không yêu cầu đầu vào về số lượng cộng đồng hay kích thước của chúng trước khi thực hiện, được chia thành hai giai đoạn: tối ưu hóa mô-đun và tổng hợp cộng đồng Sau khi hoàn thành giai đoạn đầu tiên, giai đoạn thứ hai sẽ được tiến hành Cả hai giai đoạn sẽ được thực hiện liên tục cho đến khi không còn thay đổi nào trong mạng và đạt được mô đun tối đa.
𝐴𝑖𝑗 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 thực hiện việc sắp xếp ngẫu nhiên tất cả các nút trong mạng trong quá trình Tối ưu hóa mô-đun Sau đó, từng nút sẽ được loại bỏ và chèn vào các cộng đồng khác nhau 𝐶 cho đến khi không còn sự gia tăng đáng kể về mô-đun (tham số đầu vào) được xác nhận.
Tổng trọng số của các liên kết bên trong cộng đồng 𝐶 được ký hiệu là 𝛴𝑖𝑛, trong khi 𝛴𝑡𝑜𝑡 đại diện cho tổng trọng số của tất cả các liên kết tới các nút trong 𝐶 Đối với nút 𝑖, tổng trọng số của các liên kết ngẫu nhiên được gọi là 𝑘𝑖, và trọng số của các liên kết từ nút 𝑖 tới các nút trong cộng đồng 𝐶 được ký hiệu là weight.
𝑚 là tổng trọng số của tất cả các cạnh trong đồ thị
Trong quá trình tối ưu hóa mô-đun, các giá trị 𝑘𝑖, 𝑖𝑛 và Σ𝑡𝑜𝑡 cần được tính toán cho từng cộng đồng thử nghiệm, trong khi k𝑖 / (2m) chỉ áp dụng cho nút cụ thể đang được phân tích Biểu thức này sẽ chỉ được tính toán lại khi một nút khác được xem xét.
So sánh hiệu năng và tìm hiểu các thuật toán phân cụm Trang 10
Mô hình dịch bệnh SIR
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 quan trọng trong nghiên cứu dịch bệnh, được giới thiệu bởi Kermack và McKendrick Mô hình này phân chia dân số thành ba nhóm chính dựa trên trạng thái nhiễm bệnh: S (Susceptible - Dễ bị nhiễm), I (Infectious - Nhiễm bệnh) và R (Recovered - Đã hồi phục).
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
Nhóm 3: Những người không còn khả năng mắc bệnh (Removed hay
Trong mô hình này, trạng thái của một người chỉ có thể chuyển từ S (khỏe mạnh) sang I (nhiễm bệnh) hoặc từ I sang R (bình phục hoặc chết), và không thể nhiễm lại.
Trong mô hình SIR đơn giản, số người thuộc các nhóm S(t), I(t) và R(t) tại thời điểm t được xác định, với tổng dân số N không thay đổi theo thời gian, tức là S(t) + I(t) + R(t) = N Đại lượng I(t) là yếu tố quan trọng nhất, cho thấy sự tăng trưởng hoặc giảm sút theo thời gian, từ đó phản ánh xu hướng lây lan và quy mô của dịch bệnh.
Hệ số lây nhiễm cơ bản, hay còn gọi là "hệ số R0", là một trong những đại lượng quan trọng nhất trong mô hình dịch bệnh Khi R0 nhỏ hơn 1, dịch bệnh sẽ ngừng phát triển trước khi bùng phát, trong khi R0 lớn hơn 1 cho thấy dịch sẽ bùng phát Trong mô hình SIR đơn giản, R0 được tính bằng β/γ, trong đó β đại diện cho số người khỏe mạnh mà một người mắc bệnh có thể lây nhiễm trong thời gian mắc bệnh 1/γ.
Nếu một người mắc bệnh lây cho nhiều hơn một người khác, số ca mắc bệnh sẽ tăng theo cấp số nhân Ngược lại, nếu một người chỉ lây cho ít hơn một người, số ca mắc bệnh sẽ giảm dần.
Lý do chọn mô hình SIR
Để mô phỏng sự lan truyền thông tin trong mạng, mô hình SIR được sử dụng như một ví dụ điển hình Đây là mô hình cơ bản nhất về sự lan truyền, vì vậy chúng tôi áp dụng mô hình SIR để kiểm tra độ chính xác của các thuật toán voterank.
Chúng tôi đã tiến hành so sánh hiệu năng của các thuật toán phân cụm closeness và betweenness trên các tập dữ liệu mẫu mà chúng tôi thu thập được Kết quả cho thấy sự khác biệt rõ rệt trong hiệu suất của từng thuật toán, từ đó giúp chúng tôi rút ra những nhận định quan trọng về khả năng phân cụm của chúng.
Đánh giá hiệu quả
Các phương pháp đánh giá dựa trên mô hình SIR hoặc SI có thể bị ảnh hưởng bởi yếu tố ngẫu nhiên, do đó không thể chỉ dựa vào kết quả của một lần chạy để đưa ra đánh giá Thay vào đó, mô hình cần được chạy độc lập nhiều lần và kết quả trung bình của các lần chạy sẽ được sử 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:
- n I(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
In the context of network analysis, 'n' represents the total number of nodes within the network, while F(t) indicates the ratio of nodes that have been infected to the total number of nodes The research team behind VoteRank conducted performance evaluations using four real-world datasets: YOUTUBE, COND-MAT, BERKSTAN, and NOTRE DAME.
Kết quả mô phỏng mô hình SIR với λ = 1.5 và p = 0.002 cho thấy sự lây lan của dịch bệnh trong mạng lưới, trong đó λ đại diện cho tốc độ lây nhiễm và p là tỷ lệ số node được chọn làm nguồn lây.
So sánh hiệu năng và tìm hiểu các thuật toán phân cụm Trang 12
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 toán khác
Ngoà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: n R(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
Kết quả thử nghiệm của nhóm tác giả VoteRank cho thấy giá trị của hàm F(tc) khi tỷ lệ số nodes nhiễm bệnh ban đầu p tăng dần, với λ=1.5.
So sánh hiệu năng và tìm hiểu các thuật toán phân cụm Trang 13
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 14
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
Nhóm tác giả VoteRank đã áp dụng một phương pháp đánh giá mới, đó là trung bình độ dài đường đi ngắn nhất Ls giữa các node lan truyền (spreader), nhằm đo lường sự phân tán của các node này Ls được định nghĩa theo một công thức cụ thể.
Với: l u,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 toán phân cụm Trang 15
VoteRank được thiết kế nhằm giảm thiểu sự trùng lặp trong phạm vi ảnh hưởng của các node gần nhau, dẫn đến giá trị Ls của VoteRank thường lớn hơn so với các phương pháp khác Điều này cho thấy rằng các node được chọn để lan truyền bởi VoteRank có sự phân tán cao hơn, từ đó mang lại hiệu quả lan truyền tốt hơn Nghiên cứu của Hu et al (2014) đã chỉ ra tầm quan trọng của khoảng cách giữa các nguồn lan truyền trong quá trình này.
Thực hiện chương trình trên Python
Nội dung con thằn lằn
Nguồn: http://networkrepository.com/reptilia-lizard-network-social.php
Loại mạng xã hội: Animal networks
Sự tương tác giữa các con vật, đặc biệt là thằn lằn, được định nghĩa là khi chúng giao tiếp xã hội trong khoảng cách vật lý không vượt quá 2m Điều này được xác định dựa trên vị trí GPS đồng bộ trong khoảng thời gian 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 toán phân cụm Trang 16
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: https://github.com/bansallab/asnr/tree/master/Networks/Reptilia/lizard_proximity_weighted
Nội dung con chim én
Nguồn: http://networkrepository.com/aves-barn-swallow-contact-network.php 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: https://github.com/bansallab/asnr/tree/master/Networks/Aves/barnswallow_assoc iation_weighted
-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 để trực quan hóa các thuật toán và ứng dụng của chúng trong thực tế, đồng thời áp dụng Gephi để minh họa rõ nét mô hình mạng xã hội.