复杂网络中ER随机网络C++代码实现

最近回顾了下复杂网络中的一下基本知识，记得自己当初入门时候，一个难点是将文字转变为代码的能力，另一个难点是不知道什么是网络。这篇文章给出了ER网络的算法实现，希望能帮助到刚进入复杂网络领域的同学们。

ER随机网络的算法描述与网络性质

对于刚进入复杂网络的同学来说，ER随机网络（Erdös 和 Rényi 提出的随机网络模型）肯定不会陌生，它将随机性作为基本元素，它的特点是不指定节点，而通过随机性进行连边。

算法实现一：最初的 ER 网络 퐺(푁, 푀) 的构造是通过给定网络中节点数量与边数，通过随机种子选取连边，直到给定边数全部连接。值得注意的是，通常我们都在构建网络时拒绝产生重连边与自连边。

算法实现二：ER 网络一个更为人们熟知的变体 퐺(푁, 푝) 由 Gilbert 提出，可以描述为通过给定节点数以及每个节点的连边概率 푝 (以概率 푝 与其它节点相连，以1 - 푝 的概率不相连)，遍历所有节点，即可完成 ER 随机网络的构建。当节点数量较少时 퐺(푁, 푀) 构建的随机网络与 퐺(푁, 푝) 构建的随机网络会有较大差异。但节点数量较大时，两者在统计学中是等价的。

参数	物理意义
G()	图或网络
N	网络中节点总数
M	网络中总边数
p	连边概率
k	度

ER随机网络的一个性质是满足泊松分布，即：

度分布服从泊松分布使其度在平均度〈푘〉两端呈指数衰减，这表明 ER 随机网络是一种均匀的随机网络，网络中节点的度近似于网络的平均度 푘 ≈ 〈푘〉。网络的性质不做过度赘述，基本任意一本复杂网络书籍或是综述中都有非常详细的讲解。

算法实现

算法采用C++代码实现，编译软件为Code::Blocks，其中网络使用的是邻接链表进行表示。

算法一C++代码实现：

#include 
#include 
#include 
#include 
#include 
#include "mt19937ar.c"
#include 
#include 

using namespace std;

int main()
{
    int Network_Size = 100000;       //网络节点数
    double average_degree = 4;       //平均度
    int edge = 0.5*Network_Size*average_degree;    //边数
    unsigned long idum;                   //高精度随机种子生成器初始化
    idum=(unsigned long)time(NULL);
    init_genrand(idum);

    vector degree(Network_Size,0);             //节点度
    vector > adjlist(Network_Size);     //网络邻接链表

    ofstream outfile_ER_adjlist;
    ofstream outfile_ER_degree;
    double r;
    outfile_ER_adjlist.open("ER_adjlist.txt");
    outfile_ER_degree.open("ER_degree.txt");


    for(;;)
    {
        double judge = 0;
        int random_1 = genrand_int32()%Network_Size;
        int random_2 = genrand_int32()%Network_Size;
        if(random_1 != random_2)         //解决重连边自连边问题
        {
            for(int i = 0; i < adjlist[random_1].size(); i++)
            {
                if(adjlist[random_1][i] == random_2)
                {
                    judge = 1;
                    break;
                }
            }
            if(judge == 1)
            {
                continue;
            }
            else
            {
                adjlist[random_1].push_back(random_2);
                degree[random_1]++;
                adjlist[random_2].push_back(random_1);
                degree[random_2]++;
                edge--;
            }
        }
        if(edge == 0)
            break;
    }
    for(int i = 0; i < Network_Size; i++)
    {
        for(int j = 0; j < adjlist[i].size(); j++)
        {
            outfile_ER_adjlist  << adjlist[i][j] << ' ';
        }
        outfile_ER_adjlist << endl;
    }

    for(int i = 0; i < Network_Size; i++)
    {
        outfile_ER_degree << degree[i] << endl;
    }
    return 0;
}

算法二C++代码实现：

#include 
#include 
#include 
#include 
#include 
#include "mt19937ar.c"
#include 
#include 

using namespace std;

int main()
{
    int Network_Size = 100000;       //网络节点数
    double p = 0.00004;       //连边概率
    unsigned long idum;                   //高精度随机种子生成器初始化
    idum=(unsigned long)time(NULL);
    init_genrand(idum);

    vector degree(Network_Size,0);             //节点度
    vector > adjlist(Network_Size);     //网络邻接链表

    ofstream outfile_ER_adjlist;
    ofstream outfile_ER_degree;
    double r;
    outfile_ER_adjlist.open("ER_adjlist.txt");
    outfile_ER_degree.open("ER_degree.txt");


    for(int i = 0; i < Network_Size; ++i)
    {
        for(int j = i + 1; j < Network_Size; ++j)
        {
            r = genrand_real2();
            if(r < p)
            {
                adjlist[i].push_back(j);
                degree[i]++;
                adjlist[j].push_back(i);
                degree[j]++;
            }
        }
    }

    for(int i = 0; i < Network_Size; i++)
    {
        for(int j = 0; j < adjlist[i].size(); j++)
        {
            outfile_ER_adjlist  << adjlist[i][j] << ' ';
        }
        outfile_ER_adjlist << endl;
    }

    for(int i = 0; i < Network_Size; i++)
    {
        outfile_ER_degree << degree[i] << endl;
    }
    return 0;
}

"mt19937ar.c"高精度随机种子生成器


//#include 
//#include "mt19937ar.h"


#define NN 624
#define M 397
#define MATRIX_A 0x9908b0dfUL   
#define UPPER_MASK 0x80000000UL 
#define LOWER_MASK 0x7fffffffUL 

static unsigned long mt[NN]; 
static int mti=NN+1; 


void init_genrand(unsigned long s)
{
    mt[0]= s & 0xffffffffUL;
    for (mti=1; mti> 30)) + mti);
        
        
        
        
        mt[mti] &= 0xffffffffUL;
        
    }
}





void init_by_array(unsigned long init_key[], int key_length)
{
    int i, j, k;
    init_genrand(19650218UL);
    i=1; j=0;
    k = (NN>key_length ? NN : key_length);
    for (; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
          + init_key[j] + j; 
        mt[i] &= 0xffffffffUL; 
        i++; j++;
        if (i>=NN) { mt[0] = mt[NN-1]; i=1; }
        if (j>=key_length) j=0;
    }
    for (k=NN-1; k; k--) {
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
          - i; 
        mt[i] &= 0xffffffffUL; 
        i++;
        if (i>=NN) { mt[0] = mt[NN-1]; i=1; }
    }

    mt[0] = 0x80000000UL; 
}


unsigned long genrand_int32(void)
{
    unsigned long y;
    static unsigned long mag01[2]={0x0UL, MATRIX_A};
    

    if (mti >= NN) { 
        int kk;

        if (mti == NN+1)   
            init_genrand(5489UL); 

        for (kk=0;kk> 1) ^ mag01[y & 0x1UL];
        }
        for (;kk> 1) ^ mag01[y & 0x1UL];
        }
        y = (mt[NN-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[NN-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];

        mti = 0;
    }

    y = mt[mti++];

    
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);

    return y;
}


long genrand_int31(void)
{
    return (long)(genrand_int32()>>1);
}


double genrand_real1(void)
{
    return genrand_int32()*(1.0/4294967295.0);
    
}


double genrand_real2(void)
{
    return genrand_int32()*(1.0/4294967296.0);
    
}


double genrand_real3(void)
{
    return (((double)genrand_int32()) + 0.5)*(1.0/4294967296.0);
    
}


double genrand_res53(void)
{
    unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6;
    return(a*67108864.0+b)*(1.0/9007199254740992.0);
}

"mt19937ar.c"使用方法

#include 
#include 
#include "mt19937ar.c"

#define N 1000

int main(void)
{
    int i;

    // idum 为随机数发生器的种子
    unsigned long idum;
    idum=(unsigned long)time(NULL);
    init_genrand(idum); // 随机数发生器初始化

    // genrand_int32() 函数生成一个0到2^31之间的整数
    // genrand_int32()%N 则生成一个 [0,N) 之间的整数
    printf(" 10 outputs of genrand_int32()n");
    for (i=0; i<100; i++) {
      printf("%10lu ", genrand_int32()%N);
      if (i%5==4) printf("n");
    }

    // genrand_real2() 函数生成一个 [0,1) 之间的双精度随机数
    printf("n 10 outputs of genrand_real2()n");
    for (i=0; i<10; i++) {
      printf("%10.8f ", genrand_real2());
      if (i%5==4) printf("n");
    }
    return 0;
}

结语

在科学研究中，往往算法二生成的ER随机网络更为常用。尽管两种算法存在很大差异，但在网络尺度非常大时，两者是等价的。这篇文章使用的代码较为简单，希望能够帮助刚进入复杂网络领域的小伙伴理解ER随机网络的实现。同时若文章有错误处，请指正，感谢大家。

复杂网络中ER随机网络C++代码实现

C/C++/C#相关栏目本月热门文章