PageRank Berbobot
- Diperkenalkan oleh
- Xing, W. & Ghorbani, A.
- Tahun
- 2004
- Jenis
- Centrality measure / ranking algorithm
- Keluarga
- Network science
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Weighted PageRank memperluas algoritma PageRank klasik ke jaringan di mana tepi memiliki kekuatan atau frekuensi yang berbeda, mendistribusikan kepentingan secara proporsional terhadap bobot tepi masuk dan keluar, alih-alih memperlakukan semua tautan secara setara.
Hal ini membuatnya jauh lebih informatif daripada PageRank biner dalam jaringan apa pun di mana kekuatan koneksi penting.
Intuisi di balik metode
PageRank klasik memperlakukan setiap hyperlink atau ikatan secara identik: sebuah node mendapatkan prestise yang sama dari koneksi yang lemah seperti dari koneksi yang kuat. Weighted PageRank mengoreksi ini dengan menskalakan setiap suara berdasarkan bobot relatif tepi. Sebuah node yang menerima banyak ikatan masuk berbobot tinggi dari node yang sudah penting akan naik paling tinggi dalam peringkat, sementara node dengan banyak koneksi tetapi lemah akan tetap sederhana. Hal ini mencerminkan bagaimana pengaruh sebenarnya terakumulasi dalam sebagian besar jaringan dunia nyata, di mana frekuensi interaksi atau volume transaksi menandakan kepentingan sebenarnya.
Sejarah
PageRank diperkenalkan oleh Brin dan Page pada tahun 1998 sebagai dasar Google Search, memperlakukan semua hyperlink sebagai suara yang setara. Weighted PageRank diformalkan oleh Xing dan Ghorbani pada tahun 2004, memperluas algoritma untuk menetapkan distribusi peringkat yang proporsional dengan bobot tepi, berdasarkan fraksi bobot masuk dan keluar. Sejak itu, algoritma ini telah diterapkan di seluruh analisis kutipan, bioinformatika, analisis jaringan sosial, dan sistem rekomendasi di mana pun kekuatan tautan merupakan proksi yang bermakna untuk pengaruh.
Kapan digunakan
Gunakan Weighted PageRank ketika jaringan Anda memiliki bobot tepi yang bermakna dan Anda memerlukan peringkat node kepentingan global yang sadar aliran. Ini ideal untuk jaringan kutipan dengan jumlah kutipan bersama, graf web dengan volume lalu lintas, jaringan interaksi biologis dengan tingkat ekspresi, jaringan sosial dengan frekuensi interaksi, dan jaringan transaksi keuangan. Pilih Weighted PageRank daripada PageRank biner kapan pun mengabaikan kekuatan tepi akan salah merepresentasikan aliran pengaruh. Hindari jika bobot tepi tidak dapat diandalkan atau ditetapkan secara sewenang-wenang, ketika jaringan sangat jarang dan bobot sebagian besar biner (PageRank biasa sudah cukup), atau ketika Anda memerlukan ukuran sentralitas murni lokal seperti derajat tertimbang. Ini tidak sesuai untuk jaringan tak berarah di mana arah aliran secara konseptual tidak berarti.
Batasan dan pertimbangan
- Memerlukan bobot tepi yang bermakna dan terukur secara andal; bobot yang berisik atau sewenang-wenang menurunkan kualitas peringkat.
- Faktor redaman (d) adalah parameter bebas; nilai konvensional 0,85 mungkin tidak optimal untuk jaringan non-web.
- Sensitif terhadap skema normalisasi bobot yang dipilih; hasil dapat berbeda jika bobot masuk dan keluar digabungkan secara berbeda.
- Tidak membedakan antara jenis tepi yang berbeda; model bobot tunggal dapat meruntuhkan perbedaan struktural yang penting.
- Konvergensi bisa lambat pada jaringan yang sangat besar dan padat tanpa implementasi matriks jarang yang efisien.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Memasukkan kekuatan tepi secara langsung ke dalam propagasi kepentingan, memberikan peringkat yang lebih realistis daripada PageRank biner dalam jaringan berbobot.
- Menangkap prestise global, di seluruh jaringan, daripada hanya konektivitas lokal.
- Mempertahankan mekanisme teleportasi PageRank, membuatnya kuat terhadap node menggantung dan komponen yang terputus ketika dikoreksi.
- Menskalakan ke jaringan besar melalui komputasi iteratif yang efisien; operasi matriks jarang menjaga memori tetap dapat dikelola.
- Mudah diinterpretasikan: skor tinggi berarti sebuah node menerima dukungan berbobot kuat dari node berperingkat tinggi lainnya.
Penerapan
- Mengidentifikasi makalah atau penulis berpengaruh dalam jaringan kutipan dan kolaborasi penulisan berbobot.
- Memberi peringkat halaman web atau dokumen ketika volume lalu lintas hyperlink atau tingkat klik tersedia.
- Mendeteksi protein atau gen kunci dalam jaringan interaksi biologis berbobot.
- Memprioritaskan node dalam jaringan transaksi keuangan berdasarkan aliran volume transaksi.
- Memberi peringkat pengguna atau konten dalam graf interaksi media sosial berbobot.
- Membangun sistem rekomendasi di mana frekuensi kemunculan bersama item berfungsi sebagai bobot tepi.
Cara kerjanya
Cara kerjanya
Representasikan jaringan sebagai graf di mana setiap tepi memiliki bobot numerik yang mencerminkan kekuatan ikatan — seperti frekuensi interaksi, volume transaksi, jumlah kolaborasi penulisan, atau skor kesamaan. Algoritma ini memerlukan bobot ini bernilai non-negatif; bobot negatif harus ditransformasikan sebelum analisis.
Untuk setiap tepi berarah dari node v ke node u, hitung dua faktor bobot: faktor bobot masuk yang menormalisasi bobot tepi berdasarkan total bobot masuk u, dan faktor bobot keluar yang menormalisasikannya berdasarkan total bobot keluar v. Pecahan ini menentukan seberapa banyak peringkat v yang didistribusikan ke u melalui tepi spesifik ini.
Rumus
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}Terapkan formula Weighted PageRank secara iteratif: peringkat setiap node sama dengan suku teleportasi dasar (1 dikurangi faktor redaman d, biasanya 0,85) ditambah d dikalikan jumlah dari semua tetangga masuk dari peringkat mereka yang diskalakan oleh dua faktor bobot. Hal ini mendistribusikan peringkat secara proporsional terhadap kekuatan tepi, bukan secara seragam.
Rumus
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)Ulangi pembaruan peringkat hingga perubahan pada skor setiap node turun di bawah toleransi kecil (umumnya 1e-6). Konvergensi dijamin untuk graf yang terhubung kuat; untuk graf dengan node menggantung atau komponen terisolasi, terapkan koreksi node menggantung standar sebelum melakukan iterasi.
Setelah skor konvergen, urutkan semua node berdasarkan skor Weighted PageRank mereka dalam urutan menurun. Peringkat ini mencerminkan kepentingan struktural global setiap node yang memperhitungkan topologi jaringan dan kekuatan tepi.
Kesalahan umum
- Menggunakan bobot tepi mentah yang tidak dinormalisasi tanpa memeriksa skalanya — mencampur jumlah puluhan dengan nilai jutaan mendistorsi propagasi peringkat.
- Lupa menangani node menggantung (node tanpa tepi keluar), yang dapat menguras peringkat dari seluruh jaringan jika tidak dikoreksi.
- Mengasumsikan faktor redaman default 0,85 cocok secara universal; dalam jaringan kutipan atau biologis, nilai yang berbeda mungkin lebih baik mencerminkan domain.
- Menginterpretasikan skor Weighted PageRank sebagai probabilitas absolut daripada peringkat relatif — hanya urutannya yang stabil di berbagai putaran.
- Membandingkan skor Weighted PageRank di berbagai jaringan dengan ukuran berbeda tanpa normalisasi.
Pertanyaan yang sering diajukan
Bagaimana Weighted PageRank berbeda dari PageRank standar?
PageRank standar mendistribusikan peringkat sebuah node secara merata ke semua tetangga keluar tanpa memandang kekuatan tepi. Weighted PageRank menskalakan distribusi ini berdasarkan bobot masuk dan keluar relatif dari setiap tepi, sehingga koneksi yang lebih kuat membawa peringkat secara proporsional lebih banyak.
Faktor redaman apa yang harus saya gunakan?
Nilai konvensional adalah 0,85, berasal dari asumsi graf web tentang penjelajahan acak. Untuk jaringan sosial, biologis, atau kutipan, nilai antara 0,5 dan 0,9 dieksplorasi dalam literatur. Analisis sensitivitas pada berbagai nilai redaman direkomendasikan.
Bisakah Weighted PageRank diterapkan pada jaringan tak berarah?
Ya, dengan merepresentasikan setiap tepi tak berarah sebagai sepasang tepi berarah dengan bobot yang sama. Algoritma kemudian menghasilkan faktor bobot masuk dan keluar yang simetris, yang menyederhanakan menjadi formula yang masih menghormati kekuatan tepi.
Bagaimana cara menangani tepi dengan bobot nol?
Tepi dengan bobot nol tidak berkontribusi pada propagasi peringkat, sehingga dapat dihapus sebelum analisis. Jika bobot nol bermakna secara struktural (ketidakhadiran versus data yang hilang), dokumentasikan perbedaannya dengan jelas sebelum menghapusnya.
Apakah Weighted PageRank lebih baik dari sentralitas derajat tertimbang?
Tergantung pada pertanyaan penelitian. Sentralitas derajat tertimbang hanya menangkap koneksi langsung, sementara Weighted PageRank menangkap prestise global yang dipropagasi ke seluruh jaringan. Gunakan derajat tertimbang untuk pengaruh lokal dan Weighted PageRank untuk kepentingan di seluruh jaringan.
Metode terkait
Sumber
Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.
Buka referensi DOIDisalin.PageRank. Wikipedia.
Buka referensi publikasiDisalin.