сравнить сообщества из графов с разным количеством вершин - PullRequest
Новая
       50

сравнить сообщества из графов с разным количеством вершин

0 голосов
/ 22 февраля 2019

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

Мы хотим попытаться определить команды исполнителей по их коммуникационным данным.Поскольку исполнители имеют предпочтения для различных методов связи, графики имеют разные размеры и могут иметь некоторые уникальные вершины, которые могут отсутствовать в обоих.Когда я пытаюсь сравнить объекты сообщества из соответствующих графиков, igraph :: compare () выдает исключение.См. Игрушку представьте ниже.

Я рассмотрел dplyr :: full_join () или inner_join () из списков вершин, прежде чем создавать граф и объекты сообщества, чтобы сделать их одинаковыми по размеру, но беспокоюсь о влиянии этого.на результирующие решения cluster_louvain ().

Есть какие-нибудь идеи о том, как я могу сравнивать объекты сообщества друг с другом из этих разных способов коммуникации?Заранее спасибо! 

library(tidyverse, warn.conflicts = FALSE)
library(igraph, warn.conflicts = FALSE)

nodes <- as_tibble(list(id = c("sample1", "sample2", "sample3")))
edge <- as_tibble(list(from = "sample1",
                       to = "sample2"))
net <- graph_from_data_frame(d = edge, vertices = nodes, directed = FALSE)
com <- cluster_louvain(net)

nodes2 <- as_tibble(list(id = c("sample1","sample21", "sample22","sample23"
                                )))
edge2 <- as_tibble(list(from = c("sample1", "sample21"),
                       to = c("sample21", "sample22")))
net2 <- graph_from_data_frame(d = edge2, vertices = nodes2, directed = FALSE)
com2 <- cluster_louvain(net2)

# # uncomment to see graph plots
# plot.igraph(net, mark.groups = com)
# plot.igraph(net2, mark.groups = com2)

compare(com, com2)
#> Error in i_compare(comm1, comm2, method): At community.c:3106 : community membership vectors have different lengths, Invalid value

Создано в 2019-02-22 с помощью представительного пакета (v0.2.1)

1 Ответ

0 голосов
/ 22 февраля 2019

Вы не сможете (я не верю) сравнить алгоритмы кластеризации из двух разных графов, которые содержат два разных набора узлов.Практически вы не можете сделать это в igraph, и концептуально это сложно, потому что сравнение алгоритмов кластеризации заключается в рассмотрении всех пар узлов в графе и проверке, расположены ли они в одном кластере или в другом кластере в каждом издва кластерных подхода.Если оба подхода к кластеризации обычно объединяют одни и те же узлы и разделяют одни и те же узлы, то они считаются более похожими. 1

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

Поэтому для сравнения необходимо использовать все одинаковые узлы на обоих графиках.На самом деле, я думаю, что самый простой способ сделать это - поместить все одни и те же узлы в один граф и иметь разные типы ребер.Затем вы можете рассчитать свои кластеры для каждого типа ребер отдельно, а затем сделать сравнение.Надеемся, что приведенное ниже представление ясно: 

# repeat your set-up
library(tidyverse, warn.conflicts = FALSE)
library(igraph, warn.conflicts = FALSE)

nodes <- as_tibble(list(id = c("sample1", "sample2", "sample3")))
edge <- as_tibble(list(from = "sample1",
                       to = "sample2"))

nodes2 <- as_tibble(list(id = c("sample1","sample21", "sample22","sample23")))
edge2 <- as_tibble(list(from = c("sample1", "sample21"),
                        to = c("sample21", "sample22")))

# approach from a single graph
# concatenate edges
edges <- rbind(edge, edge2)
# create an edge attribute indicating network type
edges$type <- c("phone", "email", "email")
# the set of nodes (across both graphs)
nodes <- unique(rbind(nodes, nodes2))

g <- graph_from_data_frame(d = edges, vertices = nodes, directed = F)

# We cluster over the graph without the email edges
com_phone <- cluster_louvain(g %>% delete_edges(E(g)[E(g)$type=="email"]))
plot(g, mark.groups = com_phone)


# Now we can cluster over the graph without the phone edges
com_email <- cluster_louvain(g %>% delete_edges(E(g)[E(g)$type=="phone"]))
plot(g, mark.groups = com_email)


# Now we can compare
compare(com_phone, com_email)
#> [1] 0.7803552

Как видно из графиков, которые мы выбираемта же самая исходная структура кластеризации, которую вы обнаружили на отдельных графиках с добавлением дополнительных изолированных узлов.

1: Очевидно, это довольно расплывчатое объяснение.Алгоритм по умолчанию, используемый в compare, взят из этой статьи , с которой приятно поговорить.

...