Ist meine Subroutine korrekt zum Generieren eines zufälligen Barabasi-Albert-Graphen?

Question

Ich möchte einen zufälligen Barabasi-Albert-Graph mit 10.000 Knoten erzeugen, aber mein Programm ist sehr langsam. Kann jemand helfen, wenn mein Unterprogramm korrekt ist oder nicht? In meinem Code ist ran1() der Standard-Zufallszahlengenerator. Danke für die Hilfe.

*********************************************************************** 
     subroutine barabasi_albert(kon,n,m0,m,a,idum) 
*********************************************************************** 
     implicit real*8(a-h,o-z) 
     implicit integer*4(i-n) 
     logical linked(n) ! logical array for storing if a node is connected 
          ! to the current one 
     dimension kon(n,n) ! connectivity matrix 
          ! m0: number of initial nodes 
          ! m: minimal degree 
          ! a: scale parameter 
          ! idum: argument to the random number generation 
c 
c Initialize kon(:,:) 
c       
     kon(:n,:n)=0 
c 
c Create complete graph of m0 node 
c       
     kon(:m0,:m0)=1 
     do i=1,m0 
     kon(i,i)=0 
     end do 
c 
c Extend the graph with n-m0 node 
c  
     do i=m0+1,n 
     linked(:i)=.false. 
c 
c Add edges while the vertex degree of the ith node is less than m 
c   
     do 
      if(sum(kon(i,:i-1)).eq.m) exit 
      ii=floor(dble(i-1)*ran1(idum))+1 
      if(.not.linked(ii)) then 
       p=(dble(sum(kon(ii,:i-1)))/sum(kon(:i-1,:i-1)))**a 
       if(p.gt.ran1(idum)) then 
        kon(i,ii)=1 
        kon(ii,i)=1 
        linked(ii)=.true. 
       endif 
      endif 
     end do 
     end do 
     end 

Einige verbunden Links:

https://math.stackexchange.com/questions/454188/why-does-my-barabasi-albert-model-implementation-doesnt-produce-a-scale-free-ne

https://math.stackexchange.com/questions/1824097/creating-barab%c3%a1si-albertba-graph-with-spacific-node-and-edgs

Implementing Barabasi-Albert Method for Creating Scale-Free Networks

Answer 1

ich mit Fortran nicht vertraut bin, aber ein paar Dinge auffallen. Berücksichtigen Sie zunächst die zeitliche Komplexität Ihrer Funktion. Sie haben zwei verschachtelte Schleifen. Die erste läuft n mal, wobei n proportional zur Größe des Eingangs ist. Die zweite läuft, bis es m0 Verbindungen gefunden hat. Innerhalb der innersten Schleife berechnen Sie jedoch die Summe der Teile des Arrays. Erste Summe besteht aus i*(i-1) Ergänzungen, das ist wahrscheinlich der teuerste. So ist die zeitliche Komplexität durch O(n*m0*i^2) begrenzt. Unter der Annahme, m0 ist klein, wird dies O(n^3).

Die beste Verbesserung, die ich denke, ist, zu einem Algorithmus mit geringerer Zeitkomplexität zu wechseln, aber wenn das nicht möglich ist, können Sie noch optimieren, was Sie haben. Zuerst cachen Sie Ihre Summen. Errechnen Sie nicht zweimal dieselbe Summe. Oder wenn Sie sum(1:i) berechnen, speichern Sie dieses Ergebnis und verwenden Sie es, wenn Sie sum(1:i+1) oder sum(1:i-1) berechnen.