CheiRank
   HOME

TheInfoList



OR:

The CheiRank is an
eigenvector In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...
with a maximal real eigenvalue of the
Google matrix A Google matrix is a particular stochastic matrix that is used by Google's PageRank algorithm. The matrix represents a graph with edges representing links between pages. The PageRank of each page can then be generated iteratively from the Google ...
G^* constructed for a directed network with the inverted directions of links. It is similar to the
PageRank PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. According ...
vector, which ranks the network nodes in average proportionally to a number of incoming links being the maximal eigenvector of the
Google matrix A Google matrix is a particular stochastic matrix that is used by Google's PageRank algorithm. The matrix represents a graph with edges representing links between pages. The PageRank of each page can then be generated iteratively from the Google ...
G with a given initial direction of links. Due to inversion of link directions the CheiRank ranks the network nodes in average proportionally to a number of outgoing links. Since each node belongs both to CheiRank and
PageRank PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. According ...
vectors the ranking of information flow on a directed network becomes
two-dimensional In mathematics, a plane is a Euclidean (flat), two-dimensional surface that extends indefinitely. A plane is the two-dimensional analogue of a point (zero dimensions), a line (one dimension) and three-dimensional space. Planes can arise as s ...
.


Definition

For a given directed network the Google matrix is constructed in the way described in the article
Google matrix A Google matrix is a particular stochastic matrix that is used by Google's PageRank algorithm. The matrix represents a graph with edges representing links between pages. The PageRank of each page can then be generated iteratively from the Google ...
. The
PageRank PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. According ...
vector is the eigenvector with the maximal real eigenvalue \lambda=1 . It was introduced in and is discussed in the article
PageRank PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. According ...
. In a similar way the CheiRank is the eigenvector with the maximal real eigenvalue of the matrix G^* built in the same way as G ''but'' using inverted direction of links in the initially given
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
. Both matrices G and G^* belong to the class of Perron–Frobenius operators and according to the
Perron–Frobenius theorem In matrix theory, the Perron–Frobenius theorem, proved by and , asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding eigenvector can be chosen to have strictly positive component ...
the CheiRank P^*_i and PageRank P_i eigenvectors have nonnegative components which can be interpreted as probabilities. Thus all N nodes i of the network can be ordered in a decreasing probability order with ranks K^*_i, K_i for CheiRank and PageRank P^*_i, P_i respectively. In average the PageRank probability P_i is proportional to the number of ingoing links with P_i \propto 1/^\beta . For the World Wide Web (WWW) network the exponent \beta =1/(\nu-1) \approx 0.9 where \nu \approx 2.1 is the exponent for ingoing links distribution. In a similar way the CheiRank probability is in average proportional to the number of outgoing links with P^*_i \propto 1/^ with \beta^* =1/(\nu^*-1) \approx 0.6 where \nu^* \approx 2.7 is the exponent for outgoing links distribution of the WWW. The CheiRank was introduced for the procedure call network of Linux Kernel software in, the term itself was used in Zhirov. While the PageRank highlights very well known and popular nodes, the CheiRank highlights very communicative nodes. Top PageRank and CheiRank nodes have certain analogy to authorities and hubs appearing in the
HITS algorithm Hyperlink-Induced Topic Search (HITS; also known as hubs and authorities) is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. The idea behind Hubs and Authorities stemmed from a particular insight into the creation of web ...
but the HITS is query dependent while the rank probabilities P_i and P^*_i classify all nodes of the network. Since each node belongs both to CheiRank and PageRank we obtain a two-dimensional ranking of network nodes. There had been early studies of PageRank in networks with inverted direction of links but the properties of two-dimensional ranking had not been analyzed in detail.


Examples

An example of nodes distribution in the plane of PageRank and CheiRank is shown in Fig.1 for the procedure call network of Linux Kernel software. The dependence of P, P^* on K, K^* for the network of hyperlink network of Wikipedia English articles is shown in Fig.2 from Zhirov. The distribution of these articles in the plane of PageRank and CheiRank is shown in Fig.3 from Zhirov. The difference between PageRank and CheiRank is clearly seen from the names of Wikipedia articles (2009) with highest rank. At the top of PageRank we have 1.United States, 2.United Kingdom, 3.France while for CheiRank we find 1.Portal:Contents/Outline of knowledge/Geography and places, 2.List of state leaders by year, 3.Portal:Contents/Index/Geography and places. Clearly PageRank selects first articles on a broadly known subject with a large number of ingoing links while CheiRank selects first highly communicative articles with many outgoing links. Since the articles are distributed in 2D they can be ranked in various ways corresponding to projection of 2D set on a line. The horizontal and vertical lines correspond to PageRank and CheiRank, 2DRank combines properties of CheiRank and PageRank as it is discussed in Zhirov. It gives top Wikipedia articles 1.India, 2.Singapore, 3.Pakistan. The 2D ranking highlights the properties of Wikipedia articles in a new rich and fruitful manner. According to the PageRank the top 100 personalities described in Wikipedia articles have in 5 main category activities: 58 (politics), 10 (religion),17 (arts), 15 (science), 0 (sport) and thus the importance of politicians is strongly overestimated. The CheiRank gives respectively 15, 1, 52, 16, 16 while for 2DRank one finds 24, 5, 62, 7, 2. Such type of 2D ranking can find useful applications for various complex directed networks including the WWW. CheiRank and PageRank naturally appear for the world trade network, or
international trade International trade is the exchange of capital, goods, and services across international borders or territories because there is a need or want of goods or services. (see: World economy) In most countries, such trade represents a significant ...
, where they and linked with export and import flows for a given country respectively. Possibilities of development of two-dimensional search engines based on PageRank and CheiRank are considered. Directed networks can be characterized by the correlator between PageRank and CheiRank vectors: in certain networks this correlator is close to zero (e.g. Linux Kernel network) while other networks have large correlator values (e.g. Wikipedia or university networks).


Simple network example

A simple example of the construction of the Google matrices G and G^* , used for determination of the related PageRank and CheiRank vectors, is given below. The directed network example with 7 nodes is shown in Fig.4. The matrix S , built with the rules described in the article
Google matrix A Google matrix is a particular stochastic matrix that is used by Google's PageRank algorithm. The matrix represents a graph with edges representing links between pages. The PageRank of each page can then be generated iteratively from the Google ...
, is shown in Fig.5; the related Google matrix is G=\alpha S + (1-\alpha)e e^/N and the PageRank vector is the right eigenvector of G with the unit eigenvalue ( G P=P). In a similar way, to determine the CheiRank eigenvector all directions of links in Fig.4 are inverted, then the matrix S^* is built, according to the same rules applied for the network with inverted link directions, as shown in Fig.6. The related Google matrix is G^*=\alpha S^* + (1-\alpha)e e^/N and the CheiRank vector is the right eigenvector of G^* with the unit eigenvalue ( G^* P^*=P^*). Here \alpha \approx 0.85 is the damping factor taken at its usual value.


See also

*
PageRank PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. According ...
,
HITS algorithm Hyperlink-Induced Topic Search (HITS; also known as hubs and authorities) is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. The idea behind Hubs and Authorities stemmed from a particular insight into the creation of web ...
,
Google matrix A Google matrix is a particular stochastic matrix that is used by Google's PageRank algorithm. The matrix represents a graph with edges representing links between pages. The PageRank of each page can then be generated iteratively from the Google ...
*
Markov chains A Markov chain or Markov process is a stochastic process, stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought ...
,
Transfer operator Transfer may refer to: Arts and media * ''Transfer'' (2010 film), a German science-fiction movie directed by Damir Lukacevic and starring Zana Marjanović * ''Transfer'' (1966 film), a short film * ''Transfer'' (journal), in management studies ...
,
Perron–Frobenius theorem In matrix theory, the Perron–Frobenius theorem, proved by and , asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding eigenvector can be chosen to have strictly positive component ...
*
Information retrieval Information retrieval (IR) in computing and information science is the process of obtaining information system resources that are relevant to an information need from a collection of those resources. Searches can be based on full-text or other co ...
*
Web search engines A search engine is a software system designed to carry out web searches. They search the World Wide Web in a systematic way for particular information specified in a textual web search query. The search results are generally presented in a ...


References

{{Reflist


External links


Two-dimensional ranking of Wikipedia articles

World trade: CheiRank versus PageRank

Towards two-dimensional search engines

Top people of Wikipedia
Link analysis