CheiRank

Knoten mit Links im Flugzeug von PageRank und Cheirank

Das Cheirank ist ein Eigenvektor mit einem maximalen realen Eigenwert der Google Matrix ${\ displayStyle g^{*}}$ Konstruiert für ein gerichtetes Netzwerk mit den umgekehrten Richtungen von Links. Es ähnelt dem Seitenrang Vektor, der die Netzwerkknoten im Durchschnitt proportional zu einer Reihe eingehender Verbindungen rangiert, die der maximale Eigenvektor der sind Google Matrix ${\ displayStyle g}$ mit einer bestimmten anfänglichen Richtung von Links. Aufgrund der Inversion der Link -Richtungen rangiert die Cheirank die Netzwerkknoten im Durchschnitt proportional zu einer Reihe von ausgehenden Links ein. Da gehört jeder Knoten beides zu Cheirank und Seitenrang Vektoren Das Ranking des Informationsflusses in einem gerichteten Netzwerk wird zweidimensional.

Definition

Abb. 1. Verteilung von Verfahrensaufrufen des Linux -Kernel -Netzwerks in der Ebene der PageRank -Wahrscheinlichkeit

{\ displayStyle x = \ log _ {10} p_ {i}}

und Cheirankwahrscheinlichkeit

{\ displayStyle y = \ log _ {10} {p} _ {i}^{*}}

Für Linux Version 2.6.32 mit Matrixgröße

{\ displayStyle n = 285509}

bei

{\ displayStyle \ alpha = 0,85}

Die Farbe zeigt die Dichte der Knoten mit Weiß für maximal und blau zum Minimum, schwarzer Raum hat keine Knoten (von Chepelianskii)

Für ein bestimmtes gerichtetes Netzwerk wird die Google -Matrix in der Art und Weise konstruiert, die im Artikel beschrieben wird Google Matrix. Das Seitenrang Vektor ist der Eigenvektor mit dem maximalen realen Eigenwert ${\ displayStyle \ lambda = 1}$ . Es wurde in eingeführt^[1] und wird im Artikel erörtert Seitenrang. In ähnlicher Weise ist die Cheirank der Eigenvektor mit dem maximalen realen Eigenwert der Matrix ${\ displayStyle g^{*}}$ auf die gleiche Weise eingebaut wie ${\ displayStyle g}$ aber Verwenden der invertierten Richtungen von Links in der anfangs gegebenen Adjazenzmatrix. Beide Matrizen ${\ displayStyle g}$ und ${\ displayStyle g^{*}}$ gehören zur Klasse der Operatoren von Perron -Frobenius und gemäß den Perron -Frobenius -Theorem die Cheirank ${\ displayStyle p_ {i}^{*}}$ und PageRank ${\ displayStyle p_ {i}}$ Eigenvektoren haben nichtnegative Komponenten, die als Wahrscheinlichkeiten interpretiert werden können.^[2]^[3] So alle ${\ displayStyle n}$ Knoten ${\ displayStyle i}$ des Netzwerks kann in einer abnehmenden Wahrscheinlichkeitsreihenfolge mit Rängen bestellt werden ${\ displayStyle k_ {i}^{*}, k_ {i}}$ für Cheirank und PageRank ${\ displayStyle p_ {i}^{*}, p_ {i}}$ beziehungsweise. Im Durchschnitt die PageRank -Wahrscheinlichkeit ${\ displayStyle p_ {i}}$ ist proportional zur Anzahl der Ingoing -Verbindungen mit ${\ displayStyle p_ {i} \ drant 1/{k_ {i}}^{\ beta}}$ .^[4]^[5]^[6] Für das World Wide Web (WWW) -Netzwerk der Exponent ${\ displayStyle \ Beta = 1/(\ nu -1) \ ca. 0,9}$ wo ${\ displayStyle \ nu \ ca. 2.1}$ ist der Exponent für die Verteilung von Links.^[4]^[5] In ähnlicher Weise ist die Cheirank -Wahrscheinlichkeit im Durchschnitt proportional zur Anzahl der ausgehenden Verbindungen mit $oder$ mit ${\ displayStyle \ Beta ^{*} = 1/(\ nu ^{*}-1) \ ca. 0,6}$ wo ${\ displayStyle \ nu ^{*} \ ca. 2.7}$ ist der Exponent für die Verteilung der ausgehenden Links des WWW.^[4]^[5] Die Cheirank wurde für das Verfahrensnetz von Linux -Kernel -Software in, eingeführt, in,^[7] Der Begriff selbst wurde in Zhirov verwendet.^[8] Während die PageRank sehr bekannte und beliebte Knoten hervorhebt, hebt der Cheirank sehr kommunikative Knoten hervor. Top -PageRank- und Cheirank -Knoten haben eine gewisse Analogie zu Behörden und Hubs, die in der angezeigt werden Hits Algorithmus^[9] Aber die Hits sind abhängig, während die Rangwahrscheinlichkeiten abhängig sind ${\ displayStyle p_ {i}}$ und ${\ displayStyle p_ {i}^{*}}$ Klassifizieren Sie alle Knoten des Netzwerks. Da jeder Knoten sowohl zu Cheirank als auch zu PageRank gehört, erhalten wir eine zweidimensionale Rangfolge von Netzwerkknoten. In Netzwerken mit umgekehrter Linksdirektion gab es frühzeitige Studien zu PageRanks^[10]^[11] Die Eigenschaften einer zweidimensionalen Rangliste waren jedoch nicht im Detail analysiert worden.

Abb. 2. Abhängigkeit der Wahrscheinlichkeit von PageRank

{\ displayStyle p}

(rote Kurve) und Cheirank

{\ displayStyle p^{*}}

(blaue Kurve) auf den entsprechenden Rangindizes

{\ displayStyle K}

und

{\ displayStyle k^{*}}

. Die geraden gestrichelten Linien zeigen die Abhängigkeit der Machtgesetz von der Steigung

{\ displayStyle \ Beta = 0,92; 0,57}

entsprechend entspricht

{\ displayStyle \ Beta = 1/(\ nu -1)}

(aus Zhirov)

Beispiele

Ein Beispiel für die Verteilung der Knoten in der Ebene von PageRank und Cheirank ist in Abb.1 für das Verfahrensaufrufnetzwerk der Linux -Kernel -Software dargestellt.^[7]

Abb. 3. Dichteverteilung der englischen Artikel von Wikipedia (2009) in der Ebene der PageRank- und Cheirank -Indizes

{\ displayStyle 0 <\ ln k, \ ln k^{*} <\ ln n}

durch Farbe mit blau für minimal und weiß für maximal (schwarz für Null); Green/Red Points zeigen die Top 100 Persönlichkeiten von PageRank/Cheirank, Yellow Pluses zeigen die Top 100 Persönlichkeiten aus Harts Buch, Anzahl der Artikel

{\ displayStyle n = 3282257}

(aus Zhirov)

Die Abhängigkeit von ${\ displayStyle p, p^{*}}$ an ${\ displayStyle k, k^{*}}$ Für das Netzwerk des Hyperlink -Netzwerks von englischen Artikeln von Wikipedia ist in Fig. 2 von Zhirov gezeigt. Die Verteilung dieser Artikel in der Ebene von PageRank und Cheirank ist in Abb.3 von Zhirov dargestellt. Der Unterschied zwischen Pagerank und Cheirank ist deutlich aus den Namen von Wikipedia -Artikeln (2009) mit dem höchsten Rang zu sehen. An der Spitze des PageRanks haben wir 1.Nitierte Staaten, 2. Eingeführtes Königreich, 3.France, während für Cheirank wir 1.portal finden: Inhalt/Umriss des Wissens/Geographie und Orte, 2. Liste der Staats- und Regierungschefs bis zum Jahr, 3. Portal: Inhalt/Index/Geographie und Orte. Offensichtlich wählt PageRank erste Artikel zu einem allgemein bekannten Thema mit einer großen Anzahl von Ingoing -Links aus, während Cheirank erste hochkommunikative Artikel mit vielen ausgehenden Links auswählt. Da die Artikel in 2D verteilt sind, können sie auf verschiedene Weise eingestuft werden, die der Projektion von 2D -Set auf einer Zeile entsprechen. Die horizontalen und vertikalen Linien entsprechen PageRank und Cheirank.^[8] Es gibt Top -Wikipedia -Artikel 1.indien, 2.Singapore, 3.pakistan.

Das 2D -Ranking unterstreicht die Eigenschaften von Wikipedia -Artikeln auf neue und fruchtbare Weise. Nach Angaben der PageRank haben die in Wikipedia -Artikel beschriebenen Top -100 -Persönlichkeiten in 5 Hauptkategorienaktivitäten: 58 (Politik), 10 (Religion), 17 (Kunst), 15 (Wissenschaft), 0 (Sport) und damit die Bedeutung von Politikern ist stark überschätzt. Die Cheirank gibt jeweils 15, 1, 52, 16, 16, während für 2drang eine 24, 5, 62, 7, 2 findet. Ein solcher 2D -Ranking kann nützliche Anwendungen für verschiedene komplex gerichtete Netzwerke finden, einschließlich des WWW.

Cheirank und PageRank erscheinen natürlich für das World Trade Network, oder internationaler Handel, wo sie und mit Export- und Importströmen für ein bestimmtes Land verbunden sind.^[12]

Die Möglichkeiten der Entwicklung von zweidimensionalen Suchmaschinen auf der Grundlage von PageRank und Cheirank werden berücksichtigt.^[13] Geführte Netzwerke können durch den Korrelator zwischen PageRank- und Cheirank -Vektoren charakterisiert werden: In bestimmten Netzwerken liegt dieser Korrelator nahe Null (z. B. Linux -Kernel -Netzwerk), während andere Netzwerke große Korrelatorwerte (z. B. Wikipedia- oder Universitätsnetzwerke) aufweisen.^[7]^[13]

Einfaches Netzwerkbeispiel

Abb4. Beispiel eines gerichteten Netzwerks

Abb .5. Verwandte Matrix

{\ displayStyle S}

Abb. 6. Verwandte Matrix

{\ displayStyle S^{*}}

Ein einfaches Beispiel für die Konstruktion der Google -Matrizen ${\ displayStyle g}$ und ${\ displayStyle g^{*}}$ Die für die Bestimmung der verwandte PageRank- und Cheirank -Vektoren wird unten angegeben. Das angegebene Netzwerkbeispiel mit 7 Knoten ist in Abb.4 dargestellt. Die Matrix ${\ displayStyle S}$ , gebaut mit den in dem Artikel beschriebenen Regeln Google Matrix, ist in Abb.5 gezeigt; Die zugehörige Google -Matrix ist ${\ displayStyle g = \ alpha s+(1- \ alpha) ee^{t}/n}$ und der PageRank -Vektor ist der richtige Eigenvektor von ${\ displayStyle g}$ mit dem Einheits -Eigenwert ( ${\ displayStyle gp = p}$ ). In ähnlicher Weise sind alle Richtungen von Links in Abb.4 umgekehrt, dann die Matrix, um den Cheirank -Eigenvektor zu bestimmen ${\ displayStyle S^{*}}$ wird gemäß den gleichen Regeln für das Netzwerk mit invertierten Verbindungsrichtungen erstellt, wie in Abb.6 gezeigt. Die zugehörige Google -Matrix ist ${\ displaystyle g^{*} = \ alpha s^{*}+(1- \ alpha) ee^{t}/n}$ und der Cheirank -Vektor ist der richtige Eigenvektor von ${\ displayStyle g^{*}}$ mit dem Einheits -Eigenwert ( ${\ displaystyle g^{*} p^{*} = p^{*}}$ ). Hier ${\ displaystyle \ alpha \ ca. 0,85}$ ist der Dämpfungsfaktor, der zu seinem üblichen Wert genommen wird.

Siehe auch

Verweise

^ Brin S.; Seite L. (1998), "Die Anatomie einer groß angelegten hypertextuellen Web-Suchmaschine", Computernetzwerke und ISDN -Systeme, 30 (1–7): 107, doi:10.1016/s0169-7552 (98) 00110-x
^ Langville, Amy N.; Carl Meyer (2006). Googles PageRank und darüber hinaus. Princeton University Press. ISBN 0-691-12202-4.
^ Austin, David (2008). "Wie Google Ihre Nadel im Heuhaufen des Webs findet". AMS -Feature -Spalten.
^ ^a ^b ^c Donato d.; Laura L.; Leonardi S.; Millozzi S. (2004), "Große Eigenschaften des Webgraphen", Europäisches physisches Journal B, 38 (2): 239, Bibcode:2004EPJB ... 38..239d, doi:10.1140/EPJB/E2004-00056-6, S2CID 10640375
^ ^a ^b ^c Pandurangan G.; Ranghavan P.; UPFAL E. (2005), "Verwenden Sie PageRank, um die Webstruktur zu charakterisieren", Internet -Mathematik., 3: 1, doi:10.1080/15427951.2006.10129114
^ Litvak n.; Scheinhardt W. R. W.; Volkovich Y. (2008), Probabilistische Beziehung zwischen In-Grad und PageRank, Vorlesungsnotizen in Informatik, Vol. 4936, p. 72
^ ^a ^b ^c Chepelianskii, Alexei D. (2010). "Auf dem Weg zu physischen Gesetzen für Softwarearchitektur". Arxiv:1003,5455 [cs.se].
^ ^a ^b Zhirov A.O.; Zhirov O.V.; Shepelyansky D.L. (2010), "Zweidimensionales Ranking von Wikipedia-Artikeln", Europäisches physisches Journal B, 77 (4): 523, Arxiv:1006.4270, Bibcode:2010epjb ... 77..523z, doi:10.1140/EPJB/E2010-10500-7, S2CID 18014470
^ Kleinberg, Jon (1999). "Autoritative Quellen in einer hyperlinkten Umgebung". Journal of the ACM. 46 (5): 604–632. doi:10.1145/324133.324140. S2CID 221584113.
^ Fogaras, D. (2003), Wo kann man im Internet stöbern?, Vorlesungsnotizen in Informatik, Vol. 2877, p. 65
^ Hrisitidis v.; Hwang H.; Papakonstantinou Y. (2008), "Autoritätsbasierte Keywordsuche in Datenbanken", ACM trans. Datenbanksystem., 33: 1, doi:10.1145/1331904.1331905, S2CID 11978441
^ Ermann L.; Shepelyansky D.L. (2011). "Google -Matrix des Welthandelsnetzwerks". Acta Physica Polonica a. 120 (6a): A. Arxiv:1103.5027. Bibcode:2011ACPPA.120..158e. doi:10.12693/aphyspola.120.A-158. S2CID 18315654.
^ ^a ^b Ermann L.; Chepelianskii A.D.; Shepelyansky D.L. (2011). "In Richtung zweidimensionaler Suchmaschinen". Journal of Physics A: Mathematisch und theoretisch. 45 (27): 275101. Arxiv:1106.6215. Bibcode:2012JPHA ... 45A5101E. doi:10.1088/1751-8113/45/27/275101. S2CID 14827486.

Externe Links

[1] Brin S.; Seite L. (1998), "Die Anatomie einer groß angelegten hypertextuellen Web-Suchmaschine", Computernetzwerke und ISDN -Systeme, 30 (1–7): 107, doi:10.1016/s0169-7552 (98) 00110-x

[2] Langville, Amy N.; Carl Meyer (2006). Googles PageRank und darüber hinaus. Princeton University Press. ISBN 0-691-12202-4.

[3] Austin, David (2008). "Wie Google Ihre Nadel im Heuhaufen des Webs findet". AMS -Feature -Spalten.

[Donato-4] Donato d.; Laura L.; Leonardi S.; Millozzi S. (2004), "Große Eigenschaften des Webgraphen", Europäisches physisches Journal B, 38 (2): 239, Bibcode:2004EPJB ... 38..239d, doi:10.1140/EPJB/E2004-00056-6, S2CID 10640375

[Pandurangan-5] Pandurangan G.; Ranghavan P.; UPFAL E. (2005), "Verwenden Sie PageRank, um die Webstruktur zu charakterisieren", Internet -Mathematik., 3: 1, doi:10.1080/15427951.2006.10129114

[6] Litvak n.; Scheinhardt W. R. W.; Volkovich Y. (2008), Probabilistische Beziehung zwischen In-Grad und PageRank, Vorlesungsnotizen in Informatik, Vol. 4936, p. 72

[Chepelianskii-7] Chepelianskii, Alexei D. (2010). "Auf dem Weg zu physischen Gesetzen für Softwarearchitektur". Arxiv:1003,5455 [cs.se].

[Zhirov-8] Zhirov A.O.; Zhirov O.V.; Shepelyansky D.L. (2010), "Zweidimensionales Ranking von Wikipedia-Artikeln", Europäisches physisches 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). "Autoritative Quellen in einer hyperlinkten Umgebung". Journal of the ACM. 46 (5): 604–632. doi:10.1145/324133.324140. S2CID 221584113.

[10] Fogaras, D. (2003), Wo kann man im Internet stöbern?, Vorlesungsnotizen in Informatik, Vol. 2877, p. 65

[11] Hrisitidis v.; Hwang H.; Papakonstantinou Y. (2008), "Autoritätsbasierte Keywordsuche in Datenbanken", ACM trans. Datenbanksystem., 33: 1, doi:10.1145/1331904.1331905, S2CID 11978441

[12] Ermann L.; Shepelyansky D.L. (2011). "Google -Matrix des Welthandelsnetzwerks". Acta Physica Polonica a. 120 (6a): A. Arxiv:1103.5027. Bibcode:2011ACPPA.120..158e. doi:10.12693/aphyspola.120.A-158. S2CID 18315654.

[Ermann-13] Ermann L.; Chepelianskii A.D.; Shepelyansky D.L. (2011). "In Richtung zweidimensionaler Suchmaschinen". Journal of Physics A: Mathematisch und theoretisch. 45 (27): 275101. Arxiv:1106.6215. Bibcode:2012JPHA ... 45A5101E. doi:10.1088/1751-8113/45/27/275101. S2CID 14827486.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]