Recently, eigenvector localization of complex network has seen a spurt in activities due to its versatile applicability in many different areas which includes networks centrality measure, spectral partitioning, development of approximation algorithms and disease spreading phenomenon. For a network, an eigenvector is said to be localized when most of its components are near to zero, with few taking very high values. Here, we develop three different randomized algorithms, which by using edge rewiring method, can evolve a random network having a delocalized principal eigenvector to a network having a highly localized principal eigenvector. We discuss drawbacks and advantages of these algorithms. Additionally, we show that the construction of such networks corresponding to the highly localized principal eigenvector is a non-convex optimization problem when the objective function is the inverse participation ratio.
It has been shown that a network with localized PEV explains disease propagation in SIS model @cite_28 and reduces perturbation propagation in mutualistic ecological networks @cite_40 . used PEV localization to analyze the brain network dynamics @cite_3 . Moreover, dynamics over the networks have been analyzed through eigenvector localization @cite_4 @cite_43 . Low order eigenvectors have also been studied to develop machine learning tools @cite_8 . They used IPR as well as another kind of measure for the eigenvector localization, called as statistical leverage scores @cite_39 which has an impact on statistics and modern big data analysis. Eigenvector localization has been applied to cryptographic applications @cite_48 , development of spectral clustering algorithm @cite_45 , and analyzing of Google matrix for better performance @cite_42 . It has been observed that sometimes eigenvector centrality @cite_24 and spectral partitioning @cite_32 method fail due to eigenvector localization. Note that eigenvector centrality and eigenvector localization are different. Recently, network properties corresponding to highly localized PEV has been investigated for single layer network and multiplex networks @cite_15 @cite_37 .
@cite_37 @cite_4 @cite_8 @cite_28 @cite_48 @cite_42 @cite_32 @cite_3 @cite_39 @cite_24 @cite_43 @cite_40 @cite_45 @cite_15
1973379861 2963806762 2017990598 2170782029 1977984059 2162403210 1714924059 2344861233 332837856 2772041599
We present a comparative study of the application of modern eigenvalue algorithms to an eigenvalue problem arising in quantum physics, namely, the computation of a few interior eigenvalues and their associated eigenvectors for the large, sparse, real, symmetric, and indefinite matrices of the Anderson model of localization. We compare the Lanczos algorithm in the 1987 implementation of Cullum and Willoughby with the implicitly restarted Arnoldi method coupled with polynomial and several shift-and-invert convergence accelerators as well as with a sparse hybrid tridiagonalization method. We demonstrate that for our problem the Lanczos implementation is faster and more memory efficient than the other approaches. This seemingly innocuous problem presents a major challenge for all modern eigenvalue algorithms. Using the SIS model on unweighted and weighted networks, we consider the disease localization phenomenon. In contrast to the well-recognized point of view that diseases infect a finite fraction of vertices right above the epidemic threshold, we show that diseases can be localized on a finite number of vertices, where hubs and edges with large weights are centers of localization. Our results follow from the analysis of standard models of networks and empirical data for real-world networks. Spectral methods, ranging from traditional Principal Components Analysis to modern Laplacian matrix factorization, have proven to be a valuable tool for a wide range of diverse data mining applications. Commonly these methods are stated as optimization problems and employ the extremal (maximal or minimal) eigenvectors of a certain input matrix for deriving the appropriate statistical inferences. Interestingly, recent studies have questioned this "modus operandi" and revealed that useful information may also be present within low-order eigenvectors whose mass is concentrated (localized) in a small part of their indexes. An application context where localized low-order eigenvectors have been successfully employed is "Differential Power Analysis" (DPA). DPA is a well studied side-channel attack on cryptographic hardware devices (such as smart cards) that employs statistical analysis of the device's power consumption in order to retrieve the secret key of the cryptographic algorithm. In this work we propose a data mining (clustering) formulation of the DPA process and also provide a theoretical model that justifies and explains the utility of low-order eigenvectors. In our data mining formulation, we consider that the key-relevant information is modelled as a "low-signal" pattern that is embedded in a "high-noise" dataset. In this respect our results generalize beyond DPA and are applicable to analogous low-signal, hidden pattern problems. The experimental results using power trace measurements from a programmable smart card, verify our approach empirically. We study the properties of eigenvalues and eigenvectors of the Google matrix of the Wikipedia articles hyperlink network and other real networks. With the help of the Arnoldi method, we analyze the distribution of eigenvalues in the complex plane and show that eigenstates with significant eigenvalue modulus are located on well defined network communities. We also show that the correlator between PageRank and CheiRank vectors distinguishes different organizations of information flow on BBC and Le Monde web sites. Investigating the performance of different methods is a fundamental problem in graph partitioning. In this paper, we estimate the so-called detectability threshold for the spectral method with both unnormalized and normalized Laplacians in sparse graphs. The detectability threshold is the critical point at which the result of the spectral method is completely uncorrelated to the planted partition. We also analyze whether the localization of eigenvectors affects the partitioning performance in the detectable region. We use the replica method, which is often used in the field of spin-glass theory, and focus on the case of bisection. We show that the gap between the estimated threshold for the spectral method and the threshold obtained from Bayesian inference is considerable in sparse graphs, even without eigenvector localization. This gap closes in a dense limit. Eigenvector localization refers to the situation when most of the components of an eigenvector are zero or near-zero. This phenomenon has been observed on eigenvectors associated with extremal eigenvalues, and in many of those cases it can be meaningfully interpreted in terms of "structural heterogeneities" in the data. For example, the largest eigenvectors of adjacency matrices of large complex networks often have most of their mass localized on high-degree nodes; and the smallest eigenvectors of the Laplacians of such networks are often localized on small but meaningful community-like sets of nodes. Here, we describe localization associated with low-order eigenvectors, i.e., eigenvectors corresponding to eigenvalues that are not extremal but that are "buried" further down in the spectrum. Although we have observed it in several unrelated applications, this phenomenon of low-order eigenvector localization defies common intuitions and simple explanations, and it creates serious difficulties for the applicability of popular eigenvector-based machine learning and data analysis tools. After describing two examples where low-order eigenvector localization arises, we present a very simple model that qualitatively reproduces several of the empirically-observed results. This model suggests certain coarse structural similarities among the seemingly-unrelated applications where we have observed low-order eigenvector localization, and it may be used as a diagnostic tool to help extract insight from data graphs when such low-order eigenvector localization is present. The relationships between the core–periphery architecture of the species interaction network and the mechanisms ensuring the stability in mutualistic ecological communities are still unclear. In particular, most studies have focused their attention on asymptotic resilience or persistence, neglecting how perturbations propagate through the system. Here we develop a theoretical framework to evaluate the relationship between the architecture of the interaction networks and the impact of perturbations by studying localization, a measure describing the ability of the perturbation to propagate through the network. We show that mutualistic ecological communities are localized, and localization reduces perturbation propagation and attenuates its impact on species abundance. Localization depends on the topology of the interaction networks, and it positively correlates with the variance of the weighted degree distribution, a signature of the network topological heterogeneity. Our results provide a different perspective on the interplay between the architecture of interaction networks in mutualistic communities and their stability. This paper introduces the SpecLoc algorithm that performs clustering without pre-assigning the number of clusters. This is achieved by the use of a special property of matrix eigenvectors, called weak localization. The signless Laplacian matrix is created on the basis of a mutual neighbor graph. A new measure, introduced in this work, allows for selection of weakly localized eigenvectors. Experiments confirm good performance of the proposed algorithm for weakly separated groups of real datasets, including cancer gene expression matrices. We study localization properties of principal eigenvector (PEV) of multiplex networks. Starting with a multiplex network corresponding to a delocalized PEV, we rewire the network edges using an optimization technique such that the PEV of the rewired multiplex network becomes more localized. The framework allows us to scrutinize structural and spectral properties of the networks at various localization points during the rewiring process. We show that by rewiring only one layer of the multiplex network, we can achieve the PEV localization of the entire system. Our investigations reveal the sensitivity of the PEV to a single edge rewiring in the optimized multiplex network structure corresponding to the most localized PEV providing the deeper insight into the localization behavior of the multiplex networks. Furthermore, by constructing multiplex network using real-world social and biological data, we show that our simulation results for model multiplex network are in good agreement with the properties of these real-world multiplex network. The study is relevant to applications that require understanding of how perturbation propagates in multiplex networks.