Peer-to-Peer-Netzwerke: Algorithmen und Methoden

zwischendurch seine Nachbar-Liste erweitert.
    So gesehen handelt es sich in der Haufigskeitsverteilung der Ausgrade (Anzahl der Nachbarn) nicht um ein Resultat eines Algorithmus, sondern um ein soziales Phanomen. In [33, 54, 55] wurde genau these Haufigkeitsverteilung untersucht. Das Ergebnis ist in Abbildung 9.1 dargestellt. Auf den Achsen ist jeweils die Haufigkeit and der Grad logarithmisch abgetragen. Es zeigt sich ein linearer Zusammenhang zwischen den GrOBen, d.h., fur Konstanten c and k gilt:

    Lost man these Gleichung nach der Anzahl der Peers auf, so erhalt man fur C = 2°:

Pareto-Verteilungen
    Im Englischen nennt man einen solchen Zusammenhang ein Power Law. Derartige Relationen findet man auch andernorts. Die zugehorigen Wahrscheinlichkeitsvertei- lungen werden nach ihrem Entdecker Wilfried Fritz Pareto als Pareto-Verteilungen bezeichnet. Zu beachten ist, dass die obige Gleichung keine mathematisch exakte Beschreibung des Grades ist, sondern lediglich eine Formel, die die Beobachtung ganz gut annahert.

    Die diskrete Pareto-Verteilung ist fur x E {1, 2, 3, ...} definiert als

    Pareto-Verteilungen besitzen die so genannte Heavy Tail-Eigenschaft. Damit wird beschrieben, dass fur groBe Werte die Wahrscheinlichkeiten im Vergleich zu Poisson-Verteilungen oder geometrischen Verteilungen nur Behr langsam abnehmen. Im Gegensatz zu diesen sind namlich nicht alle Momente E[Xk] einer ParetoVerteilung definiert. Auch existiert der Erwartungswert einer Pareto-Verteilung nur, wenn a > 2 gilt. Die Varianz and das zweite Moment E[X2] existieren genau dann, wenn a > 3 ist and E[X k] ist genau dann definiert, wenn a > k + 1.
    Der Vollstandigkeit halber geben wir hier noch die Dichtefunktion der kontinuierlichen Pareto-Funktion an. Sie ist fur x > xo definiert als
    Abb. 9.1. Haufigkeit der Ausgrade im Gnutella-Netzwerk (Messung im Marz 2001) [54].

    Einen Graph, dessen Knotengrade Pareto-verteilt sind, bezeichnen wir im Weiteren auch kurz als Pareto-Graph. Wir werden nun sehen, welche Aussagen uber die Struktur eines Graphen sich allein durch die Pareto-Verteilung der Grade treffen lassen. Aiello, Chung and Lu untersuchen in [56] Graphen, deren Grade gemaB einer Pareto-Verteilung mit Exponent a gewahlt wurden. Diese Graphen werden durch den folgenden Zufallsprozess erzeugt. Zuerst wahlt man die Anzahl der Nachbarn in einem Pareto-verteilten Zufallsprozess mit Exponenten a. Nachdem man auf diese Weise die Anzahl der Nachbarn festgelegt hat, werden diese nun zufallig zugelost.
    Fur genugend groBe Graphen mit n Knoten lassen sich in Abhangigkeit des Exponenten a folgende Aussagen uber Pareto-Graphen treffen:
    • Ist a < 1, dann ist der resultierende Graph mit Wahrscheinlichkeit 1 - o(1) zusammenhangend.
    • Fur a > 1 sind Pareto-Graphen mit Wahrscheinlichkeit 1 - o(1) nicht zusammenhangend.
    • Fur 1 < a < 2 gibt es eine Zusammenhangskomponente der GroBe O(n).
    • Fur 2 < a < 3, 4785... gibt es eine Zusammenhangskomponente der GroBe (9 (n) and sonst nur kleinere Zusammenhangskomponenten der maximalen GroBe O(log n).
    • Fur a > 3.4785 gibt es keine groBe Zusammenhangskomponente der GroBe (9 (n).
    Der Fall a < 1 ist auf den ersten Blick irritierend, denn fur solche Koeffizienten ist der normalisierende Faktor fur beliebige GroBen von Graphen keine Konstante mehr. Man behilft sich hier, indem man einen normalisierenden Faktor in Abhangigkeit der GroBe des Graphen zulasst.
    Man kann also aus dem Grad eines Pareto-Graphen schon erstaunlich viel Struk- turinformation herauslesen. Pareto-Verteilungen sind ein Behr typisches Phanomen in sozialen Prozessen. 1897 beobachtete Pareto [57], dass die Verteilung des Wohl- stands in der Bevolkerung einer solchen Verteilung folgt. Bis heute wurde these These immer wieder mit den aktuellen Daten uberpruft. Das Ergebnis ist, dass sich zwar die Koeffizienten der Pareto-Verteilung andern, dass aber die Ergebnisse weiterhin Gultigkeit haben. (Oftmals versteht man unter der Pareto-Verteilung nur eine verball- hornte Form: 20% der Bevolkerung haben 80% des Einkommens, and 80% Prozent der Bevolkerung haben 20% des Einkommens. Diese Darstellung ubersimplifiziert jedoch Paretos Beobachtung.)
Andere Beispiele fur Pareto-Verteilungen

    Spater wurde der Begriff der Zipf-Verteilung ausgedehnt and auch fur andere Koeffizienten definiert. Der entscheidende Unterschied zwischen Zipf- and ParetoVerteilung ist, dass sich die Zipfverteilung auf den Rang and nicht den Wert bezieht, d.h., eine Folge xl < x2 <