Misplaced Pages

#834165

29-514: For a given directed network the Google matrix is constructed in the way described in the article Google matrix . The PageRank vector is the eigenvector with the maximal real eigenvalue λ = 1 {\displaystyle \lambda =1} . It was introduced in and is discussed in the article PageRank . In a similar way the CheiRank is the eigenvector with the maximal real eigenvalue of

58-399: 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

87-449: A decreasing probability order with ranks K i ∗ , K i {\displaystyle K_{i}^{*},K_{i}} for CheiRank and PageRank P i ∗ , P i {\displaystyle P_{i}^{*},P_{i}} respectively. In average the PageRank probability P i {\displaystyle P_{i}}

116-730: A given PageRank value scales as N P ∝ 1 / P ν {\displaystyle N_{P}\propto 1/P^{\nu }} with the exponent ν = 1 + 1 / β ≈ 2.1 {\displaystyle \nu =1+1/\beta \approx 2.1} . The left eigenvector at λ = 1 {\displaystyle \lambda =1} has constant matrix elements. With 0 < α {\displaystyle 0<\alpha } all eigenvalues move as λ i → α λ i {\displaystyle \lambda _{i}\rightarrow \alpha \lambda _{i}} except

145-486: A graph with edges representing links between pages. The PageRank of each page can then be generated iteratively from the Google matrix using the power method . However, in order for the power method to converge, the matrix must be stochastic, irreducible and aperiodic . In order to generate the Google matrix G , we must first generate an adjacency matrix A which represents the relations between pages or nodes. Assuming there are N pages, we can fill out A by doing

174-503: A line or column, thus only about 10 N multiplications are needed to multiply a vector by matrix  G . An example of the matrix S {\displaystyle S} construction via Eq.(1) within a simple network is given in the article CheiRank . For the actual matrix, Google uses a damping factor α {\displaystyle \alpha } around 0.85. The term ( 1 − α ) {\displaystyle (1-\alpha )} gives

203-436: A rapid convergence of a random initial vector to the PageRank approximately after 50 multiplications on G {\displaystyle G} matrix. At α = 1 {\displaystyle \alpha =1} the matrix G {\displaystyle G} has generally many degenerate eigenvalues λ = 1 {\displaystyle \lambda =1} (see e.g. [6] ). Examples of

232-531: A surfer probability to jump randomly on any page. The matrix G {\displaystyle G} belongs to the class of Perron-Frobenius operators of Markov chains . The examples of Google matrix structure are shown in Fig.1 for Misplaced Pages articles hyperlink network in 2009 at small scale and in Fig.2 for University of Cambridge network in 2006 at large scale. For 0 < α < 1 {\displaystyle 0<\alpha <1} there

261-514: Is discussed in Zhirov. It gives top Misplaced Pages articles 1.India, 2.Singapore, 3.Pakistan. The 2D ranking highlights the properties of Misplaced Pages articles in a new rich and fruitful manner. According to the PageRank the top 100 personalities described in Misplaced Pages articles have in 5 main category activities: 58 (politics), 10 (religion),17 (arts), 15 (science), 0 (sport) and thus the importance of politicians

290-448: Is only one maximal eigenvalue λ = 1 {\displaystyle \lambda =1} with the corresponding right eigenvector which has non-negative elements P i {\displaystyle P_{i}} which can be viewed as stationary probability distribution. These probabilities ordered by their decreasing values give the PageRank vector P i {\displaystyle P_{i}} with

319-565: Is proportional to the number of ingoing links with P i ∝ 1 / K i β {\displaystyle P_{i}\propto 1/{K_{i}}^{\beta }} . For the World Wide Web (WWW) network the exponent β = 1 / ( ν − 1 ) ≈ 0.9 {\displaystyle \beta =1/(\nu -1)\approx 0.9} where ν ≈ 2.1 {\displaystyle \nu \approx 2.1}

SECTION 10

#1732851525835

348-612: 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 , 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

377-706: 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 ∗ ∝ 1 / K i ∗ β ∗ {\displaystyle P_{i}^{*}\propto 1/{K_{i}^{*}}^{\beta ^{*}}} with β ∗ = 1 / ( ν ∗ − 1 ) ≈ 0.6 {\displaystyle \beta ^{*}=1/(\nu ^{*}-1)\approx 0.6} where ν ∗ ≈ 2.7 {\displaystyle \nu ^{*}\approx 2.7}

406-460: 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 but

435-485: The Perron–Frobenius theorem the CheiRank P i ∗ {\displaystyle P_{i}^{*}} and PageRank P i {\displaystyle P_{i}} eigenvectors have nonnegative components which can be interpreted as probabilities. Thus all N {\displaystyle N} nodes i {\displaystyle i} of the network can be ordered in

464-487: The HITS is query dependent while the rank probabilities P i {\displaystyle P_{i}} and P i ∗ {\displaystyle 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

493-399: The PageRank K i {\displaystyle K_{i}} used by Google search to rank webpages. Usually one has for the World Wide Web that P ∝ 1 / K β {\displaystyle P\propto 1/K^{\beta }} with β ≈ 0.9 {\displaystyle \beta \approx 0.9} . The number of nodes with

522-425: The PageRank vector is the right eigenvector of G {\displaystyle G} with the unit eigenvalue ( G P = P {\displaystyle GP=P} ). In a similar way, to determine the CheiRank eigenvector all directions of links in Fig.4 are inverted, then the matrix S ∗ {\displaystyle S^{*}} is built, according to the same rules applied for

551-435: 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. Misplaced Pages or university networks). A simple example of the construction of the Google matrices G {\displaystyle G} and G ∗ {\displaystyle G^{*}} , used for determination of

580-523: The eigenvalue spectrum of the Google matrix of various directed networks is shown in Fig.3 from and Fig.4 from. The Google matrix can be also constructed for the Ulam networks generated by the Ulam method [8] for dynamical maps. The spectral properties of such matrices are discussed in [9,10,11,12,13,15]. In a number of cases the spectrum is described by the fractal Weyl law [10,12]. The Google matrix can be constructed also for other directed networks, e.g. for

609-404: The following: Then the final Google matrix G can be expressed via S as: By the construction the sum of all non-negative elements inside each matrix column is equal to unity. The numerical coefficient α {\displaystyle \alpha } is known as a damping factor. Usually S is a sparse matrix and for modern directed networks it has only about ten nonzero elements in

SECTION 20

#1732851525835

638-439: The matrix G ∗ {\displaystyle G^{*}} built in the same way as G {\displaystyle G} but using inverted direction of links in the initially given adjacency matrix . Both matrices G {\displaystyle G} and G ∗ {\displaystyle G^{*}} belong to the class of Perron–Frobenius operators and according to

667-722: The maximal eigenvalue λ = 1 {\displaystyle \lambda =1} , which remains unchanged. The PageRank vector varies with α {\displaystyle \alpha } but other eigenvectors with λ i < 1 {\displaystyle \lambda _{i}<1} remain unchanged due to their orthogonality to the constant left vector at λ = 1 {\displaystyle \lambda =1} . The gap between λ = 1 {\displaystyle \lambda =1} and other eigenvalue being 1 − α ≈ 0.15 {\displaystyle 1-\alpha \approx 0.15} gives

696-609: The network of hyperlink network of Misplaced Pages 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 Misplaced Pages 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

725-449: The network with inverted link directions, as shown in Fig.6. The related Google matrix is G ∗ = α S ∗ + ( 1 − α ) e e T / N {\displaystyle G^{*}=\alpha S^{*}+(1-\alpha )ee^{T}/N} and the CheiRank vector is the right eigenvector of G ∗ {\displaystyle G^{*}} with

754-719: The procedure call network of the Linux Kernel software introduced in [15]. In this case the spectrum of λ {\displaystyle \lambda } is described by the fractal Weyl law with the fractal dimension d ≈ 1.3 {\displaystyle d\approx 1.3} (see Fig.5 from ). Numerical analysis shows that the eigenstates of matrix G {\displaystyle G} are localized (see Fig.6 from ). Arnoldi iteration method allows to compute many eigenvalues and eigenvectors for matrices of rather large size [13]. Other examples of G {\displaystyle G} matrix include

783-415: The properties of two-dimensional ranking had not been analyzed in detail. 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 ∗ {\displaystyle P,P^{*}} on K , K ∗ {\displaystyle K,K^{*}} for

812-473: The related PageRank and CheiRank vectors, is given below. The directed network example with 7 nodes is shown in Fig.4. The matrix S {\displaystyle S} , built with the rules described in the article Google matrix , is shown in Fig.5; the related Google matrix is G = α S + ( 1 − α ) e e T / N {\displaystyle G=\alpha S+(1-\alpha )ee^{T}/N} and

841-458: The unit eigenvalue ( G ∗ P ∗ = P ∗ {\displaystyle G^{*}P^{*}=P^{*}} ). Here α ≈ 0.85 {\displaystyle \alpha \approx 0.85} is the damping factor taken at its usual value. Google matrix A Google matrix is a particular stochastic matrix that is used by Google 's PageRank algorithm. The matrix represents

#834165