An intensely debated topic is whether political polarization on social media is on the rise. We can investigate this question only if we can quantify polarization, by taking into account how extreme the opinions of the people are, how much they organize into echo chambers, and how these echo chambers organize in the network. Current polarization estimates are insensitive to at least one of these factors: They cannot conclusively clarify the opening question. Here, we propose a measure of ideological polarization that can capture the factors we listed. The measure is based on the generalized Euclidean distance, which estimates the distance between two vectors on a network, e.g., representing people’s opinion. This measure can fill the methodological gap left by the state of the art and leads to useful insights when applied to real-world debates happening on social media and to data from the U.S. Congress.
Determining a set of “important” nodes in a network constitutes a basic endeavor in network science. Inspired by electrical flows in a resistor network, we propose the best conducting node in a graph as the minimizer of the diagonal element of the pseudoinverse matrix of the weighted Laplacian matrix of the graph . We propose a new graph metric that complements the effective graph resistance and that specifies the heterogeneity of the nodal spreading capacity in a graph. Various formulas and bounds for the diagonal element are presented. Finally, we compute the pseudoinverse matrix of the Laplacian of star, path, and cycle graphs and derive an expansion and lower bound of the effective graph resistance based on the complement of the graph .
This article introduces a new approach to discrete curvature based on the concept of effective resistances. We propose a curvature on the nodes and links of a graph and present the evidence for their interpretation as a curvature. Notably, we find a relation to a number of well-established discrete curvatures (Ollivier, Forman, combinatorial curvature) and show evidence for convergence to continuous curvature in the case of Euclidean random graphs. Being both efficient to approximate and highly amenable to theoretical analysis, these resistance curvatures have the potential to shed new light on the theory of discrete curvature and its many applications in mathematics, network science, data science and physics.
Due to the open data policies, nowadays, some countries have their power grid data available online. This may bring a new concern to the power grid operators in terms of malicious threats. In this paper, we assess the vulnerability of power grids to targeted attacks based on network science. By employing two graph models for power grids as simple and weighted graphs, we first calculate the centrality metrics of each node in a power grid. Subsequently, we formulate different node-attack strategies based on those centrality metrics, and empirically analyse the impact of targeted attacks on the structural and the operational performance of power grids. We demonstrate our methodology in the high-voltage transmission networks of 5 European countries and in commonly used IEEE test power grids.
6 January 2022 in Linear Algebra and its Applications
We propose an approximation framework that unifies and generalizes a number of existing mean-field approximation methods for the susceptible-infected-susceptible (SIS) epidemic model on complex networks. We derive the framework, which we call the unified mean-field framework (UMFF), as a set of approximations of the exact Markovian SIS equations. Our main novelty is that we describe the mean-field approximations from the perspective of the isoperimetric problem, which results in bounds on the UMFF approximation error. These new bounds provide insight in the accuracy of existing mean-field methods, such as the N-intertwined mean-field approximation and heterogeneous mean-field method, which are contained by UMFF. Additionally, the isoperimetric inequality relates the UMFF approximation accuracy to the regularity notions of Szemerédi's regularity lemma.