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.

In this paper, we address the problem of fast computation and optimization of opinion-based quantities in the Friedkin–Johnsen (FJ) model. We first introduce the concept of partial rooted forests and present an efficient algorithm for computing these quantities using this method. Furthermore, we study two optimization problems in the FJ model: the Opinion Minimization Problem and the Polarization and Disagreement Minimization Problem. For both problems, we propose fast algorithms based on partial rooted forest sampling. Our methods reduce the time complexity from linear to sublinear. Extensive experiments on real-world networks demonstrate that our algorithms are both accurate and efficient, outperforming state-of-the-art methods and scaling effectively to large-scale networks.

Centrality measures are essential for identifying important nodes and edges in networks. In this paper, we focus on two forest-based centrality measures on undirected graphs: forest node centrality (FNC) and forest edge centrality (FEC), which capture the influence of nodes and edges through their participation in spanning forests. Both centrality measures can be represented using entries of the forest matrix. To address the challenge of computing the two measures on large networks, we propose two scalable algorithms from different perspectives. The first algorithm IFGN combines two variance reduction techniques to approximate the entries of the forest matrix, applicable to both FNC and FEC.The second algorithm FECE incorporates a new physical interpretation of FEC, allowing for a better overall estimation. We provide error guarantees for both algorithms and demonstrate their efficiency and effectiveness through extensive experiments on various real-world networks.

The resistance distance is a fundamental metric in circuit networks, with broad applications across various domains. While signed graphs provide a more expressive framework for modeling real-world interactions, the presence of negative edges challenges conventional methods for computing resistance distances, leading to a lack of efficient algorithms. To address this challenge, an equivalent formulation of resistance distances for signed graphs is derived, establishing its physical interpretation as voltage differences in an equivalent circuit network. This formulation enables the development of two approximation algorithms: SolverRD, which employs a linear equation solver to achieve high accuracy, and RandomwalkRD, which simulates a random walk with a trap and enhances computational efficiency while maintaining relative accuracy. Extensive experiments on real-world networks containing more than ten millions of nodes validate the effectiveness and efficiency of the proposed algorithms, advancing the resistance distance computation for signed circuit networks. The proposed algorithms could find applications for detecting important nodes in large-scale complex networks.