Algoritma terdesentralisasi untuk menentukan node yang berpengaruh di jejaring sosial

13

Dalam makalah oleh Kempe-Kleinberg-Tardos, Penulis mengusulkan algoritma rakus berdasarkan fungsi submodular untuk menentukan paling berpengaruh node dalam grafik, dengan aplikasi untuk jaringan sosial.k

Pada dasarnya algoritma berjalan sebagai berikut:

  1. S=emhalty set
  2. pilih node dengan pengaruh individu tertinggi, sebut saja ; S = S ∪ v 1v1S=S∪v1
  3. hapus dan semua tepi yang menghubungkan v 1 ke seluruh jaringanv1v1
  4. ulangi sampai memiliki simpul kSk

Saya punya dua pertanyaan tentang node yang berpengaruh di jejaring sosial.
a) Apakah ada algoritma untuk menemukan solusi, atau perkiraannya secara desentralisasi?
b) Apakah ada yang menerapkan algoritma lain, seperti Page-Rank dan sejenisnya, untuk menyelesaikan masalah yang sama?

ds.algorithms graph-theory dc.distributed-comp social-sciences heuristics Bob
sumber
Bagaimana Anda mendefinisikan simpul "berpengaruh"?
Timothy Sun
2
menurut makalah, setiap tautan didefinisikan dengan probabilitas untuk berhasil mengirim pesan dari satu simpul ke simpul lainnya. Tujuannya adalah untuk menemukan subset dari node yang akan mengirimkan pesan ke jumlah node terbesar, sesuai harapan.
Bob
Mengenai algoritma terdistribusi: Secara umum, masalah apa pun dari bentuk "temukan simpul terbaik" bersifat global; itu tidak dapat diselesaikan lebih cepat daripada dalam waktu D , di mana D adalah diameter grafik. Untuk melihat ini, pertimbangkan kasus k = 1 dan hubungkan dua node "baik" dengan jalur yang panjang; untuk menentukan node mana yang terbaik, Anda perlu menyebarkan informasi untuk urutan D hop. kDDk=1D
Jukka Suomela
Aku mengerti itu. Kekhawatiran saya adalah jika ada, setidaknya, algoritma suboptimal untuk mendekati solusi optimal.
Bob

Jawaban: