Построение разбиения двудольного графа занимает гораздо больше времени, чем весь граф - PullRequest
Новая
       28

Построение разбиения двудольного графа занимает гораздо больше времени, чем весь граф

0 голосов
/ 03 марта 2019

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

Вот код: 

rm(list=ls())
library(igraph)
library(tictoc)
nodes <- read.csv("./ma_nodes.csv", header=T, as.is=T)
links <- read.csv("./ma_edges.csv", header=T, as.is=T)
nodes$type <- as.logical(nodes$IsInvestor)
net <- graph_from_data_frame(d=links, vertices=nodes, directed=T)
net.bp <- bipartite_projection(net, multiplicity=F)
net.prj1 = net.bp$proj1
net.prj2 = net.bp$proj2

tic("Plotting bibpartite net")
plot(net)
toc()

tic("Plotting prj2")
plot(net.prj2)
toc()

tic("Plotting prj1")
plot(net.prj1)
toc()

Вот результат: 

Plotting bibpartite net: 5.04 sec elapsed
Plotting prj2: 0.21 sec elapsed
Plotting prj1: 77.9 sec elapsed

Также обратите внимание, что для измерения используется Sys.time ()время (и принимая разницу времени окончания - время начала), этот эффект не фиксируется.Но это не так: построение последнего графика занимает гораздо больше времени, чем построение двух других.Это проблема sys.time (), которая не в состоянии уловить это (но, вероятно, это для другого вопроса)

Что здесь происходит?

1 Ответ

0 голосов
/ 05 апреля 2019

Я думаю, что это было бы лучше в качестве комментария.Но у меня нет необходимой репутации.Таким образом, я отвечу на ваш вопрос более подробно.

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

Двухсторонняя проекция из ненаправленной сети с 500 ребрами приведет к 124750 (или n * (n-1) / 2) ребрам. 

library(igraph)
library(tictoc)

g <- data.frame(c(1:500), "A")
g <- graph_from_data_frame(g)
V(g)$type <- bipartite_mapping(g)$type
bp <- bipartite_projection(g)

gsize(g)
500

gsize(bp$proj1)
124750

И время построения увеличится на 8,5с (MacBook Pro от 2015 года с Intel i7 и 16 ГБ ОЗУ): 

tic("Plotting bibpartite net")
plot(g)
toc()
Plotting bibpartite net: 1.194 sec elapsed

tic("Plotting projected net")
plot(bp$proj1)
toc()
Plotting projected net: 9.621 sec elapsed

Проблема заключается в том, что число связей в проектируемой сети растет в геометрической прогрессии, а также время создания графика.

...