BA无标度网络模型构造算法

昵称41280102 2017-09-18

展开全文

BA无边度网络模型构造算法

（1）增长：从一个具有 m_0 个节点的联通网络开始，每次引入一个新的节点, 并且连到 m 个已经存在的节点上，这里 m <= m_0。

（2）优先连接：一个新的节点与一个已经存在的节点 i 相连的概率 w 与节点 i 的度 k_i 之间的关系为 w = k_i / ( k_1 + k_2 + k_3 + ... + k_n ),其中n为网络中的节点的总个数。

特别的说明下代码中涉及到结构体Node的作用和思路：

三个数据域：

(1) degree：表示节点的度
(2) weight：表示被选择的概率，即 w_i = k_i / ( k_1 + k_2 + ... + k_n )
(3) probabilityDistribution: 给出每一个节点的概率分布，作用是通过产生0~1之间的随机数来做出决策。
为什么在有了weight的情况下还需要用probabilityDistribution？
example：假设在一个网络中一共有5个节点，每个节点的度如下: d_1 = 4, d_2 = 1, d_3 = 2, d_4 = 2, d_5 = 1.
那么可以计算出每个节点的weight如下: w_1 = 0.4, w_2 = 0.1, w_3 = 0.2, w_4 = 0.2, w_5 = 0.1
也就是说, 当有一个新的节点出现时候，它连接到节点1的概率为0.4，连接到节点2的概率为0.1, ...
可以用下图来表示:

这个时候，这个新的节点要选择已有网络中的那个节点连接是随机的，但是和这些已有节点的度是成正比的，度愈大的节点越有可能被连接，此时，由系统产生一个 0~1 之间的随机数，比如0.6,那么则选择新的节点与节点 3 相连。

代码实现

[cpp] view plain copy

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#include "for_plot.c"
int NETWORK_SIZE, M, M_0;
struct Node;
typedef struct Node* NodePtr;
typedef struct Node{
int degree;
double weight;
double probabilityDistribution;
}Node;
Node* decisionMaking;
int** adjacentMatrix;
int* initalNetwork;
void initial();
void initalNetwork_M0_connected();
void updateDecisionMakingData();
void generateFreeScaleNetwork();
void showAdjacentMatrix();
void writeDataToFile();
int main(int argc, char** argv)
{
if( 4 != argc )
{
printf("this algorithm requires 4 user-specify parameters\n");
printf("\t1.the size of network\n");
printf("\t2.the initial size of network\n");
printf("\t1.the size of \n");
printf("\texample: \"a.exe 100 3 3\"\n");
exit(0);
}
NETWORK_SIZE = atoi(argv[1]);
M_0 = atoi(argv[2]);
M = atoi(argv[3]);
srand((unsigned)time(NULL));
initial();
initalNetwork_M0_connected();
generateFreeScaleNetwork();
writeDataToFile();
showAdjacentMatrix();
write2file(adjacentMatrix, NETWORK_SIZE, "freeScale_edges.data");
return 0;
}
void initial()
{
if( !(decisionMaking = (NodePtr)malloc(sizeof(Node) * (NETWORK_SIZE + 1))) )
{
printf("decisionMaking* malloc error\n");
exit(0);
}
if( !(adjacentMatrix = (int**)malloc(sizeof(int*) * (NETWORK_SIZE + 1))) )
{
printf("adjacentMatrix** malloc error\n");
exit(0);
}
int i;
for( i = 1; i <= NETWORK_SIZE; i++ )
{
if( !(adjacentMatrix[i] = (int*)malloc(sizeof(int) * (NETWORK_SIZE + 1))) )
{
printf("adjacentMatrix[%d]* malloc error\n", i);
exit(0);
}
}
if( !(initalNetwork = (int*)malloc(sizeof(int) * (M_0 + 1))) )
{
printf("initalNetwork* malloc error\n");
exit(0);
}
}
/*
* 初始化：在NETWORK_SIZE中随机选择M_0个节点构成连通的网络。
* */
void initalNetwork_M0_connected(){
int i, j, randomFirst, randomSecond;
for( i = 1; i <= NETWORK_SIZE; i++ )
for( j = 1; j <= NETWORK_SIZE; j++ )
adjacentMatrix[i][j] = 0;
// 随机产生M_0个节点
for( i = 1; i <= M_0; i++ )
{
initalNetwork[i] = rand() % NETWORK_SIZE + 1;
for( j = 1; j < i; j++ )
if( initalNetwork[i] == initalNetwork[j] )
{
i--;
break;
}
}
for( i = 1; i < M_0; i++ )
adjacentMatrix[initalNetwork[i]][initalNetwork[i+1]] = adjacentMatrix[initalNetwork[i+1]][initalNetwork[i]] = 1;
adjacentMatrix[initalNetwork[M_0]][initalNetwork[1]] = adjacentMatrix[initalNetwork[1]][initalNetwork[M_0]] = 1;
//showAdjacentMatrix();
updateDecisionMakingData();
}
/*
* 通过adjacentMatrix更新decisionMaking数组
* */
void updateDecisionMakingData(){
int i, j, totalDegree = 0;
for( i = 1; i <= NETWORK_SIZE; i++ )
decisionMaking[i].degree = 0;
for( i = 1; i <= NETWORK_SIZE; i++ )
for( j = 1; j <= NETWORK_SIZE; j++ )
decisionMaking[i].degree += adjacentMatrix[i][j];
for( i = 1; i <= NETWORK_SIZE; i++ )
totalDegree += decisionMaking[i].degree;
//printf("\n%d\n", totalDegree);
for( i = 1; i <= NETWORK_SIZE; i++ )
decisionMaking[i].weight = decisionMaking[i].degree/(double)totalDegree;
decisionMaking[1].probabilityDistribution = decisionMaking[1].weight;
for( i = 2; i <= NETWORK_SIZE; i++ )
decisionMaking[i].probabilityDistribution = decisionMaking[i - 1].probabilityDistribution + decisionMaking[i].weight;
}
/*
* 构造BA无标度网络模型
* */
void generateFreeScaleNetwork(){
int i, k, j = 1, length = 0;
int random_auxiliary_old[NETWORK_SIZE + 1];
int random_auxiliary[NETWORK_SIZE + 1 - M_0];
/*
* 要保证每次引入一个<新的>的节点，所以要随机选择不重复的节点加入，并且把初始网络中的M_0个节点先删除
* */
for( i = 1; i <= NETWORK_SIZE; i++ )
random_auxiliary_old[i] = i;
for( i = 1; i <= M_0; i++ )
random_auxiliary_old[initalNetwork[i]] = 0;
for( i = 1; i <= NETWORK_SIZE; i++ )
if( random_auxiliary_old[i] != 0 )
random_auxiliary[j++] = random_auxiliary_old[i];
/*
* 添加新的节点构造无标度网络
* */
int new_node_index, new_node_value;
double random_decision = 0.0;
int targetNode; //表示找到的已经在网络中的将要连接的节点
length = NETWORK_SIZE - M_0;
int flag;
for( i = 1; i <= NETWORK_SIZE - M_0; i++ )
{
new_node_index = rand() % length + 1;
new_node_value = random_auxiliary[new_node_index];
random_auxiliary[new_node_index] = random_auxiliary[length--];
for( j = 1; j <= M; j++ ) //根据概率连接到已存在网络中的M个节点，不可以重边，不可以自连。
{
flag = 0;
random_decision = (rand()%1000)/(double)1000;
for( k = 1; k <= NETWORK_SIZE; k++ )
{
// 从第一个节点到最后一个节点比较probabilityDistribution和random_desction的大小，
// 由于probabilityDistribution是有序的，所以可以使用一些高级的算法来提高查找的效率.
if( decisionMaking[k].probabilityDistribution >= random_decision && decisionMaking[k].degree != 0 && adjacentMatrix[new_node_value][k] != 1 )
{
/*
*
* 如何按照可能性大小来选择要连哪一个点：
* 选择的已经在网络中的点是：随机产生的0-1之间的概率p，找这样的点：
* 它的累加概率（probabilityDistribution）是大于p的最小的值所对应的点。
*
*/
targetNode = k;
flag = 1;
break;
}
}
if( flag == 0 )
/*
* 之前少考虑了这种情况，因为总要选择一个网络中的点接入。但是当产生了比较大的随机概率p，可能
* 在他后面（按probabilityDistribution来说）没有可选的点（要么选择过了，要么不在网络中），则重新开始
*/
{
for( k = 1; k <= NETWORK_SIZE; k++ )
{
if( decisionMaking[k].degree != 0 && adjacentMatrix[new_node_value][k] != 1 )
{
targetNode = k;
break;
}
}
}
//printf(" target node is %d\n", targetNode);
adjacentMatrix[new_node_value][targetNode] = adjacentMatrix[targetNode][new_node_value] = 1;
}
updateDecisionMakingData(); //else新选的加入节点和已有网络中的M个边都链接后再更新
}
}
void showAdjacentMatrix(){
int i, j;
int numberOfEage = 0;
printf("\tshow adjacentMatrix\n");
for( i = 1; i <= NETWORK_SIZE; i++ )
{
for( j = 1; j <= NETWORK_SIZE; j++ )
{
printf("%d", adjacentMatrix[i][j]);
if( adjacentMatrix[i][j] == 1 )
numberOfEage++;
}
printf("\n");
}
printf("the number of eage is %d\n", numberOfEage/2);
}
void writeDataToFile(){
FILE* fout;
if( NULL == (fout = fopen("freeScaleNetwork.data", "w")))
{
printf("open file(freeScaleNetwork) error!\n");
exit(0);
}
int i;
int j;
for( i = 1; i <= NETWORK_SIZE; i++ )
{
for( j = 1; j <= NETWORK_SIZE; j++ )
fprintf(fout, "%d ", adjacentMatrix[i][j]);
fprintf(fout, "\n");
}
}