Jumlah node yang berbeda secara acak

Waktu perjalanan dalam grafik yang terhubung didefinisikan sebagai jumlah langkah yang diharapkan dalam jalan acak yang dimulai pada , sebelum simpul dikunjungi dan kemudian simpul tercapai lagi. Ini pada dasarnya adalah jumlah dari dua kali memukul dan . $G=(V,E)$ $i$ $j$ $i$ $H(i,j)$ $H(j,i)$

Apakah ada yang mirip dengan waktu perjalanan (tidak persis sama) tetapi didefinisikan dalam hal node? Dengan kata lain, berapakah jumlah simpul berbeda yang diharapkan, jalan acak yang dimulai pada dan kembali pada saat akan mengunjungi? $i$ $i$

Pembaruan (30 September 2012): Ada sejumlah pekerjaan terkait pada jumlah situs berbeda yang dikunjungi oleh walker acak di atas kisi (yaitu, ). Misalnya, lihat: http://jmp.aip.org/resource/1/jmapaq/v4/i9/p1191_s1?isAuthorized=no $\mathbb{Z}^n$

Adakah yang pernah membaca sesuatu tentang ini?

graph-theory co.combinatorics random-walks pr.probability Fabrizio Silvestri
sumber

Apa masalah dengan argumen berikut? Jalan acak pada grafik dapat dijelaskan oleh rantai Markov di mana status adalah simpul. Demikian pula, orang dapat mewakili jalan yang sama dengan rantai Markov di mana negara dapat menjadi ujungnya. (Setiap sisi juga menyimpan info simpul yang dikunjungi saat ini.) Setelah rantai Markov diperoleh, Anda dapat menggunakan definisi / hasil rantai Markov apa pun.

Abuzer Yakaryilmaz

Terima kasih atas komentarnya. Saya benar-benar lupa mengatakan node yang berbeda . Saya akan mengubah pertanyaan sekarang.

Fabrizio Silvestri

Mungkin saya melewatkannya (maaf jika demikian), tetapi apa URL untuk posting SE?

Saya telah menghapus pos SE ... Dilarang memposting pertanyaan yang sama di dua tempat yang berbeda.

Fabrizio Silvestri

itu tergantung pada grafik tertentu, kan? dapatkah Anda membuat sketsa apa pun yang diketahui tentang masalah serupa?

vzn

Jawaban:

dari T&J bersama Anda di komentar, Anda tampaknya tertarik mempelajari sesuatu yang didefinisikan sebagai jarak tumpukan dalam rangkaian slide ini, Pada pemodelan matematika dari cache

tentukan jarak stack referensi menjadi jumlah alamat blok unik antara referensi saat ini dan referensi sebelumnya ke nomor blok yang sama.

ini memiliki beberapa analisis empiris melalui tolok ukur. katanya secara umum ada "tidak diketahui pengukuran lokalitas" permintaan cache dan kemudian mengusulkan jarak stack sebagai ukuran tersebut. itu tidak menghubungkannya dengan teori grafik acak meskipun Anda membuat sketsa koneksi seperti itu di komentar Anda. (Sepertinya ada jarak stack yang bisa dikaitkan dengan markov chain mixing ?)

tampaknya Anda tertarik untuk memodelkan kinerja cache atau algoritma pengoptimalan dengan mempertimbangkan permintaan cache sebagai simpul grafik dan tepinya sebagai transisi antara permintaan yang berdekatan. belum melihat makalah yang mempelajari struktur grafik ini. tampaknya tidak menjadi grafik acak murni dalam aplikasi nyata karena keberhasilan cache dalam praktek dan apa yang disebut sebagai lokalitas spasial dan temporal dalam slide di atas. yaitu semacam "pengelompokan" seperti joe membuat sketsa dalam jawabannya.

(mungkin ia memiliki struktur dunia kecil ?, yang cukup di mana-mana dalam data dunia nyata)

ay
sumber

Tangkapan bagus. Memang, ia memiliki struktur dunia kecil. Bahkan, dalam aplikasi yang saya miliki dalam distribusi derajat pikiran mengikuti hukum-kekuasaan. Sekarang, ini bisa membantu ... Namun, kami belum menemukan cara yang baik untuk pergi :)

Fabrizio Silvestri

Terima kasih. parameter caching apa yang Anda coba optimalkan? tampaknya itu cenderung berkorelasi langsung dengan eksponen hukum kekuasaan entah bagaimana ....? menduga bahwa pendekatan monte carlo sederhana dapat menunjukkan bahwa jarak stack terkait dengan eksponen hukum kekuasaan, dll

vzn

baik ... Pada awalnya, saya berpikir untuk mengkorelasikan k dengan dalam hukum kekuasaan. Jelas, nilai yang berbeda dari , yaitu, , harus diperlakukan secara terpisah. Saya hanya mencoba melihat apakah ada sesuatu di luar grafik hukum-kekuasaan. Sesuatu yang lebih umum, bisa dikatakan. Bagaimanapun, saya ingin memeriksa konsep jarak stack. Tidak tahu tentang itu.

α

$\alpha$

α

$\alpha$

= 1, < 1, > 1

$=1, < 1, > 1$

Fabrizio Silvestri

Sepertinya jarak stack belum dipelajari secara langsung dalam teori grafik tetapi bidangnya luas. perhatikan model watt / strogatz baik untuk pendekatan monte-carlo menghasilkan grafik dunia kecil. juga jalan acak pada grafik oleh lovasz adalah survei yang baik tentang teori jalan pada grafik acak.

vzn

Sebuah komentar: Baru-baru ini saya menghadiri ceramah oleh Bruce Reed dengan judul Catching a Drunk Miscreant , yang merupakan kerja sama dengan Natasha Komorov dan Peter Winkler. Jika Anda bisa mendapatkan hasil dari pekerjaan ini, mungkin itu dapat membantu Anda ke beberapa arah.

Secara umum, mereka membuktikan batas atas pada jumlah langkah yang dibutuhkan polisi dalam grafik umum untuk dapat menangkap perampok, ketika kita tahu perampok bergerak secara acak di sepanjang tepi.

Pål GD
sumber

Adakah kemungkinan untuk memiliki konsep atau salinan slide?

Fabrizio Silvestri

Maaf saya tidak punya apa-apa lagi untuk diberikan, tapi mungkin utas MO ini adalah untuk membantu: Polisi dan perampok mabuk .

Pål GD

Terima kasih Pål ... Saya melihat kertas yang ditautkan dari utas MO.

Fabrizio Silvestri

Ini sebenarnya bukan jawaban yang tepat untuk pertanyaan Anda, tetapi agak terlalu panjang untuk dikomentari.

Jumlah yang Anda cari akan bervariasi dari grafik ke grafik, dan akan tergantung pada situs awal walker. Jumlah yang diharapkan dari simpul-simpul perantara yang berbeda akan sangat bergantung pada pengelompokan dalam grafik, dan saya berharap jumlah yang diharapkan dari simpul-simpul perantara yang berbeda berkorelasi dengan koefisien pengelompokan .

Cluster pada dasarnya adalah subset dari verteks yang berbagi banyak sisi, sehingga setiap vertex terhubung ke sebagian besar dari verteks lain dalam cluster. Ketika walker memasuki sebuah cluster, ia kemungkinan besar akan tetap berada di wilayah itu untuk sejumlah besar hop, mungkin mengunjungi setiap node berkali-kali. Memang, menggunakan jalan acak dengan cara ini adalah salah satu teknik komputasi yang digunakan untuk mengidentifikasi cluster dalam grafik besar. Jadi untuk walker yang dimulai dalam sebuah cluster, jumlah yang diharapkan dari simpul-simpul menengah yang berbeda kemungkinan akan berskala dengan ukuran cluster dan probabilitas rata-rata meninggalkan cluster.

$N$ $\frac{1}{N}$ $N+1$

Tingkat rata-rata simpul dalam grafik juga akan memainkan peran penting, meskipun ini terkait dengan pengelompokan. Alasan untuk ini adalah bahwa ketika walker melompat ke puncak dengan derajat 1, itu harus melompat kembali ke puncak sebelumnya pada hop berikutnya. Bahkan ketika derajatnya 2, hanya ada satu jalur yang bisa diikuti melalui grafik, meskipun bisa dilalui ke arah mana pun di setiap lompatan. Di sisi lain, untuk grafik dengan derajat lebih tinggi dari 2, jumlah jalur dapat meledak, sehingga sangat tidak mungkin untuk kembali ke situs awal bahkan jika jalur terpendek antara itu kecil.

Dengan demikian Anda akan mengharapkan jumlah simpul menengah yang berbeda menjadi tinggi untuk grafik yang keduanya memiliki derajat rata-rata secara substansial di atas 2, dan juga tidak memiliki pengelompokan yang signifikan, seperti pohon.

Tentu saja komentar-komentar ini tidak lagi berlaku dalam kasus berjalan acak kuantum, tapi saya kira Anda hanya peduli dengan kasus klasik.

Joe Fitzsimons
sumber