算法大作业.docx
- 文档编号:10258763
- 上传时间:2023-05-24
- 格式:DOCX
- 页数:47
- 大小:221.04KB
算法大作业.docx
《算法大作业.docx》由会员分享,可在线阅读,更多相关《算法大作业.docx(47页珍藏版)》请在冰点文库上搜索。
算法大作业
算法大作业
姓名学号
基于社团评估函数Q的社区网络检测算法
1、问题描述
随着对网络性质的物理意义和数学特性的深入研究,人们发现许多实际网络都具有一个共同性质,即社团结构。
也就是说,整个网络是由若干个“群”或“团”构成的。
每个群内部的节点之间的连接相对非常紧密,但是各个群之间的连接相对来说却比较稀疏,如图所示。
图中的网络包含三个社团,分别对应图中三个虚线圆圈包围的部分。
在这些社团内部,节点之间的联系非常紧密,而社团之间的联系就稀疏的多。
一般而言,社团可以包含模块、类、群、组等各种含义。
例如,www可以看成是由大量网站社团组成,其中同一个社团内部的各个网站所讨论的都是一些有共同兴趣的话题。
类似的,在生物网络或者电路网络中,同样可以根据该节点根据其不同的性质划分为不同的社团。
揭示网络中的社团结构,对于了解网络结构与分析网络特性都是很重要的。
社团结构分析在生物学、物理学、计算机图形学和社会学中都有广泛的应用。
问题模型化后,变成在一个无向图
中,如何根据节点之间的连接关系,对图进行划分,使之成为可分的网络社团。
2、算法描述
原理描述
每次新扩展一个距离最短的点,更新与其相邻的点的距离。
当所有边权都为正时,由于不会存在一个距离更短的没扩展过的点,所以这个点的距离永远不会再被改变,因而保证了算法的正确性。
不过根据这个原理,用Dijkstra求最短路的图不能有负权边,因为扩展到负权边的时候会产生更短的距离,有可能就破坏了已经更新的点距离不会改变的性质。
伪代码
输入:
含权有向图
V={1,2,....,n}。
输出:
G中顶点1到其他顶点的距离。
1.X={1};Y←V-{1};
[1]←0
2.fory←2ton
3.Ify相邻于1then
[y]←length[1,y]
4.else
[y]←∞
5.endif
6.endfor
7.forj←1ton-1
令y∈Y,使得
[y]为最小
X←X
{y}
Y←Y
{y}
for每条边(y,w)
Ifw∈Yand
[y]+length[y,w]<
[w]then
[w]←
[y]+length[y,w]
Endfor
8.Endfor
社团评估函数Q
设有i、j社团,
为i社团中点的度与无向图所有的度的比值,
,
为从i社团一点不经过其他点,直接连接外部社团的边数与无向图所有边数的比值。
则可得到刻画社团划分关系及内连接与外连接的函数
,当Q>0.3时,划分为典型社团,Q<0.3时为非典型社团。
3、流程图
4、源代码
社区网络检测代码
#include
#include
#include
#definevector25//主要参数修改部分。
//关于邻接矩阵中的编码问题只要保证第一行为first节点的连接关系就可以,对其他节点的描述可随意排序,
//最终的编码将有计算机完成,以a的值保存节点标号对于连接关系不是很密集的图,
typedefstructnode//定义节点,包含自身名称(永久),连接关系(n维)——这一点可以拓展为有向图。
{
intname;//节点名称,个别算法中用处不太大
intrealword;
node*conn[vector];//图的连接关系体现。
intedge[vector];//对于有向或无向图中的边的权值,几乎不可能出现一个节点和所有节点都有连接的情况。
即edge[vecrot-1]必定为0
node*parent;//定义为父辈节点
charflag1,flag2;//定义为标志位,用以标记是否被访问,是否为其他节点的父辈节点。
inta,b;//在寻找关节点算法中应用
intw;//在dijkstra算法中应用
}
vertex;
typedefstruct
{
vertexv[vector];
intconter;
}final;
typedefstructnode3//分割结点集链表形式,信息以结点编号存入数组中;
{
intpair[2];
node3*next;
}cutlink;
typedefstruct//在寻找关节点的算法当中的结果返回,节点名称,节点数目。
{
intv[vector];
intcounter;
}finlist;
typedefstruct//用以记录生成最短路径时的具体路径。
{
intvalue[vector][vector];//用矩阵存储记录每一个edge(pairofvertex)成为最短路径的次数
intaccount;
}least_way;
typedefstruct//节点指针列表,采用线性表结构。
方便找到所有的节点
{
vertex*element[vector];
intnumber;
}pointlist;
typedefstructnode1//整体构成链表形式的寄存器,可以任意存取节点地址。
利于不采用序号方式存取节点地址的使用方式
{
vertex*element2;
node1*next;
}cell;
typedefstruct
{
cell*front,*rear;
}midlist;
typedefstruct//dijkstra算法的最基本输出
{
intname;
intweight[vector];
}dijkstra_result;
//***********************一些全局变量
pointlist*communities[vector];//检测结果:
每一个社团自成一个线性表
intcommunity_count;//记录下分成社团的个数
pointlist*orignal;//保留原有图结构用以计算Q值和比对结果
intall_the_edge;//记录下所有边的数值。
charbreaks;
//**************************
voidaddmidlist(midlist*openlist,vertex*v);//增加一个节点到队列尾部
floatcalculator(pointlist*all);//计算Q值评价现有的划分结果的好坏;但对于数量比较小的all表,如只有一个节点的,划分规则将有所变化
voidcheck_and_remove(midlist*openlist);
voidcopyelement(vertex*A,vertex*B);//复制节点的连接关系与编号
voiddelete_e(pointlist*all,inta,intb);//根据一次dijkstra全迭代,选择性删除一条被调用最多的edge的相应节点对连接关系
voiddetection(pointlist*all);
voiddijkstra(pointlist*all,least_way*way,intn);
voiddivide(pointlist*all,pointlist*child_all0,pointlist*child_all1);//基于成功分割后的一次源于all中第一个节点的dijkstra运算后各节点的w值完成划分
voidfind_the_next_one(midlist*openlist,least_way*A);//寻找的结果是对open表进行了更新,对open表中的节点的部分信息做更新,
voidinital(pointlist*all);
voidinitallist1(pointlist*&ex);//初始化所有结果列表,可用于open,close,all列表。
voidinitallist2(midlist*&ex);
voidnewget(pointlist*all);
voidprim_tree(pointlist*all,intn,least_way*&tree,FILE*fp);
voidwritedown(pointlist*all);//将可以认为是一个社团的节点加入到社团community_count中;
voidoutput();
//finlistarticpoints(vertex*first);
voidmain()
{
pointlist*all;
initallist1(all);
initallist1(orignal);
newget(all);
newget(orignal);
inital(all);
inital(orignal);
breaks='0';
detection(all);
output();
//根据分割结果确立新的一种对于原有all的二划分child_all[2](图变为非连通),并随之计算Q值,此算法可用递归调用,自顶向下,递归终止条件为所有的child_all[2]形成明显的社团
//二分割all子程序
//分别计算Q,对于小于0.3的进行递归式进入。
//返回到第一层程序结束
//采用静态数组指针保留每个社团内的vertex。
}
voidnewget(pointlist*all)//程序完成对一个邻接矩阵转化为一个无向图的转化;有待测试12,13
{
inti,j,m,ci=0,co=0;
FILE*fp;
vertex*inpoint[vector];
inpoint[0]=(vertex*)malloc(sizeof(vertex));
inpoint[0]->flag1='1';
all_the_edge=0;
if((fp=fopen("rand_matrx(6).dat","r"))==NULL)
{
printf("cannotopenthismat.\n");
}
for(i=0;i { inpoint[i]=NULL; } for(i=0;i { if(inpoint[i]==NULL) { inpoint[i]=(vertex*)malloc(sizeof(vertex)); inpoint[i]->flag1='1'; inpoint[i]->name=i;//改变命名方式,根据邻接矩阵的顺序进行命名 all->element[ci]=inpoint[i]; ci++; } all->element[i]->realword=i; for(j=0;j { fscanf(fp,"%d,",&m); if(m! =0) { if(inpoint[j]==NULL) { inpoint[j]=(vertex*)malloc(sizeof(vertex)); inpoint[j]->flag1='1'; inpoint[j]->name=j;//改变命名方式,根据邻接矩阵的顺序进行命名 all->element[ci]=inpoint[j]; ci++; } inpoint[i]->conn[co]=inpoint[j];//每次内循环中处理外循环节点的连接问题 inpoint[i]->edge[co]=m; co++; } } for(j=co;j { inpoint[i]->conn[j]=NULL; inpoint[i]->edge[j]=0; } all_the_edge+=co; co=0; } all_the_edge=all_the_edge/2; all->number=ci; fclose(fp); } voidinitallist1(pointlist*&ex)//初始化所有结果列表,可用于all列表。 { inti; ex=(pointlist*)malloc(sizeof(pointlist)); for(i=0;i { ex->element[i]=NULL; } ex->number=0; } voidinitallist2(midlist*&ex)//初始化所有的中间记录表midlist,采用链表方式,每一此访问都是蛮力搜索。 { ex=(midlist*)malloc(sizeof(midlist)); ex->front=(cell*)malloc(sizeof(cell)); ex->rear=ex->front; ex->rear->next=NULL; } voidinital(pointlist*all)//对all进行刷新,主要用于articpoints,dijkstra算法的初始化 { inti; for(i=0;i { all->element[i]->flag1='0'; all->element[i]->flag2='0'; all->element[i]->parent=NULL; all->element[i]->w=0; all->element[i]->a=0; all->element[i]->b=0; } } voidaddmidlist(midlist*openlist,vertex*v)//增加一个节点到队列尾部 { cell*add; add=(cell*)malloc(sizeof(cell));//开辟一个新节点 add->element2=v; add->next=NULL; openlist->rear->next=add; openlist->rear=openlist->rear->next; } voidcheck_and_remove(midlist*openlist) { inti; charf='0'; cell*checker,*behind; behind=openlist->front; checker=behind->next; while(checker! =NULL) { for(i=0;i { if(checker->element2->conn[i]! =NULL) { if(checker->element2->conn[i]->flag1=='0') { f='1'; break; } } } if(i==vector)//如果这个节点的连接节点都已被标记则此节点应被从open表中删除 { behind->next=checker->next; free(checker); checker=behind->next; } else//不然的话检查下一个节点。 直到完成对所有节点的检查 { behind=checker; checker=checker->next; } } openlist->rear=behind; } voidfind_the_next_one(midlist*openlist,least_way*A)//寻找的结果是对open表进行了更新,对open表中的节点的部分信息做更新, { inti; cell*checker,*behind; vertex*goal,*source; intmin=-1; behind=openlist->front; checker=behind->next; for(i=0;i { if(checker->element2->conn[i]! =NULL) { if(checker->element2->conn[i]->flag1=='0') { min=(checker->element2->w)+(checker->element2->edge[i]); break; } } else break; } while(checker! =NULL) { for(i=0;i { if(checker->element2->conn[i]! =NULL) { if(checker->element2->conn[i]->flag1=='0') { if((checker->element2->w)+(checker->element2->edge[i])<=min) { min=(checker->element2->w)+(checker->element2->edge[i]); source=checker->element2; goal=checker->element2->conn[i]; } } } else break; } checker=checker->next; } if(min! =-1) { goal->w=min; goal->flag1='1'; addmidlist(openlist,goal); A->value[source->name][goal->name]++;//同时在leastway中做记录 } } voiddijkstra(pointlist*all,least_way*way,intn)//对任意的图(通过all和n联合给出不涉及对图中结点个数的参数给定)适用 { midlist*openlist; initallist2(openlist); all->element[n]->flag1='1'; addmidlist(openlist,all->element[n]); while(openlist->front->next! =NULL)//检查openlist是否为空。 dijkstra算法的终止条件 { find_the_next_one(openlist,way);//寻找open表中代价最少的节点对,此过程中包含添加节点到openlist中,算法的核心之处 check_and_remove(openlist);//对openlist的检查与删除节点 } } voiddelete_e(pointlist*all,inta,intb)//根据一次dijkstra全迭代,选择性删除一条被调用最多的edge的相应节点对连接关系 { inti,j; vertex*s,*d; for(i=0;i { if(all->element[i]->name==a) s=all->element[i]; if(all->element[i]->name==b) d=all->element[i]; } for(i=0;i { if(s->conn[i]==d) { for(j=i;j { s->conn[j]=s->conn[j+1]; s->edge[j]=s->edge[j+1]; } s->conn[j]=NULL; s->edge[j]=0; break; } } for(i=0;i { if(d->conn[i]==s) { for(j=i;j { d->conn[j]=d->conn[j+1]; d->edge[j]=d->edge[j+1]; } d->conn[j]=NULL; d->edge[j]=0; break; } } } voidprim_tree(pointlist*all,intn,least_way*&tree,FILE*fp)//最小生成树算法,可以作为对edge关键性的评价 { inti,j=0; midlist*openlist; cell*checker,*behind; vertex*goal,*source; initallist2(openlist); tree=(least_way*)malloc(sizeof(least_way)); for(i=0;i { for(j=0;j { tree->value[i][j]=0; } } addmidlist(openlist,all->element[n]); while(openlist->front->next! =NULL) { intmin=-1; behind=openlist->front; checker=behind->next; for(i=0;i { if(checker->element2->conn[i]! =NULL) { if(checker->element2->conn[i]->flag1=='0') { min=(checker->element2->edge[i]); break; } } else break; } while(checker! =NULL) { for(i=0;i { if(checker->element2->conn[i]! =NULL) { if(checker->element2->conn[i]->flag1=='0') { if(checker->element2->edge[i]<=min) { min=(checker->element2->edge[
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 作业
![提示](https://static.bingdoc.com/images/bang_tan.gif)