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

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

-Расчитывает все возможные сообщества

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

-Возвратычлены / количество членов каждого (оптимального) сообщества

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

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)

}  

Ответы [ 2 ]

5 голосов
/ 27 марта 2012

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

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

summary(clusters(all2)$membership)

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

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

clusters(all2)$csize

чтобы получить список размеров ваших кластеров. Имейте в виду, что ваши кластерные идентификаторы, как упоминалось ранее, начинаются с 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, но кто-то может указать вам пакет, который может это сделать. Возможно, вам удастся опубликовать этот вопрос в качестве отдельного вопроса, либо здесь, либо в другом месте.

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

1 голос
/ 31 декабря 2015

Что касается «как контролировать количество сообществ» в вопросе OP, я использую функцию 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
...