Model grafik acak, untuk jaringan komputer nyata

Saya tertarik pada model grafik acak yang mirip dengan grafik jaringan komputer nyata. Saya tidak yakin apakah model dipelajari dengan baik ( n simpul, setiap sisi yang mungkin dipilih dengan probabilitas p ) baik untuk mempelajari jaringan komputer nyata (bukan?).$G(n,p)$$n$$p$

model grafik acak apa yang berguna untuk memahami perubahan jaringan komputer dalam praktik?

Lebih umum, model-model lain dari grafik acak terbatas (selain yang setara dengan model ) telah dipelajari dalam literatur? (Jawaban ideal akan menjadi penunjuk ke survei untuk model yang dipelajari dari grafik acak terbatas.)$G(n,p)$

Dalam beberapa tahun terakhir, studi tentang grafik acak dengan batasan struktural "alami" telah mendapatkan daya tarik. Sebagai contoh, seseorang dapat mempertimbangkan grafik planar yang diambil dari kelas semua grafik planar dengan simpul dan mempelajari bagaimana berperilaku sebagai n → ∞ . Berbeda dengan grafik acak Erd-Rényi atau model serupa lainnya, tepi dalam grafik ini sangat tergantung, jadi salah satu motivasi semu untuk mempelajari distribusi semacam itu adalah menganalisis model jaringan dengan independensi yang sangat terbatas di antara tepi.$n$$n \rightarrow \infty$

Namun, mungkin saat ini tujuan ini tampaknya cukup jauh karena independensi yang terbatas membuatnya jauh lebih sulit untuk menganalisis sifat-sifat grafik tersebut. Bahkan, beberapa pertanyaan dasar yang sangat mudah dijawab untuk , seperti distribusi urutan derajat hanya diselesaikan untuk grafik planar acak baru-baru ini.$G(n, p)$

Untuk referensi yang pasti, lihat makalah dari Konstantinos Panagiotou dan kutipan yang terkandung di dalamnya. Untuk kenyamanan, berikut adalah contoh kecil beberapa makalah yang relevan:

• Pada Gelar Distribusi Grafik Planar Acak . Konstantinos Panagiotou dan Angelika Steger . Untuk muncul dalam Prosiding Simposium ACM-SIAM Tahunan ke-22 tentang Algoritma Diskrit (SODA '11).
• Pada Properti Diseksi dan Triangulasi Acak . Nicla Bernasconi, Konstantinos Panagiotou dan Angelika Steger . Dalam Prosiding Simposium ACM-SIAM Tahunan ke-19 tentang Algoritma Diskrit (SODA '08), hal. 132-141. [http://www.mpi-inf.mpg.de/~kpanagio/Dissections.pdf]
• Pada Urutan Derajat Outerplanar Acak dan Seri-Paralel Grafik . Nicla Bernasconi, Konstantinos Panagiotou dan Angelika Steger . Dalam Prosiding Lokakarya Internasional ke-12 tentang Teknik Acak dalam Komputasi (RANDOM'08), hal. 303-316. [http://www.mpi-inf.mpg.de/~kpanagio/OPSP.pdf]

Survei ini, Struktur dan fungsi jaringan kompleks oleh Newman, mengulas teknik dan model untuk jaringan kompleks nyata termasuk konsep-konsep seperti efek dunia kecil, distribusi derajat, dan model grafik acak. Juga, penulis yang sama memiliki makalah yang bagus, grafik acak sebagai model jaringan , tentang adaptasi grafik acak untuk memodelkan jaringan nyata.

Referensi:

1) Grafik acak sebagai model jaringan, MEJ Newman, dalam Handbook of Graphs and Networks, S. Bornholdt dan HG Schuster (eds.), Wiley-VCH, Berlin (2003)

2) Struktur dan fungsi jaringan yang kompleks, MEJ Newman, SIAM Review 45, 167-256 (2003)

Jaringan komputer nyata di lapisan apa? Internet adalah, pada level AS (bisa dibilang level paling atas), sebuah jaringan dunia kecil dengan beberapa node yang sangat tinggi. Ketika lapisan semakin dekat dengan kabel aktual, grafik menjadi lebih terkait dengan geografi dan kurang terkait dengan lapisan sosial (sosial adalah jenis kata yang salah - apakah itu benar-benar jaringan sosial ketika entitas yang menjadi "teman" adalah perusahaan multinasional?) . Dalam kasus ekstrem, ethernet lokal adalah pohon logis yang (mungkin) merupakan subgraph dari pola fisik koneksi kawat, dan bahwa pola koneksi kawat mungkin tidak terlalu banyak kabel lebih dari pohon.

"Jaringan komputer sungguhan" memiliki banyak rasa dan lapisan. Beberapa dari mereka terlihat seperti jejaring sosial, beberapa tidak. Untuk informasi lebih lanjut tentang ini, saya dengan tidak hormat merujuk Anda ke bab 2 disertasi saya - http://home.manhattan.edu/~peter.boothe/thesis.pdf

$n$$u$$v$$\beta e^{-d/(L\alpha)}$$d$$L$

Waxman, Routing koneksi multipoint , IEEE J. Select. Area Komunal. 6 (9), 1617-1622, 1988. Zegura, Calvert, Bhattacharjee, Cara Membuat Model Internetwork , Proc. IEEE INFOCOM '96, 1996.

Walter Willinger telah membangun karier pada penggunaan grafik bebas skala untuk memodelkan jaringan. Ada terlalu banyak untuk dikutip, jadi saya akan mengarahkan Anda ke entri DBLP-nya . Titik kunci dalam model ini adalah bahwa mereka memiliki properti yang mirip dengan jaringan "nyata" yang tidak ditangkap oleh G (n, p).

Anda mungkin ingin memeriksa buku Durrett . Saya yakin Anda harus banyak membaca.

Alih-alih dengan susah payah menemukan, membenarkan, dan menganalisis model tertentu, Anda mungkin ingin menggunakan data kehidupan nyata apa yang Anda miliki (jika ada). Itu berarti mendefinisikan model probabilistik umum dan melatih parameternya memberikan data Anda (misalnya dengan estimasi kemungkinan maksimum).

$S \rightarrow p_1 : (S)S \mid p_2 : \varepsilon$$p_1, p_2$

Jelas, tata bahasa spesifik dapat (dan seharusnya!) Menggunakan pengetahuan domain. Pertimbangkan misalnya tata bahasa yang berbeda yang digunakan untuk prediksi struktur sekunder RNA di Dowell, Eddy (2004) untuk rasa.

Temukan beberapa detail tentang teknik ini di Weinberg, Nebel (2010) . Saya tidak tahu bagaimana (well) itu dapat diterapkan pada grafik umum.

Jika Anda membutuhkan lebih banyak kekuatan, Anda dapat pindah ke hal-hal seperti CFG multidimensi (S) (misalnya Seki, Kato (2008) ) atau SCFG yang bergantung pada posisi / panjang ( Weinberg, Nebel (2010) ).

$G(n,p)$$G(n,m)$

Seperti yang mungkin Anda ketahui, tampaknya ada perbedaan antara grafik konektivitas untuk World Wide Web dan menentang grafik konektivitas untuk infrastruktur Internet. Saya tentu saja tidak mengklaim sebagai seorang ahli, tetapi saya telah melihat kertas Li, Alderson, Tanaka, Doyle dan Willinger "Menuju Teori Grafik Skala-Bebas: Definisi, Properti, dan Implikasi" yang memperkenalkan metrik-a 'untuk mengukur' skala-kehijauan 'grafik (dengan definisi grafik bebas skala masih dalam perdebatan sejauh yang saya tahu) yang mengklaim memiliki model grafik yang membuat grafik yang mirip dengan konektivitas internet di router. tingkat.

Berikut adalah beberapa model generatif yang mungkin menarik:

Karya Berger, Borgs, Chayes, D'Souza dan Kleinberg "Lampiran Preferensial yang Diinduksi Kompetisi"

Carlson dan Toleransi Doyle yang Sangat Dioptimalkan: Mekanisme untuk Hukum Kekuasaan dalam Sistem yang Dirancang

Molloy dan Reed's A Critical Point untuk Grafik Acak dengan Urutan Derajat yang Diberikan yang memperkenalkan "Model Konfigurasi yang Dihapus"

Clustering Newman dan lampiran preferensial dalam jaringan yang sedang tumbuh (yang telah disebutkan sebelumnya)

Orang juga bisa secara eksplisit menghasilkan distribusi derajat dan membuat grafik dengan cara ini, tetapi tidak jelas bagi saya seberapa dekat ini memodelkan grafik internet pada tingkat router.

Tentu saja, ada lebih banyak literatur tentang masalah ini dan saya hanya memberikan beberapa (yang saya anggap sebagai) sorotan.

$G(n,p)$$G(n,m)$) tidak bekerja secara tepat karena gelar bebas skala atau hukum kekuasaan mendistribusikan grafik acak yang menyimpang momen kedua dalam distribusi derajat. Saya tidak mengklaim cukup tahu tentang subjek untuk secara kategoris membuat klaim tentang "sebagian besar" bukti, tetapi dari apa yang saya lihat, salah satu dari beberapa baris pertama bukti untuk properti pada grafik acak Erdos-Renyi secara eksplisit mengasumsikan terbatas. momen kedua dalam distribusi gelar. Dari sudut pandang saya, ini masuk akal sebagai momen kedua yang terbatas membuat grafik Erdos-Renyi jauh lebih mirip pohon secara lokal (lihat Informasi, fisika, dan perhitungan Mertens dan Montanari)) yang secara efektif memberikan sifat / jalur / struktur independensi. Karena grafik acak terdistribusi tingkat hukum memiliki momen kedua yang berbeda, struktur mirip pohon lokal ini dihancurkan (dan karenanya memerlukan teknik pembuktian yang berbeda?). Saya akan senang jika intuisi ini tidak berlaku jika seseorang dengan pengetahuan atau wawasan lebih banyak menunjukkan mengapa hal ini tidak terjadi.

Semoga itu bisa membantu.

Meskipun itu adalah topik lama saya membalas karena ada banyak orang yang masih mengunjungi posting seperti itu. Saya termotivasi dari komentar di balasan lain.

Model Barabasi-Albert dan model lain yang menghasilkan grafik bebas skala telah diusulkan untuk memodelkan Internet pada tingkat router dan pada tingkat sistem otonom. Meskipun awalnya model-model semacam itu di mana dianggap akurat ternyata kami tidak memiliki gambar lengkap dari topologi internet karena kesulitan dalam menemukan semua tautan. Meskipun diyakini sebagai ekor yang berat, itu cukup banyak pekerjaan yang sedang berlangsung.

Untuk referensi Anda, Anda dapat membaca: RG Clegg, C Di Cairano-Gilfedder, S Zhou, Pandangan kritis pada pemodelan hukum daya Internet

Ada beberapa buku tentang grafik acak, seperti Bollobás 'Book dan ada beberapa model grafik acak seperti tautan wikipedia dunia kecil atau tautan wikipedia lampiran preferensial , untuk memodelkan jaringan dengan jarak kecil antara komputer atau yang dengan distribusi derajat mengikuti hukum kekuatan masing-masing.

Saya pikir tidak ada cara mudah untuk memodelkan jaringan komputer nyata, tapi saya cukup yakin bahwa G (n, p) tidak akan memodelkannya dengan sangat baik. Kecuali jika Anda bekerja dengan jaringan terorganisir yang sangat spesifik.

Rekomendasi saya adalah makalah survei yang ditulis oleh penemu generator grafik acak R-MAT. http://portal.acm.org/citation.cfm?id=1132954

Generator grafik acak R-MAT sangat sederhana dan banyak digunakan. Sebagai contoh, generator ini diadopsi dalam benchmark Graph500 ( http://www.graph500.org/ ).