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.

For random walks on graph \(\mathcal{G}\) with \(n\) vertices and \(m\) edges, the mean hitting time \(H_{j}\) from a vertex chosen from the stationary distribution to vertex \(j\) measures the importance for \(j\) , while the Kemeny constant \(\mathcal{K}\) is the mean hitting time from one vertex to another selected randomly according to the stationary distribution. In this article, we first establish a connection between the two quantities, representing \(\mathcal{K}\) in terms of \(H_{j}\) for all vertices. We then develop an efficient algorithm estimating \(H_{j}\) for all vertices and \(\mathcal{K}\) in nearly linear time of \(m\) . Moreover, we extend the centrality \(H_{j}\) of a single vertex to \(H(S)\) of a vertex set \(S\) , and establish a link between \(H(S)\) and some other quantities. We further study the NP-hard problem of selecting a group \(S\) of \(k\ll n\) vertices with minimum \(H(S)\) , whose objective function is monotonic and supermodular. We finally propose two greedy algorithms approximately solving the problem. The former has an approximation factor \((1-\frac{k}{k-1}\frac{1}{e})\) and \(O(kn^{3})\) running time, while the latter returns a \((1-\frac{k}{k-1}\frac{1}{e}-\epsilon)\) -approximation solution in nearly-linear time of \(m\) , for any parameter \(0{\lt}\epsilon{\lt}1\) . Extensive experiment results validate the performance of our algorithms.

A signed graph offers richer information than an unsigned graph, since it describes both collaborative and competitive relationships in social networks. In this paper, we study opinion dynamics on a signed graph, based on the Friedkin-Johnsen model. We first interpret the equilibrium opinion in terms of a defined random walk on an augmented signed graph, by representing the equilibrium opinion of every node as a combination of all nodes’ internal opinions, with the coefficient of the internal opinion for each node being the difference of two absorbing probabilities. We then quantify some relevant social phenomena and express them in terms of the$\ell _{2}$norms of vectors. We also design a nearly-linear time signed Laplacian solver for assessing these quantities, by establishing a connection between the absorbing probability of random walks on a signed graph and that on an associated unsigned graph. We further study the opinion optimization problem by changing the initial opinions of a fixed number of nodes, which can be optimally solved in cubic time. We provide a nearly-linear time algorithm with an error guarantee to approximately solve the problem. Finally, we execute extensive experiments on sixteen real-life signed networks, which show that both of our algorithms are effective and efficient, and are scalable to massive graphs with over 20 million nodes.

The operation of creating edges has been widely applied to optimize relevant quantities of opinion dynamics. In this paper, we consider a problem of polarization optimization for the leader-follower opinion dynamics in a noisy social network with n nodes and m edges, where a group Q of q nodes are leaders, and the remaining n-q nodes are followers. We adopt the popular leader-follower DeGroot model, where the opinion of every leader is identical and remains unchanged, while the opinion of every follower is subject to white noise. The polarization is defined as the steady-state variance of the deviation of each node's opinion from leaders' opinion, which equals one half of the effective resistance RQ between the node group Q and all other nodes. Concretely, we propose and study the problem of minimizing RQ by adding k new edges with each incident to a node in Q. We show that the objective function is monotone and supermodular. We then propose a simple greedy algorithm with an approximation factor 1-1/e that approximately solves the problem in O((n-q)3) time. To speed up the computation, we also provide a fast algorithm to compute (1-1/e-ε)-approximate effective resistance RQ, the running time of which is O~ (mkε-2) for any ε>0, where the O~(·) notation suppresses the poly(log n) factors. Extensive experiment results show that our second algorithm is both effective and efficient.

The cover time of random walks on a graph has found wide practical applications in different fields of computer science, such as crawling and searching on the World Wide Web and query processing in sensor networks, with the application effects dependent on the behavior of the cover time: the smaller the cover time, the better the application performance. It was proved that over all graphs with N nodes, complete graphs have the minimum cover time N log N . However, complete graphs cannot mimic real-world networks with small average degree and scale-free small-world properties, for which the cover time has not been examined carefully, and its behavior is still not well understood. In this article, we first experimentally evaluate the cover time for various real-world networks with scale-free small-world properties, which scales as N log N . To better understand the behavior of the cover time for real-world networks, we then study the cover time of three scale-free small-world model networks by using the connection between cover time and resistance diameter. For all the three networks, their cover time also behaves as N log N . This work indicates that sparse networks with scale-free and small-world topology are favorable architectures with optimal scaling of cover time. Our results deepen understanding the behavior of cover time in real-world networks with scale-free small-world structure, and have potential implications in the design of efficient algorithms related to cover time.

As an important factor governing opinion dynamics, stubbornness strongly affects various aspects of opinion formation. However, a systematically theoretical study about the influences of heterogeneous stubbornness on opinion dynamics is still lacking. In this paper, we study a popular opinion model in the presence of inhomogeneous stubbornness. We show analytically that heterogeneous stubbornness has a great impact on convergence time, expressed opinion of every node, and the overall expressed opinion. We provide an explanation of the expressed opinion in terms of stubbornness-dependent spanning diverging forests. We propose quantitative indicators to quantify some social concepts, including conflict, disagreement, and polarization by incorporating heterogeneous stubbornness, and develop a nearly linear time algorithm to approximate these quantities, which has a proved theoretical guarantee for the error of each quantity. To demonstrate the performance of our algorithm, we perform extensive experiments on a large set of real networks, which indicate that our algorithm is both efficient and effective, scalable to large networks with millions of nodes.

One of the main subjects in the field of social networks is to quantify conflict, disagreement, controversy, and polarization, and some quantitative indicators have been developed to quantify these concepts. However, direct computation of these indicators involves the operations of matrix inversion and multiplication, which make it computationally infeasible for large-scale graphs with millions of nodes. In this paper, by reducing the problem of computing relevant quantities to evaluating ℓ2 norms of some vectors, we present a nearly linear time algorithm to estimate all these quantities. Our algorithm is based on the Laplacian solvers, and has a proved theoretical guarantee of error for each quantity. We execute extensive numerical experiments on a variety of real networks, which demonstrate that our approximation algorithm is efficient and effective, scalable to large graphs having millions of nodes.

The issue of opinion sharing and formation has received considerable attention in the academic literature, and a few models have been proposed to study this problem. However, existing models are limited to the interactions among nearest neighbors, ignoring those second, third, and higher-order neighbors, despite the fact that higher-order interactions occur frequently in real social networks. In this paper, we develop a new model for opinion dynamics by incorporating long-range interactions based on higher-order random walks. We prove that the model converges to a fixed opinion vector, which may differ greatly from those models without higher-order interactions. Since direct computation of the equilibrium opinions is computationally expensive, which involves the operations of huge-scale matrix multiplication and inversion, we design a theoretically convergence-guaranteed estimation algorithm that approximates the equilibrium opinion vector nearly linearly in both space and time with respect to the number of edges in the graph. We conduct extensive experiments on various social networks, demonstrating that the new algorithm is both highly efficient and effective.

For random walks on a graph, the mean hitting time $H_j$ from a vertex i chosen from the stationary distribution to the target vertex j can be used as a measure of importance for vertex j, while the Kemeny constant K is the mean hitting time from a vertex i to a vertex j selected randomly according to the stationary distribution. Both quantities have found a large variety of applications in different areas. However, their high computational complexity limits their applications, especially for large networks with millions of vertices. In this paper, we first establish a connection between the two quantities, representing K in terms of $H_j$ for all vertices. We then express both quantities in terms of quadratic forms of the pseudoinverse for graph Laplacian, based on which we develop an efficient algorithm that provides an approximation of $H_j$ for all vertices and K in nearly linear time with respect to the edge number, with high probability. Extensive experiment results on real-life and model networks validate both the efficiency and accuracy of the proposed algorithm.

The mean hitting time from a node i to a node j selected randomly according to the stationary distribution of random walks is called the Kemeny constant, which has found various applications. It was proved that over all graphs with N vertices, complete graphs have the exact minimum Kemeny constant, growing linearly with N. Here we study numerically or analytically the Kemeny constant on many sparse real-world and model networks with scale-free small-world topology, and show that their Kemeny constant also behaves linearly with N. Thus, sparse networks with scale-free and small-world topology are favorable architectures with optimal scaling of Kemeny constant. We then present a theoretically guaranteed estimation algorithm, which approximates the Kemeny constant for a graph in nearly linear time with respect to the number of edges. Extensive numerical experiments on model and real networks show that our approximation algorithm is both efficient and accurate.