Эффективное вычисление влияния от узла u к узлу v в сети igraph R - PullRequest
Новая
       6

Эффективное вычисление влияния от узла u к узлу v в сети igraph R

0 голосов
/ 30 апреля 2018

Как гласит заголовок, вычислив все пути, начиная с узла u и заканчивая узлом v, я должен вычислить влияние узла u на узел v "I (u, v)" по следующему типу: I(u,v) = Sum(for all the paths from u to v)[ Product of all the weights of consecutive edges from u to v ]

Вот как я это делаю: 

Alpha<-array(0,dim = c(length(V(g)),length(V(g))))
if( u!=v ){
paths<-all_simple_paths(g, from = V(g)[u])#computing all paths from u
UpathV<-paths[unlist(lapply(paths, function(p){p[length(p)] %in% v}))]#extracting those that end to v
if(length(UpathV)!=0){#computing probability matrix from u to v
          Flist<-array(NA,dim = c(length(UpathV),max(lengths(UpathV))))
          Flist[1:length(UpathV)]<-1
          for(i in 1:length(UpathV)){
            for(j in 2:length(UpathV[[i]])){
              Flist[i,j]<-Flist[i,j-1]*E(g)[get.edge.ids(g,as.numeric(UpathV[[i]][(j-1):j]))]$weight
            }
          }
        }#if length(pspaths)
        if(length(UpathV)!=0){
          for(i in 1:length(UpathV)){
            Alpha[u,v]<-Alpha[u,v]+Flist[i,length(UpathV[[i]])]            
          }#computing I(u,v)
        }  
  }else{
        Alpha[u,v]<-1
  }

где Alpha [u, v] - это I (u, v), а Flist [i, j] - для пути i, вероятность u до j-го узла, направляющегося в v. В соответствии Flist<-array(NA,dim=c(length(UpathV),max(lengths(UpathV)))) Вы можете видеть, что если 3-й путь 1-> 2-> 3-> 4, то он имеет длину 4, а затем Flist [3,4] является весом ребра w (1-> 2) * w (2- > 3) * W (3-> 4). Мое решение работает, но для больших сетей требуется много времени для вычисления матрицы. Учитывая тот факт, что мне нужно вычислять I (u, v) от каждого u до каждого vi, нужно знать, есть ли более эффективный способ сделать мои расчеты без смены строк 3-4. Заранее большое спасибо!

1 Ответ

0 голосов

Через некоторое время я нашел способ ускорить вычисления, изменив одну строку кода и добавив еще одну. При вычислении массива Flist вместо того, чтобы получать каждое весовое значение из E (g) $ weight, мы должны вместо этого получать его из матрицы смежности. Я обнаружил, что в R это гораздо быстрее делать вещи с матрицами, чем с dataframes.So add: AjM<-as_adjacency_matrix(g,attr = "weight") а также: Flist[i,j]<-Flist[i,j-1]*AjM[as.numeric(UpathV[[i]][j-1]),as.numeric(UpathV[[i]][j])]

...