Computer Science – Discrete Mathematics
Scientific paper
2011-09-07
Computer Science
Discrete Mathematics
21 pages, 12 figures
Scientific paper
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.
Cucuringu Mihai
Mahoney Michael W.
No associations
LandOfFree
Localization on low-order eigenvectors of data matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Localization on low-order eigenvectors of data matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Localization on low-order eigenvectors of data matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-305621