按照圖形理論,聚集系數是表示一個圖形中節點聚集程度的系數,證據顯示,在現實中的網絡中,尤其是在特定的網絡中,由于相對高密度連接配接點的關系,節點總是趨向于建立一組嚴密的組織關系。在現實世界的網絡,這種可能性往往比兩個節點之間随機設立了一個連接配接的平均機率更大。
在很多網絡中,如果節點v1連接配接于節點v2,節點v2連接配接于節點v3,那麼節點v3很可能與v1相連接配接。這種現象展現了部分節點間存在的密集連接配接性質。可以用聚類系數(CC)來表示,在無向網絡中,聚類系數定義為: C = 2*n/(k*(k-1))其中,n表示在節點v的所有k個鄰居間的邊數。
#include <bits/stdc++.h>
#define N 5
#define M 8
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define m(a, x) memset(a, x, sizeof(a))
#define fs(u,v) fscanf(fp1,"%d %d",&(u),&(v))
using namespace std ;
FILE *fp1=fr("shuju.dat") , *fq1=fw("jiju.dat");
double s[N] , cc[N];
int du[N],a[N][N],b[N][N];
void read_data()//讀入資料
{
m(a,0) , m(b,0);
for (int i=0;i<M;i++)
{
int u , v;
fs(u,v);//讀入資料
a[u][v]=a[v][u] = 1 ;//無向圖
}
for (int i=0;i<N;i++) for (int j=0;j<N;j++) b[i][j]=a[i][j]*2;//計算鄰接矩陣
fprintf(fq1,"該圖每個點的度數為:\n");
for(int i=0;i<N;i++)
{
int l=0 ;
for (int j=0;j<N;j++) if(b[i][j]) l++;
du[i]=l;
fprintf(fq1,"%d %d\n",i,du[i]);
}
fprintf(fq1,"\n");
return;
}
void get_cluser()//求集聚系數
{
int s1,l1,s2;
double sum, ave ;
fprintf(fq1,"每個點的集聚系數為:\n");
for (int i=0;i<N;i++)
{
l1=0;
memset(s,0,sizeof(s));
if(du[i]>=2)
{
for (int j=0;j<N;j++) if(b[i][j]) s[j]=1;
for (int k=0;k<N;k++)
{
if(s[k]==1)
{
s1=k;
for (int x=s1;x<N;x++)
{
if(s[x]==1)
{
s2=x;
if(b[s1][s2]) l1++;
}
}
}
}
cc[i]=(2.0*l1)/((du[i]*(du[i]-1)));
}
if(du[i]!=0) fprintf(fq1,"%d %f\n",i,cc[i]);
}
fprintf(fq1,"\n");
sum=0.0;
for(int i=0;i<N;i++) sum+=cc[i]*1.0;
ave=sum/N;
fprintf(fq1,"平均集聚系數為:%f\n",ave);
return;
}
int main()
{
read_data();
get_cluser();
fclose(fp1);
fclose(fq1);
return 0;
}