Bagaimana Algoritma Unfolding Cepat Mengesan Komuniti dalam Rangkaian Besar

Analisis rangkaian sosial melibatkan mengkaji corak dalam rangkaian kehidupan nyata yang besar yang terdiri daripada berjuta-juta nod. Sekiranya anda mempunyai pengetahuan asas mengenai teori grafik, anda boleh melakukan analisis ini.

Dunia digital telah membuka cara yang sama sekali berbeza untuk menjalin hubungan. Ini juga melepaskan sejumlah data yang dapat kita analisis untuk mendapatkan pemahaman yang lebih baik tentang tingkah laku manusia.

Data media sosial merujuk kepada semua pandangan dan maklumat mentah yang dikumpulkan dari aktiviti media sosial seseorang individu. Kita boleh membuat rangkaian dari aktiviti media sosial ini untuk mendapatkan persepsi yang lebih baik terhadap individu tersebut.

Rangkaian ini boleh merangkumi secara meluas dan mungkin merangkumi rakan Facebook anda, produk yang baru anda beli di Amazon, tweet yang anda suka atau retweet, makanan kegemaran anda yang anda pesan dari Zomato, carian yang anda buat di Google, atau gambar yang baru anda sukai di Instagram .

Syarikat menggunakan rangkaian ini untuk mengklasifikasikan penggunanya ke dalam kumpulan yang berbeza. Ini membantu mereka

  • melakukan penyelidikan pasaran
  • menjana petunjuk
  • melayani pelanggan mereka dengan lebih baik
  • cari dan kongsi foto dan video
  • menemui dan membincangkan kandungan tren
  • berkongsi maklumat mengenai perkhidmatan dan restoran
  • berhubung dengan orang lain dengan minat atau hobi bersama
  • dan banyak lagi.

Senarai ini hampir tidak berkesudahan.

Sebelum kita masuk ke dalam rumpai, mari kita cepat membezakan perbezaan antara komponen rangkaian yang berbeza.

Apa itu Rangkaian?

Rangkaian adalah jaringan hubungan peribadi yang saling berkaitan. Sebagai contoh, individu yang berbeza dapat berkomunikasi antara satu sama lain dalam kumpulan media sosial melalui jaringan hubungan yang dinamik.

Rangkaian terdiri daripada nod (pelaku individu, orang, atau perkara dalam rangkaian) dan ikatan , tepi , atau pautan (hubungan atau interaksi) yang menghubungkannya.

Apa itu kumpulan?

Reicher SD dalam Penentuan tingkah laku kolektif menggambarkan kumpulan sebagai kumpulan individu yang menganggap diri mereka sebagai kumpulan. Anggota kumpulan yang sama mempunyai sekumpulan kepercayaan dan tingkah laku bersama.

Apa itu komuniti?

Menurut David W. McMillan ( Sense of Community: A Definition and Theory ) , komuniti boleh didefinisikan sebagai berikut:

" Rasa Komuniti adalah perasaan yang dimiliki oleh anggota, perasaan bahawa anggota penting antara satu sama lain dan kumpulan, dan kepercayaan bersama bahawa keperluan anggota akan dipenuhi melalui komitmen mereka untuk bersama. "

Komuniti atau sub-unit adalah sub-rangkaian dalam rangkaian yang merupakan nod yang saling berkaitan.

Komuniti menunjukkan adanya struktur dalaman yang mempunyai ciri khas atau memainkan peranan yang sama dalam rangkaian.

Kumpulan individu atau objek yang sangat berkaitan di dalam rangkaian ini adalah komuniti. Biasanya terletak di titik persimpangan rangkaian dan kumpulan.

Sekarang kita mempunyai idea yang jelas tentang rangkaian, kumpulan, dan komuniti, mari kita selami lebih mendalam bagaimana rangkaian ini dibahagikan kepada komuniti kecil.

Kami akan melihat Algoritma Fast Unfolding yang popular . Vincent C. Blondel dan pengarang bersama makalah ini membandingkan algoritma ini dengan algoritma pengesanan komuniti yang lain. Mereka mendapati bahawa algoritma ini mengatasi setiap algoritma lain dalam rangkaian besar.

Apa itu Algoritma Cepat Membongkar?

Algoritma Fast Unfolding digunakan untuk mengenal pasti komuniti bahasa dalam rangkaian telefon bimbit Belgia yang berjumlah 2.6 juta pelanggan.

Ia juga digunakan untuk menganalisis grafik web 118 juta nod dan lebih dari satu bilion pautan.

Mengenal pasti komuniti dalam rangkaian yang begitu besar hanya mengambil masa 152 minit. Jadi algoritma ini cepat dan cekap.

Bagaimana algoritma berfungsi

Algoritma berfungsi dalam dua fasa:

Fasa 1

  1. Tetapkan komuniti yang berbeza untuk setiap nod dalam rangkaian.
  2. Kemudian, untuk setiap nod, saya mempertimbangkan node j dan menilai keuntungan dalam modulariti dengan membuang node i dari komunitinya dan meletakkannya di komuniti j.
  3. Node i ditempatkan dalam komuniti yang memperoleh modulariti maksimum, tetapi keuntungan harus positif. Sekiranya keuntungan negatif, maka node i tetap berada dalam komuniti yang sama.

Fasa 2

  1. Fasa kedua algoritma terdiri dalam membina rangkaian baru yang nodenya sekarang adalah komuniti yang dijumpai pada fasa pertama. Oleh itu, kami membina nod dengan menggabungkan semua nod dalam komuniti sebagai satu nod.
  2. Berat pautan antara node diberikan dengan jumlah berat pautan antara nod dalam dua komuniti yang sepadan.
  3. Hubungan antara nod komuniti yang sama membawa kepada gelung diri untuk komuniti dalam rangkaian baru.
  4. Ulangi Fasa 1 sehingga tiada peningkatan yang dapat dicapai.

Bagaimana Pengiraan Modulariti dikira

Kualiti Partition ( Q ) diukur dengan Modularity (aka modularity partition). Ini adalah nilai skalar antara -1 dan 1, dan mengukur kepadatan pautan di dalam komuniti berbanding dengan hubungan antara komuniti.

The Gain dalam Suai (ΔQ) yang diperolehi dengan menggerakkan nod terpencil i ke dalam C masyarakat dengan mudah boleh dikira dengan:

Σin adalah jumlah berat pautan di dalam C.

Σtot adalah jumlah berat pautan yang berlaku ke nod di C.

ki adalah jumlah berat pautan dari i ke nod di C.

m adalah jumlah berat semua pautan dalam rangkaian.

Keuntungan dalam Modulariti dinilai dengan membuang i dari komunitinya dan kemudian memindahkannya ke komuniti jiran. Sekiranya keuntungan positif maka simpul tersebut dimasukkan ke dalam komuniti jiran.

Aliran algoritma kering

Di rangkaian di sebelah kiri (15 node), pertama-tama kami menetapkan komuniti unik untuk setiap nod. Kemudian, kami menilai Modulariti setiap nod dan menetapkan semula komuniti berdasarkan keuntungan. Ini dipanggil Pengoptimuman Modulariti .

Pada fasa seterusnya, kami membina nod dengan menggabungkan semua nod dalam komuniti tersebut menjadi satu nod. Dalam komuniti hijau, kami mempunyai 5 simpul dan terdapat 7 tepi di antara mereka.

Oleh itu, setelah Gabungan Komuniti , berat gelung diri dari nod hijau akan menjadi 14 (7 * 2 kerana ia adalah pautan dua arah). Begitu juga, berat gelung diri dari nod merah akan menjadi 16, simpul biru akan menjadi 4, dan simpul biru muda akan menjadi 2.

Berat tepi antara nod hijau dan biru akan menjadi 4 kerana terdapat sejumlah 4 tepi antara komuniti hijau dan biru selepas Pengoptimuman Modulariti.

Pada langkah seterusnya, kami menilai semula Modulariti untuk nod baru dan melakukan proses yang sama sekali lagi.

Akhirnya, kami mendapat dua komuniti, Hijau dan Biru Muda. Komuniti Hijau mempunyai 26 gelung diri kerana terdapat sejumlah 13 tepi antara nod komuniti hijau. Dan kami mempunyai 12 kelebihan dalam komuniti biru muda, sebanyak 24 gelung diri.

Kelebihan algoritma

  1. Langkahnya intuitif dan mudah dilaksanakan dan hasilnya tidak diawasi.
  2. Algoritma ini sangat pantas. Simulasi komputer pada rangkaian modular yang sangat besar menunjukkan bahawa kerumitannya adalah linear pada data biasa dan jarang. Ini mungkin kerana Keuntungan Modulariti mudah dihitung dan jumlah komuniti menurun secara drastik hanya setelah beberapa hantaran.

Batasan algoritma

  1. Pengoptimuman modulariti gagal mengenal pasti komuniti yang lebih kecil daripada skala tertentu. Oleh itu, ini menyebabkan had penyelesaian pada komuniti yang dihitung menggunakan pendekatan pengoptimuman modulariti murni.
  2. Untuk rangkaian kecil, kebarangkalian dua komuniti yang terpisah dapat digabungkan dengan memindahkan setiap nod sangat rendah.

Kesimpulannya

Sekiranya anda bertahan di sana selama ini ... terima kasih! Saya harap ada maklumat berharga untuk anda.

Oleh itu, sekarang anda tahu bagaimana Algoritma Unfolding Cepat berfungsi, dan sangat berkesan untuk mengesan komuniti dalam rangkaian yang sangat besar.

Cara mengira Gain in Modularity menjadikan algoritma mengatasi setiap algoritma lain di luar sana. Tinggalkan saya nota jika anda merasa berguna atau mempunyai pertanyaan susulan.

Terima kasih untuk membaca!