Harmonic Centrality vs PageRank: Menyelam Lebih Dalam
Pembicara Internet Marketing – Baru-baru ini, sebuah posting diterbitkan di Search Engine Journal, yang ditulis oleh Aysun Akarsu , tentang pengertian Harmonic Centrality – salah satu dari beberapa ukuran kedekatan, atau sentralitas, ke titik-titik penting dalam teori grafik.
Karya ini membahas kelayakan ukuran ini sebagai algoritma peringkat alternatif yang potensial untuk PageRank – dalam teori grafik, node dan edge seperti halaman web dan tautan.
Menarik & Wawasan
Saya pikir karya itu luar biasa – sangat mendalam, dan menggugah pikiran.
Karya itu membuat saya penasaran, jadi saya pergi ke Google Cendekia untuk menjalankan beberapa pencarian di “sentralitas harmonik” dan mencari tahu lebih banyak.
Makalah Lainnya Menyentuh Harmoni Sentralitas
Saya menemukan beberapa kertas yang sepertinya juga relevan untuk itu (salah satunya dikutip oleh Akarsu):
- Aksioma untuk Sentralitas
- Struktur grafik di web ditinjau kembali – tipuan dari ekor yang berat
- Struktur Grafik di Web – Dianalisa pada Berbagai Tingkat Agregasi
Beberapa dari makalah ini tampaknya cukup tua dan mereka tidak memiliki banyak kutipan (tentu saja tidak dalam kisaran ribuan), yang membuat saya berpikir bahwa ini belum dilaksanakan pada skala (yaitu, diadopsi oleh mesin pencari utama belum ), karena lebih banyak referensi, terutama karena mereka menyamakannya dengan PageRank.
Aksioma untuk Sentralitas
Salah satu hasil yang dikembalikan dalam Google Cendekia telah dikutip dalam artikel oleh Akarsu – makalah penelitian 2013 oleh Paolo Boldi dan Sebastiano Vigna berjudul ‘Aksioma untuk sentralitas’.
Pekerjaan mereka dilakukan sebagai bagian dari studi analisis grafik tautan yang membandingkan berbagai metode algoritmik dan keefektifan keluarannya ketika berusaha memahami simpul paling penting dalam jaringan, memanfaatkan “sentralitas”.
Indeks Sentral Tujuan Umum?
Sementara penelitian ini, khususnya, dilakukan pada jejaring sosial, untuk mengidentifikasi poin-poin terpenting dalam jejaring, menurut Boldi dan Vigna, mereka mengklaim dalam temuan mereka bahwa Harmonisasi Sentral berpotensi diperluas sebagai indeks sentralitas tujuan umum untuk grafik yang diarahkan sewenang-wenang, dan seperti yang dikutip Akarsu:
“Hasil kami menunjukkan bahwa langkah-langkah sentralitas berdasarkan jarak, yang pada tahun-tahun terakhir telah diabaikan dalam pengambilan informasi yang mendukung langkah-langkah sentralitas spektral, memang memberikan sinyal berkualitas tinggi; selain itu, Harmonic Centrality muncul sebagai indeks sentralitas tujuan umum yang sangat baik untuk grafik yang diarahkan sewenang-wenang. ”(Boldi & Vigna, 2013).
Boldi dan Vigna juga menemukan:
“Anehnya, hanya ukuran sederhana baru berdasarkan jarak, sentralitas harmonik, ternyata memuaskan semua aksioma; pada dasarnya, sentralitas harmonik adalah koreksi terhadap sentralitas kedekatan klasik Bavelas yang dirancang untuk memperhitungkan node yang tidak terjangkau dengan cara yang alami. ”
Profesor Ricardo Baeza-Yates
Penasaran lebih lanjut, saya menghubungi Profesor Ricardo Baeza-Yates , untuk bertanya apa pendapatnya tentang gagasan sentralisasi harmonis sebagai alternatif untuk PageRank, karena saya pikir akan bermanfaat untuk mendapatkan pendapat tambahan.
Saya bertanya kepada Baeza-Yates karena ia adalah penulis ‘Pengambilan Informasi Modern’, sebuah buku teks inti tentang pencarian informasi (dikutip lebih dari 17.000 kali oleh akademisi dan praktisi industri dari dunia insinyur pencarian), dan juga mantan Wakil Presiden Penelitian di Yahoo Labs.
Biaya Komputasi
Pikiran awal Baeza-Yates adalah bahwa, (berkaitan dengan biaya komputasi yang terlibat):
“Masalah pertama saya adalah menghitung ukuran sentralitas dalam grafik besar SANGAT mahal karena itu bukan ukuran penghubung lokal.”
Karena itu, pikirannya adalah bahwa sentralitas harmonis akan lebih lambat untuk dihitung daripada PageRank.
Saya berbagi artikel Akarsu dengannya, yang dia jawab, setelah membaca:
“Artikel yang menarik, menurut ini semudah menghitung PageRank. Saya tahu Paolo (Boldi) dan Sebastiano (Vigna). Saya akan meminta mereka terlebih dahulu. “
Baeza-Yates merujuk pada penelitian ‘Aksioma Sentralitas’ yang dikutip oleh Akarsu dalam artikel tersebut. Karena dia tahu penulis, dia akan membahas makalah, teori, dan eksperimen dengan Boldi dan kembali padaku.
Saya juga bertanya kepada Baeza-Yates tentang hal berikut terkait dengan ukuran dataset, karena sepertinya masuk akal bahwa mungkin ada nilai untuk proyek yang lebih kecil tidak sebesar web itu sendiri – misalnya, dalam situs perusahaan (atau lebih kecil):
“Bagaimana kalau di dalam situs individu misalnya, menghitung sesuatu yang mirip dengan PageRank dalam domain itu sendiri? Saya berpikir dari perspektif ekuitas internal secara lokal, katakanlah di situs besar (misalnya 1 juta + halaman), daripada skala web. Mungkin ini dapat memiliki nilai bagi situs perusahaan untuk mendapatkan gagasan kekuatan di berbagai bagian situs dengan ukuran ini? “
Situs web Adalah Pohon
Tanggapan Baeza-Yates:
“Situs web adalah pohon yang sangat berbeda dari struktur web biasa di tingkat domain. Untuk situs web akan lebih baik untuk menentukan ukuran yang sama sekali baru yang tidak terkait dengan sentralitas tetapi lebih banyak tentang jarak ke root, kohesi semantik, dll. Misalnya, apakah ada yang tahu apa yang sebenarnya menjadi ciri khas situs web yang bagus? Struktur tautan apa yang harus dimilikinya? ”
Tanggapan saya:
“Saya melihat banyak pendapat berbeda tentang struktur situs yang optimal – datar atau dengan kategori hierarki dan silo. Saya lebih suka hierarkis diratakan melalui halaman lompatan untuk mempersingkat jalur klik dan tautan saudara serta hubungan anak. Ada orang lain yang bersikeras dengan silo topikal. “
Ikatan Dasi Web
Pada topik grafik tautan dari web itu sendiri (dan struktur web secara keseluruhan), saya mengajukan pertanyaan apakah Baeza-Yates menganggap bentuk web masih seperti bowtie dari “The Bowtie of The Web ”
“Bowtie dari web” berasal dari makalah tahun 2000 oleh Broder et al, Graph Structure in the Web (dikutip oleh ribuan, dan jika Anda belum membacanya, ini adalah bacaan yang disarankan).
Titik sentral pada bowtie adalah “komponen yang sangat terhubung” (titik sentral dengan banyak tautan masuk dan keluar).
Baeza-Yates menegaskan:
“Itu masih harus dasi kupu-kupu. Ada sebuah makalah yang menunjukkan bahwa situs web IBM yang sangat besar juga memiliki struktur ini tetapi juga memiliki karakteristik lain (dan kertas lama sekarang, lebih dari 10 tahun). Saat ini sebagian besar situs web sepenuhnya dinamis atau persentase yang besar adalah dinamis dan itu juga menyiratkan struktur tautan yang berbeda., Sehingga strukturnya tidak begitu penting. Yang penting adalah kemampuan menemukan! ”
Dia juga mengklarifikasi pertanyaan saya tentang Harmonic Centrality dari perspektif jarak:
Pertanyaan saya:
“Jika saya tidak salah, sentralitas harmonik tampaknya hanya menjadi ukuran jarak dari komponen yang terhubung kuat?”
Jawabannya:
“Ini adalah ukuran ‘jarak terbalik’ (itulah sebabnya disebut harmonis, karena ini berasal dari rata-rata harmonik) dari semua node lain yang terhubung ke sebuah node, jadi semuanya harus berada dalam komponen yang terhubung. Jika diameternya terlalu besar, jalur lengkapnya akan terlalu panjang. Di sisi lain, saat Anda menambahkan ketentuan berat proporsional dengan 1 / jarak, kontribusi lebih kecil setiap kali (tetapi tidak dapat diabaikan karena jumlah 1 / i tidak konvergen, seperti yang tumbuh seperti log (n)), di mana n adalah jumlah istilah dalam jumlah. Ini adalah satu perbedaan utama dengan PageRank, di mana setiap kali Anda mengalikan dengan q dan q ^ i berkurang jauh lebih cepat daripada 1 / i. ”
Eksperimen untuk Membandingkan: Pagerank vs. Harmonic
Sementara itu Baeza-Yates telah mengajukan pertanyaan tentang biaya komputasi pada dataset yang lebih besar dengan Boldi, percaya bahwa Harmonic Centrality akan lebih lambat untuk dihitung, yang kemudian melakukan percobaan sebagai hasil dari diskusi dan melaporkan sebagai berikut:
“Paolo Boldi dan Sebastiano Vigna menjalankan percobaan singkat pada dataset web kecil (84 juta halaman). PageRank dengan alpha = 0,85 membutuhkan perhitungan 1 jam untuk mendapatkan norma L1 yang selisihnya lebih kecil dari 10 -6) , sedangkan sentralitas harmonik membutuhkan 14 jam (untuk deviasi standar 4,6 persen). Katakanlah satu urutan lebih besar (meskipun mungkin demikian, standar deviasi yang lebih besar bisa sama baiknya). ”
Mereka melanjutkan:
“Kualitas hasil untuk sentralitas harmonis tampaknya lebih baik. Coba situs web di bawah ini dan urutkan berdasarkan PageRank dan kemudian oleh Harmonic untuk melihat perbedaannya: http://wwwranking.webdatacommons.org/ . “
Oleh karena itu, untuk menyimpulkan, lebih lanjut ke percobaan tindak lanjut singkat oleh Boldi dan Vigna mengikuti diskusi dan komentar oleh Baeza-Yates:
“Sementara Harmonic Centrality tampaknya lebih baik untuk hasilnya, waktu komputasi jauh lebih lama.”
Eksperimen ini dilakukan karena beberapa komentar yang dibuat Baeza-Yates kepada Boldi, di mana ia percaya bahwa Harmonic Centrality akan lebih lambat untuk dikomputasi (yang tampaknya benar).
Kekhawatiran lainnya
Saya bertanya kepada Baeza-Yates apakah ada kekhawatiran dan pertimbangan lain dengan Harmonic Centrality versus PageRank, yang dia jawab:
“Saya pikir itu adalah perhatian utama (biaya komputasi). Pertanyaan lain adalah manakah yang lebih mudah melakukan spam? Saya kira sentralitas Harmonik lebih kuat karena itu tergantung pada jalur yang lebih panjang (PageRank memiliki peluruhan eksponensial sementara Harmonic Centrality memiliki peluruhan harmonis). “
Ukuran Tautan-Peringkat
Baeza-Yates juga membuat poin menarik berikut:
“PageRank dinilai berlebihan sebagai ukuran peringkat tautan dan hal yang sama berlaku untuk ukuran berdasarkan tautan apa pun karena hari ini ada begitu banyak spam tautan, sebelum kami memiliki webmaster untuk menambahkan tautan. Hari ini, siapa pun dapat menambahkan tautan. Sinyal berbasis klik adalah yang terbaik hari ini. “
Either way, Akarsu benar bahwa Harmonic Centrality adalah sesuatu yang patut dipelajari lebih lanjut. Ini tentu merupakan topik yang akan saya jelajahi lebih lanjut.
Uji sendiri PageRank versus Harmonic Centrality melalui perbandingan dengan eksperimen yang dibuat oleh Boldi dan Vigna di Web Data Commons.