Die Einflussmaximierung verständlich erklärt

Eine Nachricht soll über Bekannte möglichst viele Menschen erreichen, aber Sie können nur wenige selbst anrufen. Wen rufen Sie an? Diese Seite zeigt, warum ab dem zweiten Anruf zählt, wer etwas Neues bringt.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Wen rufen Sie zuerst an?

Stellen Sie sich vor, Ihre Straße wird am Wochenende gesperrt. Die Nachricht soll möglichst viele Haushalte erreichen. Sie haben aber nur Zeit, drei Haushalte selbst anzurufen.

Jeder Angerufene erzählt es weiter, aber nicht sicher. Mancher vergisst es, mancher hat keine Zeit. Wir nehmen an: Wer es weiß, erzählt es jedem seiner Bekannten mit derselben Wahrscheinlichkeit, und nur ein einziges Mal. So läuft die Nachricht von Bekanntem zu Bekanntem durch das Netz der Bekanntschaften.

Weil der Zufall mitspielt, zählt der Durchschnitt: Wie viele wissen am Ende Bescheid, wenn man das Weitererzählen immer wieder durchspielt? Die Frage, wen man dafür zuerst anruft, heißt Einflussmaximierung.

Vier Wege, die Anrufer zu wählen

Zwei Regeln versteht jeder sofort. Die dritte braucht einen Gedanken mehr, die vierte einen Computer:

• Die mit den meisten Bekannten (Fachwort: Gradregel). Wer viele kennt, kann vielen etwas erzählen.
• Die Person mittendrin (Fachwort: Nähe). Gewählt wird, wer im Schnitt die wenigsten Zwischenstationen bis zu allen anderen braucht. Von dort kommt die Nachricht überall schnell hin.
• Die Abwertungsregel (Fachwort: Degree Discount). Sie wählt wie die erste Regel, rechnet aber nach jeder Wahl um: Die Bekannten der schon Gewählten zählen nun weniger. Sie erfahren die Nachricht von den Gewählten wahrscheinlich ohnehin, rufen Sie sie also nicht extra an.
• Eins nach dem anderen, mit Rechnen (Fachwort: Greedy). Der Computer spielt das Weitererzählen immer wieder durch. Zuerst nimmt er, wer allein am meisten erreicht. Danach fragt er bei jeder Wahl: Wer erreicht zusätzlich am meisten, wenn die schon Gewählten feststehen?

Warum ab dem zweiten Anruf das Neue zählt

Stellen Sie sich zwei Flugblatt-Verteiler vor. Stehen beide in derselben Fußgängerzone, bekommen viele Passanten das Blatt zwei Mal. Der zweite Verteiler bringt dann wenig Neues.

Bei den Anrufen ist es ebenso. Wer die Bekanntesten der Reihe nach anruft, kann Menschen aus demselben Freundeskreis erwischen. Ihre Reichweiten überlappen. Ab dem zweiten Anruf zählt deshalb nur noch, wer etwas Neues bringt.

Die Person mittendrin war bei einem einzigen Anruf in sechs von sieben Netzarten so gut wie Greedy, denn von ihr aus ist jeder schnell erreicht. Bei mehreren Anrufen liegen aber die Zweit- und Drittmittendrinnen gleich neben der ersten. Die Regel wählt dann Nachbarn, und deren Reichweiten überlappen.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser. Der erste Knopf unten öffnet es, der zweite führt zum zweiten Teil. Zum Verstehen brauchen Sie es nicht.

Es rechnet mit erfundenen Netzen von Betrieben und damit an einem vereinfachten Rechenbild (Fachwort: Modell). Die Aussagen in diesem Teil beschreiben diese Netze, nicht die Wirklichkeit.

Zwei Regler stellen ein, wie viele Betriebe angerufen werden und wie stark sich die Nachricht ausbreitet. „Stark“ heißt: Ein einzelner Anruf erreicht im Mittel einen größeren Teil der Betriebe. Hier steht schwach für 3 % und stark für 15 % der Betriebe. Es gibt sieben Netzarten. Zwei davon brauchen wir genauer:

• Zufallsnetz: Jeder Betrieb kennt ein paar zufällig gewählte andere.
• Gitter: Die Betriebe liegen wie die Felder eines Schachbretts, jeder kennt die Betriebe auf den angrenzenden Feldern.

Die übrigen fünf sind Mischformen: ein Ring mit Abkürzungen (jeder kennt seine Nachbarn im Kreis, dazu einzelne Abkürzungen), Verbünde (dichte Gruppen mit wenigen Verbindungen dazwischen) und drei Netze, in denen wenige Betriebe sehr viele Bekannte haben und die meisten nur wenige.

Was das Rechenbild zeigt

Die Person mittendrin war im Gitter bei einem einzigen Anruf so gut wie Greedy. Bei schwacher Ausbreitung und zwanzig Anrufen erreichte ihre Gruppe dort weniger als die Hälfte von dem, was Greedy erreichte. Der Grund steht oben: Die Gewählten sitzen nebeneinander.

Die Regel „meiste Bekannte“ fiel bei zehn Anrufen ebenfalls zurück, aber nicht überall gleich. Im Zufallsnetz lag sie nur um einige Hundertstel hinter Greedy, im Gitter etwa ein Zehntel. Eine Deutung dieser Seite, nicht gemessen: Im Zufallsnetz gibt es kaum enge Gruppen, in denen sich Bekanntenkreise überlappen. Im Gitter haben fast alle gleich viele Bekannte, die Regel wählt also nahezu beliebig und deckt manche Gegenden gleich zwei Mal ab.

Die Abwertungsregel kam bei schwacher Ausbreitung in fünf von sieben Netzarten auf das Niveau von Greedy. Das passt zu ihrem Gedanken: Wer schon versorgt ist, zählt weniger. Im Gitter und im Ring mit Abkürzungen erreichte sie weniger als Greedy.

Gerechnet wurde auch an einem echten Netz: den Verlinkungen einer Website mit 50 Seiten und 300 Programmen zum Ausprobieren. Greedy wählte als Erstes die Startseite, die mit fast allen anderen verlinkt ist. Als Zweites wählte es eine Fehlerseite, auf die keine andere Seite verweist. Das wirkt seltsam. Der Grund: Die Fehlerseite bringt sicher einen Betrieb dazu, nämlich sich selbst. Jeder andere bringt nach der Startseite im Schnitt weniger als einen.

Häufige Missverständnisse

• „Der Computer findet die eine beste Gruppe.“ Nein. Wurde Greedy acht Mal mit frisch ausgewürfelten Weitergaben wiederholt, kamen acht verschiedene Gruppen heraus. Ihre Reichweiten unterschieden sich nur um wenige Betriebe, bei insgesamt 250 Betrieben (Zufallsnetz, zehn Anrufe). In 80 Versuchen mit winzigen Netzen aus sieben bis neun Betrieben konnte man alle Gruppen durchprobieren. Greedy traf die beste Gruppe nur 29 Mal. Seine Gruppe erreichte aber mindestens neun Zehntel von deren Reichweite. Es gibt eben viele fast gleich gute Gruppen.
• „Wer die meisten Bekannten hat, erreicht auch die meisten.“ Nicht immer. Stellen Sie sich jemanden mit sehr vielen Bekannten vor, die sonst niemanden kennen. Ruft man ihn an, erfahren alle seine Bekannten davon, doch dort endet die Nachricht. Im Rechenbild gab es so ein Netz. Bei einem einzigen Anruf und starker Ausbreitung erreichte die Regel dort weniger als die Hälfte von Greedy.

Woran Sie das im Alltag erkennen

Anzeichen, wenn Sie etwas über Bekannte verbreiten wollen:

• Sie können nur wenige Menschen direkt ansprechen, etwa bei einer Einladung, einem Spendenaufruf oder einer Warnung.
• Ihre ersten Kandidaten kennen einander. Dann hören viele dieselbe Nachricht gleich zwei Mal, und andere gar nicht.

Wie ernst ist das Rechenbild zu nehmen?

Die Netze sind erzeugt. Jede Bekanntschaft gibt mit derselben Wahrscheinlichkeit weiter, und jeder Anruf kostet gleich viel. Echte Gruppen sind ungleicher, die Aussagen gelten nur für diese Rechenbilder.

Was Sie mitnehmen:

• Fragen Sie vor jedem weiteren Anruf, ob die Person im Kreis einer schon Gewählten steht.
• Ob sich eine genauere Rechnung lohnt, hängt davon ab, wie die Bekanntschaften verteilt sind.
• Erreichen mehrere Gruppen fast gleich viel, darf man die nehmen, die sich am leichtesten anrufen lässt.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt das Ausbreitungsmodell, die Auswahlverfahren und die Messreihen der Demo: Greedy mit Beschleunigung CELF, auf Schnappschüssen gerechnet, gegen einfache Auswahlregeln.

• Ausbreitung: ungerichtetes Netz, \(k\) Starter, Independent Cascade. Jeder Informierte gibt die Nachricht jedem Partner mit derselben Wahrscheinlichkeit \(p\) weiter, jede Kante bekommt genau eine Chance. Das ist gleichbedeutend mit Erreichbarkeit im Zufallsnetz \(G_p\), in dem jede Kante unabhängig mit Wahrscheinlichkeit \(p\) bleibt (Schnappschuss). Der erwartete Spread einer Startmenge \(S\) ist die mittlere Größe der Vereinigung der Zusammenhangskomponenten ihrer Knoten.
• Ausbreitungsstärke: Statt \(p\) wird der Anteil der Knoten eingestellt, den ein zufälliger einzelner Starter im Mittel erreicht; \(p\) wird per Bisektion berechnet. Gemessen wurde bei 3 %, 10 % und 15 %.
• Schätzung: Greedy rechnet auf 300 festen Trainings-Schnappschüssen, jede Auswahl wird auf 600 davon unabhängigen bewertet. Greedy ist auf den Trainings-Schnappschüssen optimiert, Verhältnisse knapp über 1 sind deshalb Schätzrauschen. Der Standardfehler liegt bei etwa ein bis zwei Knoten.
• Netze: sieben erzeugte Typen mit \(n\) Knoten (live bis 250; beim Gitter auf ein Quadrat gerundet) und dem Parameter \(c\), dazu das echte Link-Netz einer Website mit 350 Knoten, nämlich 50 Seiten und 300 Demos. Das Ausgangsnetz der Demo ist ein Zufallsnetz mit \(n = 150\), \(c = 6\), Ausbreitungsstärke 10 % und \(k = 5\).
• Die sieben Typen: Zufallsnetz (\(c\) ist der mittlere Grad); Potenzgesetz-Netz (Gradfolge mit Potenzgesetz, Konfigurationsmodell; \(c\) ist der mittlere Grad); skalenfrei (Wachstum mit bevorzugter Anbindung, zwei Kanten je neuem Knoten, also \(c/2\) gerundet); Verbünde (dichte Gruppen, die meisten Kanten bleiben im eigenen Verbund); Ring mit Abkürzungen (\(c\) Nachbarn auf dem Ring, dazu zufällige Abkürzungen); Gitter (\(c\) legt die Nachbarschaft fest: nur Vier-Nachbarschaft, mit einer oder mit beiden Diagonalen); Hubs am Rand (dichter Kern, wenige Hubs mit je einer Kante in den Kern und vielen Blättern, dazu Randknoten mit mehreren Kernkontakten; Hubs haben hohen Grad, aber Kernzahl 1).
• Regeln: Grad (Zahl der Nachbarn), Nähe (kleinster mittlerer Abstand zu allen anderen), Betweenness (Zahl der kürzesten Wege durch den Knoten), PageRank, Kernzahl (größte Zahl \(q\), für die der Knoten in einem Teilnetz liegt, in dem jeder Knoten mindestens \(q\) Nachbarn hat), Degree Discount, Single Discount (jeder Nachbar eines gewählten Starters verliert genau einen Kontakt), jeweils mit zufälliger Auflösung der Gleichstände (Mittel über zehn Ziehungen), dazu Degree Discount mit der Gleichstandsregel „kleinste Knotennummer“ und Zufall (30 Ziehungen). Die Regeln wählen die \(k\) besten Knoten nach dem Maß; nur Degree Discount und Single Discount werten nach jeder Wahl um.
• Maß: der Spread einer Regel geteilt durch den Spread von Greedy. In den Messreihen ist es der Median über die acht festen Netze je Zelle mit \(n = 250\) und \(c = 6\), wo nichts anderes steht.

Die Formeln

Der erwartete Spread einer Startmenge \(S\) ist der Erwartungswert der Zahl der Knoten, die in \(G_p\) von \(S\) aus erreichbar sind; \(R_{G_p}(S)\) bezeichnet diese Menge:

\[\sigma(S) = \mathbb{E}\bigl[\,|R_{G_p}(S)|\,\bigr]\]

Mit \(N\) Schnappschüssen \(G^{(1)}, \dots, G^{(N)}\) wird er durch \(\hat\sigma(S) = \frac{1}{N} \sum_{r=1}^{N} |R_{G^{(r)}}(S)|\) geschätzt. Der Zuwachs eines Knotens \(v\) zu \(S\) ist:

\[\Delta(v \mid S) = \sigma(S \cup \{v\}) - \sigma(S)\]

Der Spread ist monoton und submodular (Kempe, Kleinberg, Tardos 2003). Monoton heißt: Für \(S \subseteq T\) gilt \(\sigma(S) \le \sigma(T)\), mehr Starter erreichen nie weniger. Submodular heißt: Für \(S \subseteq T\) gilt \(\Delta(v \mid S) \ge \Delta(v \mid T)\), ein Knoten bringt zu einer größeren Menge höchstens so viel Zuwachs wie zu einer kleineren. Das Greedy-Ergebnis \(S_\mathrm{G}\) mit \(k\) Startern (Index G für Greedy) erreicht gegenüber dem Optimum \(S^*\):

\[\sigma(S_\mathrm{G}) \ge \Bigl(1 - \frac{1}{e}\Bigr) \sigma(S^*)\]

Das gilt bei exakt berechnetem Spread. Mit Schnappschüssen ist die Schätzung \(\hat\sigma\) selbst monoton und submodular, die Garantie gilt dann bezogen auf \(\hat\sigma\); gegenüber dem wahren \(\sigma\) kommt der Schätzfehler hinzu. Degree Discount ist eine Heuristik, für die die Demo keine Garantie angibt. Die Abwertung (Chen, Wang, Yang 2009) setzt den Grad \(d_v\) eines Knotens \(v\) herab, nachdem \(t_v\) seiner Nachbarn gewählt wurden:

\[dd_v = d_v - 2\, t_v - (d_v - t_v)\, t_v\, p\]

Die Redundanz einer Menge \(S\) ist der Spread der Menge geteilt durch die Summe der Einzelspreads. Der Wert 1 bedeutet, dass die Reichweiten nicht überlappen:

\[\rho(S) = \frac{\sigma(S)}{\sum_{v \in S} \sigma(\{v\})}\]

Herleitung Schritt für Schritt

Die Schritte 1 bis 4 folgen der üblichen Lehrbuchherleitung (Standardwissen der Theorie, hier als Skizze, nicht als Beweis). Dabei ist \(m\) die Zahl der Kanten, \(n\) die der Knoten und \(S_i\) die Menge der ersten \(i\) von Greedy gewählten Starter.

• Schritt 1, Schnappschuss: Jede Kante wird einmal gewürfelt und bleibt mit Wahrscheinlichkeit \(p\). Ein Starter informiert dann genau die Knoten seiner Zusammenhangskomponente. Die Demo prüft diese Gleichwertigkeit an 30 kleinen Netzen gegen den exakten Spread durch Aufzählung aller \(2^m\) Kantenzustände (Band 0,2 Knoten).
• Schritt 2, Überdeckung: In einem festen Schnappschuss ist \(|R_G(S)|\) die Summe der Größen der Komponenten, in denen Starter liegen. Zwei Starter in derselben Komponente zählen sie nur einmal. Das ist eine Überdeckungsfunktion, also monoton und submodular. Das Mittel über Schnappschüsse behält beides: Die Ungleichung \(\Delta(v \mid S) \ge \Delta(v \mid T)\) gilt in jedem Schnappschuss einzeln, also auch für den Mittelwert. Außerdem ist \(\sigma(\emptyset) = 0\).
• Schritt 3, Garantie: Wegen Monotonie und Submodularität gilt \(\sigma(S^*) \le \sigma(S_i) + k \max_v \Delta(v \mid S_i)\). Greedy wählt das größte \(\Delta\), also schließt jeder Schritt mindestens den Anteil \(1/k\) der Lücke zum Optimum. Nach \(k\) Schritten bleibt höchstens \((1 - 1/k)^k\) der anfänglichen Lücke, und diese Zahl ist höchstens \(1/e\). Das ist die Garantie von oben (Nemhauser, Wolsey, Fisher, aus dem Gedächtnis, nicht geprüft).
• Schritt 4, CELF: Wegen der Submodularität kann ein Zuwachs, der in einer früheren Runde berechnet wurde, nur kleiner werden. Er ist eine obere Schranke. CELF rechnet daher nur den obersten Eintrag der Liste neu und wählt ihn, sobald er nach der Neuberechnung oben bleibt. Die Auswahl ist dieselbe wie bei Greedy ohne Beschleunigung, sofern Gleichstände gleich aufgelöst werden.
• Schritt 5, Zählung der Auswertungen: Greedy ohne Beschleunigung bewertet in Runde \(i\) alle \(n - i\) übrigen Knoten, zusammen \(\sum_{i=0}^{k-1}(n - i) = kn - k(k-1)/2\) Zuwachs-Auswertungen. Das ist eine Rechnung dieser Seite; sie stimmt mit den Zahlen der Messreihe überein, \(n = 250\) mit \(k = 10\) und \(k = 20\).

Die Herleitung der Abwertung \(dd_v\) steht in der Originalarbeit und wird hier nicht nachvollzogen. Die Demo prüft ihre Rechnung gegen eine unabhängig geschriebene Neuberechnung der Formel.

Durchgerechnet: Pfad und zwei Dreiecke

Pfad mit drei Knoten \(a - b - c\) und \(p = 0{,}5\), Spread von Hand. Startet man in der Mitte \(b\), sind \(b\) selbst sicher, \(a\) und \(c\) je mit Wahrscheinlichkeit \(p\) erreicht: \(\sigma(\{b\}) = 1 + 0{,}5 + 0{,}5 = 2\). Startet man am Ende \(a\), kommt \(b\) mit \(0{,}5\) und \(c\) nur über beide Kanten mit \(p^2\) hinzu: \(\sigma(\{a\}) = 1 + p + p^2 = 1{,}75\). Die Demo rechnet diese beiden Werte (2 und 1,75) ebenso. Für einen Starter ist die Mitte also besser, für den Beginn von Greedy die richtige Wahl.

Die Redundanz zeigt die Überlappung an zwei getrennten Dreiecken mit \(p = 1\). Ein Starter je Dreieck erreicht beide Dreiecke ganz, die Summe der Einzelspreads ist ebenso groß, also \(\rho = 1\). Zwei Starter im selben Dreieck erreichen nur dieses Dreieck, die Summe der Einzelspreads ist doppelt so groß, also \(\rho = 1/2\). Die Demo liefert beide Werte (Redundanz 1 und 1/2). Beide Rechnungen dieses Abschnitts sind Handrechnungen dieser Seite am Modell, keine Messreihen. Greedy würde deshalb nach dem ersten Starter einen aus dem anderen Dreieck wählen, denn nur der bringt Neues. Grad und Nähe bewerten in diesem Beispiel alle sechs Knoten gleich und sehen die Überlappung nicht.

Befunde

Alle Zahlen sind Verhältnisse zum Spread von Greedy (Median über acht feste Netze je Zelle, \(n = 250\), \(c = 6\), \(k = 10\)), bewertet auf unabhängigen Schnappschüssen. Erste Tabelle: Gradregel und Nähe bei schwacher (3 %) und starker (15 %) Ausbreitung.

Netztyp	Grad (3 % / 15 %)	Nähe (3 % / 15 %)
Zufallsnetz	0,97 / 0,98	0,92 / 0,96
Potenzgesetz-Netz	0,97 / 0,92	–
skalenfrei	0,97 / 0,94	–
Verbünde	0,95 / 0,96	0,88 / 0,94
Ring mit Abkürzungen	0,89 / 0,90	0,67 / 0,76
Gitter	0,87 / 0,91	0,45 / 0,60
Hubs am Rand	0,99 / 0,98	0,69 / 0,71

Der Strich bedeutet: hier nicht ausgewiesen. Die Gradregel erreicht bei schwacher Ausbreitung in 5 von 7 Netztypen mindestens 0,95, bei starker in 3 von 7. Zweite Tabelle: mittlerer Abstand der Starter im Netz (in Schritten über Kanten) und, wo ausgewiesen, die Redundanz, bei \(k = 10\) und 15 %.

Netztyp	Greedy: Abstand / Redundanz	Grad	Nähe
Potenzgesetz-Netz	3,7 / 0,38	1,4 / 0,11	1,3 / 0,11
skalenfrei	3,0 / 0,24	1,6 / 0,13	–
Zufallsnetz	3,1 / 0,24	2,4 / 0,20	–
Ring mit Abkürzungen	5,6	3,7	2,5
Gitter	9,9	7,8	1,7 / 0,17
Hubs am Rand	3,7 / 0,35	2,4 / 0,19	1,3 / 0,10

Dritte Tabelle: wie der Verlust von der Zahl der Starter \(k\) und von der Regel abhängt, jeweils mit seinen Voraussetzungen.

Frage	Befund
Ist die Nähe bei einem Starter schlechter? (\(k = 1\), 3 % und 15 %)	Nein: In sechs von sieben Netztypen ist sie bei \(k = 1\) gleichwertig, die Ausnahme sind die Verbünde (0,90 bei 3 %, 0,94 bei 15 %). Im Gitter (3 %) liegt sie bei \(k = 1\) gleichauf mit Greedy, bei \(k = 10\) wie bei \(k = 20\) bei 0,45.
Wie hängt der Verlust von \(k\) ab? (Hubs am Rand, 15 %)	Gradregel: \(k = 1\): 0,46, \(k = 3\): 0,86, \(k = 5\): 0,99, \(k = 10\): 0,98. Kernzahl-Regel im selben Netz: \(k = 1\): 1,00, \(k = 20\): 0,68. Sie wählt zunächst die Kerne, später Randknoten.
Wie schneiden die anderen Maße ab? (\(k = 10\), 3 %)	Betweenness im Gitter 0,47, PageRank 0,52. Kernzahl zwischen 0,69 (Hubs am Rand) und 0,94 (Potenzgesetz-Netz). Zufall zwischen 0,69 und 0,82.
Wie nah ist Degree Discount? (\(k = 10\), 3 %)	1,00 in 5 von 7 Netztypen. Im Gitter und im Ring 0,89 bis 0,94.
Was kostet die Gleichstandsregel? (\(k = 10\), Gitter)	Zufällige Auflösung 0,89 / 0,93 (3 % / 15 %), „kleinste Knotennummer“ 0,63 / 0,70. Das sind 23 bis 26 Prozentpunkte.

Vierte Tabelle: Aufwand, Garantie, Eindeutigkeit und einzelne Beispielnetze.

Frage	Befund
Wie viel spart CELF? (10 %, \(k = 10\) und 20)	53 % bis 87 % weniger Zuwachs-Auswertungen bei gleicher Auswahl in allen Netztypen. Zufallsnetz: 1 149 statt 2 455 (\(k = 10\)) und 1 486 statt 4 810 (\(k = 20\)); Hubs am Rand: 648 statt 4 810 bei \(k = 20\).
Garantie gegen Wirklichkeit (40 kleine Zufallsnetze, \(n = 7\) bis 9, exakter Spread bei \(p = 0{,}5\), \(k = 2\) und 3)	Greedy erreicht im Median 99,3 % des Optimums, mindestens 92,2 %, und trifft das Optimum in 29 von 80 Fällen. Die Garantie 63,2 % liegt darunter.
Ist die Auswahl eindeutig? (Zufallsnetz, \(k = 10\), acht Läufe auf frischen Schnappschüssen)	Nein: bei 50 wie bei 300 Trainings-Schnappschüssen 8 von 8 verschiedene Mengen, der Spread der Läufe streut um 2,5 bzw. 1,8 Knoten (Spannweite, nicht der Standardfehler der Schätzung; Median 98,8 bzw. 100,0 von 250).
Ausgangsnetz (Zufallsnetz, \(n = 150\), \(c = 6\), 10 %, \(k = 5\))	450 Kanten, \(p = 0{,}191\). Greedy erreicht 52,1 Knoten (Standardfehler 0,7). Degree Discount liegt bei 100 %, Kernzahl bei 90 %, Zufall bei 86 % von Greedy. Abstand der Greedy-Starter 2,4, Redundanz 0,45. Zuwachs-Auswertungen: 740 ohne, 518 mit CELF.
Potenzgesetz-Netz (\(n = 150\), 15 %, \(k = 10\), Grad)	Grad bei 90 % von Greedy; Abstand der Starter 1,6 gegen 3,4, Redundanz 0,13 gegen 0,32.
Link-Netz (350 Knoten, 15 %, \(k = 10\))	\(p = 0{,}085\), Greedy erreicht 142,4 Knoten, die Gradregel 94,6 % davon. Greedy wählt als Erstes die Startseite, als Zweites die Fehlerseite 404.html, den einzigen Knoten ohne Verlinkung. Ihr Zuwachs ist genau 1 (nur sie selbst), danach ist jeder andere Zuwachs kleiner als 1. Der Abstand der Grad-Starter ist 1,0.

Grenzen und was die Messung zeigt

Die Messreihen belegen Aussagen über die sieben erzeugten Netztypen bei den genannten Größen und Ausbreitungsstärken, nicht über beliebige Netze:

• Modell: ungerichtet, gleiche Weitergabewahrscheinlichkeit, nur Independent Cascade. Mit Gewichten, Richtungen, Schwellenmodellen oder Kosten je Betrieb sind Spread und Garantie andere Größen.
• Kalibrierung: \(p\) wird über einen zufälligen Einzelstarter festgelegt. Eine andere Kalibrierung ergibt andere Lücken. Die Befunde gelten für die gemessenen Stärken 3 %, 10 % und 15 %.
• Streuung: Standardfehler etwa ein bis zwei Knoten. Die Streuung der Verhältnisse zwischen den acht Netzen ist nicht ausgewiesen, und „Greedy ist die beste Regel“ ist nur im Median über acht Netze belegt. Bei 3 % Ausbreitung liegt keine Regel mehr als 1,1 % über Greedy; bei 10 % ist die Obergrenze nach einer Nachrechnung dieser Seite etwas höher, bei etwa anderthalb Prozent. Beides liegt im Rahmen des Schätzrauschens und ist kein Beweis. In der Demo selbst rechnen die Reihen laut Beschriftung mit vier statt acht Netzen je Zelle, die Werte dort weichen daher von den Tabellen ab.
• Greedy ist nicht optimal: Sein Abstand zum Optimum ist nur auf winzigen Netzen (\(n = 7\) bis 9) gemessen, weil der exakte Spread eine Aufzählung braucht; für große Netze nicht.
• Gleichstände: Auf regelmäßigen Netzen (Gitter, Ring) haben viele Knoten denselben Wert. Der Vergleich mit einfachen Regeln hängt dort an der Auflösung der Gleichstände (dritte Tabelle).
• Link-Netz: ein Sonderfall, denn die Startseite ist mit allen anderen Knoten außer der Fehlerseite verlinkt. Die Zahlen gelten für den Schnappschuss, nicht für die heutige Website.
• Nicht gemessen: Reverse-Influence-Sampling (TIM+, IMM, OPIM), der heutige Stand der Technik für große Netze, und lernbasierte Löser. Mehr als 20 Starter und Netze über 250 Knoten rechnet die Demo nicht live.

Quellen

• Kempe, D., Kleinberg, J., Tardos, É. (2003): Maximizing the spread of influence through a social network. KDD 2003, 137–146.
• Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., Glance, N. (2007): Cost-effective outbreak detection in networks. KDD 2007. (CELF)
• Chen, W., Wang, Y., Yang, S. (2009): Efficient influence maximization in social networks. KDD 2009. (NewGreedy, Degree Discount)
• Kitsak, M. u. a. (2010): Identification of influential spreaders in complex networks. Nature Physics 6, 888–893. (Kernzahl und Abstand der Starter)
• Tang, Y., Xiao, X., Shi, Y. (2014): Influence maximization: near-optimal time complexity meets practical efficiency. SIGMOD 2014. (TIM/TIM+, Reverse-Influence-Sampling)

Die Angaben stammen aus der Demo; sie sind dort bereits nachgeschlagen. Die Formel von Degree Discount stammt aus dem Originaltext, die Arbeiten selbst sind nicht vollständig gelesen. Der Satz zur Garantie von Nemhauser, Wolsey und Fisher steht aus dem Gedächtnis hier, nicht geprüft.