Grafik alami yang tidak bebas skala

8

Sekarang menjadi pengamatan yang terkenal bahwa banyak struktur grafis yang muncul dalam pengaturan alami cenderung mematuhi sifat bebas skala, seperti hukum kekuatan distribusi derajat.

Adakah contoh bagus grafik alami yang cukup acak dan tidak serta-merta mematuhi sifat bebas skala?

Arnab
sumber

Jawaban:

7

Topologi jaringan jaringan ad hoc nirkabel dan jaringan sensor nirkabel sering ditangkap oleh grafik geometri acak. Ini berarti, mengambil titik acak dalam domain planar, dan menghubungkan dua titik yang berada dalam ambang jarak tertentu. Grafik ini memiliki distribusi tingkat Poisson, meskipun mereka sangat berbeda dari grafik acak Erdos-Renyi, dan mereka muncul secara alami sebagai model jaringan.

Andras Farago
sumber
3

Meskipun saya tidak yakin apa yang Anda maksud dengan "acak", grafik alami non-skala bebas yang jelas adalah jaringan jalan.

Snowie
sumber
Nah, acak dalam arti bahwa simpul akan datang secara acak dan melampirkan kepada orang lain mengikuti beberapa distribusi probabilitas (mungkin tersembunyi).
Arnab
6
Sebenarnya, jaringan jalan bebas skala, jika dilihat dengan tepat. Jelas representasi alami tidak, karena sebagian besar persimpangan memiliki derajat paling banyak 4 atau kadang-kadang 5 atau jarang 6. Tetapi jika Anda mengambil representasi ganda - simpul untuk setiap jalan, dan tepi di antara mereka jika jalan pernah bertemu - Anda mendapatkan jaringan bebas-skala: cs.unm.edu/~treport/tr/05-10/RoadNetworks.pdf .
Joshua Grochow