R: igraph, обнаружение сообщества, метод edge.betweenness, подсчет/список членов каждого сообщества?

Question

У меня относительно большой график с вершинами: 524 Edges: 1125, сделок реального мира. Края направлены и имеют вес (включение необязательно). Я пытаюсь исследовать различные общины в графике и по существу нужен метод, который:

-Calculates все возможные сообщества

-Calculates оптимальное количество общин

-Returns Участники Форума/№ члены каждого (оптимального) сообщества

До сих пор мне удалось собрать следующий код, на котором изображен цветной график, соответствующий различным сообществам, однако я не знаю, как контролировать количество сообществ (т. е. сюжет 5 лучших сообществ с h самое высокое членство) или список членов определенного сообщества.

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) 

---

Поскольку метод края промежуточность выполняется так плохо, я попробовал еще раз, используя метод 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 кластеров - гораздо лучше!

Теперь скажите, что у меня был «известный кластер» со списком его членов и я хотел проверить каждый из наблюдаемых кластеров на наличие членов из «известного кластера». Возврат процента найденных участников. Не удалось завершить следующее.

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

Пара этих вопросов может быть обнаружена путем тщательного изучения документации по функциям, которые вы используете. Например, документация clusters в разделе «Значения» описывает, что будет возвращено из функции, причем пара из них отвечает на ваши вопросы. В документации вы всегда можете использовать функцию str для анализа макияжа любого конкретного объекта.

Сообщалось, что для получения членов или номеров членов в определенном сообществе вы можете посмотреть объект membership, возвращенный функцией clusters (которую вы уже используете для назначения цвета). Так что-то вроде:

summary(clusters(all2)$membership) 

будет описывать идентификаторы используемых кластеров. В случае ваших данных образца, похоже, у вас есть кластеры с идентификаторами от 0 до 585, всего 586 кластеров. (Обратите внимание, что вы не будете в состоянии отображать те очень точно с помощью схемы окраски вы сейчас используете.)

Чтобы определить количество вершин в каждом кластере, вы можете посмотреть на csize компонент также возвращенного clusters , В этом случае это вектор длиной 586, который хранит один размер для каждого подсчитанного кластера. Таким образом, вы можете использовать

clusters(all2)$csize 

, чтобы получить список размеров ваших кластеров. Будьте предупреждены, что ваши идентификаторы clusterID, как упоминалось ранее, начинаются с 0 («нуль-индексированный»), тогда как R-векторы начинаются с 1 («одноиндексированный»), поэтому вам нужно будет сдвинуть эти индексы на единицу. Например, clusters(all2)$csize[5] возвращает размер кластера с идентификатором 4.

Чтобы перечислить вершины в любом кластере, вы просто хотите найти, какие идентификаторы в упомянутом выше компоненте membership соответствуют указанному кластеру. Так что, если я хочу найти вершины в кластере # 128 (есть 21 из них, по словам clusters(all2)$csize[129]), я мог бы использовать:

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

и получить вершины в этой группе, я могу использовать функцию V и передать в индексах, которые я только вычисленных, которые являются членом этого кластера:

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

Это будет охватывать основные вопросы igraph вы имели. Остальные вопросы связаны с теорией графов. Я не знаю, как контролировать количество кластеров, создаваемых с помощью iGraph, но кто-то может указать вам на пакет, который может это сделать. У вас может быть больше успешных сообщений в качестве отдельного вопроса, как здесь, так и в другом месте.

Что касается ваших первых пунктов, желающих перебирать все возможные сообщества, я думаю, вы обнаружите, что это невозможно для графика значительного размера. Число возможных компоновки вектора membership для 5 различных кластеров будет 5^n, где n - размер графика. Если вы хотите найти «все возможные сообщества», это число действительно будет O (n^n), если моя ментальная математика верна. По сути, было бы невозможно вычислить это исчерпывающе над любой сетью разумного размера, даже учитывая массовые вычислительные ресурсы. Поэтому я думаю, вам будет лучше использовать какой-то интеллект/оптимизацию для определения количества сообществ, представленных на вашем графике, как это делает функция clusters.

Answer 2

Что касается «как контролировать количество сообществ» в вопросе OPs, я использую функцию cut_at в сообществах, чтобы вырезать результирующую иерархическую структуру в нужное количество групп. Надеюсь, кто-то может подтвердить, что я делаю что-то здравомыслящее. А именно, рассмотрим следующее:

#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 

Теперь, обратите внимание, что существует 43 групп, но мы хотим, чтобы более крупные сокращения, следовательно, изучить дендрограммы:

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

и разрезают на его основе. Я произвольно выбрал 6 разрезов, но, тем не менее, теперь у вас более грубые кластеры

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