Enhancing the spectral gap of networks by node removal

The evolving topology of the Lightning Network: Centralization, efficiency, robustness, synchronization, and anonymity

The Lightning Network (LN) was released on Bitcoin’s mainnet in January 2018 as a solution to favor scalability. This work analyses the evolution of the LN during its first year of existence in order to assess its impact over some of the core fundamentals of Bitcoin, such as: node centralization, resilience against attacks and disruptions, anonymity of users, autonomous coordination of its members. Using a network theory approach, we find that the LN represents a centralized configuration with few highly active nodes playing as hubs in that system. We show that the removal of these central nodes is likely to generate a remarkable drop in the LN’s efficiency, while the network appears robust to random disruptions. In addition, we observe that improvements in efficiency during the sample period are primarily due to the increase in the capacity installed on the channels, while nodes’ synchronization does not emerge as a distinctive feature of the LN. Finally, the analysis of the structure of the network suggests a good preservation of nodes’ identity against attackers with prior knowledge about topological characteristics of their targets, but also that LN is probably weak against attackers that are within the system.

Perturbation analysis and comparison of network synchronization methods

In many networked systems, synchronization is important and useful, and how to enhance synchronizability is an interesting problem. Based on the matrix perturbation theory, we analyze five methods of network synchronization enhancement, including the link removal, node removal, dividing hub node, pull control, and pinning control methods, and obtain explicit expressions for eigenvalue changes. By these comparisons, we find that, among all these methods, the pull control method is remarkable, as it can extend the synchronization (coupling strength) region from both the left and right sides, for any controlled node. Extensive simulation results are given to support the accuracy of the perturbation-based analysis.

Origin and implications of zero degeneracy in networks spectra

The spectra of many real world networks exhibit properties which are different from those of random networks generated using various models. One such property is the existence of a very high degeneracy at the zero eigenvalue. In this work, we provide all the possible reasons behind the occurrence of the zero degeneracy in the network spectra, namely, the complete and partial duplications, as well as their implications. The power-law degree sequence and the preferential attachment are the properties which enhances the occurrence of such duplications and hence leading to the zero degeneracy. A comparison of the zero degeneracy in protein-protein interaction networks of six different species and in their corresponding model networks indicates importance of the degree sequences and the power-law exponent for the occurrence of zero degeneracy.

Enhancing synchronizability of diffusively coupled dynamical networks: a survey

In this paper, we review the literature on enhancing synchronizability of diffusively coupled dynamical networks with identical nodes. The last decade has witnessed intensive investigations on the collective behavior over complex networks and synchronization of dynamical systems is the most common form of collective behavior. For many applications, it is desired that the synchronizability-the ability of networks in synchronizing activity of their individual dynamical units-is enhanced. There are a number of methods for improving the synchronization properties of dynamical networks through structural perturbation. In this paper, we survey such methods including adding/removing nodes and/or edges, rewiring the links, and graph weighting. These methods often try to enhance the synchronizability through minimizing the eigenratio of the Laplacian matrix of the connection graph-a synchronizability measure based on the master-stability-function formalism. We also assess the performance of the methods by numerical simulations on a number of real-world networks as well as those generated through models such as preferential attachment, Watts-Strogatz, and Erdos-Rényi.

Decreasing the spectral radius of a graph by link removals

The decrease of the spectral radius, an important characterizer of network dynamics, by removing links is investigated. The minimization of the spectral radius by removing m links is shown to be an NP-complete problem, which suggests considering heuristic strategies. Several greedy strategies are compared, and several bounds on the decrease of the spectral radius are derived. The strategy that removes that link l=i~j with largest product (x(1))(i)(x(1))(j) of the components of the eigenvector x(1) belonging to the largest adjacency eigenvalue is shown to be superior to other strategies in most cases. Furthermore, a scaling law where the decrease in spectral radius is inversely proportional to the number of nodes N in the graph is deduced. Another sublinear scaling law of the decrease in spectral radius versus the number m of removed links is conjectured.