Jak ustalić prawdopodobne połączenia w sieci społecznościowej?

Interesuje mnie określenie podejścia do rozwiązania algorytmu „sugerowanych przyjaciół”.

Facebook ma funkcję, w której poleci ci osoby, z którymi według ciebie możesz się zapoznać. Ci użytkownicy zwykle (z wyłączeniem skrajnych przypadków, w których użytkownik szczególnie poleca znajomemu ) mają bardzo podobną sieć do siebie. Oznacza to, że liczba wspólnych znajomych jest wysoka. Zakładam, że Twitter podąża podobną ścieżką w ramach mechanizmu „Who To Follow”.

Stephen Doyle (Igy) , pracownik Facebooka, zasugerował, że pokrewny kanał informacyjny wykorzystujący formułę EdgeRank, który wydaje się wskazywać, że więcej należy docenić niż znajomych, takich jak wygląd, to podobne posty. Inny użytkownik zasugerował system Google Rank.

Facebook twierdzi ich News Feed Optimization jako gdzie$\sum u_{e}w_{e}d_{e}$

= wynik powinowactwa między przeglądającym użytkownikiem a twórcą krawędzi w e = waga dla tej krawędzi (tworzenie, komentowanie, dodawanie znaczników itp.) d e = współczynnik zaniku czasu na podstawie tego, jak dawno utworzono krawędź $u_{e}$
$w_{e}$
$d_{e}$

Podsumowanie tych przedmiotów ma dać rangę obiektu, który zakładam, jak Igy podpowiedział, oznacza, że ​​sugerowani przyjaciele używają czegoś w podobnym formacie.

Zgaduję więc, że w ten sposób połączenia dla wszystkich typów są generalnie wykonywane za pomocą systemu rang?

Można myśleć o wykresie społecznej jako macierz . Jedno podejście do problemu jest pierwszym oblicz M 2 , które dadzą wszystkich ścieżek o długości dwa między dwoma podmiotami w sieci społecznej. Można to postrzegać jako wagę połączenia między tymi przyjaciółmi znajomych. Następnym krokiem jest wybranie kolumny z rzędu M 2 odpowiadającym osobie zainteresowania w celu uzyskania najlepszych kandydatów na nowych przyjaciół.$\mathbf{M}$$\mathbf{M}^2$$\mathbf{M}^2$

To, czego szukasz, to heurystyka. Żaden algorytm nie może powiedzieć, biorąc pod uwagę wykres przyjaciół jako jedyne dane wejściowe, czy dwie osoby, które nie są bezpośrednio połączone, są przyjaciółmi, czy nie; relacja przyjaźń / znajomość nie jest gwarantowana jako przechodnia (możemy założyć symetrię, ale może to być nawet odcinek w prawdziwym życiu). Dlatego każda dobra heurystyka będzie musiała opierać się na zrozumieniu interakcji między ludźmi, a nie na matematycznym zrozumieniu natury wykresów relacji (chociaż będziemy musieli oszacować heurystykę w tych kategoriach).

Sugerowanie przyjaciołom znajomych z jednakowym prawdopodobieństwem jest względnie tanią, ale niedokładną heurystyką. Na przykład mój ojciec ma przyjaciół, ale nie powiedziałbym, że jestem przyjacielem któregokolwiek z nich (chociaż prawdopodobnie powiedziałbym, że jestem przyjacielem mojego ojca dla celów np. Sieci społecznościowej). Posiadanie osoby w stosunkowo bliskiej odległości niekoniecznie czyni ją doskonałym kandydatem.

Sugerowanie ludzi, z którymi masz bardzo wiele rozszerzonych połączeń, wydaje się ogólnie złym wyborem, ponieważ doprowadzi to do gwałtownego wzrostu przyjaciół ludzi, którzy robią postępy wcześniej (siedem stopni oddzielenia od gry Kevina Bacona jest przykład tego).

$R$

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

Powiedzmy, że chcemy znaleźć nowych przyjaciół a. a„s obecne są przyjaciele b, ci f. Oceniamy równoważny opór netto pomiędzy ai każdego d, e, g, h, i i:

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

Według tej heurystyki djest najlepszym przyjacielem kandydata, a zaraz za nim h. gjest kolejnym najlepszym zakładem, a tuż za nim e. idzięki tej heurystyce nigdy nie może zostać kandydatem na przyjaciela. Ważne jest to, czy wyniki tej heurystyki będą reprezentatywne dla rzeczywistych ludzkich interakcji społecznych. Pod względem obliczeniowym wymagałoby to znalezienia podsgrafu zawierającego wszystkie ścieżki między dwiema jednostkami (lub, co ciekawe, niektóre znacząco wybrane skrócenia tego), a następnie oceny równoważnego oporu między węzłem źródłowym i ujścia.

EDYCJA: Więc jaka jest moja motywacja społeczna? Cóż, może to być przybliżony model tego, jak trudno jest się skontaktować, a następnie przekazać potencjalnie znaczne ilości informacji za pośrednictwem pośredników (przyjaciół). Pod względem CS (a nie fizyki) można to interpretować jako przepustowość między dwoma węzłami na wykresie. Rozszerzenia tego systemu pozwoliłyby na różnego rodzaju połączenia między osobami o różnych wagach (opór, przepustowość itp.) I postępowałyby jak wyżej.

Wiele pracy poświęcono temu problemowi, ponieważ popularność sieci społecznościowych spadła. Problem jest zwykle nazywany „Prognozowaniem linków”, a bardzo dobre i wyczerpujące ankiety można znaleźć tutaj i tutaj . Metody wahają się od bardzo prostych (np. Podobieństwo Jaccarda między węzłami) do bardzo złożonych (np. Konstruowanie modeli statystycznych procesu generatywnego połączenia). Zależy to w dużej mierze od konkretnych funkcji dostępnych w zbiorze danych (np. Po prostu struktura sieci, atrybuty węzłów ?, atrybuty brzegowe, ...), ale te ankiety dadzą ci dobry pomysł, od czego zacząć.

Oświadczenie: Zgaduję tutaj; Nie czytałem żadnych badań gatunku.

Możesz sprawdzić, ile połączeń z węzłami współdzieli w stosunku do liczby połączeń w węźle. To bardzo naiwny (lokalny) pomysł, ale proszę bardzo.

$N$$C_N$$N_1$$N_2$$N_2$$N_1$

$\qquad \displaystyle \frac{|C_{N_1} \cap C_{N_2}|}{|C_{N_1}|} \geq \alpha$

$\alpha \in [0,1]$

Kolejny pomysł jest bardziej globalny: określ zestaw węzłów podobnych do tego, który masz pod ręką i zaproponuj połączenia, z których korzysta wiele z nich. Zdefiniuj zestaw podobnych węzłów

$\qquad \displaystyle S_N = \left\{M : \frac{|C_N \cap C_M|}{N} \geq \alpha\right\}$

i zestaw wiarygodnych sugestii

$\qquad \displaystyle \left\{ S : \frac{\sum_{M \in S_N} [S \in M]}{|S_N|} \geq \beta \right\}$

$\alpha, \beta \in [0,1]$

$S_N$