聚类系数可调的无标度网络生成算法

0. BA无标度网络模型简单介绍：实际网络的两个重要的特性：（1）增长性：即网络的规模是不断的增长的，ER随机图和WS小世界模型中的网络的大小是固定（2）优先连接（Preferential attachment以下简称PA）：新的节点更倾向于和那些具有较高的连接度的hub节点相连。这种现象也叫作“富者更富（Rich get richer）”或者是“马太效应”

土肥宅娘口三三

8665人浏览 · 2017-04-17 22:33:25

土肥宅娘口三三 · 2017-04-17 22:33:25 发布

0. BA无标度网络模型简单介绍：

实际网络的两个重要的特性：

（1）增长性：即网络的规模是不断的增长的，ER随机图和WS小世界模型中的网络的大小是固定

（2）优先连接（Preferential attachment以下简称PA）：新的节点更倾向于和那些具有较高的连接度的hub节点相连。这种现象也叫作“富者更富（Rich get richer）”或者是“马太效应”

本文主要实现Petter Holme发表在PRE上的一篇paper《Growing scale-free networks with tunable clustering》中讲述的构造聚类系数可以调节的BA网络的算法。

1.论文简单介绍

通过在标准的BA网络模型构造算法中添加一步“构造三角形”的方法，可以通过不同的参数形成具有不同的聚类系数的网络。通过该算法生成的网络在保持了经典的BA网络的幂律度分布特性的同时，还具有较高的聚类系数，而经典的BA网络在网络的规模越来越大的时候，网络的聚类系数趋于0.

2. 算法流程
        （1）：   初始时，网络中有 M_0 个全连接的节点。
        （2）：   每一步新增一个带有 M 条边的节点 i 。
        （3）：   PA。节点 i 先采用和BA网络模型相同的优先连接规则，和网络中的已经存在的节点 j 做一次优先连接。
        （4）：   TF（triad formation）。为了增加网络的聚类系数，接下来节点 i 将以概率 pt 随机的和节点 j 的邻居做三角连接，以 1 - pt 的概率做优先连接。直到所有的 m 条边都被添加完。网络在添加下一个节点。

算法中引入triad formation可以理解为当我们认识一个人的时候，也会想要去认识他的朋友。

（BA无标度网络模型的构造算法可以参见我先前的文章）

3. 程序源码

程序中出现的由main函数带入的参数m_t为论文中介绍的控制参数，其中m_t = （M - 1）*Pt，公式中的M为每次添加一个节点的时候要带入网络中的边数，Pt为上述的算法流程中出现的概率。通过输入不通的参数m_t可以调控网络的聚类系数。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct Node;
typedef struct Node* NodePtr;
typedef struct Node{
	int degree;
	double weight;
	double probabilityDistribution;
}Node;

Node* decisionMaking;
int** adjacentMatrix;
int* initalNetwork;

int NETWORK_SIZE, M, M_0;	
				/*
				 * NETWORK_SIZE:网络的大小
				 * M:		每次向已有的网络中添加一个节点M条边
				 * M_0:		初始的全联通网络的大小
				 * */
double m_t;	
				/*
			 	* 用于调控网络的聚类系数 m_t = (M-1) * Pt
			 	*/

void initial();
void initalNetwork_M0_connected();
void updateDecisionMakingData();
void generateFreeScaleNetwork();
void saveNetwork();

double calClusteringCoefficient();
double calClusteringCoefficientOfNode();
void cal_averageDegree();

int main(int argc, char** argv)
{
	if( 5 != 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("\t3.the size of add edges per times.\n");
		printf("\t4.the control parameter m_t.\n");
		printf("\texample: \"a.exe 100 3 3 0.9\"\n");
		exit(0);
	}
	srand((unsigned)time(NULL));
	NETWORK_SIZE = atoi(argv[1]);
	M_0 = atoi(argv[2]);
	M = atoi(argv[3]);
	m_t = atof(argv[4]);

	initial();
	initalNetwork_M0_connected();
	generateFreeScaleNetwork();
	saveNetwork();

	printf("ClusteringCoefficient : %f\n", calClusteringCoefficient());
	cal_averageDegree();
	//write2file(adjacentMatrix, NETWORK_SIZE, "freeScaleWithCluster_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;

	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;
	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;
	int connectedNodeSet[M];
	for( i = 1; i <= NETWORK_SIZE - M_0; 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--];

		/*
		 * one BA step
		 * */
		//对于选择到的节点new_node_value(i)做一次优先连接, 连接到一个网络中已经存在的节点。
		flag = 0;
		random_decision = (rand() % NETWORK_SIZE) / (double)NETWORK_SIZE;
		for( k = 1; k <= NETWORK_SIZE; k++ )
			if( decisionMaking[k].probabilityDistribution >= random_decision && decisionMaking[k].degree != 0 && adjacentMatrix[new_node_value][k] != 1 )
			{	
				targetNode = k;	
				flag = 1;
				break;
			}
		if( flag == 0 )	
			for( k = 1; k <= NETWORK_SIZE; k++ )
				if( decisionMaking[k].degree != 0 && adjacentMatrix[new_node_value][k] != 1 )
				{
					targetNode = k;
					break;
				}
		adjacentMatrix[new_node_value][targetNode] = adjacentMatrix[targetNode][new_node_value] = 1;

		/*
		 * TF step
		 * */
		int remainEdges = M - 1;
		while( remainEdges > 0 )
		{
			//以概率pt做三角连接
			double exeTFConnect = (rand()%NETWORK_SIZE)/(double)NETWORK_SIZE;
			if( exeTFConnect < ( m_t / (double)(M - 1) ) )
			{
				int neighbors_Number = 0;
				for( k = 1; k <= NETWORK_SIZE; k++ )
					if( k != new_node_value && adjacentMatrix[targetNode][k] && !adjacentMatrix[k][new_node_value] )
						neighbors_Number++;
				if( neighbors_Number != 0 )
				{
					int neighborSet[neighbors_Number];
					int temp_count = 0;
					for( k = 1; k <= NETWORK_SIZE; k++ )
						if( k != new_node_value && adjacentMatrix[targetNode][k] && !adjacentMatrix[k][new_node_value] )
							neighborSet[temp_count++] = k;
					int random_neighbor_index = rand() % neighbors_Number;
					adjacentMatrix[neighborSet[random_neighbor_index]][new_node_value] = adjacentMatrix[new_node_value][neighborSet[random_neighbor_index]] = 1;
					remainEdges--;
				}
			}

			if( remainEdges <= 0 )
				continue;

			//以概率1-pt做优先连接
			double exeBAconnect = (rand()%NETWORK_SIZE)/(double)NETWORK_SIZE;
			if( exeBAconnect < 1 - (m_t / (double)(M - 1)) )
			{
				flag = 0;
				random_decision = (rand() % 1000) / (double)1000;
				for( k = 1; k <= NETWORK_SIZE; k++ )
					if( decisionMaking[k].probabilityDistribution >= random_decision && decisionMaking[k].degree != 0 && adjacentMatrix[new_node_value][k] != 1 )
					{	
						targetNode = k;	
						flag = 1;
						break;
					}
				if( flag == 0 )	
					for( k = 1; k <= NETWORK_SIZE; k++ )
						if( decisionMaking[k].degree != 0 && adjacentMatrix[new_node_value][k] != 1 )
						{
							targetNode = k;
							break;
						}
				adjacentMatrix[new_node_value][targetNode] = adjacentMatrix[targetNode][new_node_value] = 1;

				remainEdges--;
			}
		}
		updateDecisionMakingData();		
	}
}

void saveNetwork()
{
	FILE* fwrite;
	int i, j;
	if( NULL == (fwrite = fopen("SF_tunableClustering.data", "w")) )
	{
		printf("open file error");
		exit(0);
	}
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		for( j = 1; j <= NETWORK_SIZE; j++ )
		{
			fprintf(fwrite, "%d ", adjacentMatrix[i][j]);	
		}
		fprintf(fwrite, "\n");
	}
	fclose(fwrite);
}



/****************************************************************************************************
 *
 * 	计算网络的聚类系数
 *
 *****************************************************************************************************/
double calClusteringCoefficient()
{
	int i;
	double clusteringCoefficient = 0.0;
	for( i = 1; i <= NETWORK_SIZE; i++ )
		clusteringCoefficient += calClusteringCoefficientOfNode(i);
	return clusteringCoefficient / NETWORK_SIZE;
}
/*
 * 计算每一个节点的聚类系数
 * */
double calClusteringCoefficientOfNode(int node)
{
	int neighbors, triad;
	int i, j;
	triad = neighbors = 0;
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		for( j = i + 1; j <= NETWORK_SIZE; j++ )
		{
			if( adjacentMatrix[node][i] && adjacentMatrix[node][j] && adjacentMatrix[i][j] )
			{
				triad++;
			}
		}
	}
	for( i = 1; i <= NETWORK_SIZE; i++ )
		if( adjacentMatrix[node][i] )
			neighbors++;
	return (double)(triad * 2)/(double)(neighbors * (neighbors - 1));
}

/*
 * 计算网络的平均度
 * */
void cal_averageDegree()
{
	int i, j;
	int degree = 0;
	for( i = 1; i <= NETWORK_SIZE; i++ )
		for( j = 1; j <= NETWORK_SIZE; j++ )
			if( adjacentMatrix[i][j] )
				degree++;
	printf("the average degree is %f\n", degree/(double)NETWORK_SIZE);
}

4.论文结果复现

在论文中给出了控制参数m_t对于网络的聚类系数的影响。下图分别为论文给出的结果和自己复现的结果，有一定的差异，但是总体的应该是趋势是正确的。