R: igraph, rilevamento della comunità, metodo del metodo di spigolo, conta/elenca i membri di ogni comunità?

Question

Ho un grafico relativamente grande con Vertices: 524 Bordi: 1125, di transazioni nel mondo reale. I bordi sono diretti e hanno un peso (l'inclusione è facoltativa). Sto cercando di indagare le diverse comunità all'interno del grafico ed essenzialmente bisogno di un metodo che:

-Calculates tutti i possibili comunità

-Calculates il numero ottimale di comunità

I ritorni la membri/° membri di ciascuna comunità (ottimale)

Finora sono riuscito a riunire il seguente codice che traccia un grafico con codice colore corrispondente alle varie comunità, tuttavia non ho idea di come controllare il numero di comunità (es. traccia le prime 5 comunità con la h più alta adesione) o elencare i membri di una particolare comunità.

library(igraph) 
edges <- read.csv('http://dl.dropbox.com/u/23776534/Facebook%20%5BEdges%5D.csv') 
all<-graph.data.frame(edges) 
summary(all) 

all_eb <- edge.betweenness.community(all) 
mods <- sapply(0:ecount(all), function(i) { 
all2 <- delete.edges(all, all_eb$removed.edges[seq(length=i)]) 
cl <- clusters(all2)$membership 
modularity(all, cl) 
}) 


plot(mods, type="l") 

all2<-delete.edges(all, all_eb$removed.edges[seq(length=which.max(mods)-1)]) 

V(all)$color=clusters(all2)$membership 

all$layout <- layout.fruchterman.reingold(all,weight=V(all)$weigth) 

plot(all, vertex.size=4, vertex.label=NA, vertex.frame.color="black", edge.color="grey", 
edge.arrow.size=0.1,rescale=TRUE,vertex.label=NA, edge.width=.1,vertex.label.font=NA) 

---

Poiché il metodo bordo betweenness eseguita così male ho riprovato con il metodo walktrap:

all_wt<- walktrap.community(all, steps=6,modularity=TRUE,labels=TRUE) 
all_wt_memb <- community.to.membership(all, all_wt$merges, steps=which.max(all_wt$modularity)-1) 


colbar <- rainbow(20) 
col_wt<- colbar[all_wt_memb$membership+1] 

l <- layout.fruchterman.reingold(all, niter=100) 
plot(all, layout=l, vertex.size=3, vertex.color=col_wt, vertex.label=NA,edge.arrow.size=0.01, 
        main="Walktrap Method") 
all_wt_memb$csize 
[1] 176 13 204 24 9 263 16 2 8 4 12 8 9 19 15 3 6 2 1 

19 ammassi - Molto meglio!

Ora dire che avevo un "cluster noto" con un elenco dei suoi membri e che volevo controllare ciascuno dei cluster osservati per la presenza di membri dal "cluster noto". Restituzione della percentuale di membri trovati. Impossibile completare quanto segue ??

list<-read.csv("http://dl.dropbox.com/u/23776534/knownlist.csv") 
ength(all_wt_memb$csize) #19 

for(i in 1:length(all_wt_memb$csize)) 
{ 

match((V(all)[all_wt_memb$membership== i]),list) 

} 

Answer 1

Un paio di queste domande possono essere scoperte guardando attentamente la documentazione delle funzioni che state utilizzando. Ad esempio, la documentazione di clusters, nella sezione "Valori", descrive cosa verrà restituito dalla funzione, un paio dei quali rispondono alle tue domande. Documentazione a parte, è sempre possibile utilizzare la funzione str per analizzare il trucco di un particolare oggetto.

Detto questo, per ottenere membri o numeri di membri in una particolare comunità, è possibile esaminare l'oggetto membership restituito dalla funzione clusters (che si sta già utilizzando per assegnare il colore). Quindi, qualcosa di simile a:

summary(clusters(all2)$membership) 

avrebbe descritto gli ID dei cluster che vengono utilizzati. Nel caso dei dati di esempio, sembra che ci siano cluster con ID compresi tra 0 e 585, per un totale di 586 cluster. (Nota che non sarai in grado di visualizzarli in modo molto accurato usando lo schema di colorazione che stai usando.)

Per determinare il numero di vertici in ciascun cluster, puoi guardare il componente csize restituito anche da clusters . In questo caso, è un vettore di lunghezza 586, che memorizza una dimensione per ciascun cluster calcolato. Quindi puoi usare

clusters(all2)$csize 

per ottenere l'elenco delle dimensioni dei tuoi cluster. Tieni presente che i tuoi clusterID, come accennato in precedenza, partono da 0 ("zero-indicizzati") mentre i vettori R iniziano da 1 ("indicizzati"), quindi dovrai spostare questi indici di uno. Ad esempio, clusters(all2)$csize[5] restituisce la dimensione del cluster con l'ID di 4.

Per elencare i vertici in qualsiasi cluster, si desidera solo individuare quali ID nel componente membership precedentemente menzionati corrispondono al cluster in questione. Quindi, se voglio trovare i vertici a grappolo # 128 (ci sono 21 di queste, secondo clusters(all2)$csize[129]), potrei usare:

which(clusters(all2)$membership == 128) 
length(which(clusters(all2)$membership == 128)) #21 

e per recuperare i vertici in tale cluster, posso usare la funzione V e passare gli indici che ho appena calcolati che sono un membro del cluster:

> V(all2)[clusters(all2)$membership == 128] 
Vertex sequence: 
[1] "625591221 - Clare Clancy"   
[2] "100000283016052 - Podge Mooney"  
[3] "100000036003966 - Jennifer Cleary" 
[4] "100000248002190 - Sarah Dowd"  
[5] "100001269231766 - LirChild Surfwear" 
[6] "100000112732723 - Stephen Howard" 
[7] "100000136545396 - Ciaran O Hanlon" 
[8] "1666181940 - Evion Grizewald"  
[9] "100000079324233 - Johanna Delaney" 
[10] "100000097126561 - Órlaith Murphy" 
[11] "100000130390840 - Julieann Evans" 
[12] "100000216769732 - Steffan Ashe"  
[13] "100000245018012 - Tom Feehan"  
[14] "100000004970313 - Rob Sheahan"  
[15] "1841747558 - Laura Comber"   
[16] "1846686377 - Karen Ni Fhailliun"  
[17] "100000312579635 - Anne Rutherford" 
[18] "100000572764945 - Lit Đ Jsociety" 
[19] "100003033618584 - Fall Ball"   
[20] "100000293776067 - James O'Sullivan" 
[21] "100000104657411 - David Conway" 

in grado di coprire le domande IGRAPH di base che hai avuto. Le altre domande sono più legate alla teoria dei grafi. Non conosco un modo per controllare il numero di cluster da creare usando iGraph, ma qualcuno potrebbe essere in grado di indicarti un pacchetto che è in grado di farlo. Potresti avere più successo nel postarlo come domanda separata, qui o in un'altra sede.

Per quanto riguarda i tuoi primi punti di voler ripetere tutte le possibili comunità, penso che troverai che non è fattibile per un grafico di dimensioni significative. Il numero di possibili disposizioni del vettore membership per 5 diversi cluster sarebbe 5^n, dove n è la dimensione del grafico. Se vuoi trovare "tutte le comunità possibili", quel numero sarà effettivamente O (n^n), se la mia matematica mentale è corretta. Essenzialmente, sarebbe impossibile calcolare in modo esauriente su qualsiasi rete di dimensioni ragionevoli, anche in presenza di enormi risorse computazionali. Quindi penso che starai meglio usando una sorta di intelligenza/ottimizzazione per determinare il numero di comunità rappresentate nel tuo grafico, come fa la funzione clusters.

Answer 2

Riguardo a "come controllare il numero di comunità" nella domanda OPs, uso la funzione cut_at sulle comunità per tagliare la struttura gerarchica risultante in un numero desiderato di gruppi. Spero che qualcuno possa confermare che sto facendo qualcosa di sano. Vale a dire, considerare quanto segue:

#Generate graph 
adj.mat<- matrix(,nrow=200, ncol=200) #empty matrix 
set.seed(2) 

##populate adjacency matrix 
for(i in 1:200){adj.mat[i,sample(rep(1:200), runif(1,1,100))]<-1} 
adj.mat[which(is.na(adj.mat))] <-0 

for(i in 1:200){ 
    adj.mat[i,i]<-0 
} 

G<-graph.adjacency(adj.mat, mode='undirected') 
plot(G, vertex.label=NA) 

##Find clusters 
walktrap.comms<- cluster_walktrap(G, steps=10) 
max(walktrap.comms$membership) #43 

    [1] 6 34 13 1 19 19 3 9 20 29 12 26 9 28 9 9 2 14 13 14 27 9 33 17 22 23 23 10 17 31 9 21 2 1 
[35] 33 23 3 26 22 29 4 16 24 22 25 31 23 23 13 30 35 27 25 15 6 14 9 2 16 7 23 4 18 10 10 22 27 27 
[69] 23 31 27 32 36 8 23 6 23 14 19 22 19 37 27 6 27 22 9 14 4 22 14 32 33 27 26 14 21 27 22 12 20 7 
[103] 14 26 38 39 26 3 14 23 22 14 40 9 5 19 29 31 26 26 2 19 6 9 1 9 23 4 14 11 9 22 23 41 10 27 
[137] 22 18 26 14 8 15 27 10 5 33 21 28 23 22 13 1 22 24 14 18 8 2 18 1 27 12 22 34 13 27 3 5 27 25 
[171] 1 27 13 34 8 10 13 5 17 17 25 6 19 42 31 13 30 32 15 30 5 11 9 25 6 33 18 33 43 10 

Ora, notare che ci sono 43 gruppi, ma ci vogliono i tagli più grossi di conseguenza, esaminare il dendrogramma:

plot(as.hclust(walktrap.comms), label=F) 

e tagliare basati su di esso. Ho arbitrariamente scelto 6 tagli, ma ora avete cluster più grossi

cut_at(walktrap.comms, no=6) 

    [1] 4 2 5 4 5 5 3 5 3 4 3 5 5 3 5 5 3 1 5 1 1 5 1 6 1 1 1 4 6 5 5 2 3 4 1 1 3 5 1 4 6 6 3 1 5 5 1 1 5 4 3 1 
[53] 5 2 4 1 5 3 6 3 1 6 6 4 4 1 1 1 1 5 1 4 3 3 1 4 1 1 5 1 5 2 1 4 1 1 5 1 6 1 1 4 1 1 5 1 2 1 1 3 3 3 1 5 
[105] 3 3 5 3 1 1 1 1 3 5 2 5 4 5 5 5 3 5 4 5 4 5 1 6 1 3 5 1 1 1 4 1 1 6 5 1 3 2 1 4 2 1 2 3 1 1 5 4 1 3 1 6 
[157] 3 3 6 4 1 3 1 2 5 1 3 2 1 5 4 1 5 2 3 4 5 2 6 6 5 4 5 3 5 5 4 4 2 4 2 3 5 5 4 1 6 1 2 4