WS小世界ネットワークモデル構築アルゴリズム

/***********************************************************************************************************************
 * WS         ：
 * 		（1）      ：      N             ，
 * 		                     K/2     ，K   。
 * 		（2）     ：   p                  ，
 * 		                    ，             
 * 		               ，             。
 *
 * 	Note： p = 0         ，p = 1          。    p           
 * 	               。          ，               1,2,3,..N,  
 * 	             i ，        i    K/2       ，           i， 
 * 	         p                      。
 ***********************************************************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define NETWORK_SIZE 	100	//     
#define K		6	//         K，  ：            K/2     。K   
#define P		0.3	//   p                 

int adjacentMatrix[NETWORK_SIZE + 1][NETWORK_SIZE + 1];
void generate_NearestNeighborCoupledNetwork();
void generateSmallWorld();
void writeDataToFile();

int main(){
	srand((unsigned)time(NULL));
	generate_NearestNeighborCoupledNetwork();
	generateSmallWorld();
	writeDataToFile();
	return 0;
}

/*
 *            :           K/2     
 * */
void generate_NearestNeighborCoupledNetwork(){
	int i;
	int j;
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		for( j = 1; j <= NETWORK_SIZE; j++ )
		{
			adjacentMatrix[i][j] = 0;
		}
	}
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		for( j = 1; j <= K/2; j++ )
		{
			if( i - j >= 1 && i + j <= NETWORK_SIZE )
			{
				adjacentMatrix[i][i - j] = 1;
				adjacentMatrix[i][i + j] = 1;
			}
			else if( i - j < 1 )
			{
				adjacentMatrix[i][NETWORK_SIZE + i - j] = 1;
				adjacentMatrix[i][i + j] = 1;
			}
			else if( i + j > NETWORK_SIZE )
			{
				adjacentMatrix[i][i + j - NETWORK_SIZE] = 1;
				adjacentMatrix[i][i - j] = 1;
			}
		}
	}
	//test
	/*
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		for( j = 1; j <= NETWORK_SIZE; j++ )
		{
			printf("%d ", adjacentMatrix[i][j]);
		}
		printf("
");
	}
	*/
	//test END
}

/*
 *   WS     
 * */
void generateSmallWorld(){
	int i;
	int j;
	double isChange = 0.0;			//     0~1    ，              ， isChange<p ，    
	int re_connectRandomNode;		//            ，               (      ，      )
	int hasEage[NETWORK_SIZE + 1];		//                  ，      ，           
	int number_changedEage = 0;
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		for( j = 1; j <= K/2; j++ )
		{
			//     ：adjacentMatrix[i][i + j];   : adjacentMatrix[i][i + j - NETWORK_SIZE];
			isChange = (rand()%NETWORK_SIZE)/(double)NETWORK_SIZE;
			//printf("(%d, %d)random probability is %f
", i, i+j, isChange);
			if( isChange < P )	//  
			{
				while( 1 )	//        ：          
				{
					re_connectRandomNode = (rand() % NETWORK_SIZE) + 1;
					if( adjacentMatrix[i][re_connectRandomNode] == 0 && re_connectRandomNode != i )
						break;
				}
				if( i + j <= NETWORK_SIZE )
				{
					adjacentMatrix[i][i + j] = 0;
					adjacentMatrix[i + j][i] = 0;
				}
				else	//i + j > NETWORK_SIZE
				{
					adjacentMatrix[i][i + j - NETWORK_SIZE] = 0;
					adjacentMatrix[i + j - NETWORK_SIZE][i] = 0;
				}
				adjacentMatrix[i][re_connectRandomNode] = 1;
				adjacentMatrix[re_connectRandomNode][i] = 1;
				number_changedEage++;
			}
			else
			{
				//printf("(%d, %d) no change
", i, i+j);
			}	
		}
	}
	//test
	printf("------------Small World NetWork------------------
");
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		for( j = 1; j <= NETWORK_SIZE; j++ )
		{
			printf("%d", adjacentMatrix[i][j]);
		}
		printf("
");
	}
	printf("the number of changed eage is %d, ratio is %f
", number_changedEage, (double)number_changedEage/(NETWORK_SIZE * K / 2));
}

/*
 *           adjacentMatrix     
 * */
void writeDataToFile(){
	FILE* fout;
	int i;
	int j;
	if( NULL == (fout = fopen("smallWorldNetwork.data", "w")))
	{
		printf("open file(smallWorldNetwork.data) error!");
		exit(0);
	}
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		for( j = 1; j <= NETWORK_SIZE; j++ ){
			fprintf(fout, "%d ", adjacentMatrix[i][j]);
		}
		fprintf(fout,"
");
	}
	fclose(fout);
}

/*
 *               
 * */
double clusterArray[NETWORK_SIZE + 1];
double calculateCluter(){
	int i;
	int j;
	int k = 1;
	int t, n;
	int numberOfNeighbor = 0;
	int* neighborArray;
	int cluster = 0;
	double finalcluster = 0.0;
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		numberOfNeighbor = 0;
		cluster = 0;
		k = 1;
		for( j = 1; j <= NETWORK_SIZE; j++ )
		{
			if( adjacentMatrix[i][j] == 1 )
			{
				numberOfNeighbor++;
			}
		}
		neighborArray = (int*)malloc(sizeof(int)*(numberOfNeighbor + 1));
		if( neighborArray == NULL )
		{
			printf("malloc error!
");
			exit(0);
		}
		//   i      
		for( j = 1; j <= NETWORK_SIZE; j++ )
		{
			if( adjacentMatrix[i][j] == 1 )
			{
				neighborArray[k++] = j;
			}
		}
		//test
		/*
		for( j = 1; j <= numberOfNeighbor; j++ )
			printf("%d ", neighborArray[j]);
		printf("
");
		*/
		//testEND
		for( t = 1; t < numberOfNeighbor; t++ )
		{
			for( n = t + 1; n <= numberOfNeighbor; n++ )
			{
				if( adjacentMatrix[neighborArray[t]][neighborArray[n]] == 1 )
					cluster++;
			}
		}
		//printf("%d
", cluster);
		clusterArray[i] = cluster/(double)(numberOfNeighbor * (numberOfNeighbor - 1) / 2);
		free(neighborArray);
	}
	
	for( i = 1; i <= NETWORK_SIZE; i++ )
		finalcluster += clusterArray[i];
	finalcluster = finalcluster/(double)NETWORK_SIZE;
	//test
	/*
	printf("print cluster of all node is 
");
	for( i = 1; i <= NETWORK_SIZE; i++ )
	{
		printf("%f\t", clusterArray[i]);
	}
	*/
	//test END
	return finalcluster;
}