Hm... nur ein paar verworrene Gedanken meinerseits:
Wenn Du 1000 Benutzer hast, dann könnte man über eine Matrix (1000 x 1000) angeben, über wieviele Ecken zwei Leute sich kennen (minimal). Dabei könntest Du eine Grenze max_ecken einführen, die dafür sorgt, dass nicht alle Felder besetzt werden (nämlich jeweils die Felder von je Personen, die sich über mehr als max_ecken kennen, bleiben leer).
Wenn nun max_user größer wird und max_ecken klein bleibt, wird deine Matrix sehr spärlich besetzt und es kann sinnvoll sein, sie über eine Tabelle (user1, user2, anz_ecken) zu ersetzen. Außerdem ist die Matrix natürlich diagonalsymetrisch (da gabs auch mal einen Fachausdruck für), so dass Du (user2, user1, anz_ecken) gar nicht erst zu setzen brauchst.
Natürlich müsste die Tabelle immer aktualisiert werden, wenn user1 oder user2 an seinen oder ihren Kontakten rumfummelt. Das dürfte aber deutlich seltener auftreten als die Anzeige der möglichen Verbindungen.
Nun weißt Du aber nur, welche Beziehungen es sich lohnt anzugucken. Man könnte aber die Tabelle erweitern (user1, user2, anz_ecken, pfad). Wobei pfad eine Liste der UserIDs ist, über die die Beziehung aufgebaut ist. Ich speichere sowas gerne als Text-Feld ab und mache mir dann die
MySQL-spezifische(?) Funktion FIND_IN_SET zu Nutze. Mit "FIND_IN_SET(user.id, relation.pfad)" kann ich alle User-Einträge auswählen, deren IDs in der Liste vorkommen.
Keinen blassen Schimmer, ob Dir das weiterhilft. ist jedenfalls reine Theorie und basiert auf keinerlei Erfahrung mit großen Userzahlen
Viel Spaß!
Sir Twist