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

29

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 gdzieuewede

= 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ź ue
we
de

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?

phwd
źródło
Jako prosty punkt wyjścia możesz skorzystać z systemu rekomendacji „przyjaciół znajomych”. To znaczy, jeśli masz wielu przyjaciół, którzy są przyjaciółmi osoby X, to może powinieneś być przyjaciółmi z osobą X.
Joe
1
istnieją różne modele wykresów losowych, które próbują uchwycić strukturę prawdziwej sieci społecznościowej. Obliczanie prawdopodobieństwa potencjalnej krawędzi zależy od używanego modelu i dostępnych informacji.
Kaveh

Odpowiedzi:

7

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ół.MM2M2

Dave Clarke
źródło
1
Dałoby to liczbę ścieżek między osobą p , które można następnie wykorzystać do uszeregowania przyjaciół. Przyznaję, że jest szorstki. fip
Dave Clarke
Myślę, że modelowanie problemu za pomocą wykresu jest zarówno łatwiejsze, jak i bardziej intuicyjne.
MMS
11

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.

Patrick87
źródło
10

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ąć.

Nacięcie
źródło
4

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.

NCNN1N2N2N1

|CN1CN2||CN1|α

α[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

SN={M:|CNCM|Nα}

i zestaw wiarygodnych sugestii

{S:MSN[SM]|SN|β}

α,β[0,1]

SN

Raphael
źródło