Google matrix, dynamical attractors, and Ulam networks

Google matrix of the citation network of Physical Review

We study the statistical properties of spectrum and eigenstates of the Google matrix of the citation network of Physical Review for the period 1893-2009. The main fraction of complex eigenvalues with largest modulus is determined numerically by different methods based on high-precision computations with up to p = 16384 binary digits that allow us to resolve hard numerical problems for small eigenvalues. The nearly nilpotent matrix structure allows us to obtain a semianalytical computation of eigenvalues. We find that the spectrum is characterized by the fractal Weyl law with a fractal dimension d(f) ≈ 1. It is found that the majority of eigenvectors are located in a localized phase. The statistical distribution of articles in the PageRank-CheiRank plane is established providing a better understanding of information flows on the network. The concept of ImpactRank is proposed to determine an influence domain of a given article. We also discuss the properties of random matrix models of Perron-Frobenius operators.

Google matrix analysis of DNA sequences

For DNA sequences of various species we construct the Google matrix [Formula: see text] of Markov transitions between nearby words composed of several letters. The statistical distribution of matrix elements of this matrix is shown to be described by a power law with the exponent being close to those of outgoing links in such scale-free networks as the World Wide Web (WWW). At the same time the sum of ingoing matrix elements is characterized by the exponent being significantly larger than those typical for WWW networks. This results in a slow algebraic decay of the PageRank probability determined by the distribution of ingoing elements. The spectrum of [Formula: see text] is characterized by a large gap leading to a rapid relaxation process on the DNA sequence networks. We introduce the PageRank proximity correlator between different species which determines their statistical similarity from the view point of Markov chains. The properties of other eigenstates of the Google matrix are also discussed. Our results establish scale-free features of DNA sequence networks showing their similarities and distinctions with the WWW and linguistic networks.

Information discovery on electronic health records using authority flow techniques

BACKGROUND

As the use of electronic health records (EHRs) becomes more widespread, so does the need to search and provide effective information discovery within them. Querying by keyword has emerged as one of the most effective paradigms for searching. Most work in this area is based on traditional Information Retrieval (IR) techniques, where each document is compared individually against the query. We compare the effectiveness of two fundamentally different techniques for keyword search of EHRs.

METHODS

We built two ranking systems. The traditional BM25 system exploits the EHRs' content without regard to association among entities within. The Clinical ObjectRank (CO) system exploits the entities' associations in EHRs using an authority-flow algorithm to discover the most relevant entities. BM25 and CO were deployed on an EHR dataset of the cardiovascular division of Miami Children's Hospital. Using sequences of keywords as queries, sensitivity and specificity were measured by two physicians for a set of 11 queries related to congenital cardiac disease.

RESULTS

Our pilot evaluation showed that CO outperforms BM25 in terms of sensitivity (65% vs. 38%) by 71% on average, while maintaining the specificity (64% vs. 61%). The evaluation was done by two physicians.

CONCLUSIONS

Authority-flow techniques can greatly improve the detection of relevant information in EHRs and hence deserve further study.

Spectral properties of the Google matrix of the World Wide Web and other directed networks

We study numerically the spectrum and eigenstate properties of the Google matrix of various examples of directed networks such as vocabulary networks of dictionaries and university World Wide Web networks. The spectra have gapless structure in the vicinity of the maximal eigenvalue for Google damping parameter α equal to unity. The vocabulary networks have relatively homogeneous spectral density, while university networks have pronounced spectral structures which change from one university to another, reflecting specific properties of the networks. We also determine specific properties of eigenstates of the Google matrix, including the PageRank. The fidelity of the PageRank is proposed as a characterization of its stability.

Google matrix and Ulam networks of intermittency maps

We study the properties of the Google matrix of an Ulam network generated by intermittency maps. This network is created by the Ulam method which gives a matrix approximant for the Perron-Frobenius operator of dynamical map. The spectral properties of eigenvalues and eigenvectors of this matrix are analyzed. We show that the PageRank of the system is characterized by a power law decay with the exponent beta dependent on map parameters and the Google damping factor alpha . Under certain conditions the PageRank is completely delocalized so that the Google search in such a situation becomes inefficient.