Phân tích mạng trong R: Các thước đo độ trung tâm

Một trong những việc quan trọng nhất bạn sẽ muốn làm khi thực hiện phân tích mạng là xác định độ trung tâm của một nút trong mạng xã hội. Nói cách khác, khi bạn có một mạng để phân tích, bạn sẽ muốn xác định nút nào có ảnh hưởng lớn nhất đến các nút khác. Hướng dẫn này sẽ tập trung đúng vào điều đó. Trong đó, bạn sẽ tìm hiểu thêm về các chủ đề sau:

• Định nghĩa của độ trung tâm là gì?
• Các loại thước đo độ trung tâm gồm những gì?
• Quy trình xác định thước đo độ trung tâm tốt nhất theo cấu trúc tô-pô của mạng như thế nào?

Định nghĩa về Độ trung tâm

Ngày nay, học cách tìm các nút cốt lõi của một mạng là điều thiết yếu với mọi nhà nghiên cứu muốn làm việc trong khoa học mạng. Khi bạn tiến xa hơn, các mạng trong bối cảnh các ngành khoa học khác nhau trở nên lớn hơn và phức tạp hơn. Do đó, việc phân tích tỉ mỉ từng nút là tốn kém, mất thời gian và ở một mức độ nào đó là bất khả thi. Mô tả về độ trung tâm trả lời câu hỏi: "Nút nào là quan trọng nhất trong mạng?".

Một hàm gán một giá trị số cho mỗi đỉnh của mạng theo mức độ ảnh hưởng của nó lên các đỉnh khác. Tầm quan trọng của một nút được xác định bởi vị trí của nó trong mạng. Tùy thuộc vào loại mạng, bạn có thể mô tả ý nghĩa của tầm quan trọng. Nó có thể là một người có ảnh hưởng trong mạng xã hội hoặc các nút hạ tầng then chốt trong mạng lưới đô thị.

Các thước đo Độ trung tâm: Phân loại

Các chỉ số độ trung tâm có thể được phân loại theo phạm vi cục bộ và toàn cục.

Thước đo Độ trung tâm cục bộ

Một ví dụ về thước đo độ trung tâm cục bộ là độ trung tâm theo bậc (degree), đếm số liên kết mà mỗi nút sở hữu và chỉ ra những cá nhân có thể nhanh chóng kết nối với mạng rộng hơn. Đây là thước đo cục bộ vì nó không xét đến phần còn lại của mạng và mức độ quan trọng mà bạn gán cho giá trị này phụ thuộc mạnh vào kích thước mạng.

Để tính các thước đo độ trung tâm phổ biến như degree, bạn có thể dùng gói igraph. Bạn có thể nạp gói bằng hàm library():

library(igraph)Được hỗ trợ bởi

Trước khi thực hiện bất kỳ phép tính độ trung tâm nào, bạn cần có một mạng. Để làm điều này, bạn có thể dùng một trong các thuật toán ngẫu nhiên, như mô hình Erdos-Renyi, để xây dựng đồ thị mẫu.

Mô hình Erdos-Renyi được giới thiệu bởi Paul Erdos và Alfred Renyi, hai nhà toán học vĩ đại, vào năm 1959. Nó hữu ích để tạo các đồ thị ngẫu nhiên trong đó mỗi cặp nút được nối với nhau bằng một xác suất bằng nhau để tạo thành một cạnh. Trong mô hình đồ thị ngẫu nhiên này, hầu hết các nút có số kết nối xấp xỉ bằng nhau và phân phối bậc của mô hình thường là nhị thức hoặc Poisson. Mô hình này có thể được dùng trong các phương pháp xác suất để chứng minh sự tồn tại của các đồ thị với những tính chất đa dạng, hoặc để so sánh về mặt cấu trúc với các mạng thực.

Để xem ví dụ về mô hình Erdos-Renyi, bạn có thể dùng hàm sample_gnm() từ gói igraph.

# n = số nút, m = số cạnh
erdos.gr <- sample_gnm(n=10, m=25) 

plot(erdos.gr)Được hỗ trợ bởi

Đây là một mạng vô hướng, tức đồ thị với các cạnh hai chiều, trái ngược với đồ thị có hướng nơi hướng đi của cạnh từ đỉnh này tới đỉnh khác được xét đến, với 10 nút và 25 cạnh.

Độ trung tâm theo bậc của đồ thị này được tính bằng hàm centr_degree():

degree.cent <- centr_degree(erdos.gr, mode = "all")
degree.cent$res

##  [1] 2 3 5 6 7 7 6 3 6 5Được hỗ trợ bởi

Như minh họa, nút 1 có giá trị độ trung tâm theo bậc cao nhất trong toàn bộ mạng mẫu.

Thước đo Độ trung tâm toàn cục

Ngược lại, các thước đo độ trung tâm toàn cục xét đến toàn bộ mạng. Một trong những thước đo được dùng rộng rãi nhất là độ trung tâm theo độ gần (closeness). Thước đo này chấm điểm mỗi nút dựa trên mức độ gần gũi của chúng với tất cả các nút khác trong mạng.

Nó tính các đường đi ngắn nhất giữa mọi cặp nút, sau đó gán cho mỗi nút một điểm dựa trên tổng độ dài các đường đi ngắn nhất, và hữu ích để tìm những cá nhân ở vị trí tốt nhất nhằm ảnh hưởng toàn bộ mạng một cách nhanh nhất.

Khuyến nghị dùng Closeness để tìm các đỉnh trung tâm trong một cụm đơn. Bạn có thể tính chỉ số này qua hàm closeness() trong gói igraph.

closeness.cent <- closeness(erdos.gr, mode="all")
closeness.cent

##  [1] 0.05882353 0.06250000 0.07142857 0.08333333 0.09090909 0.09090909
##  [7] 0.08333333 0.06250000 0.08333333 0.07692308Được hỗ trợ bởi

Theo kết quả độ trung tâm theo độ gần, trái với độ trung tâm theo bậc, các nút 1 và 9 có giá trị trung tâm cao nhất trong toàn mạng. Điều này có nghĩa là các nút này có vai trò quan trọng ngang nhau trong dòng chảy của mạng.

Cách chọn Thước đo Độ trung tâm tốt nhất

Mặc dù có nhiều loại thước đo độ trung tâm để xác định các nút ảnh hưởng nhất của một mạng, hiện vẫn chưa có một quy trình chuẩn được đồng thuận trong khoa học mạng để chọn và triển khai thước đo phù hợp nhất cho một mạng cụ thể.

Để minh họa, biểu đồ sau thể hiện biểu đồ phân tán giữa hai thước đo độ trung tâm tên là "độ trung tâm dưới đồ thị" (subgraph centrality) và "hệ số tô-pô" (topological coefficient). Đường màu đỏ cho thấy mối liên hệ âm mạnh giữa hai thước đo này.

Bạn có thể kết luận từ hình trên rằng do hai thước đo này có quan hệ nghịch đảo, chúng có thể phân biệt các nút trung tâm trong mạng dựa trên các mẫu khác nhau và vì vậy kết quả tính độ trung tâm sẽ thay đổi tùy theo loại thước đo.

Hiện có hơn 140 chỉ báo để xác định các đỉnh trung tâm, nhưng nên dùng chỉ báo nào để tính các nút có ảnh hưởng?

Thêm vào đó, vì các đặc trưng tô-pô của mạng ảnh hưởng đến kết quả tính độ trung tâm, bạn phải chọn một tiêu chí có mức thông tin cao nhất về các đỉnh ảnh hưởng dựa trên tô-pô của mạng.

CINNA (Central Informative Nodes in Network Analysis) là một gói R để tính toán, phân tích và so sánh các thước đo độ trung tâm, đã được đưa lên kho CRAN.

Để xem cách dùng gói này, bạn bắt đầu với một trong các bộ dữ liệu có sẵn trong gói tên là Zachary. Bộ dữ liệu này mô tả tình bạn giữa các thành viên của một câu lạc bộ karate đại học:

library(CINNA)

data("zachary")

plot(zachary)Được hỗ trợ bởi

Đây là một đồ thị vô hướng, với 34 đỉnh và 78 cạnh. Lưu ý rằng đồ thị vô hướng là đồ thị mà các cạnh không có hướng: chúng là hai chiều. Ví dụ: A<--->B == B<--->A.

Để xác định các loại độ trung tâm có thể tính dựa trên cấu trúc đồ thị, hàm proper_centralities() có thể hữu ích.

pr_cent<-proper_centralities(zachary)

##  [1] "subgraph centrality scores"                      
##  [2] "Topological Coefficient"                         
##  [3] "Average Distance"                                
##  [4] "Barycenter Centrality"                           
##  [5] "BottleNeck Centrality"                           
##  [6] "Centroid value"                                  
##  [7] "Closeness Centrality (Freeman)"                  
##  [8] "ClusterRank"                                     
##  [9] "Decay Centrality"                                
## [10] "Degree Centrality"                               
## [11] "Diffusion Degree"                                
## [12] "DMNC - Density of Maximum Neighborhood Component"
## [13] "Eccentricity Centrality"                         
## [14] "eigenvector centralities"                        
## [15] "K-core Decomposition"                            
## [16] "Geodesic K-Path Centrality"                      
## [17] "Katz Centrality (Katz Status Index)"             
## [18] "Kleinberg's authority centrality scores"         
## [19] "Kleinberg's hub centrality scores"               
## [20] "clustering coefficient"                          
## [21] "Lin Centrality"                                  
## [22] "Lobby Index (Centrality)"                        
## [23] "Markov Centrality"                               
## [24] "Radiality Centrality"                            
## [25] "Shortest-Paths Betweenness Centrality"           
## [26] "Current-Flow Closeness Centrality"               
## [27] "Closeness centrality (Latora)"                   
## [28] "Communicability Betweenness Centrality"          
## [29] "Community Centrality"                            
## [30] "Cross-Clique Connectivity"                       
## [31] "Entropy Centrality"                              
## [32] "EPC - Edge Percolated Component"                 
## [33] "Laplacian Centrality"                            
## [34] "Leverage Centrality"                             
## [35] "MNC - Maximum Neighborhood Component"            
## [36] "Hubbell Index"                                   
## [37] "Semi Local Centrality"                           
## [38] "Closeness Vitality"                              
## [39] "Residual Closeness Centrality"                   
## [40] "Stress Centrality"                               
## [41] "Load Centrality"                                 
## [42] "Flow Betweenness Centrality"                     
## [43] "Information Centrality"Được hỗ trợ bởi

Kết quả chứa một danh sách cho biết 43 tên thước đo độ trung tâm phổ biến, dành riêng cho cấu trúc vô hướng-không trọng số.

Hãy chọn năm thước đo đầu tiên trong danh sách và truyền chúng vào hàm calculate_centralities(), vì tính toán tất cả các độ trung tâm có thể tính sẽ tốn nhiều thời gian.

Ở bước tiếp theo, bạn dùng thuật toán Phân tích Thành phần Chính (PCA) để phân biệt thước đo độ trung tâm nhiều thông tin nhất.

Lưu ý rằng PCA là một kỹ thuật giảm chiều dùng cho phân tích tuyến tính.

Ở bước phân tích này, mỗi thước đo độ trung tâm đóng vai trò như một biến. Do đó, các độ trung tâm tương quan với các thành phần chính là quan trọng nhất trong việc xác định các nút trung tâm. Tiêu chí “đóng góp” từ PCA cho thấy các biến đóng góp như thế nào vào các thành phần chính.

Nói cách khác, mức đóng góp của các biến phản ánh độ biến thiên tương ứng với các thành phần chính (theo phần trăm). Nhờ tiêu chí này trong phương pháp PCA, bạn có thể phát hiện các độ trung tâm nào có nhiều thông tin hơn về các nút trung tâm và vì thế, thước đo nào mô tả các đỉnh ảnh hưởng của mạng chính xác hơn. Do đó, các chỉ số đóng góp đã được sắp xếp của các độ trung tâm có thể được trực quan hóa như bên dưới.

Tiếp theo, bạn sẽ áp dụng liên tiếp hai bước vừa rồi bằng cách dùng toán tử pipe %>%:

calculate_centralities(zachary, include = pr_cent[1:5])%>%
  pca_centralities(scale.unit = TRUE)Được hỗ trợ bởi

Như thể hiện trên biểu đồ, Barycenter Centrality có giá trị đóng góp lớn nhất trong năm chỉ số độ trung tâm.

Nói cách khác, nó có nhiều thông tin nhất về các nút ảnh hưởng trong số các thước đo đã tính. Do vậy, nó có thể xác định các nút trung tâm chính xác hơn so với các thước đo được chọn khác.

Một cách biểu diễn đồ thị trong đó kích thước mỗi nút phản ánh giá trị độ trung tâm tương ứng sẽ như bên dưới.

visualize_graph( zachary , centrality.type="Barycenter Centrality")Được hỗ trợ bởi

Theo đó, nút 1 là nút trung tâm nhất trong toàn bộ mạng.

Tổng kết

Tóm lại, để định lượng khả năng kết nối của một mạng, khuyến nghị áp dụng PCA lên một số thước đo độ trung tâm mà bạn có thể tính theo cấu trúc mạng và chọn thước đo nhiều thông tin nhất để tính toán và giải thích mức đóng góp tối đa tương ứng với các thành phần chính của chúng.

Trong hướng dẫn này, trước tiên bạn đã nêu định nghĩa về độ trung tâm và đề cập một số thước đo phổ biến. Sau đó, bạn nhấn mạnh rằng vì các thuộc tính toàn cục của một mạng sẽ ảnh hưởng đến việc phát hiện thành phần trung tâm, các nút ảnh hưởng của một mạng sẽ khác nhau tùy theo tô-pô mạng.

Ở bước tiếp theo, bạn đã dùng gói CINNA, vốn cung cấp mọi hàm cần thiết để áp dụng phân tích độ trung tâm trong một mạng. Với gói này, bạn có thể thực hiện phân tích độ trung tâm trên mạng của mình mà không cần thêm công việc bổ sung. Hơn nữa, điều này giúp tăng đáng kể độ chính xác trong việc xác định các nút trung tâm.

Nếu bạn muốn tìm hiểu sâu ngay và xem cách nó hoạt động, hãy xem bài báo này, và cả bài này.

Nếu bạn có bất kỳ câu hỏi hay băn khoăn nào về nội dung trên, vui lòng liên hệ với tôi qua Minoo_Ashtiani.

Để tìm hiểu thêm về R, hãy xem hướng dẫn Kỹ năng lập trình cơ bản trong R và các khóa học sau: