eine art der spam detection

[UweT]

Eine Methode von Google um Linkspam zu erkennen...

Spam Detection. The eigenvectors corresponding to the second eigenvalue are an artifact of certain structures in the web graph. In particular, each pair of leaf nodes in the SCC graph for the chain + corresponds to an eigenvector of C with eigenvalue 0. These leaf nodes in the SCC are those subgraphs in the web link graph which may have incoming edges, but have no edges to other components. Link spammers often generate such structures in attempts to hoard rank. Analysis of the nonprincipal eigenvectors of C may lead to strategies for combating link spam.

Quelle: The Second Eigenvalue of the Google Matrix

[Webby]

umm ja, hab jede wort verstanden

[Ice Man]

Babel Fish-Übersetzung

Auf Deutsch:

Spam Abfragung. Die Eigenvektoren, die dem zweiten Eigenwert entsprechen, sind ein Kunstprodukt bestimmter Strukturen im Netzdiagramm. Insbesondere entspricht jedes Paar Blattnullpunkte im SCC Diagramm für das Ketten + einem Eigenvektor von C mit Eigenwert 0. Diese treiben Nullpunkte im SCC sind jene Subgraphen im Netzverbindung Diagramm, das ankommende Ränder haben kann, aber haben keine Ränder zu anderen Bestandteilen Blätter. Verbindung Spammers erzeugen häufig solche Strukturen in den Versuchen, Rank zu horten. Analyse der nonprincipal Eigenvektoren von C kann zu Strategien für bekämpfendes Verbindung Spam führen

Alles Klar

Nach der übersetzung verstehe ich noch weniger

[Halli]

Jo, da war doch mal was ....

Da war doch mal was mit Eigenvektoren und so ...
Aber meine Mathe-Vorlesungen sind jetzt doch ca. 20 Jahre her ....

Also, lieber Mathe-Profis unter Euch Hobby-Seos: Erklärt uns mal, was hier wirklich gemeint ist!

[Seoxx]

Einfach ausgedrückt verstehe ich daraus, dass kleine Spammernetzwerke an Hand von der meist kleinen Netzwerkstruktur erkannt werden.

kleines Beispiel:
Gruppe A Domains mit der Anzahl x linken auf Gruppe B, C und D Domains, aber nicht mehr woanders hin. Somit ist die Netzwerkstruktur mehr als verdächtig und könnte als Spamnetzwerk ausgehebelt werden.

Gruß
Frank
P.S. Allerdings bin ich mir nicht sicher ob ich es auch richtig verstanden habe.

[UweT]

Leider ... wurde mein Post beim Serverwechsel verschluckt....deswegen hier nochmal.

Meiner Einschätzung nach, dient diese Methode, welche in die PageRank-Ermittlung einfliesst dazu, dass man kein PR-Netzwerk bilden kann, somit kein PageRank sammeln kann. Es muss immer einen "Einlauf" von PageRank in ein Netzwerk geben und bricht dieser "Einlauf" weg, verliert das Netzwerk seinen PageRank. Die Eigenvektorenmethode dient als dagegen vorzubeugen, dass man PageRank sammeln kann. Es wird also versucht zu verhindern, dass man ein Seiten Netzwerk aufzubauen kann und dann in diesem Netzwerk den einmalig eingespeisten PageRank zu *fangen*.

Beispiel:
Man besitzt ein Netzwerk mit 100 Domains auf 10 verschiedenen IPs und speisst an einer Stelle einen PR9 ein, dann breitet sich der PageRank auf das Netzwerk aus. Verliert man nun an der einen Stelle diesen PR9, könnten die sich mittlerweile mit PageRank bestückten Seiten ja selbst "tragen", d.h. man hätte so ein Netzwerk welches sich selbst trägt (vorgetäuschte Wichtigkeit) und gegen dieses Szenario wirkt die Eigenvektorenmethode.

Gruß
tbone.

[Seoxx]

welches sich selbst trägt (vorgetäuschte Wichtigkeit) und gegen dieses Szenario wirkt die Eigenvektorenmethode.

Aber das währe doch nichts Neues, oder irre ich mich da? Auch bisher ist doch ein gesamtes Netzwerk zusammengebrochen, wenn man der PR-Quelle den PR wieder entzieht, egal wieviele Domains davon profitierten, oder nicht? Nur hat man es so nie gehandabt.

Logisch währe nun eine Kombination aus meinem und deinem Post. Wird solch ein Netzwerk aufgedeckt, dann entzieht man "nun" der PR-Quelle den PR und somit wird das dahinter stehende Netzwerk ausgehebelt.

Gruß
Frank

[UweT]

Aber das währe doch nichts Neues, oder irre ich mich da? Auch bisher ist doch ein gesamtes Netzwerk zusammengebrochen, wenn man der PR-Quelle den PR wieder entzieht, egal wieviele Domains davon profitierten, oder nicht? Nur hat man es so nie gehandabt.

Neu ist das nicht aber wenn man es schafft im Laufe der Zeit seine Seite "echte" Wichtigkeit zu verschaffen, dann ist die "vorgetäuschte" Wichtigkeit ein tolles Hilfsmittel. Die vorgetäuschte Wichtigkeit ist zum einen die Chance, echte Wichtigkeit zu bekommen sowie eine Beschleunigung diese zu erreichen. (Auf ein neues Produkt bezogen)

Logisch währe nun eine Kombination aus meinem und deinem Post. Wird solch ein Netzwerk aufgedeckt, dann entzieht man "nun" der PR-Quelle den PR und somit wird das dahinter stehende Netzwerk ausgehebelt

.

Nja, der Fall das ein "Spammer" nur eine PR-Quelle besitzt ist recht selten...und wie's ausschaut vererbt leo ja auch nicht mehr volle breitseite an yalpo...

gruß
tbone.

[Seoxx]

Nja, der Fall das ein "Spammer" nur eine PR-Quelle besitzt ist recht selten...und wie's ausschaut vererbt leo ja auch nicht mehr volle breitseite an yalpo...

Jepp, genauso ist es. Vorallem gibt es natürlich überall PR-Quellen. Ist immer nur eine Frage des Geldes.

Gruß
Frank

[bugscout]

moin moin,

während das normale internet eine relative homogene linkstruktur hat, kommt es in solchen fällen zu einer auffälligen verknüpfungsansammlung von links und domains ähnlich den ausgebeulten taschen eines ladendiebes, der zuviel eingesteckt hat, da die links ja möglichst nicht wieder verplempert werden sollen.

genauso haben linktrader ein auffälliges verknüpfungsbild.

grüsse

[auer]

Die Aussagen in dem PDF-Dokument sind 'etwas andere'. Das Problem ist nicht die Theorie - die problematischen Netzstrukturen sind schon lange bekannt. Sondern das Problem liegt darin, daß die rechnerische Ermittlung solcher 'strongly connected components' (SCC, stark zusammenhängende Komponenten - siehe Grundlegende Graphenalgorithmen bislang aufwendig war - immerhin handelt es sich um einen etwa 4 Milliarden Dimensionen umfassenden Vektorraum. Die PR-Berechnung entspricht der Ermittlung des Eigenvektors zum Eigenwert 1. Der zweite Eigenwert war bislang unbekannt, zu ihm gehören jedoch Eigenvektoren, denen solche SCC entsprechen.

Der bewiesene Hauptsatz besagt, daß - unter sehr schwachen, im Web erfüllten Voraussetzungen - der 2. EW gleich c, normalerweise = 0.85, also nicht geschätzt werden muß, sondern in voraus bekannt ist.

Folgerungen:

1. Zur Berechnung des PR wird aktuell das Potenzverfahren angewandt - Matrix * Vektor, bis sich der Vektor nicht mehr ändert. Die Konvergenz (wieviele Rechenschritte - 5, 15, 100 - sind notwendig) hängt vom 2.EW ab. Damit können weitaus mehr Testrechnungen durchgeführt werden, da man für diese ein höheres c (0.95) verwenden kann und nun besser abschätzen kann, wo die Iteration abgebrochen werden darf, ohne die Relevanz der Ergebnisse zu gefährden. Zur Ermittlung kritischer Netzstrukturen genügt das.

2. Numerische Mathematik hat es immer mit Rechenungenauigkeiten zu tun. Weiß man, daß der 2.EW = c sein muß, dreht sich die Situation um - jeder Eigenvektor zu diesem Eigenwert ist kritisch - diese lassen sich weitaus schneller ermitteln, wenn man den EW kennt. Früher hat man hundertmal iteriert und wußte nichts genaues, heute kriegt man die Kandidaten schneller und weiß definitiv, daß da sehr enge Linkbeziehungen existieren.

[Edit - da war ein etwas ungenauer Teilsatz]

3. Eher belustigte Anmerkungen: (1) Eine 'single, unique Domain' hat dieses Problem nicht. (2) Damit existiert eine Grundlage, um dritte und vierte Eigenwerte näher einschränken zu können und damit weitere Linkspam-Strukturen zu identifizieren. (3) Wiederholt gibt es in Foren Hinweise, daß google neuerdings so langsam beim Spidern sei - obwohl bsp. ein Link von einer hoch bewerteten Domain gesetzt sei. Wahrscheinlich berücksichtigt google längst die PR-Quelle. (4) Linkt eine Domain nur auf sehr hochwertige Linkziele, dann ist der Weg zurück über dort ausgehende Links sehr weit - damit sind zugehörige Eigenwerte eines Teilraums ziemlich klein, also harmlos. (5) Der Beweis wurde im März 2003 veröffentlicht. Im Mai 2002 hat derselbe Verfasser das Dokument zum topic-sensitive-pagerank veröffentlicht, seit 10/2003 ist er Mitarbeiter bei google.

------------
Gruß, Jürgen Auer

[Seoxx]

Hallo Jürgen,

überaus interessant dein Post, vielen Dank.

Gruß
Frank

[auer]

Aus dem Satz, daß der zweite Eigenwert = c, also bekannt ist, ergeben sich Folgerungen für die Identifikation problematischer Linkstrukturen, die weit über den Netztyp hinausgehen, den @Seoxx oben skizziert hat.

Der Fall, daß ein gekaufter Link oder ein dmoz-Eintrag in ein geschlossenes System gelenkt wird, ist rechnerisch eher einfach, weil es sich um einen gerichteten Graphen handelt, PR fließt nur in eine Richtung. Weitaus interessanter ist der Fall von paarweise, unabhängig voneinander verabredeten Linkpartnerschaften, die schließlich zu sehr großen strongly connected components führen.

Domain A verabredet eine Partnerschaft mit Domain B, also A <-> B, ferner B <-> C <-> D <-> E. Knüpft nun E eine Partnerschaft mit A, so entsteht ein SCC, das weitaus dichter ist als ein gerichteter Graph. Die Kette kann noch mehr Domains umfassen, es können Zwischenglieder auftreten (B <-> D), da jede Domain jemandem anderen gehört, werden alle Beziehungen bloß paarweise vereinbart, niemand nimmt wahr, daß ein fast geschlossenes System entstanden ist. Solche Systeme werden noch dichter, falls Foren oder Kataloge beteiligt sind und tausendfach abgehende Links existieren. Damit sind die meisten domainexternen Links zu SCC-internen Links geworden, je mehr Domains beteiligt sind, umso höher wird der Eigenwert dieses Teilsystems.

Damit läßt sich bsp. jeder Domain ein Koeffizient zwischen 0.001 (praktisch unabhängig) und c = 0.85 (Zentrum eines SCC) zuordnen. Verwendet man etwa den Quotienten aus bisherigem PR und diesem Koeffizient, um über die Häufigkeit und Tiefe des Spiderns zu entscheiden, so verliert der PR völlig seine Bedeutung für die Vorhersage des Spiderns - ein hoher PR in Kombination mit einem hohen SCC führt zum anschließenden Austrocknen dieser Domain aufgrund eines zu seltenen Indiziert-Werdens, damit brechen auch die ganzen ausgehenden Links dieser Domain weg, das Netz löst sich von innen her auf. Ein niedriger PR und ein niedriger SCC (wenige, aber aus sehr verschiedenen Richtungen kommende Links, ausgehende Links nur auf hochwertige Ziele) kann dagegen durchaus ein häufiges Spidern produzieren. Interessanterweise tritt der austrocknende Effekt am ehesten nach einer PR-Erhöhung aufgrund eines Schubs eingehender Links auf.

Wohlgemerkt: Einerseits sind dies Spekulationen. Andererseits eröffnet das Vorliegen solcher Beweise die Möglichkeit, diese 'netten Werkzeuge' zu entwickeln, 'ausgebeulte Hosentaschen' konkret zu identifizieren und abzuwerten, da in ihnen überproportional hohe Linkdichten existieren.

---------
Gruß, Jürgen Auer

[Seoxx]

Hallo Jürgen,

ist schon klar das mein Beispiel natürlich das Thema nur angerissen hat.

Deine Ausführung erinnert mich sehr stark an ein existierendes System namens Linktrade, kann das sein?

Gruß
Frank

[auer]

Das Konzept des 'random walk' als Empfehlung für die Zielseite macht nur dann Sinn, falls das Verhältnis zwischen externen Links und Seiten im Web (weltweit) sehr niedrig ist. In diesem Fall können eingehende Links der Seite additiv zugerechnet werden - zwei Empfehlungen sind doppelt so gut wie eine Empfehlung. Dieses Prinzip wird konterkariert, falls jede Seite mit jeder Seite verlinkt ist bzw. falls es Bereiche gibt, in denen man von einer Seite / Domain über überdurchschnittlich viele 'kurze Wege' erst von der Seite / Domain weg und dann wieder zu dieser hinkommt. Der Eigenwert eines Teilsystems stellt ein Maß dar, mit dem die Menge solcher 'kurzer Wege' im Vergleich zur 'durchschnittlichen Weglänge im Web' gemessen werden kann.

Die reinen LinkTrade-Partnerschaften sind unter dieser Betrachtung noch eher harmlos, weil jede Domain von bsp. 500 Domains nur einmal auf jede andere verweist und die 'positiven Effekte' erst bei sehr vielen beteiligten Domains sichtbar werden. Haben die Domains 'ordentlich viele Seiten' (bsp. 100), so bleibt das Verhältnis von SCC-Links zur Gesamtzahl beteiligter Seiten gering. Weitaus dichtere SCC's werden produziert, wenn eine Domain A von allen 100 Unterseiten auf eine andere Domain B linkt und einen Backlink erhält. Setzt sich dies kreisförmig fort, so daß man von B zu A auch über C -> A oder über C -> D -> E -> A kommt, sind auf einzelnen Etappen weitere solcher Massenlinks gesetzt und kann man umgekehrt von A auch über E -> D -> C -> B zurückkommen, dann unterscheidet sich ein solches System von einem LinkTrade-System durch zwei Dinge: (1) Bei LinkTrade weiß einer, daß er mit 500 Partnern linkt, hier dagegen wird der Linktausch nur paarweise verabredet, der Zyklus ergibt sich erst, wenn E und A tauschen, B muß nichts davon wissen. (2) Bei jedem Massenaustausch, etwa aufgrund unterschiedlicher PR, wirkt sich die Zahl der Seiten auf der Domain aus - bei LinkTrade führt die Beteiligung großer Domains zur Abschwächung des Verhältnisses SCC-Links / Gesamtzahl der Seiten, hier führt die Beteiligung einer großen Domain gerade zum Wachstum dieses Quotienten, weil nicht pro Domain einmal, sondern von jeder Unterseite gelinkt wird.

Die Bemerkung von Caschi, daß massenhaft eingehende Links mit demselben Keyword gefiltert werden, kann auch dadurch erklärt werden, daß die beiden Domains 'zu dicht' verlinkt waren und die Links einfach abgewertet bzw. negativ berücksichtigt werden, da sie aus einem SCC stammen. Ein Vergleich der Suchergebnisse "roman empire" mit allinanchor:"roman empire" zeigt beidesmal denselben Spitzenreiter, dieser bekommt den Linktext von sehr verschiedenartigen Domains, das kann man mit link: überprüfen. Eine andere Domain ist bei allinanchor etwa auf Platz 35 und erhält viele eingehende Links von einer Domain - sie ist unter den ersten 1000 Ergebnissen nicht vorhanden, obwohl es sich um zwei Suchworte handelt.

-----------
Gruß, Jürgen Auer