Wie ermittelt man wahrscheinliche Verbindungen in einem sozialen Netzwerk?

Question

Ich bin neugierig, einen Ansatz zur Bekämpfung eines Algorithmus "Vorgeschlagener Freunde" zu bestimmen.

Facebook hat eine Funktion, in der es Ihnen Personen empfohlen wird, die Sie vielleicht kennen. Diese Benutzer normalerweise (ohne die Kantenfälle in was ein Benutzer ausdrücklich einen Freund empfiehlt) ein sehr ähnliches Netzwerk mit sich selbst haben. Das heißt, die Anzahl der gemeinsamen Freunde ist hoch. Ich nehme an, Twitter folgt einem ähnlichen Weg für ihren Mechanismus "Who to folge".

Stephen Doyle (IGY), ein Facebook -Mitarbeiter schlug vor, dass der zugehörige Newsfeed, der verwendet Edgerank -Formel Dies scheint darauf hinzudeuten, dass mehr zu bewerten ist, als Freunde wie das Aussehen ähnliche Beiträge sind. Ein anderer Benutzer schlug das Google Rank -System vor.

Facebook gibt ihre News -Feed -Optimierung als $ sum u_ {e} w_ {e} d_ {e} $ wo an

$ u_ {e} $ = Affinitätsbewertung zwischen dem Betrachten von Benutzern und Edge Creator
$ w_ {e} $ = Gewicht für diese Kante (erstellen, kommentieren, wie, Tag usw.)
$ d_ {e} $ = Zeitabfallfaktor basierend darauf, wie lange die Kante erstellt wurde

Das Summieren dieser Elemente soll den Rang eines Objekts geben, den ich als IGY annehme, bedeutet, dass etwas in einem ähnlichen Format für empfohlene Freunde verwendet wird.

Ich vermute also, dass dies die Art und Weise ist, wie Verbindungen für alle Typen im Allgemeinen über ein Rangsystem hergestellt werden?

Answer 1

Sie können sich das soziale Diagramm als Matrix $ mathbf {m} $ vorstellen. Ein Ansatz für das Problem besteht darin, zuerst $ mathbf {m}^2 $ zu berechnen, wodurch alle Wege der Länge zwei zwischen zwei Akteuren im sozialen Netzwerk verleiht. Dies kann als Gewicht der Verbindung zwischen diesen Freunden von Freunden angesehen werden. Der nächste Schritt besteht darin, die Spalten aus der Zeile von $ mathbf {m}^2 $ auszuwählen, die der interessierenden Person entspricht, um die besten Kandidaten für neue Freunde zu erhalten.

Answer 2

Was Sie suchen, ist eine Heuristik. Kein Algorithmus kann sagen, dass ein Diagramm von Freunden als einzige Eingabe, unabhängig davon, ob zwei nicht direkt verbundene Freunde sind oder nicht sind. Die Freundschafts-/Bekanntschaftsbeziehung ist nicht garantiert transitiv (wir können Symmetrie annehmen, aber das könnte sogar im wirklichen Leben eine Strecke sein). Jede gute Heuristik muss daher auf dem Verständnis der Interaktion der Menschen beruhen, und nicht auf einem mathematischen Verständnis der Natur der Beziehungengrafiken (obwohl wir die Heuristik in diesen Begriffen quantifizieren müssen).

Freunde von Freunden mit gleicher Wahrscheinlichkeit vorzuschlagen, ist eine relativ billige, aber ungenaue Heuristik. Zum Beispiel hat mein Vater Freunde, aber ich würde nicht sagen, dass ich mit einem von ihnen befreundet bin (obwohl ich wahrscheinlich sagen würde, ich bin ein Freund meines Vaters für die Zwecke von, z. B. ein soziales Netzwerk). Eine Person in relativ enger Entfernung zu haben, macht sie nicht unbedingt zu einem großartigen Kandidaten.

Die Vorschläge der Menschen, denen Sie sehr viele erweiterte Verbindungen haben Beispiel dafür).

Ich schlage ein schaltungsbasiertes Modell vor. Angenommen, jede Verbindung ist ein Widerstand des Widerstands $ r $. Dann könnte der beste Kandidat für einen neuen Freund die Person mit dem niedrigsten äquivalenten Widerstand sein. Hier ist ein schlecht ausgeführtes ASCII-Grafikbeispiel:

  _____
 /     \
a---c   f
|   | /
b   d---e
| \ |
g   h   i

Sagen Sie, wir wollen neue Freunde finden für a. aDie aktuellen Freunde sind b, c, und f. Wir bewerten den äquivalenten Netto -Widerstand zwischen a und jeder von d, e, g, h, und i:

pair   resistance
(a,d)   6/7
(a,e)  13/7
(a,g)   7/4
(a,h)   1/1
(a,i)   inf

Nach dieser Heuristik, d ist der beste Kandidatenfreund, genau befolgt von h. g ist die nächstbeste Wette, genau gefolgt von e. i kann niemals ein Kandidatenfreund von dieser Heuristik sein. Ob Sie die Ergebnisse dieser Heuristik als repräsentativ für reale menschliche soziale Interaktionen finden, ist wichtig. Bei der rechnerischen Sprechung würde dies das Finden eines Untergraphen, der alle Pfade zwischen zwei Personen (oder möglicherweise interessanterweise, eine sinnvoll ausgewählte Kürzung davon enthält) und dann den äquivalenten Widerstand zwischen Quellen- und Sinkknoten bewertet.

EDIT: Also, was ist meine soziale Motivation dafür? Nun, dies könnte ein grobes Modell dafür sein, wie schwierig es ist, in Kontakt zu treten und anschließend möglicherweise erhebliche Informationsmengen durch Vermittler (Freunde) zu kommunizieren. In CS -Begriffen (anstelle von physikalischen Begriffen) kann dies als Bandbreite zwischen zwei Knoten in einem Diagramm ausgelegt werden. Erweiterungen dieses Systems würden darin bestehen, verschiedene Arten von Verbindungen zwischen Menschen mit unterschiedlichen Gewichten (Widerstand, Bandbreite usw.) zu ermöglichen und wie oben weiterzumachen.

Answer 3

Es gibt eine Menge Arbeit zu diesem Problem, da die Popularität des sozialen Netzwerks gestartet wurde. Das Problem wird in der Regel als "Link -Vorhersage" bezeichnet und sehr gute und umfassende Umfragen können gefunden werden hier und hier. Die Methoden reichen von der sehr einfachen (zB Jaccard -Ähnlichkeit zwischen Knoten) bis zum sehr komplexen (z. B. statistische Modelle des generativen Verbindungsprozesses). Es hängt stark von den spezifischen Funktionen ab, die Sie in Ihrem Datensatz verfügbar haben (z. B. nur Netzwerkstruktur, Knotenattribute?, Edge Attribute, ...), aber diese Umfragen geben Ihnen eine gute Vorstellung davon, wo Sie beginnen sollen.

Answer 4

Haftungsausschluss: Ich rate hier wild; Ich habe keine Genreforschung gelesen.

Sie können sich ansehen, wie viele Verbindungen zu Knoten relativ an die Anzahl der Konnträle eingehen, die ein Knoten hat. Dies ist eine sehr naive (als lokale) Idee, aber hier geht.

Jeder Knoten $ n $ (Person oder ein anderes Konzept) hat eine Reihe von Verbindungen $ C_N $. Angesichts von zwei Knoten $ n_1 $ und $ n_2 $, schlagen Sie $ n_2 $ bis $ n_1 $ vor, wenn

$ qquad displayStyle frac {| c_ {n_1} cap c_ {n_2} |} {| c_ {n_1} |} geq alpha $

für ein vernünftiges $ alpha in [0,1] $ (und umgekehrt).

Eine andere Idee ist globaler: Bestimmen Sie eine Reihe von Knoten ähnlich zu dem zur Hand und schlägt Verbindungen vor, die viele von ihnen teilen. Definieren Sie also den Satz ähnlicher Knoten

$ qquad displayStyle s_n = links {m: frac {| c_n cap c_m |} {n} geq alpha rechts } $

und die festgelegten plausiblen Vorschläge von

$ qquad displaystyle links {s: frac { sum_ {m in s_n} [s in m]} {| s_n |} geq Beta right } $

Wieder für vernünftige $ alpha, beta in [0,1] $.

In Wirklichkeit möchten Sie sicherlich die Verbindungen einzeln aufnehmen. Zum Beispiel sollten Elemente von $ S_N $, mit denen Sie bereits verbunden sind, einen größeren Import haben als so, dass Sie weit von Ihnen entfernt sind.