绘制二分图的分区比绘制整个图花费更多的时间

Question

在我的代码中，绘制整个二分图比单独绘制一个投影花费的时间少得多（当然，它的节点比二分图少，因为它只是二分图的一部分） .怎么可能？

代码如下：

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() 的一个问题，无法捕获它（但可能是另一个问题）

这是怎么回事？

Answer 1

我认为这作为评论会更好。但是我没有必要的声誉。因此，我将更详细地回答您的问题。

您没有提供样品。所以我只能做一个假设。与二分网络相比，您的投影很可能有更多的边。根据您的特定网络，这可能会大大增加创建情节的时间。

来自具有 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 秒（2015 年配备 Intel i7 和 16 GB RAM 的 MacBook Pro）：

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

问题是投影网络中的关系数量呈指数增长，创建情节的时间也呈指数增长。

绘制二分图的分区比绘制整个图花费更多的时间

Plotting a partition of a bipartite graph takes much more time than the entire graph

plot

r

graph-theory

igraph