The function or performance of a network is strongly dependent on its robustness, quantifying the ability of the network to continue functioning under perturbations. While a wide variety of robustness metrics have been proposed, they have their respective limitations. In this paper, we propose to use the forest index as a measure of network robustness, which overcomes the deficiencies of existing metrics. Using such a measure as an optimization criterion, we propose and study the problem of breaking down a network by attacking some key edges. We show that the objective function of the problem is monotonic but not submodular, which impose more challenging on the problem. We thus resort to greedy algorithms extended for non-submodular function by iteratively deleting the most promising edges. We first propose a simple greedy algorithm with a proved bound for the approximation ratio and cubic-time complexity. To confront the computation challenge for large networks, we further propose an improved nearly-linear time greedy algorithm, which significantly speeds up the process for edge selection but sacrifices little accuracy. Extensive experimental results for a large set of real-world networks verify the effectiveness and efficiency of our algorithms, demonstrating that our algorithms outperform several baseline schemes.

Abstract Edge centrality has found wide applications in various aspects. Many edge centrality metrics have been proposed, but the crucial issue that how good the discriminating power of a metric is, with respect to other measures, is still open. In this paper, we address the question about the benchmark of the discriminating power of edge centrality metrics. We first use the automorphism concept to define equivalent edges, based on which we introduce a benchmark for the discriminating power of edge centrality measures and develop a fast approach to compare the discriminating power of different measures. According to the benchmark, for a desirable measure, equivalent edges have identical metric scores, while inequivalent edges possess different scores. However, we show that even in a toy graph, inequivalent edges cannot be discriminated by three existing edge centrality metrics. We then present a novel edge centrality metric called forest centrality (FC). Extensive experiments on real-world networks and model networks indicate that FC has better discriminating power than three existing edge centrality metrics.

Centrality metrics are one of the most fundamental tools in social network analysis and network science, and various measures for evaluating node importance metrics have been devised. However, the crucial issue of testing the discriminating power of different centrality measures is still open. In this article, we propose to assess the discriminating power of node centrality measures by using the notion of automorphism and orbit: nodes in the same orbit have identical metric scores, while nodes in different orbits should have different centrality values. Under this assumption, we present a benchmark for the discriminating power of node centrality measures. Moreover, we propose an efficient approach to evaluate centrality measures in terms of the discriminating power, which is devoid of finding orbits. Extensive experiments on real and model networks are executed to compare seven commonly used node centrality metrics.

Individual's opinions are fundamentally shaped and evolved by their interactions with other people, and social phenomena such as disagreement and polarization are now tightly woven into daily life. The quantification and optimization of these concepts have been the subject of much recent research behind a wealth of high-impact data mining applications. In particular, researchers have addressed the question of how such concepts can be optimized by influencing the opinion of a small number of individuals or by designing the network from scratch.Here, rather than a “design-from-scratch” approach or altering the initial opinion, we study the optimization problem of recommending $k$ new links to minimize the sum of polarization and disagreement in a social network with $n$ nodes and $m$ edges. We show that our objective function of this combinatorial optimization problem is not submodular, although it is monotone. We propose a simple greedy algorithm with a constant-factor approximation that solves the problem in cubic running time, and we provide theoretical analysis of the approximation guarantee for the algorithm. To overcome the computation challenge for large networks, we also provide a fast algorithm with computation complexity $\Otil (mk\eps^{-2})$ for any $\eps>0$, where the $\Otil (\cdot)$ notation suppresses the ${\rm poly} (\log n)$ factors. Extensive experiments on real datasets demonstrate both the efficiency and effectiveness of our algorithms.

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.

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.