Sentralitas PageRank
- Diperkenalkan oleh
- Page, Brin, Motwani & Winograd
- Tahun
- 1999
- Jenis
- Iterative link-based centrality algorithm
- Keluarga
- Centrality
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
PageRank adalah algoritma sentralitas berbasis tautan yang memberikan skor kepentingan pada setiap simpul dalam graf berarah dengan mengukur berapa banyak simpul berkualitas tinggi yang menunjuk padanya.
Diperkenalkan oleh Larry Page, Sergey Brin, Rajeev Motwani, dan Terry Winograd di Universitas Stanford pada tahun 1999, algoritma ini menjadi dasar matematis mesin pencari Google dan tetap menjadi salah satu algoritma paling berpengaruh dalam ilmu jaringan dan pengambilan informasi.
Intuisi di balik metode
Bayangkan seorang penjelajah web acak yang mengklik tautan secara acak, sesekali melompat ke halaman yang benar-benar acak alih-alih mengikuti tautan. Fraksi waktu yang dihabiskan penjelajah ini di setiap halaman, setelah klik tak terhingga, adalah PageRank halaman tersebut. Halaman yang sering dikunjungi — karena banyak halaman populer menautkannya — menerima skor tinggi. Faktor redaman (biasanya 0,85) memodelkan probabilitas melanjutkan mengklik daripada melompat.
Sejarah
PageRank dikembangkan di Universitas Stanford oleh Larry Page dan Sergey Brin sebagai mekanisme peringkat inti dari proyek mesin pencari BackRub mereka, yang menjadi Google pada tahun 1998. Laporan teknis dasar, yang ditulis bersama Rajeev Motwani dan Terry Winograd, diterbitkan pada tahun 1999. Algoritma ini mempopulerkan penggunaan sentralitas berbasis eigenvector dalam jaringan berarah skala besar dan secara langsung menginspirasi algoritma analisis tautan selanjutnya termasuk HITS dan TrustRank.
Kapan digunakan
PageRank sesuai ketika Anda perlu memberi peringkat simpul dalam graf berarah berdasarkan kepentingan struktural global, terutama ketika arah tepi mengkodekan dukungan atau pengaruh (hyperlink, kutipan, pengikut sosial). Algoritma ini mengasumsikan graf dapat dimodelkan sebagai rantai Markov dan memerlukan komponen yang terhubung atau terhubung kuat untuk konvergensi yang bersih. Algoritma ini kurang cocok untuk jaringan tak berarah di mana sentralitas HITS atau antara mungkin lebih disukai, dan dapat sensitif terhadap spam tautan atau derajat masuk yang ditingkatkan secara artifisial.
Batasan dan pertimbangan
- Memerlukan graf berarah; penerapan pada jaringan tak berarah memerlukan pilihan konvensi
- Kecepatan konvergensi bergantung pada celah spektral matriks transisi dan bisa lambat untuk graf yang terhubung buruk
- Sensitif terhadap pilihan faktor redaman d; nilai yang berbeda dapat secara substansial mengubah peringkat
- Rentan terhadap manipulasi peternakan tautan dan tautan masuk yang dibuat secara artifisial
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Dasar probabilistik yang berprinsip melalui model rantai Markov penjelajah acak
- Skalabilitas ke graf yang sangat besar melalui produk matriks-vektor jarang dan iterasi pangkat
- Menangkap topologi graf global, memberi penghargaan pada simpul yang didukung oleh simpul berperingkat tinggi lainnya
- Divalidasi secara luas di seluruh domain web, kutipan, biologis, dan jaringan sosial
Penerapan
- Peringkat mesin pencari web: mengurutkan hasil pencarian berdasarkan otoritas global halaman web
- Analisis kutipan akademik: mengidentifikasi makalah atau jurnal berpengaruh dalam jaringan literatur ilmiah
- Pengukuran pengaruh jaringan sosial: memberi peringkat pengguna berdasarkan prestise pengikut mereka
- Analisis jaringan biologis: menemukan protein hub atau gen dalam jaringan interaksi protein dan regulasi gen
- Sistem rekomendasi: menyebarkan sinyal preferensi melalui graf bipartit pengguna-item
Cara kerjanya
Cara kerjanya
Setiap simpul dalam graf dimulai dengan skor PageRank yang sama yaitu 1/N, di mana N adalah jumlah total simpul. Inisialisasi seragam ini memastikan tidak ada simpul yang memiliki keuntungan awal buatan dan menyediakan distribusi probabilitas yang valid di seluruh jaringan sebelum iterasi pertama.
Rumus
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}Matriks transisi stokastik kolom M dibangun dari struktur ketetanggaan graf. Setiap entri M_ij sama dengan 1 dibagi dengan derajat keluar simpul j jika ada tepi dari j ke i, dan nol jika tidak. Simpul menggantung (tidak ada tepi keluar) biasanya ditangani dengan mendistribusikan ulang skornya secara seragam ke semua simpul.
Rumus
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}Vektor PageRank diperbarui secara iteratif menggunakan rumus penjelajah acak. Dengan faktor redaman d (default 0,85), setiap simpul menerima probabilitas teleportasi dasar (1-d)/N ditambah d kali jumlah tertimbang dari skor yang disumbangkan oleh semua simpul yang menautkannya. Langkah ini diulang sampai skor stabil.
Rumus
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}Setelah setiap iterasi, norma L1 dari perubahan vektor skor dibandingkan dengan toleransi kecil epsilon (misalnya, 1e-6). Ketika perubahan jatuh di bawah ambang batas ini, algoritma telah konvergen dan vektor skor saat ini dikembalikan sebagai distribusi PageRank akhir.
Rumus
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilonKesalahan umum
- Mengabaikan simpul menggantung (simpul tanpa tepi keluar) dapat merusak sifat stokastik matriks transisi dan menyebabkan skor yang salah
- Menggunakan PageRank pada graf tak berarah tanpa mengonversi ke model transisi simetris dapat menghasilkan perkiraan sentralitas yang menyesatkan
- Menetapkan toleransi terlalu longgar menyebabkan konvergensi prematur; terlalu ketat meningkatkan komputasi tanpa perubahan skor yang berarti
- Menginterpretasikan PageRank sebagai metrik kepentingan absolut daripada peringkat relatif dalam konteks graf tertentu
Pertanyaan yang sering diajukan
Apa yang diwakili oleh faktor redaman d dan bagaimana seharusnya dipilih?
Faktor redaman d (biasanya 0,85) adalah probabilitas bahwa penjelajah acak mengikuti tautan daripada berteleportasi ke simpul acak. Nilai yang mendekati 1 membuat algoritma lebih sensitif terhadap struktur graf tetapi lebih lambat untuk konvergen dan lebih rentan terhadap genangan peringkat; nilai yang mendekati 0 mendekati peringkat seragam. Nilai 0,85 divalidasi secara empiris oleh Page dan Brin untuk graf web dan merupakan default standar.
Bagaimana PageRank berbeda dari sentralitas derajat?
Sentralitas derajat hanya menghitung jumlah langsung tautan masuk ke suatu simpul, memperlakukan semua sumber secara setara. PageRank memberi bobot pada setiap tautan masuk berdasarkan skor simpul yang menautkan, sehingga dukungan dari simpul berperingkat tinggi berkontribusi lebih banyak daripada dari simpul berperingkat rendah. Definisi rekursif ini menangkap struktur graf global daripada hanya konektivitas lokal.
Bisakah PageRank diterapkan pada graf tak berarah?
Ya, tetapi dengan catatan. Graf tak berarah harus dikonversi ke representasi berarah dengan mengganti setiap tepi tak berarah dengan dua tepi berarah. Skor PageRank yang dihasilkan kemudian sama dengan fungsi dari derajat simpul, mengurangi algoritma menjadi sentralitas derajat tertimbang. Untuk jaringan tak berarah, ukuran sentralitas alternatif seperti sentralitas eigenvector atau sentralitas antara seringkali lebih informatif.
Metode terkait
Sumber
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.
Buka referensi publikasiDisalin.