Die Analyse der Struktur sehr großen Netzwerke wie des Webgraphen, von Freundschaftsgraphen sozialer Netzwerke oder von Zitationsgraphen wird in vielen Wissenschaftsfeldern benötigt und stellt eine große Herausforderung für die Informatik dar. Aufgrund der Größe der Netzwerke und der Komplexität der ihr zugrunde liegenden Probleme sind heutige Algorithmen nur selten in der Lage eine Netzwerkanalyse durchzuführen. Daher versucht man, solche Netzwerke mit Hilfe von zufälligen Stichproben zu analysieren. Dabei treten zwei wesentliche Fragstellungen auf:
Ist es z.B. besser von einem zufällig gezogenen Knoten die komplette Nachbarschaft zu erkunden oder sollte man sich lieber Schritt für Schritt von einem Knoten zu einem zufälligen Nachbarknoten bewegen (Random Surfer Modell)? Je nach Problemstellung können die Antworten hier unterschiedlich ausfallen.
Was kann eine lokale Stichprobe über die globale Struktur eines Netzwerks aussagen? Unterscheidet sich beispielsweise ein Netzwerk, das lokal planar ist (das Netzwerk kann ohne Kantenkreuzungen gezeichnet werden), auch global nicht signifikant von einem planaren Netzwerk? Man könnte hier schnell vermuten, dass dies der Fall ist, aber es gibt Beispiele von Netzwerken, die lokal planar sind und sich global sehr deutlich von planaren Netzwerken unterscheiden.
Diese und ähnliche Fragen werden im Rahmen des von der Europäischen Union mit über 1.4 Millionen Euro geförderten ERC Starting Grants „Sublinear Algorithms for the Analysis of very large Graphs“ von Prof. Dr. Christian Sohler untersucht werden.