Độ quan trọng dựa trên bước đi ngẫu nhiên.

Tóm tắt báo cáo

Trong phân tích mạng xã hội, bài toán tìm phần tử trung tâm là một trong những bài toán quan trọng để giải quyết nhiều vấn đề trong xã hội nói chung và ngành CNTT nói riêng. Trong đó biện pháp tính độ trung tâm Centrality là một trong những biện pháp được nghiên cứu nhiều nhất nhằm xác định độ quan trọng tương đối của một đỉnh trong đồ thị. Thông thường độ đo Centrality được xây dựng dựa trên các thuật toán tìm đường đi ngắn nhất. Tuy nhiên cách tính này có hạn chế là chỉ xét trên các đường đi ngắn nhất mà không xét các đường đi còn lại. Vì vậy một cách tính khác dựa trên bước đi ngẫu nhiên Random Walk được đưa ra để khắc phục hạn chế này. Có hai chỉ số Centrality dựa trên Random Walk thường được sử dụng: Hệ số trung tâm trung gian dựa trên bước đi ngẫu nhiên (Random walk betweenness centrality) và Hệ số trung tâm lân cận dựa trên bước đi ngẫu nhiên (Random walk closeness centrality)