Zhongzhi Zhang

Biharmonic distance (BD) is a fundamental metric that measures the dissimilarity of a node pair s, t in a graph, encapsulating rich local and global structural information. It has found applications across various fields, including network science, graph machine learning, and computational graphics. Existing algorithms for pairwise BD queries, including the state-of-the-art (SOTA) solution that relies on sampling a significant number of long random walks, are often computationally infeasible on large graphs. In this work, we propose two novel formulations of BD based on a pivot node, derived through novel proof techniques. These formulations enhance our theoretical understanding of BD and enable efficient approximation algorithms. Our first algorithm, B ac kP ush , is a deterministic method based on a newly established local pushback operation designed for BD. The second algorithm, F ast W alk , is a randomized approach that estimates BD using ℓ-truncated absorbing random walks and counting their collisions. Lastly, we introduce F ast T ree , an algorithm inspired by a novel connection between BD and spanning trees. These algorithms, tailored to leverage more prior structural knowledge (particularly the relative connectivity to the pivot node), significantly improve efficiency and versatility compared to existing methods. Extensive empirical evaluations on benchmark networks with hundreds of millions of edges demonstrate that our algorithms can produce more accurate solutions than the SOTA methods over 100 times faster.

The identification of crucial nodes in complex networks is a fundamental problem with broad applications in graph mining, influence maximization, and other domains. Centrality measures, such as Markov centrality, quantify node importance by leveraging random walk dynamics, particularly hitting times. However, optimizing group Markov centrality, which is defined as the inverse of the expected hitting time to a node set, poses significant computational challenges due to its NP-hard nature. In this work, we propose efficient approximation algorithms based on dynamic forest sampling and Schur complement techniques to address this problem. Our algorithms exploit the supermodularity of hitting time functions and employ rooted spanning forest sampling to estimate electrical network quantities, enabling scalable and accurate node selection. Theoretical guarantees demonstrate that our methods achieve near-linear solutions with provable error bounds. Extensive experiments on diverse real-world networks validate the practical effectiveness of our approaches, demonstrating significant improvements in computational efficiency and scalability compared to conventional methods.

The phenomenon of opinion disagreement has been empirically observed and reported in the literature, which is affected by various factors, such as the structure of social networks. An important discovery in network science is that most real-life networks, including social networks, are scale-free and sparse. In this paper, we study noisy opinion dynamics in sparse scale-free social networks to uncover the influence of power-law topology on opinion disagreement. We adopt the popular discrete-time DeGroot model for opinion dynamics in a graph, where nodes' opinions are subject to white noise. We first study opinion disagreement in many realistic and model networks with a scale-free topology, which approaches a constant, indicating that a scale-free structure is resistant to noise in the opinion dynamics. Moreover, existing algorithms for estimating opinion disagreement are computationally impractical for large-scale networks due to their high computational complexity. To solve this challenge, we introduce a sublinear-time algorithm to approximate this quantity with a theoretically guaranteed error. This algorithm efficiently simulates truncated random walks starting from a subset of nodes while preserving accurate estimation. Extensive experiments demonstrate its efficiency, accuracy, and scalability.