algorithm - 我的子例程对于生成随机Barabasi-Albert图是否正确？

Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
我想生成一个有10000个节点的随机Barabasi-Albert图，但是我的程序很慢如果我的子程序正确与否，有人能帮忙吗在我的代码中ran1（）是标准随机数生成器谢谢你的帮助。

 ***********************************************************************
      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

某些链接连接到：
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

最佳答案

我不熟悉Fortran，但有几件事很突出。首先考虑函数的时间复杂度。有两个嵌套循环。第一个运行n次，其中n与输入的大小成比例。第二次运行，直到找到m0连接。但在最里面的循环中，计算数组各部分的和第一个总和包括i*(i-1)加法，这可能是最昂贵的。因此时间复杂度受限于O(n*m0*i^2)。假设m0很小，这就变成O(n^3)。
我认为最好的改进是将算法转换成具有较低时间复杂度的算法，但是如果不可能的话，你仍然可以调整你所拥有的。首先，把钱存起来不要计算同一个和两次或者，如果计算sum(1:i)，请保存该结果并在计算sum(1:i+1)或sum(1:i-1)时使用。

关于algorithm - 我的子例程对于生成随机Barabasi-Albert图是否正确？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39674081/