Average Distance Approximation for Static Large Graphs

Abstract

Calculating average distances in large-scale networks is computationally intensive and constrained by limited main memory, posing a significant challenge in graph analytics. This study explores and evaluates two primary approaches for estimating average distances: a graph sampling-based method (Random Walk) and landmark-based methods, including the Size Estimation Framework (SEF) and the Eppstein-Wang (EW) algorithm. Random Walk was found to be unreliable for small sample sizes and computationally expensive for larger ones, requiring at least 15% of nodes for accuracy. Landmark-based approaches, leveraging probabilistic data structures like HyperLogLog for memory-efficient neighbor exploration, demonstrated superior performance. Among these, the SEF algorithm offers better memory efficiency, while the EW algorithm achieves higher accuracy with lower computation time. Experiments on static, undirected, and unweighted graphs (both unipartite and bipartite) revealed that the EW algorithm produced results with an error margin as low as 0.02%. Additionally, a subset of 100 randomly selected nodes was sufficient for accurate estimations in most large graphs. The findings indicate that the EW algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.