최랭크

CheiRank
PageRank 및 CheiRank 플레인에 링크가 있는 노드

CheiRank는 링크의 반전 방향을 가진 다이렉트네트워크용으로 구성된 Google G{\ {\ G 최대 실제 고유값을 갖는 고유 벡터입니다.이는 PageRank 벡터와 유사하며, 주어진 링크의 초기 방향을 가진 Google G G 최대 고유 벡터인 다수의 착신 링크에 비례하여 네트워크 노드를 랭크합니다.링크 방향이 반전되기 때문에 CheiRank는 다수의 발신 링크에 비례하여 네트워크노드를 평균 랭킹합니다.각 노드는 CheiRank와 PageRank 벡터에 모두 속하기 때문에 다이렉트네트워크상의 정보 흐름의 랭킹은 2차원이 됩니다.

정의.

그림 1. PageRank x 10 { x = \ _ { } P { } 、 CheiRank 확률 {\ Pi 、 2 Pi { y = \{ } { P _ { } { P _ { 10 } { P } } { P _ { p _ { i } } } } { p _ { p _ { i } } { i } } } } }(0. 색상은 최대는 흰색, 최소는 파란색으로 표시된 노드의 밀도를 나타냅니다. 검은색 공간에는 노드가 없습니다(체펠리안스키에서).

주어진 다이렉트 네트워크에 대해 Google 매트릭스는 Google 매트릭스 기사에 설명된 방식으로 구성됩니다.PageRank 벡터는 최대 실제 고유값 고유 벡터입니다 PageRank기사에 소개되어[1] 있습니다.마찬가지로 CheiRank는G 방식으로 작성된 G {\ G 최대 실제 고유값을 갖는 고유벡터이지만 처음에 주어진 인접 행렬에서 링크의 반전 방향을 사용합니다.G(\ G G G 모두 Perron-Frobenius 연산자의 클래스에 속하며, Perron-Frobenius 정리에 따라 및 PageRank {\ P_i 고유 컴포넌트가 없습니다.확률로 [2][3]해석됩니다.따라서 네트워크의 모든 iN CheiRank, K_}^*}, i})는 각각 , Ki }^{*})는 Pi PageRank Pi(\ P_{ii})는 K_{i}의 순서로 정렬할 수 있습니다.평균에{\displaystyle P_{나는}은 페이지 랭크 확률 P}P과 나는 1/K나는 β{\displaystyle P_{나는}\propto 1{K_{나는}}^{\beta}}은 지수 β은 월드 와이드 웹(WWW)네트워크에 있어서 .[4][5][6]=1/(ν − 1)≈ 0.9{\displaystyle \beta =1(\nu))\approx 0.9}∝ 통찰력이 링크의 수에 비례합니다.어디에.1 2.1 링크 [4][5]분배를 입력하기 위한 지수입니다.마찬가지로 CheiRank 확률은 / 6 \ 1^{*}}, 1 / beta ( - 발신 링크 수에 평균 비례합니다.\nu2. [4][5]WWW의 발신 링크 배포를 나타내는 지수입니다CheiRank는 Linux 커널 소프트웨어의 프로시저 호출 네트워크를 위해 [7]도입되었으며, 그 용어 자체는 [8]Zhirov에서 사용되었습니다.PageRank는 매우 유명하고 인기 있는 노드를 강조하지만, CheiRank는 매우 커뮤니케이션적인 노드를 강조합니다.상위 PageRank 노드와 CheiRank 노드는 HITS[9] 알고리즘에 표시되는 권한 및 허브와 어느 정도 유사하지만 HITS는 쿼리에 의존하며 순위 P_}) 네트워크의 모든 노드를 분류합니다.각 노드는 CheiRank와 PageRank에 모두 속하기 때문에 네트워크 노드의 2차원 순위를 얻을 수 있습니다.링크 방향이[10][11] 반전된 네트워크에서 PageRank에 대한 초기 연구가 있었지만 2차원 순위의 특성은 자세히 분석되지 않았다.

그림2. 대응하는 순위 K(\K) K(\ K에 대한 P(빨간색 곡선) P92 {\P^{*})의 확률 의존도는 직선으로의 법칙 의존도를 나타낸다. \0. 각각 1 / (-1 )(\ \displaystyle/ (\ -1)에 합니다(Zhirov에서).

PageRank와 CheiRank의 평면 노드 분포의 예는 Linux 커널 소프트웨어의 [7]프로시저 호출 네트워크에 대한 그림 1에 나와 있습니다.

위키 피디아 영어 기사의 Fig3. 밀도 분포 페이지 랭크와 CheiRank 지표의 비행기에;ln ⁡ K, ln ⁡ K∗<>ln⁡ N{0<, \ln\displaystyle K,\ln K^{*}<0<>(2009년)\ln N} 색과 파란 색에 있어서 최소한의 흰색 모델은 최대(영점을 위해 흑인);green/red점을 보여 준 100대 성격에서 PageRank/CheiRank., 노란 색 pluses는 Hart's Book의 100대 인물, 수 N N= (Zhirov에서)

영어 위키피디아 기사 하이퍼링크 네트워크에서의P {\ P 의존성은 지로프사의 그림 2에 나타나 있다.PageRank와 CheiRank의 평면에서의 이러한 기사의 분포는 Zhirov의 그림 3에 나타나 있다.PageRank와 CheiRank의 차이는 가장 높은 순위를 가진 위키피디아 기사(2009)의 이름에서 명확히 드러난다.PageRank 맨 위에는 1이 있습니다.미국, 2.영국, 3.프랑스는 CheiRank를 위해 우리는 1을 찾는다.포털: 지식 내용/개요/지역 및 장소, 2.연도별 국가 지도자 목록, 3포털: 목차/인덱스/지역 및 장소.분명히 PageRank는 많은 수의 링크를 가진 널리 알려진 주제에 대한 첫 번째 기사를 선택하고, CheiRank는 많은 발신 링크를 가진 첫 번째 소통성이 높은 기사를 선택합니다.기사는 2D로 배포되기 때문에 2D 세트의 투영에 따라 다양한 순위를 매길 수 있습니다.수평선과 수직선은 PageRank와 CheiRank에 대응하며, 2DRank는 Zhirov에서 설명한 [8]바와 같이 CheiRank와 PageRank의 속성을 결합합니다.그것은 위키피디아의 상위 기사 1을 제공한다.인도, 2싱가포르, 3파키스탄.

2D 순위는 위키피디아 기사의 특성을 새롭고 풍부하고 알찬 방식으로 강조합니다.페이지랭크에 따르면 위키피디아 기사에 기술된 상위 100명의 인물은 5개의 주요 카테고리 활동: 58(정치), 10(종교), 17(예술), 15(과학), 0(스포츠)으로 구성되어 있으며, 따라서 정치인의 중요성은 크게 과대평가되고 있다.CheiRank는 각각 15, 1, 52, 16, 16을 제공하며, 2DRank의 경우 24, 5, 62, 7, 2를 찾습니다.이러한 2D 등급은 WWW를 포함한 다양한 복잡한 다이렉트 네트워크에 유용한 응용 프로그램을 찾을 수 있습니다.

CheiRank와 PageRank는 [12]각각 특정 국가의 수출 및 수입 흐름과 연계된 세계 무역 네트워크 또는 국제 무역에 자연스럽게 나타납니다.

PageRank와 CheiRank를 기반으로 한 2차원 검색엔진 개발 가능성을 [13]검토한다.다이렉트 네트워크는 PageRank 벡터와 CheiRank 벡터 사이의 상관기로 특징지을 수 있습니다.특정 네트워크(Linux Kernel 네트워크 등)에서는 이 상관기가 0에 가까운 반면 다른 네트워크(Wikipedia 또는 대학 네트워크 [7][13]등)에서는 큰 상관기 값을 가집니다.

단순한 네트워크 예시

그림4. 다이렉트 네트워크의 예
그림5. 관련 S \S
그림6. 관련 S { S

다음은 관련된 PageRank 및 CheiRank 벡터의 결정에 사용되는 매트릭스G(\G) 및 G의 간단한 구성 예를 제시하겠습니다.노드가 7개인 다이렉트네트워크의 예를 그림 4에 나타냅니다.Google 매트릭스에 기술된 규칙에 따라 된 매트릭스S(\S는 그림 5와 같다. 관련 Google 매트릭스는 S+ ( ) e / \ G = \ S + (- \ ) PageRank 벡터는 단위 고유값( P { GP을 가진G {\ G 오른쪽 고유 벡터입니다.마찬가지로 그림 4의 링크의 모든 방향이 반전된 CheiRank 고유 벡터를 결정하기 위해 그림 6과 같이 반전된 링크 방향을 가진 네트워크에 적용되는 동일한 규칙에 따라 S (\ S 구축됩니다.관련 Google 매트릭스는 G S + ( - ) e / {\ G^{*}=\ S CheiRank 벡터는 단위 고유값( P \ GP^{*} 을 갖는 G {\ G 고유 벡터이다.서 α0. \ \0.85 통상적인 값으로 측정된 감쇠 계수이다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Brin S.; Page L. (1998), "The anatomy of a large-scale hypertextual Web search engine", Computer Networks and ISDN Systems, 30 (1–7): 107, doi:10.1016/S0169-7552(98)00110-X
  2. ^ Langville, Amy N.; Carl Meyer (2006). Google's PageRank and Beyond. Princeton University Press. ISBN 0-691-12202-4.
  3. ^ Austin, David (2008). "How Google Finds Your Needle in the Web's Haystack". AMS Feature Columns.
  4. ^ a b c Donato D.; Laura L.; Leonardi S.; Millozzi S. (2004), "Large scale properties of the Webgraph", European Physical Journal B, 38 (2): 239, Bibcode:2004EPJB...38..239D, doi:10.1140/epjb/e2004-00056-6, S2CID 10640375
  5. ^ a b c Pandurangan G.; Ranghavan P.; Upfal E. (2005), "Using PageRank to Characterize Web Structure", Internet Math., 3: 1, doi:10.1080/15427951.2006.10129114
  6. ^ Litvak N.; Scheinhardt W.R.W.; Volkovich Y. (2008), Probabilistic Relation between In-Degree and PageRank, Lecture Notes in Computer Science, vol. 4936, p. 72
  7. ^ a b c Chepelianskii, Alexei D. (2010). "Towards physical laws for software architecture". arXiv:1003.5455 [cs.SE].
  8. ^ a b Zhirov A.O.; Zhirov O.V.; Shepelyansky D.L. (2010), "Two-dimensional ranking of Wikipedia articles", European Physical Journal B, 77 (4): 523, arXiv:1006.4270, Bibcode:2010EPJB...77..523Z, doi:10.1140/epjb/e2010-10500-7, S2CID 18014470
  9. ^ Kleinberg, Jon (1999). "Authoritative sources in a hyperlinked environment". Journal of the ACM. 46 (5): 604–632. doi:10.1145/324133.324140. S2CID 221584113.
  10. ^ Fogaras, D. (2003), Where to start browsing the web?, Lecture Notes in Computer Science, vol. 2877, p. 65
  11. ^ Hrisitidis V.; Hwang H.; Papakonstantinou Y. (2008), "Authority-based keyword search in databases", ACM Trans. Database Syst., 33: 1, doi:10.1145/1331904.1331905, S2CID 11978441
  12. ^ Ermann L.; Shepelyansky D.L. (2011). "Google matrix of the world trade network". Acta Physica Polonica A. 120 (6A): A. arXiv:1103.5027. Bibcode:2011AcPPA.120..158E. doi:10.12693/APhysPolA.120.A-158. S2CID 18315654.
  13. ^ a b Ermann L.; Chepelianskii A.D.; Shepelyansky D.L. (2011). "Towards two-dimensional search engines". Journal of Physics A: Mathematical and Theoretical. 45 (27): 275101. arXiv:1106.6215. Bibcode:2012JPhA...45A5101E. doi:10.1088/1751-8113/45/27/275101. S2CID 14827486.

외부 링크