samedi 24 septembre 2016

Is my subroutine correct for generating a random Barabasi-Albert graph?

I would like to generate a random Barabasi-Albert graph with 10,000 node, but my program is very slow. Can anybody help if my subroutine is correct or not? In my code ran1() is the standard random number generator. Thanks for the help.

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

Some links connected to:

http://ift.tt/2cult3h

http://ift.tt/2d7cMtz

Implementing Barabasi-Albert Method for Creating Scale-Free Networks




Aucun commentaire:

Enregistrer un commentaire