Apakah jejaring sosial biasanya merupakan ekspander yang baik?

11

Saya tertarik pada sifat kombinatorial jejaring sosial sebagai grafik. Orang-orang telah melihat hal-hal seperti distribusi derajat, koefisien pengelompokan dan kompresibilitas grafik ini. Satu pertanyaan mendasar adalah: Apakah grafik ini biasanya merupakan grafik expander yang bagus?

Adakah yang sudah memeriksa, katakanlah, celah spektral grafik facebook? Atau kesenjangan spektral dari jaringan dunia nyata besar lainnya? Saya berharap seseorang dapat mengarahkan saya ke arah yang benar untuk belajar tentang topik ini.

graph-theory application-of-theory expanders Zur Luria
sumber
Karena setiap langkah dalam berulang eigenvalue algoritma untuk oleh n matriks biasanya membutuhkan c n 2 langkah, grafik yang kami dapat memutuskan dengan mudah apakah mereka ekspander jauh lebih kecil daripada grafik skala web Anda bertanya tentang. Bahkan n = 10 5 adalah sebuah tantangan. Namun, jejaring sosial cukup istimewa. Pada dasarnya Anda bertanya apakah mungkin untuk memperkirakan nilai eigen dalam sesuatu seperti waktu quasilinear dan ruang quasilinear dalam n , jika grafik input jarang dan derajat verteksnya mengikuti hukum daya. nncn2n=105n
András Salamon
Huh, saya terlalu fokus pada teori. Bahkan tidak pernah terlintas dalam pikiran saya bahwa grafik facebook mungkin begitu besar sehingga mungkin tidak layak untuk menghitung celah spektralnya.
Zur Luria

Jawaban:

8

Jaringan sosial biasanya memiliki banyak simpul dengan hanya satu atau dua koneksi ke seluruh grafik. Verteks seperti itu biasanya akan menyebabkan celah spektral yang buruk.

Apa yang bisa Anda harapkan adalah perluasan vertex / edge yang bagus untuk set yang cukup besar. Namun, jika Anda memiliki komunitas yang terjalin erat dalam jaringan, maka sekali lagi Anda akan mengharapkan ekspansi rendah.

Saya tidak yakin apakah itu cukup menjawab pertanyaan Anda, tetapi makalah empiris berikut ini melihat properti mirip ekspansi di jejaring sosial. Jawabannya tampaknya bervariasi dari jaringan ke jaringan. http://fragkiskos.me/papers/expansion_SNSMW11.pdf

Saya yakin ada pekerjaan lain di luar sana di sepanjang garis ini, mungkin disamarkan menggunakan terminologi alternatif ("struktur komunitas", ukuran potong, dll).

Adam Smith
sumber
1

Grafik Power-law adalah model yang baik untuk grafik jaringan sosial. Makalah ini oleh Gkantsidis, Mihail, dan Saberi menunjukkan bahwa grafik kekuatan-hukum adalah ekspander.

Thatchaphol
sumber
Gagasan bahwa jejaring sosial didistribusikan seperti undang-undang kekuasaan baru-baru ini ditentang oleh beberapa analisis data yang sangat ketat: nature.com/articles/s41467-019-08746-5
Stella Biderman