Có hai loại phép đo: khoảng cách geodesic (geodesic distance) và khoảng cách dựa trên đi bộ ngẫu nhiên (random walk).
Khoảng cách Geodesic (Geodesic Distance)
Một phép đo đơn giản của khoảng cách giữa hai đỉnh trong đồ thị là đường đi ngắn nhất giữa các đỉnh. Thông thường, khoảng cách geodesic giữa hai đỉnh là độ dài theo số cạnh của đường đi ngắn nhất giữa các đỉnh. Đối với hai đỉnh không liên kết trong đồ thị, khoảng cách geodesic được biểu diễn là vô hạn.
Bằng cách sử dụng khoảng cách geodesic, có thể định nghĩa nhiều phép đo hữu ích cho phân tích và phân cụm đồ thị. Cho đồ thị G = (V, E), trong đó V là tập đỉnh và E là tập cạnh, có thể định nghĩa:
- Đối với đỉnh v ∈ V, độ lệch tâm (eccentricity) của v, ký hiệu eccen(v), là khoảng cách geodesic lớn nhất giữa v và bất kỳ đỉnh u ∈ V \ {v}. Độ lệch tâm của v nắm bắt v xa đến đâu từ đỉnh cuối cùng của nó trong đồ thị.
- Bán kính của đồ thị G là độ lệch tâm nhỏ nhất của tất cả đỉnh. Đó là r = min eccen(v) với v ∈ V. Bán kính nắm bắt khoảng cách giữa "điểm trung tâm nhất" và "biên xa nhất" của đồ thị.
- Đường kính của đồ thị G là độ lệch tâm lớn nhất của tất cả đỉnh. Đó là d = max eccen(v) với v ∈ V. Đường kính định nghĩa khoảng cách lớn nhất giữa bất kỳ cặp đỉnh nào.
- Đỉnh ngoại vi (peripheral vertex) là đỉnh tạo ra đường kính.
SimRank - Tương đồng dựa trên Đi bộ ngẫu nhiên và Ngữ cảnh Cấu trúc (Structural Context)
Trong nhiều ứng dụng, khoảng cách geodesic có thể không phù hợp trong tính toán tương đồng giữa các đỉnh trong đồ thị. Trong SimRank, phép đo tương đồng dựa trên đi bộ ngẫu nhiên và trên cấu trúc cơ bản của đồ thị. Trong toán học, đi bộ ngẫu nhiên (random walk) là quỹ đạo bao gồm việc thực hiện các bước ngẫu nhiên liên tiếp.
Có hai cách biểu diễn tương đồng:
- Hai người dùng được coi tương tự nhau nếu họ có các láng giềng (neighbors) giống nhau trong mạng xã hội. Heuristic này trực quan vì hai người nhận khuyến nghị từ nhiều bạn chung sẽ đưa ra quyết định giống nhau. Loại tương đồng này dựa trên cấu trúc cục bộ (tức là lân cận) của các đỉnh, gọi là tương đồng dựa trên ngữ cảnh cấu trúc (structural context-based similarity).
- Giả sử AllElectronics gửi thông tin khuyến mãi cho cả Ada và Bob trong mạng xã hội. Ada và Bob có thể ngẫu nhiên chuyển tiếp thông tin đó cho bạn bè (hoặc láng giềng) của họ trong mạng. Mức độ gần gũi giữa Ada và Bob có thể tính bằng xác suất rằng những người dùng khác nhau cùng lúc nhận được thông tin khuyến mãi ban đầu gửi cho Ada và Bob. Loại tương đồng này dựa trên khả năng tiếp cận (reachability) của đi bộ ngẫu nhiên qua mạng, do đó được định nghĩa là tương đồng dựa trên đi bộ ngẫu nhiên.