Проблема с производительностью при большом количестве ребер

Я работал над онлайн-примером, где вирус распространяется по графику. Примера достаточно для небольшого графа, то есть небольшого количества ребер и узлов. Но я попробовал это на очень большом графе, то есть 10000 узлов и 20000 ребер, но приведенной ниже функции недостаточно для большого графа, потому что он медленный.

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

spreadVirus <- function(G,Vinitial,Activation_probability){  

# Precompute all outgoing graph adjacencies

G$AdjList = get.adjlist(G,mode="out")

# Initialize various graph attributes
V(G)$color    = "blue"
E(G)$color    = "black"
V(G)[Vinitial]$color    <- "yellow"

# List to store the incremental graphs (for plotting later)
Glist <- list(G)
count <- 1

# Spread the infection
active <- Vinitial

while(length(active)>0){
new_infected <- NULL
E(G)$color = "black"

for(v in active){
# spread through the daily contacts of vertex v

daily_contacts <- G$AdjList[[v]]

E(G)[v %->% daily_contacts]$color <- "red"

for(v1 in daily_contacts){

if(V(G)[v1]$color == "blue" & new_color=="red") { 

V(G)[v1]$color <- "red"

new_infected <- c(new_infected,v1)

 } 
}
}
# the next active set
#this needed for updating

active <- new_infected

# Add graph to list
# optional dependening on if i want to graph 
count <- count + 1
Glist[[count]] <- G
}
return(Glist)
}

Мой вопрос: как можно оптимизировать приведенную ниже функцию для больших графиков?

Спасибо Муна


r igraph
person Muna Abdi    schedule 28.05.2015    source источник
comment
недостаточно в смысле чего? И каковы пределы цикла for, о которых вы говорите? Я думаю, что эти детали помогут объяснить, что вы конкретно спрашиваете.   -  person J0e3gan    schedule 28.05.2015
comment
недостаточно в смысле чего? Цикл for выполняется очень медленно, например, когда я запускал его на большом графике, он выполнялся три дня, и я не получил никакого результата. Я ограничен, я имею в виду R, это не векторизованный код. Я хочу сделать приведенный выше код векторизованным, то есть быстрым.   -  person Muna Abdi    schedule 29.05.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

spreadVirus <- function(G,Vinitial,Activation_probability){  
    # Precompute all outgoing graph adjacencies
    G$AdjList <- get.adjlist(G, mode = "out")

    # Initialize various graph attributes
    V(G)$step0    <- "blue"
    E(G)$color    <- "black"
    V(G)[Vinitial]$color    <- "yellow"

    # Spread the infection
    active <- Vinitial

    step <- 0
    while(length(active)>0){
        step <- step + 1
        new_infected <- NULL
        E(G)$color <- "black"
        vertex.attributes(g)[[sprintf('step%d', step)]] <- 
        vertex.attributes(g)[[sprintf('step%d', step - 1)]]

        for(v in active){
            # spread through the daily contacts of vertex v

            daily_contacts <- G$AdjList[[v]]

            E(G)[v %->% daily_contacts]$color <- "red"

            for(v1 in daily_contacts){

                vertex.attributes(g)[[sprintf('step%d', step)]][v1] <- "red"
                new_infected <- c(new_infected, v1)

                } 
            }
        }
    # the next active set
    #this needed for updating

    active <- new_infected

    # Add graph to list
    # optional dependening on if i want to graph 
    return(G)
}

После этого вы можете обратиться к атрибутам V(G)$step#, чтобы получить зараженные узлы в каждый момент времени. Для построения графика вы можете передать vertex.color = V(G)$step#. Вы можете получить зараженную часть графа по induced.subgraph(G, which(V(G)$step#=='red').

Вы можете сделать то же самое с атрибутами цвета края.

person deeenes    schedule 29.05.2015
comment
Спасибо, деин, не могли бы вы привести пример и что происходит с if(V(G)[v1]$color == blue & new_color==red) - person Muna Abdi; 30.05.2015
comment
Я не вижу, где вы инициализируете переменную new_color, и я не знаю, зачем это нужно. Так как v1 является соседней вершиной v, ее цвет должен быть установлен на 'red', потому что на этом шаге она заражается. Однако, если вы хотите сделать его зараженным только в том случае, если он был здоров, просто выполните if(vertex.attributes(G)[[sprintf("step%d", step-1)]][v1] == 'blue'){vertex.attributes(G)[[sprintf('step%d', step)]][v1] <- "red"}. - person deeenes; 30.05.2015