Bagaimana cara menghitung ukuran sentralitas dalam jaringan 4 juta edge menggunakan R?

9

Saya memiliki file CSV dengan 4 juta tepi jaringan terarah yang mewakili orang yang berkomunikasi satu sama lain (mis. John mengirim pesan kepada Mary, Mary mengirim pesan ke Ann, John mengirim pesan lain ke Mary, dll.). Saya ingin melakukan dua hal:

  1. Temukan derajat, perantara, dan (mungkin) langkah-langkah sentralitas eigen untuk setiap orang.

  2. Dapatkan visualisasi jaringan.

Saya ingin melakukan ini pada command-line pada server Linux karena laptop saya tidak memiliki banyak daya. Saya telah menginstal R di server itu dan perpustakaan statnet. Saya menemukan posisi seseorang di tahun 2009 ini lebih kompeten daripada saya ketika mencoba melakukan hal yang sama dan mengalami masalah dengannya. Jadi saya bertanya-tanya apakah ada orang lain yang memiliki petunjuk tentang cara melakukan ini, sebaiknya membawa saya langkah demi langkah karena saya hanya tahu cara memuat file CSV dan tidak ada yang lain.

Hanya untuk memberi Anda ide, ini adalah bagaimana file CSV saya terlihat seperti:

$ head comments.csv
    "src","dest"
    "6493","139"
    "406705","369798"
$ wc -l comments.csv 
4210369 comments.csv
r data-visualization networks amh
sumber
untuk beberapa langkah-langkah ini apakah R dapat menanganinya atau catatan akan tergantung pada berapa banyak orang yang terpisah (node) yang dimiliki jaringan. R mungkin tidak selalu menjadi alat terbaik untuk aspek komputasi. Ada seorang pria dengan nama belakang Leskovec yang dulu di Carnegie Mellon --- saya pikir sebagai seorang mahasiswa --- yang melakukan banyak hal dengan statistik deskriptif pada grafik besar. Ada banyak utilitas di luar sana untuk "memvisualisasikan" grafik, tetapi kebanyakan saya menemukan mereka cukup sulit untuk ditafsirkan atau masuk akal. Membuat grafik distribusi derajat mungkin merupakan awal pertama.
kardinal
Bahkan merencanakan 4 juta poin mungkin perlu waktu ...
Wok
@wok, nah. Sepotong kue di komputer hari ini. Bagaimanapun, Anda selalu bisa membuang ke PNG terlebih dahulu dan itu mungkin cukup baik untuk distribusi gelar. Grafik OP sebenarnya tidak terlalu besar.
kardinal

Jawaban:

7

Apa yang Anda miliki adalah daftar tepi, yang dapat dikonversi ke objek jaringan menggunakan perpustakaan jaringan. Berikut adalah contoh menggunakan data fiktif.

library(network)

src <- c("A", "B", "C", "D", "E", "B", "A", "F")
dst <- c("B", "E", "A", "B", "B", "A", "F", "A")

edges <- cbind(src, dst)
Net <- as.network(edges, matrix.type = "edgelist")

summary(Net)
plot(Net)

Namun, ada peringatan: Anda memiliki jaringan yang sangat besar dan saya tidak yakin plot akan informatif. Mungkin akan terlihat seperti bola besar benang. Saya juga tidak yakin seberapa baik perpustakaan ini menangani set data yang besar. Saya sarankan Anda melihat dokumentasi untuk perpustakaan jaringan, statnet, dan ergm. The Journal of Software statistik (v24 / 3) penawaran beberapa artikel yang mencakup perpustakaan tersebut. Masalahnya dapat ditemukan di sini:

http://www.jstatsoft.org/v24

Jason Morgan
sumber
1
Saya ingat samar-samar peta dunia dari jaringan facebook, yang dilakukan di R. Saya pikir penulis menggambarkan prosesnya secara terperinci di blognya. Saya kira menggunakan pendekatan itu akan menghasilkan peta yang informatif bahkan dengan 4 juta node.
Owe Jessen
Permintaan maaf untuk pertanyaan naif, tetapi bagaimana cara mengubah tabel menjadi apa yang Anda miliki srcdan dst. Inilah yang biasanya saya lakukan untuk memuat file (sekarang file yang dibatasi-tab): el <- read.csv("comment-net/comments-ouids.tsv",header=T,sep="\t")
amh
read.csv () harus menghasilkan data.frame. as.network () dapat membacanya secara langsung atau Anda mungkin perlu melakukan as.matrix (el).
Jason Morgan
Saya agak skeptis tentang perpustakaan ini bisa berbuat banyak dengan grafik jutaan node. Apakah Anda benar-benar menggunakannya dengan dataset yang sebanding?
Szabolcs
Poster itu merujuk ke jaringan dengan 4 juta tepi , bukan node. Saya telah menggunakan statnetkeluarga perpustakaan di jaringan yang tidak diarahkan lebih dari 3500 node (~ 8 juta kemungkinan edge). Itu cukup bisa dilakukan, terutama ketika tujuannya hanya untuk menghitung statistik jaringan. Saya bahkan memperkirakan ERGM di jaringan sebesar ini. Tapi poin Anda diterima dengan baik; Saya ragu jaringan jutaan node dapat dengan mudah dianalisis.
Jason Morgan
3

Saya tidak berpikir bahwa R adalah pilihan pertama di sini (mungkin saya salah). Anda akan membutuhkan array besar di sini untuk mengindeks dan menyiapkan file jaringan Anda dalam format data yang sesuai. Pertama-tama, saya akan mencoba menggunakan perpustakaan SNAP Jure (Rob menyebutkannya di posting di atas) ; itu ditulis dalam C ++ dan bekerja dengan sangat baik pada jaringan besar.

Andrej
sumber
Terima kasih telah menyebutkan SNAP. Saya melihatnya. Sudahkah Anda menggunakannya? Sampel sentralitas yang menyertainya tampaknya dekat dengan yang saya inginkan. Saya mencoba memodifikasinya sehingga berfungsi dengan data grafik multi-arah saya tetapi gagal dikompilasi. Saya tidak yakin apakah pantas untuk mengajukan pertanyaan tentang hal itu di sini, jadi saya dapat membuat Q.
amh
1
@ danresmh, Anda dapat mencoba mengurangi grafik untuk memiliki satu pengamatan per pasangan yang diarahkan terlebih dahulu. Untuk hal-hal nilai eigen, data Anda mungkin serupa atau setara dengan jalan acak tertimbang pada grafik. Saya tidak yakin apakah SNAP mendukung hal itu, tetapi kemungkinan besar SNAP mendukungnya. Jika semuanya gagal, Anda mungkin mengirim email yang sangat spesifik ke Jure. Dia pria yang sangat baik, jadi saya tidak akan terkejut jika dia memberikan panduan cepat.
kardinal
@ cardinal: Saya menemukan kode sampel di SNAP yang melakukan persis apa yang saya inginkan tetapi untuk grafik yang tidak terarah. Saya pikir grafik saya adalah apa yang disebut dokumen SNAP "diarahkan multi-grafik". Jadi saya mengubah hanya satu baris centrality.cppdari TUNGraphmenjadi TNEGraph(lihat pastebin.com/GHUquJvT baris 24). Itu tidak kompilasi lagi. Saya menduga itu memerlukan jenis node yang berbeda? Kesalahan yang saya dapatkan adalah: centrality.cpp:24: error: conversion from ‘TUNGraph::TNodeI’ to non-scalar type ‘TNEGraph::TNodeI’ requested(lihat kesalahan penuh di pastebin.com/86mCbByG )
amh
3

Gephi ( http://gephi.org/ ) mungkin cara mudah untuk menjelajahi data. Anda hampir pasti dapat memvisualisasikannya, dan melakukan beberapa perhitungan (meskipun saya belum menggunakannya untuk beberapa waktu sehingga saya tidak dapat mengingat semua fungsi).

celenius
sumber
3

Dari pengalaman masa lalu dengan jaringan 7 juta node, saya pikir memvisualisasikan jaringan lengkap Anda akan memberi Anda gambar yang tidak dapat diinterpretasikan. Saya mungkin menyarankan visualisasi yang berbeda menggunakan himpunan bagian dari data Anda seperti hanya menggunakan 10 node teratas dengan tautan paling banyak masuk atau keluar. Saya saran kedua celenius tentang penggunaan gephi.

Zubin
sumber
@andresmh, Maslov dan Sneppen ( Science , 2002) memiliki visualisasi yang mungkin berguna dalam konteks ini. Mencari melalui statistik terkini / kutipan yang berhubungan dengan karya ini, saya menemukan ini juga. Ini mungkin pekerjaan terkait lainnya.
kardinal
1

Jika Anda khawatir dengan ukuran jaringan, Anda bisa mencoba igraphpaket dalam R. Dan jika itu berkinerja buruk di dalam R, mungkin lebih baik sebagai modul Python. Atau bahkan networkxpaket untuk Python

fioghual
sumber
1

Apakah Anda mencurigai bahwa jaringan memiliki sejumlah kecil komponen yang terhubung sangat besar? Jika tidak, Anda dapat menguraikannya menjadi komponen yang berbeda yang akan membuatnya lebih mudah untuk menghitung ukuran sentralitas.

Michael Bishop
sumber
Beri +1 pada ini - jika ini merupakan komponen yang sepenuhnya terhubung, itu satu hal, tetapi jika Anda dapat menguraikan jaringan, Anda memiliki data yang lebih kecil, dan sebenarnya beberapa jaringan independen yang dapat dianalisis secara paralel.
Fomite
1

Ada beberapa paket perangkat lunak R yang bisa digunakan, termasuk "sna" dan "jaringan". Satu hal yang tidak perlu saya andalkan jika Anda mengalami masalah kinerja dengan sna adalah NetworkX. Saya suka NetworkX sampai mati, dan menggunakannya untuk sebagian besar analisis saya, tetapi NetworkX cukup bangga menjadi implementasi Pythonic yang sebagian besar murni. Itu tidak terlalu mengeksploitasi kode cepat pra-dikompilasi dengan baik, dan kadang-kadang melebihi NetworkX dengan margin yang cukup besar.

Fomite
sumber