Properti Grafik Diarahkan Acak dengan Fixed Out-Degree

Saya tertarik pada properti grafik berarah acak dengan tingkat out-fix $d$ . Saya membayangkan model grafik acak di mana setiap simpul memilih tetangga d (katakanlah, dengan penggantian) uar

Pertanyaan : Adakah yang diketahui tentang distribusi stasioner dan waktu pencampuran jalan acak pada grafik acak ini (untuk berbagai nilai )? $d$

Saya sangat tertarik pada kasus di mana , yang sesuai dengan model automata acak atas alfabet Boolean. (Ya, saya menyadari grafik ini sering tidak terhubung, tetapi apa yang terjadi pada komponen tertentu?) Saya senang dengan hasil parsial dan hasil tentang sifat-sifat lain dari grafik ini. $d = 2$

Tampaknya sebagian besar literatur tentang grafik acak berfokus pada model Erd-Rényi, yang memiliki sifat yang sangat berbeda dari model yang saya pikirkan.

graph-theory co.combinatorics automata-theory random-walks Lev Reyzin
sumber

Saya dapat menawarkan ini: jika Anda mencari frasa "koefisien pengelompokan" Anda mungkin menemukan lebih banyak literatur yang berhubungan. Saya memutuskan untuk tertarik pada hal-hal lain, jadi saya tidak ingat secara spesifik.

Aaron Sterling

Anda harus berburu untuk model grafik web (mulai dengan kertas Aiello / Chung ( projecteuclid.org/… ) dan teruskan maju). Mungkin Anda akan menemukan model grafik web yang menarik. Lihat juga karya terbaru Christos Faloutsos

Suresh Venkat

terima kasih untuk penunjuknya - saya telah melihat karya Chung dan tulisan ini - walaupun mereka mempertimbangkan model yang menarik, sayangnya mereka tidak menganggap

karya

Anda menyarankan proses terjadi dengan penggantian. Apakah ini berarti Anda mengizinkan multidigraf (dengan kemungkinan beberapa busur dari s ke t)?

András Salamon

Itu benar - dalam perjalanan acak Anda mengambil masing-masing sisi yang dapat dilengkapi, dan dengan beberapa busur, Anda meningkatkan kemungkinan transisi yang diberikan (dan kami juga memungkinkan loop sendiri). Namun, jika Anda ingin menjawab pertanyaan untuk memilih tepi tanpa penggantian, itu juga bagus.

Lev Reyzin

Jawaban:

Dalam kasus tidak berarah, grafik acak reguler adalah ekspander dengan probabilitas tinggi (bukan untuk , tapi saya pikir sudah mencukupi), yang menyiratkan bahwa waktu pencampuran jalan acak adalah . Saya tidak cukup ingat tentang bukti-bukti ini untuk mengetahui apakah semuanya berjalan dalam kasus yang diarahkan (tentu beberapa sifat berbeda: distribusi seragam tidak lagi stasioner), tetapi mungkin layak untuk dilihat. Referensi yang baik untuk grafik expander adalah Expander Graphs dan Aplikasi mereka oleh Hoory, Linial, dan Wigderson dan Pseudorandomness oleh Vadhan. $d$ $d=2$ $d \ge 3$ $O(\log n)$

Ian
sumber

Terima kasih - ini adalah referensi yang bagus. Saya telah melihat pekerjaan ini sebelumnya tetapi melupakannya. Tentunya layak melalui bukti mereka.

Lev Reyzin

Apakah Anda tahu tentang karya berikut (dan referensi di dalamnya)? (Ini juga tersedia di arXiv.)

Bohman, T. dan Frieze, A. (2009), siklus Hamilton dalam 3-out. Struktur & Algoritma Acak, 35: 393–417. doi: 10.1002 / rsa.20272

RJK
sumber

terima kasih - ini hasil yang menarik, tetapi memiliki siklus Hamiltonian jauh dari jenis properti yang saya pikirkan.

Lev Reyzin

Hm, mungkin saya mengambil "Saya senang dengan hasil parsial dan hasil tentang sifat-sifat lain dari grafik ini" terlalu harfiah. Bagi saya, sepertinya model k-out sangat dekat dengan model yang Anda minati dan menyelidiki hasil masa lalu pada k-out akan membuahkan hasil, terutama mengingat bahwa Hamiltonicity dan pencampuran cepat dapat dianggap sebagai bentuk konektivitas yang diperkuat di model grafik acak.

RJK

Anda benar - ini memang hasil tentang properti grafik ini, dan mungkin yang berguna. Saya tidak bisa memberikan jawaban yang diterima, tetapi tentu saja jawaban yang

positif

Apakah Anda masih mencari masalah? Makalah ini sebenarnya sedikit relevan: Alan Frieze, Páll Melsted dan Michael Mitzenmacher, " Analisis Random-Walk Cuckoo Hashing ", 2009.

Kaveh
sumber

apakah Anda memiliki tautan untuk itu?

Suresh Venkat