Barabási-Albert-Modell

Das Barabási-Albert-Modell (englisch Barabási–Albert (BA) model) beschreibt einen stochastischen Algorithmus aus dem Bereich der Graphentheorie zur Generierung ungerichteter skalenfreier Netzwerke. Das Modell wurde von Albert-László Barabási und seiner Doktorandin Réka Albert formuliert und seine wesentlichen Merkmale sind ein sukzessives Wachstum des Netzwerks, also das Hinzufügen von neuen Knoten im Laufe der Zeit, und deren Anbindung an das bestehende Netzwerk. Letzteres ist ein Zufallsprozess, der aber einer sogenannten bevorzugten Bindung (englisch preferential attachment) unterliegt. Die Auswahl der Nachbarn eines neuen Knotens wird mit höherer Wahrscheinlichkeit zugunsten von Knoten entschieden, die bereits einen hohen Grad aufweisen. In den so entstehenden Netzwerken kommen dementsprechend einige relativ bedeutende Knoten (englisch Hubs) vor, deren Grade signifikant höher sind als die der überwiegenden Mehrheit mit vergleichsweise kleinen Graden. Man spricht dann von einem skalenfreien Netzwerk, da die Gradverteilung (englisch degree distribution) einem Potenzgesetz folgt; der Charakter eines solchen Netzwerks ist demnach unabhängig von seiner Größe. Es gilt als das bekannteste Modell zur Generierung von Netzwerken.