漏桶算法java实现,pca算法matlab实现

博主第一次写社团划分的算法，原本CNM算法应该是通过维护一个大根堆来实现的，因为对这个算法还没那么熟，所以用的普通方法和邻接矩阵来实现的。不过不管怎么说，算法的基于贪婪策略，根据模块度划分社团的核心思想一定是不变的。公式的话，应该已经有不少文章介绍，大家可以参考，我就只贴代码了。

#include<iostream>#include<cstring>#define N 110#define INF 100000000using namespace std;int n,M,row,col,A[N][N],book[N],root[N];float delta_Q[N][N],a[N],Q,now_Q_change;void readData();void initialize();float themax();void update_Q_delta();void printResult();int main(){ cin>>n; Q=0; memset(book,0,sizeof(book)); readData(); initialize(); now_Q_change=themax(); //cout<<"now_Q_change是:"<<now_Q_change<<endl; while (now_Q_change>0) { //cout<<"(row,col):("<<row<<","<<col<<")"<<endl; book[col]=1; root[col]=row; cout<<"root["<<col<<"]:"<<row<<endl; cout<<"curmax:"<<now_Q_change<<endl; Q+=now_Q_change; update_Q_delta(); now_Q_change=themax(); cout<<"now_Q_change是:"<<now_Q_change<<endl; } printResult(); return 0;}void readData(){ for (int i=1;i<=n;i++) root[i]=-1; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { cin>>A[i][j]; if (A[i][j]&&i>j) M++; } } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (A[i][j]!=0) { a[i]++; } delta_Q[i][j]=-INF; } } for (int i=1;i<=n;i++) { a[i]/=(2*M); } return;}void initialize(){ float temp=0.5; temp/=M; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (A[i][j]>0) { delta_Q[i][j]=temp-a[i]*a[j]; } else delta_Q[i][j]=0; } } return ;}float themax(){ float curmax=-INF; for (int i=1;i<=n;i++) { if (book[i]==1) continue; for (int j=1;j<=n;j++) { if (book[j]==1) continue; if (curmax<delta_Q[i][j]) { curmax=delta_Q[i][j]; row=i; col=j; } } } cout<<"(row,col):("<<row<<","<<col<<")"<<endl; return curmax;}void update_Q_delta(){ //row行消失，只更新col行和col列，col列用col行对称过去即可 for (int i=1;i<=n;i++) { if (book[i]==1||col==i) continue; if (A[col][i]!=0&&A[row][i]!=0) { delta_Q[col][i]=delta_Q[col][i]+delta_Q[row][i]; } else if (A[col][i]!=0&&A[row][i]==0) { delta_Q[col][i]=delta_Q[col][i]-2*a[row]*a[i]; } else if (A[col][i]==0&&A[row][i]!=0) { delta_Q[col][i]=delta_Q[row][i]-2*a[col]*a[i]; } } for (int i=1;i<=n;i++) { if (book[i]==1) continue; delta_Q[i][col]=delta_Q[col][i]; } a[col]+=a[row]; return ;}void printResult(){ cout<<"Q值为:"<<Q<<endl; for (int i=1;i<=n;i++) { cout<<"节点"<<i<<"的根为："<<root[i]<<endl; } for (int i=1;i<=n;i++) { int now=i; while (root[now]!=-1) { now=root[now]; } cout<<"节点"<<i<<"的根是节点："<<now<<endl; } return ;}

测试数据及结果：