Có hai loại thước đo như khoảng cách trắc địa và khoảng cách dựa trên bước đi ngẫu nhiên.
Khoảng cách trắc địa - Một số đo đơn giản của khoảng cách giữa hai đỉnh trong một đồ thị là đường đi ngắn nhất trong số các đỉnh. Thông thường, khoảng cách trắc địa giữa hai đỉnh là độ dài tính theo nhiều cạnh của đường đi ngắn nhất trong số các đỉnh. Đối với hai đỉnh không được liên kết trong biểu đồ, khoảng cách trắc địa được biểu thị là vô hạn.
Bằng cách sử dụng khoảng cách trắc địa, nó có thể đại diện cho các phép đo hữu ích khác nhau để phân tích và phân nhóm đồ thị. Cho một đồ thị G =(V, E), trong đó V là tập các đỉnh và E là tập các cạnh, nó có thể biểu diễn như sau -
-
Đối với một đường đi v ∈ V, độ lệch tâm của v, được chỉ ra eccen (v), là khoảng cách trắc địa cao nhất giữa v và một số đỉnh u ∈ V - {v}. Độ lệch tâm của v cho biết v cách đỉnh cuối cùng của nó bao xa trong biểu đồ.
-
Bán kính của đồ thị G là độ lệch tâm nhỏ nhất của tất cả các đỉnh.
-
Đó là, r =min eccen (v)
v ∈ V
Bán kính ghi lại khoảng cách giữa "điểm trung tâm nhất" và "đường viền xa nhất" của biểu đồ.
-
Đường kính của đồ thị G là độ lệch tâm lớn nhất của tất cả các đỉnh.
-
Đó là, d =max eccen (v)
v ∈ V
Đường kính xác định khoảng cách cao nhất giữa một số cặp đỉnh.
-
Đỉnh ngoại vi là đỉnh tạo ra đường kính.
SimRank - Sự giống nhau dựa trên Đi bộ ngẫu nhiên và Bối cảnh cấu trúc - Trong các ứng dụng khác nhau, khoảng cách trắc địa có thể không thích hợp trong việc tính toán độ giống nhau giữa các đỉnh trong đồ thị. Trong SimRank, một thước đo độ tương tự phụ thuộc vào bước đi ngẫu nhiên và vào khung cơ bản của biểu đồ. Trong toán học, một bước đi ngẫu nhiên là một quỹ đạo bao gồm thực hiện các quá trình ngẫu nhiên liên tiếp.
Có hai phương pháp để biểu thị sự giống nhau như sau -
-
Hai người dùng được đối xử như nhau nếu họ có cùng hàng xóm trên web xã hội. Kinh nghiệm này dễ hiểu vì hai người nhận được đề xuất từ một số lượng lớn bạn bè chung đưa ra quyết định giống nhau. Loại tương tự này phụ thuộc vào cấu trúc cục bộ (tức là các vùng lân cận) của các đỉnh và nó được gọi là sự tương tự dựa trên ngữ cảnh cấu trúc.
-
Giả sử AllElectronics gửi dữ liệu khuyến mại cho cả Ada và Bob trong web xã hội. Ada và Bob có thể chuyển tiếp ngẫu nhiên dữ liệu đó đến bạn bè (hoặc hàng xóm) của họ trong mạng. Sự gần gũi giữa Ada và Bob có thể được tính bằng khả năng những người dùng khác nhau đồng thời nhận được dữ liệu khuyến mại ban đầu được gửi cho Ada và Bob. Loại tương tự này phụ thuộc vào khả năng truy cập lần lượt ngẫu nhiên trên web và do đó được định nghĩa là mức độ tương tự dựa trên lượt đi bộ ngẫu nhiên.