Geiger, Bernhard C.; geiger@ieee.org

Ein Netzwerk bzw. Graph ist ein mathematisches Objekt bestehend aus zumindest zwei Mengen: einer Menge an Knoten und einer Menge an Kanten, die Relationen zwischen den Knoten darstellen. In einem einfachen Netzwerk sind die Relationen zweistellig und Kanten verlaufen zwischen zwei Knoten (eine Kante zwischen Knoten A und Knoten B bedeutet, dass A und B in einer gewissen Relation zueinander stehen). Netzwerke können gerichtet (d. h., dass eine Relation von A nach B von einer Relation von B nach A unterschieden wird; die Kanten werden dann als Pfeile dargestellt) und/oder gewichtet (d. h., dass eine Relation von A nach B eine stärkere/schwächere Ausprägung haben kann, als eine Relation von B nach C) sein. In signierten Netzwerken können die Relationen negative Gewichte annehmen.

Ein bipartites Netzwerk besteht aus zwei Typen von Knoten, wobei innerhalb jedes Typs von Knoten keine Kanten bestehen. Man nehme zum Beispiel die Knotenmengen ‘Schriftsteller’ und ‘Roman’ sowie die Relation ‘ist Autor von’: In diesem Fall bestehen gerichtete Kanten nur von der Menge der Schriftsteller zur Menge der Romane. In einem multipartiten Netzwerk gibt es mehrere solcher Typen von Knoten.

Relevant ist auch der Multigraph, in dem mehrere Typen von Relationen dargestellt werden. Fügen wir zu obigem Beispiel noch die Relation ‘hat gelesen’ hinzu, dann erhalten wir einen bipartiten, gerichteten Multigraph, der darstellt, welche Schriftsteller welche Romane gelesen bzw. welche sie verfasst haben.