Bagaimana cara menentukan kemungkinan koneksi di jejaring sosial?

Saya ingin tahu dalam menentukan pendekatan untuk menangani algoritma "teman yang disarankan".

Facebook memiliki fitur di mana ia akan merekomendasikan individu kepada Anda yang menurutnya mungkin Anda kenal. Pengguna ini biasanya (tidak termasuk kasus tepi di mana pengguna secara khusus merekomendasikan teman ) memiliki jaringan yang sangat mirip dengan diri sendiri. Artinya, jumlah teman yang sama tinggi. Saya berasumsi Twitter mengikuti jalur serupa untuk mekanisme "Who To Follow" mereka.

Stephen Doyle (Igy) , seorang karyawan Facebook menyarankan agar umpan berita terkait yang menggunakan rumus EdgeRank yang tampaknya menunjukkan bahwa lebih banyak yang dinilai daripada teman seperti penampilan adalah posting serupa. Pengguna lain menyarankan sistem Peringkat Google.

Facebook menyatakan Optimasi Umpan Berita sebagai mana$\sum u_{e}w_{e}d_{e}$

$u_{e}$ = skor afinitas antara pengguna yang melihat dan pembuat tepi = bobot untuk tepi ini (buat, komentar, seperti, tag, dll.) = faktor peluruhan waktu berdasarkan berapa lama tepi itu dibuat
$w_{e}$
$d_{e}$

Menjumlahkan barang-barang ini seharusnya memberikan peringkat objek yang saya anggap sebagai petunjuk Igy, berarti sesuatu dalam format yang sama digunakan untuk teman yang disarankan.

Jadi saya menduga bahwa ini adalah cara di mana koneksi untuk semua jenis dilakukan secara umum melalui sistem peringkat?

Anda dapat menganggap grafik sosial sebagai matriks . Salah satu pendekatan untuk masalah ini adalah pertama menghitung , yang akan memberikan semua jalur panjang dua antara dua aktor di jejaring sosial. Ini bisa dilihat sebagai bobot hubungan antara teman-teman ini. Langkah selanjutnya adalah memilih kolom dari deretan sesuai dengan orang yang diminati untuk mendapatkan kandidat terbaik untuk teman baru.$\mathbf{M}$$\mathbf{M}^2$$\mathbf{M}^2$

Apa yang Anda cari adalah heuristik. Tidak ada algoritma yang dapat mengatakan, diberikan grafik teman sebagai satu-satunya input, apakah dua orang yang tidak terhubung langsung adalah teman atau tidak; hubungan pertemanan / kenalan tidak dijamin transitif (kita dapat mengasumsikan simetri, tetapi itu mungkin bahkan menjadi bentangan dalam kehidupan nyata). Setiap heuristik yang baik karena itu perlu didasarkan pada pemahaman tentang bagaimana orang berinteraksi, daripada beberapa pemahaman matematis tentang sifat grafik hubungan (meskipun kita perlu mengukur heuristik dalam istilah ini).

Menyarankan teman teman dengan probabilitas yang sama adalah heuristik yang relatif murah tapi tidak akurat. Misalnya, ayah saya punya teman, tetapi saya tidak akan mengatakan saya berteman dengan mereka (walaupun saya mungkin mengatakan saya adalah teman ayah saya untuk keperluan, misalnya, jejaring sosial). Memiliki seseorang pada jarak yang relatif dekat tidak selalu membuat mereka menjadi kandidat yang hebat.

Menyarankan orang kepada siapa Anda memiliki banyak koneksi yang luas juga tampaknya merupakan pilihan yang buruk secara umum, karena ini akan cenderung mengarah pada pertumbuhan eksponensial dari teman-teman orang yang maju lebih dulu (tujuh derajat pemisahan dari permainan Kevin Bacon adalah suatu contoh dari ini).

Saya menyarankan model berbasis sirkuit. Asumsikan bahwa setiap link adalah resistor perlawanan . Maka kandidat terbaik untuk teman baru mungkin adalah individu dengan resistensi setara terendah. Berikut adalah contoh grafik ASCII yang dijalankan dengan buruk:$R$

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

Katakanlah kita ingin mencari teman baru a. ateman 's saat ini b, c, dan f. Kami mengevaluasi setara perlawanan bersih antara adan masing-masing d, e, g, h, dan i:

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

Menurut heuristik ini, dadalah calon sahabat, diikuti oleh h. gadalah taruhan terbaik berikutnya, diikuti oleh e. itidak akan pernah bisa menjadi calon teman oleh heuristik ini. Apakah Anda menemukan hasil heuristik ini untuk menjadi wakil dari interaksi sosial manusia nyata adalah yang penting. Berbicara secara komputasional, ini akan melibatkan menemukan sebuah subgraf yang berisi semua jalur antara dua individu (atau, mungkin yang menarik, beberapa pemangkasan yang dipilih secara bermakna dari ini), kemudian mengevaluasi resistensi setara antara node source dan sink.

EDIT: Jadi apa motivasi sosial saya untuk ini? Yah, ini mungkin model kasar dari seberapa sulit untuk berhubungan, dan kemudian mengomunikasikan sejumlah besar informasi yang mungkin melalui perantara (teman). Dalam istilah CS (bukan istilah fisika), ini mungkin ditafsirkan sebagai bandwidth antara dua node dalam grafik. Perluasan sistem ini akan memungkinkan berbagai jenis tautan antara orang-orang dengan bobot yang berbeda (resistensi, bandwidth, dll.) Dan melanjutkan seperti di atas.

Ada banyak pekerjaan yang dilakukan untuk masalah ini karena popularitas jejaring sosial telah meningkat. Masalahnya biasanya disebut "Prediksi Tautan" dan survei yang sangat bagus dan komprehensif dapat ditemukan di sini dan di sini . Metode berkisar dari yang sangat sederhana (misalnya kesamaan Jaccard antara node) ke yang sangat kompleks (misalnya membangun model statistik dari proses koneksi generatif). Ini sangat tergantung pada fitur spesifik yang Anda miliki di dataset Anda (misalnya hanya struktur jaringan, atribut simpul ?, atribut tepi, ...), tetapi survei ini akan memberi Anda ide yang baik untuk mulai dari mana.

Penafian: Saya menebak-nebak di sini; Saya belum membaca riset genre apa pun.

Anda bisa melihat berapa banyak koneksi ke node berbagi relatif dengan jumlah koneksi yang dimiliki sebuah node. Ini adalah ide (sebagai lokal) yang sangat naif, tapi begini saja.

Setiap node (orang atau konsep lain) memiliki satu set koneksi . Sekarang, diberi dua simpul dan , sarankan ke jikaC N N 1 N 2 N 2 N $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$

untuk beberapa masuk akal (dan sebaliknya).$\alpha \in [0,1]$

Gagasan lain lebih global: tentukan satu set node yang mirip dengan yang ada dan ajukan koneksi yang banyak di antaranya miliki. Jadi, tentukan set node yang serupa

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

dan set saran yang masuk akal oleh

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

lagi untuk masuk akal .$\alpha, \beta \in [0,1]$

Pada kenyataannya, Anda tentu ingin mempertimbangkan koneksi secara individual; misalnya, elemen yang sudah terhubung dengan Anda harus memiliki impor yang lebih besar daripada yang jauh dari Anda.$S_N$