R: metoda igraph, community detection, edge.betweenness, liczba/lista członków każdej społeczności?

Question

Mam stosunkowo duży wykres z wierzchołkami: 524 krawędzie: 1125 transakcji rzeczywistych. Krawędzie są skierowane i mają ciężar (włączenie jest opcjonalne). Próbuję zbadać różne społeczności w obrębie wykresu, a przede wszystkim potrzebny jest metodą, która:

-Calculates wszystkich możliwych społeczności

-Calculates optymalna liczba wspólnot

-Returns Członkowie/liczba członkowie każdej (optymalnej) społeczności

Do tej pory udało mi się zebrać następujący kod, który kreśli kolorowy wykres odpowiadający różnym społecznościom, jednak nie mam pojęcia, jak kontrolować liczbę społeczności (np. wytypuj 5 najlepszych społeczności za pomocą h członkostwo ighest) lub wymieniać członków konkretnej społeczności.

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) 

---

Ponieważ metoda krawędź betweenness wykonywane tak źle Próbowałem ponownie stosując metodę 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 klastrów - o wiele lepszy!

Teraz mówię, że miałem "znaną gromadę" z listą jej członków i chciałem sprawdzić każdy z obserwowanych klastrów pod kątem obecności członków z "znanego klastra". Zwracanie procentu znalezionych członków. Nie można ukończyć następujących czynności?

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

Kilka z tych pytań można znaleźć, dokładnie przeglądając dokumentację funkcji, z których korzystasz. Na przykład dokumentacja clusters, w sekcji "Wartości", opisuje, co zostanie zwrócone z funkcji, z których kilka odpowie na twoje pytania. Dokumentacja na bok, zawsze możesz użyć funkcji str do analizy makijażu dowolnego konkretnego obiektu.

Mimo to, aby uzyskać członków lub liczbę członków w określonej społeczności, można spojrzeć na obiekt membership zwrócony przez funkcję clusters (której używasz już do przypisania koloru). Tak więc coś takiego:

summary(clusters(all2)$membership) 

będzie opisywać identyfikatory używanych klastrów. W przypadku przykładowych danych wygląda na to, że masz klastry z identyfikatorami od 0 do 585, łącznie dla 586 klastrów. (Zauważ, że nie będzie w stanie wyświetlać te bardzo dokładnie przy użyciu schematu kolorowania aktualnie używany.)

Aby określić liczbę wierzchołków w każdym klastrze, można spojrzeć na składniku csize również zwrócony przez clusters . W tym przypadku jest to wektor o długości 586, przechowujący jeden rozmiar dla każdego obliczonego klastra. Aby można było uzyskać listę rozmiarów klastrów, można użyć tej opcji. Aby uzyskać listę rozmiarów klastrów, można użyć tej metody. Ostrzegam, że twoje identyfikatory klastra, jak wcześniej wspomniano, zaczynają się od 0 ("zindeksowane"), podczas gdy wektory R zaczynają się od 1 ("jeden indeks"), więc będziesz musiał przesunąć te wskaźniki o jeden. Na przykład: clusters(all2)$csize[5] zwraca rozmiar klastra o identyfikatorze 4.

Aby wyświetlić wierzchołki w dowolnym klastrze, wystarczy sprawdzić, które identyfikatory w wymienionym wcześniej komponencie membership pasują do danego klastra. Więc jeśli chcę znaleźć wierzchołki klastra # 128 (istnieje 21 z nich, zgodnie z clusters(all2)$csize[129]), mogę użyć:

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

i odzyskać wierzchołki w tym klastrze, można korzystać z funkcji V i przechodzą w indeksach, które po prostu obliczone będących członkiem tej gromady:

> 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" 

To by pokryć podstawowe pytania igraph miałeś. Pozostałe pytania są bardziej związane z teorią grafów. Nie znam sposobu nadzorowania liczby klastrów, które mają być tworzone przy pomocy iGraph, ale ktoś może wskazać ci pakiet, który jest w stanie to zrobić. Możesz odnieść większy sukces, umieszczając to jako osobne pytanie, tutaj lub w innym miejscu.

Odnośnie twoich pierwszych punktów chęci iteracji przez wszystkie możliwe społeczności, myślę, że odkryjesz, że to nie jest możliwe dla wykresu znacznej wielkości. Liczba możliwych układów wektora membership dla 5 różnych klastrów wynosiłaby 5^n, gdzie n jest wielkością wykresu. Jeśli chcesz znaleźć "wszystkie możliwe społeczności", ta liczba będzie faktycznie O (n^n), jeśli moja mentalna matematyka jest poprawna. Zasadniczo niemożliwe byłoby obliczenie tego w sposób wyczerpujący w jakiejkolwiek rozsądnie wielkości sieci, nawet przy ogromnych zasobach obliczeniowych. Więc myślę, że lepiej będzie użyć inteligencji/optymalizacji do określenia liczby społeczności reprezentowanych na wykresie, tak jak ma to miejsce w przypadku funkcji clusters.

Answer 2

W odniesieniu do "jak kontrolować liczbę społeczności" w pytaniu OP, używam funkcji cut_at w społecznościach, aby przyciąć powstałą strukturę hierarchiczną do pożądanej liczby grup. Mam nadzieję, że ktoś może potwierdzić, że robię coś normalnego. Mianowicie, należy rozważyć następujące kwestie:

#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 

Teraz należy pamiętać, że istnieje 43 grup, ale chcemy grubsze kawałki stąd, bada dendrogramie:

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

i pokroić w oparciu o niego. Ja arbitralnie wybrałem 6 cięć, ale jednak masz teraz grubsze klastry:

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