The advent of online social networks has facilitated fast and wide spread of information. However, some users, especially members of minority groups, may be less likely to receive information spreading on the network, due to their disadvantaged network position. We study the optimization problem of adding new connections to a network to enhance fairness in information access among different demographic groups. We provide a concrete formulation of this problem where information access is measured in terms of resistance distance, {offering a new perspective that emphasizes global network structure and multi-path connectivity.} The problem is shown to be NP-hard. We propose a simple greedy algorithm which turns out to output accurate solutions, but its run time is cubic, which makes it undesirable for large networks. As our main technical contribution, we reduce its time complexity to linear, leveraging several novel approximation techniques. In addition to our theoretical findings, we also conduct an extensive set of experiments using both real-world and synthetic datasets. We demonstrate that our linear-time algorithm can produce accurate solutions for networks with millions of nodes.

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 total biharmonic distance, which is the sum of the biharmonic distance between every pair of nodes in a network, is a key metric for evaluating network connectivity and robustness. In this paper, we study the problem of minimizing the total biharmonic distance by adding k nonexistent edges for a given graph G and budget k. The problem is computationally challenging. We show that the objective function of the problem is monotone but not supermodular. To solve this problem, we propose simple greedy algorithms with cubic time complexity. To mitigate the high time complexity of these greedy algorithms, we apply several techniques, including the projection method, the Laplacian solver, and convex hull approximation. These techniques reduce the time complexity of our proposed algorithms from cubic to nearly linear while providing error guarantees. Finally, extensive experiments on real datasets demonstrate both the efficiency and effectiveness of our proposed algorithms.

Random walk centrality is a fundamental metric in graph mining for quantifying node importance and influence, defined as the weighted average of hitting times to a node from all other nodes. Despite its ability to capture rich graph structural information and its wide range of applications, computing this measure for large networks remains impractical due to the computational demands of existing methods. In this paper, we present a novel formulation of random walk centrality, underpinning two scalable algorithms: one leveraging approximate Cholesky factorization and sparse inverse estimation, while the other sampling rooted spanning trees. Both algorithms operate in near-linear time and provide strong approximation guarantees. Extensive experiments on large real-world networks, including one with over 10 million nodes, demonstrate the efficiency and approximation quality of the proposed algorithms.

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.

Derived from effective resistances, the current flow closeness centrality (CFCC) for a group of nodes measures the importance of node groups in an undirected graph with$n$nodes. Given the widespread applications of identifying crucial nodes, we investigate the problem of maximizing CFCC for a node group$S$subject to the cardinality constraint$\vert S \vert =k<<n$. Despite the proven NP-hardness of this problem, we propose two novel greedy algorithms for its solution. Our algorithms are based on spanning forest sampling and Schur complement, which exhibit nearly linear time complexities and achieve an approximation factor of 1- k/k-1 -∊ for any 0 < ∊ < 1. Extensive experiments on real-world graphs illustrate that our algorithms outperform the state-of-the-art method in terms of efficiency and effectiveness, scaling to graphs with millions of nodes.

Online social networks have become an integral part of modern society, profoundly influencing how individuals form and exchange opinions across diverse domains ranging from politics to public health. The Friedkin-Johnsen model serves as a foundational framework for modeling opinion formation dynamics in such networks. In this paper, we address the computational task of efficiently determining the equilibrium opinion vector and associated metrics including polarization and disagreement, applicable to both directed and undirected social networks. We propose a deterministic local algorithm with relative error guarantees, scaling to networks exceeding ten million nodes. Further acceleration is achieved through integration with successive over-relaxation techniques, where a relaxation factor optimizes convergence rates. 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 resistance diameter of a graph is the maximum resistance distance among all pairs of nodes in the graph, which has found various applications in many scenarios. However, direct computation of resistance diameter involves the pseudoinverse of graph Laplacian, which takes cubic time and is thus infeasible for huge networks with millions of nodes. In this paper, we consider the computation and optimization problems for resistance diameter of a graph. First, we develop a nearly linear time algorithm to approximate the resistance diameter, which has a theoretically guaranteed error. Then, we propose and study an optimization problem of adding a fixed number of edges to a graph, such that the resistance diameter of the resulting graph is minimized. We show that the objective function is non-supermodular but monotone. Moreover, we propose two fast heuristic algorithms to approximately solve this problem. Finally, we conduct extensive experiments on different networks with sizes up to one million nodes, demonstrating the superiority of our algorithms in terms of efficiency and effectiveness.

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.

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.

The Kirchhoff index, which is the sum of the resistance distance between every pair of nodes in a network, is a key metric for gauging network performance, where lower values signify enhanced performance. In this paper, we study the problem of minimizing the Kirchhoff index by adding edges. We first provide a greedy algorithm for solving this problem and give an analysis of its quality based on the bounds of the submodularity ratio and the curvature. Then, we introduce a gradient-based greedy algorithm as a new paradigm to solve this problem. To accelerate the computation cost, we leverage geometric properties, convex hull approximation, and approximation of the projected coordinate of each point. To further improve this algorithm, we use pre-pruning and fast update techniques, making it particularly suitable for large networks. Our proposed algorithms have nearly-linear time complexity. We provide extensive experiments on ten real networks to evaluate the quality of our algorithms. The results demonstrate that our proposed algorithms outperform the state-of-the-art methods in terms of efficiency and effectiveness. Moreover, our algorithms are scalable to large graphs with over 5 million nodes and 12 million edges.

We study resistance eccentricity, a fundamental metric in network science for measuring the structural significance of a node. For a node in a graph, the resistance eccentricity is its maximum resistance distance to all other nodes. Fast computation of resistance eccentricity for a given subset of nodes is essential for a wide range of applications. However, a naive computation, requiring the pseudoinverse of the graph Laplacian, takes cubic time and is thus infeasible for huge networks with millions of nodes. In this paper, we devise a near-linear time algorithm to approximate the resistance eccentricity for one or multiple given nodes, accompanied by a theoretically guaranteed error bound. Furthermore, we investigate the problem of minimizing the resistance eccentricity for a given node by adding$k$missing edges to the graph, for a budget$k$. We show that while the objective function is monotone, it does not possess the submodularity property, ruling out the classical hill-climbing algorithm with theoretical guarantees. Instead, we propose two fast heuristic algorithms to approximately solve this problem. Then, we conduct extensive experiments on different networks with sizes up to several million nodes, demonstrating the superiority of our algorithms in terms of efficiency and effectiveness.

Thebiharmonic distance (BD) is a fundamental metric that measures the distance of two nodes in a graph. It has found applications in network coherence, machine learning, and computational graphics, among others. In spite of BD's importance, efficient algorithms for the exact computation or approximation of this metric on large graphs remain notably absent. In this work, we provide several algorithms to estimate BD, building on a novel formulation of this metric. These algorithms enjoy locality property (that is, they only read a small portion of the input graph) and at the same time possess provable performance guarantees. In particular, our main algorithms approximate the BD between any node pair with an arbitrarily small additive error ε in time O(1/ε2 poly(log n/ε)). Furthermore, we perform an extensive empirical study on several benchmark networks, validating the performance and accuracy of our algorithms.

The forest matrix plays a crucial role in network science, opinion dynamics, and machine learning, offering deep insights into the structure of and dynamics on networks. In this paper, we study the problem of querying entries of the forest matrix in evolving graphs, which more accurately represent the dynamic nature of real-world networks compared to static graphs. To address the unique challenges posed by evolving graphs, we first introduce two approximation algorithms, SFQ and SFQPlus, for static graphs. SFQ employs a probabilistic interpretation of the forest matrix, while SFQPlus incorporates a novel variance reduction technique and is theoretically proven to offer enhanced accuracy. Based on these two algorithms, we further devise two dynamic algorithms centered around efficiently maintaining a list of spanning converging forests. This approach ensures O(1) runtime complexity for updates, including edge additions and deletions, as well as for querying matrix elements, and provides an unbiased estimation of forest matrix entries. Finally, through extensive experiments on various real-world networks, we demonstrate the efficiency and effectiveness of our algorithms. Particularly, our algorithms are scalable to massive graphs with more than forty million nodes.

Kemeny's constant for random walks on a graph is defined as the mean hitting time from one node to another selected randomly according to the stationary distribution. It has found numerous applications and attracted considerable research interest. However, exact computation of Kemeny's constant requires matrix inversion, which scales poorly for large networks with millions of nodes. Existing approximation algorithms either leverage properties exclusive to undirected graphs or involve inefficient simulation, leaving room for further optimization. To address these limitations for directed graphs, we propose two novel approximation algorithms for estimating Kemeny's constant on directed graphs with theoretical error guarantees. Extensive numerical experiments on real-world networks validate the superiority of our algorithms over baseline methods in terms of efficiency and accuracy.

The forest matrix of a graph, particularly its diagonal elements, has far-reaching implications in network science and machine learning. The state-of-the-art algorithms for the diagonal of forest matrix computation are based on the fast Laplacian solver. However, these algorithms encounter limitations when applied to digraphs due to the incapacity of the Laplacian solver. To overcome the issue, in this paper, we propose three novel sampling-based algorithms:SCF,SCFV,and SCFV+. Our first algorithm SCF leverages a probability interpretation of the diagonal of the forest matrix and utilizes an extension of Wilson's algorithm to sample spanning converging forests. To reduce the variance in the forest sampling, we develop two novel variance-reduced techniques. The first technique, leading to the proposal of the SCFV algorithm, is inspired by opinion dynamics in graphs and applies matrix-vector iteration to the spanning forest sampling. While SCFV achieves reduced variance compared to SCF, the cross-product term in its variance expression can be complex and potentially large in certain graphs. Therefore, we develop another technique, leading to a new iteration equation and the SCFV+ algorithm. SCFV+ achieves further reduced variance without the cross-product term in the variance of SCFV. We prove that SCFV+ can achieve a relative error guarantee with high probability and maintain a linear time complexity relative to the number of nodes in the graph, presenting a superior theoretical result compared to state-of-the-art algorithms. Finally, we conduct extensive experiments on various real-world networks, showing that our algorithms achieve better estimation accuracy and are more time-efficient than the state-of-the-art algorithms. Particularly, our algorithms are scalable to massive graphs with more than twenty million nodes in both undirected and directed graphs.

For an undirected graph, its Kemeny's constant is defined as the mean hitting time of random walks from one vertex to another chosen randomly according to the stationary distribution. Kemeny's constant exhibits numerous explanations from different perspectives and has found various applications in the field of complex networks. Due to the requirement of computing the inverse of the normalized Laplacian matrix, it is infeasible to get the accurate Kemeny's constant of large networks with millions of vertices. Existing methods either consume excessive memory space that are impractical for large-scale networks, or involve redundant simulation, leaving room for further optimization. In this paper, we propose two scalable Monte Carlo algorithms RefinedMC and ForestMC to approximate Kemeny's constant. RefinedMC makes several refinements based on the simulation of truncated random walks, significantly reducing the amount of required random walks, while ForestMC utilizes the newly discovered paradigm connecting Kemeny's constant with the inverse of corresponding Laplacian submatrix, which is considerably accurate. Extensive numerical experiments on model and realistic networks demonstrate that our approximation algorithms evidently outperform the baseline methods in terms of efficiency and accuracy.

Critical nodes in networks are extremely vulnerable to malicious attacks to trigger negative cascading events such as the spread of misinformation and diseases. Therefore, effective moderation of critical nodes is very vital for mitigating the potential damages caused by such malicious diffusions. The current moderation methods are computationally expensive. Furthermore, they disregard the fundamental metric of information centrality, which measures the dissemination power of nodes. We investigate the problem of removing$k$edges from a network to minimize the information centrality of a target node$v$while preserving the network's connectivity. We prove that this problem is computationally challenging: it is NP-complete and its objective function is not supermodular. However, we propose three approximation greedy algorithms using novel techniques such as random walk-based Schur complement approximation and fast sum estimation. One of our algorithms runs in nearly linear time in the number of edges. To complement our theoretical analysis, we conduct a comprehensive set of experiments on synthetic and real networks with over one million nodes. Across various settings, the experimental results illustrate the effectiveness and efficiency of our proposed 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.

In this paper, we study the opinion maximization problem for the leader-follower DeGroot model of opinion dynamics in a social network modelled by a directed graph with n nodes, where a small number of nodes are competing leader nodes with binary opposing opinions 0 or 1, and the rest are follower nodes. We address the problem of maximizing the overall opinion by adding k ⇐ n new edges, where each edge is incident to a 1-leader and a follower. We prove that the objective function is monotone and submodular, and then propose a deterministic greedy algorithm with an approximation ratio (1-1 over e) and O(n3) running time. We then develop a fast sampling algorithm based on l-truncated absorbing random walks and sample-materialization techniques, which has sublinear time complexity O(kn1/2 log3/2 n/ε3) for any error parameter ε > 0. We provide extensive experiments on real networks to evaluate the performance of our algorithms. The results show that for undirected graphs our fast sampling algorithm outperforms the state-of-the-art method in terms of efficiency and effectiveness. While for directed graphs our fast sampling algorithm is as effective as our deterministic greedy algorithm, both of which are much better than the baseline strategies. Moreover, our fast algorithm is scalable to large directed graphs with over 41 million nodes.

We study a leader selection problem for the DeGroot model of opinion dynamics in a social network with n nodes and m edges, in the presence of s0 = O(1) leaders with opinion 0. Concretely, we consider the problem of maximizing the average opinion in equilibrium by selecting k = O(1) leaders with opinion 1 from the remaining n − s0 nodes, which was previously proved to be NP-hard. A deterministic greedy algorithm was also proposed to approximately solve the problem, which has an approximation factor (1 − 1/e) and time complexity O(n3), and thus does not apply to large networks.

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.

Concomitant with the tremendous prevalence of online social media platforms, the interactions among individuals are unprecedentedly enhanced. People are free to interact with acquaintances, express and exchange their own opinions through commenting, liking, retweeting on online social media, leading to resistance, controversy and other important phenomena over controversial social issues, which have been the subject of many recent works. In this paper, we study the problem of minimizing risk of conflict in social networks by modifying the initial opinions of a small number of nodes. We show that the objective function of the combinatorial optimization problem is monotone and supermodular. We then propose a naive greedy algorithm with a (1-1/e) approximation ratio that solves the problem in cubic time. To overcome the computation challenge for large networks, we further integrate several effective approximation strategies to provide a nearly linear time algorithm with a (1-1/e-ε) approximation ratio for any error parameter ε>0. Extensive experiments on various real-world datasets demonstrate both the efficiency and effectiveness of our algorithms. In particular, the fast one scales to large networks with more than two million nodes, and achieves up to 20x speed-up over the state-of-the-art algorithm.

The spectral radius of the non-backtracking matrix for an undirected graph plays an important role in various dynamic processes running on the graph. For example, its reciprocal provides an excellent approximation of epidemic and edge percolation thresholds. In this paper, we study the problem of minimizing the spectral radius of the non-backtracking matrix of a graph with n nodes and m edges, by deleting k selected edges. We show that the objective function of this combinatorial optimization problem is not submodular, although it is monotone. Since any straightforward approach to solving the optimization problem is computationally infeasible, we present an effective, scalable approximation algorithm with complexity O (n+km). Extensive experiment results for a large set of real-world networks verify the effectiveness and efficiency of our algorithm, and demonstrate that our algorithm outperforms several baseline schemes.

The operation of adding edges has been frequently used to the study of opinion dynamics in social networks for various purposes. In this paper, we consider the edge addition problem for the DeGroot model of opinion dynamics in a social network with n nodes and m edges, in the presence of a small number s << n of competing leaders with binary opposing opinions 0 or 1. Concretely, we pose and investigate the problem of maximizing the equilibrium overall opinion by creating k new edges in a candidate edge set, where each edge is incident to a 1-valued leader and a follower node. We show that the objective function is monotone and submodular. We then propose a simple greedy algorithm with an approximation factor (1 - 1 over e) that approximately solves the problem in O(n3) time. Moreover, we provide a fast algorithm with a (1 - 1 over e -∈) approximation ratio and Õ(mke∈-2) time complexity for any ∈ > 0, where Õ (⋅) notation suppresses the poly (log n) factors. Extensive experiments demonstrate that our second approximate algorithm is efficient and effective, which scales to large networks with more than a million 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.

Ranking the relative importance of nodes is a fundamental issue in network science, especially in the analysis of social and information networks. A variety of importance metrics and related algorithms have been proposed. However, these previous measures either do not apply to disconnected networks or have some weakness when applied to disconnected networks. In this paper, we use forest distance to assess the importance of nodes in a graph, whether connected or disconnected. For a node in a graph, its forest distance is defined as the sum of forest distances from the node to all other nodes in the graph. To illustrate the discriminating power of forest distance, we first compute the exact forest distances for all nodes in the path graph, and show that the order of node importance given by forest distances is in complete agreement with our intuition. We then show that forest distance centrality has a better discriminating power than alternate metrics such as betweenness, harmonic centrality, eigenvector centrality, and PageRank. Also, we present a theoretically guaranteed estimation algorithm, which approximates the forest distances for all nodes in a graph in nearly linear time with respect to the number of edges. Finally, we perform extensive experiments on real-world networks, which show that our approximation algorithm is both efficient and accurate for large networks.

The problem of selecting a group of vertices under certain constraints that maximize their joint centrality arises in many practical scenarios. In this paper, we extend the notion of current flow closeness centrality (CFCC) to a set of vertices in a graph, and investigate the problem of selecting a subset S to maximizes its CFCC C(S), with the cardinality constraint |S| = k. We show the NP-hardness of the problem, but propose two greedy algorithms to minimize the reciprocal of C(S). We prove the approximation ratios by showing the monotonicity and supermodularity. A proposed deterministic greedy algorithm has an approximation factor and cubic running time. To compare with, a proposed randomized algorithm gives -approximation in nearly-linear time, for any ? > 0. Extensive experiments on model and real networks demonstrate the effectiveness and efficiency of the proposed algorithms, with the randomized algorithm being applied to massive networks with more than a million vertices.

Percolation threshold of a network is the critical value such that when nodes or edges are randomly selected with probability below the value, the network is fragmented but when the probability is above the value, a giant component connecting a large portion of the network would emerge. Assessing the percolation threshold of networks has wide applications in network reliability, information spread, epidemic control, etc. The theoretical approach so far to assess the percolation threshold is mainly based on spectral radius of adjacency matrix or non-backtracking matrix, which is limited to dense graphs or locally treelike graphs, and is less effective for sparse networks with non-negligible amount of triangles and loops. In this paper, we study high-order non-backtracking matrices and their application to assessing percolation threshold. We first define high-order non-backtracking matrices and study the properties of their spectral radii. Then we focus on the 2nd-order non-backtracking matrix and demonstrate analytically that the reciprocal of its spectral radius gives a tighter lower bound than those of adjacency and standard non-backtracking matrices. We further build a smaller size matrix with the same largest eigenvalue as the 2nd-order non-backtracking matrix to improve computation efficiency. Finally, we use both synthetic networks and 42 real networks to illustrate that the use of the 2nd-order non-backtracking matrix does give better lower bound for assessing percolation threshold than adjacency and standard non-backtracking matrices.