太阳城集团

  • / 14
  • 下载费用:30 金币  

一种图结构的划分分区方法及系统.pdf

关 键 词:
一种 结构 划分 分区 方法 系统
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201510690576.X

申请日:

2015.10.22

公开号:

CN105224765A

公开日:

2016.01.06

当前法律状态:

实审

有效性:

审中

法律详情: 专利申请权的转移IPC(主分类):G06F 17/50登记生效日:20161207变更事项:申请人变更前权利人:厦门亿力吉奥太阳城集团科技有限公司变更后权利人:厦门亿力吉奥太阳城集团科技有限公司变更事项:地址变更前权利人:361000 福建省厦门市思明区软件园二期观日路36号之二变更后权利人:361000 福建省厦门市思明区软件园二期观日路36号之二变更事项:申请人变更前权利人:国家电网公司 国网信通亿力科技有限责任公司变更后权利人:国网山东省电力公司电力科学研究院 国家电网公司 国网太阳城集团通信产业集团有限公司 国网信通亿力科技有限责任公司|||著录事项变更IPC(主分类):G06F 17/50变更事项:发明人变更前:刘光曹变更后:刘光曹 邵志敏|||实质审查的生效IPC(主分类):G06F 17/50申请日:20151022|||公开
IPC分类号: G06F17/50 主分类号: G06F17/50
申请人: 厦门亿力吉奥太阳城集团科技有限公司; 国家电网公司; 国网信通亿力科技有限责任公司
发明人: 刘光曹
地址: 361000 福建省厦门市思明区软件园二期观日路36号之二
优先权:
专利代理机构: 深圳市博锐专利事务所 44275 代理人: 张明
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201510690576.X

授权太阳城集团号:

|||||||||

法律状态太阳城集团日:

太阳城集团2016.12.28|||2016.11.23|||2016.02.03|||2016.01.06

法律状态类型:

专利申请权、专利权的转移|||著录事项变更|||实质审查的生效|||公开

摘要

本发明涉及数据处理领域,尤其涉及一种图结构的划分分区方法及系统。与传统分区方法相比,通过比较各节点的聚合系数与临界聚合系数的大小来进行分区的划分,再通过调节临界聚合系数的值,可以调节分区数量的增加或减少。本发明提供的预设阀值给出了临界聚合系数的最少改变量,如果临界聚合系数改变太少,分区的结果是不会改变的。为减少调节初始临界聚合系数的尝试次数,本发明的方法计算出临界聚合系数的有效改变量。

权利要求书

权利要求书
1.  一种图结构的划分分区方法,其特征在于,包括:
S1、对于给定节点间的连边和目标分区数量,预设临界聚合系数的初值;
S2、每个节点划分为一个独立区域,节点分区变化标志设置为0;
S3、对所有节点进行聚合,调节分区,具体包括步骤S31-S36:
S31、在所有节点中选取一个节点,将所述节点从所在分区中移出,分别计算所移出的节点和与其相连节点的聚合系数,得到多个聚合系数;从多个聚合系数中选取出最大值,作为所移出的节点的第一聚合系数;
S32、判断步骤S31的所述节点的第一聚合系数是否大于临界聚合系数,若是,则将所述节点移入所述第一聚合系数涉及的另一节点所在的区域;若否,则将所述节点移回原来所在分区;判断所述节点所在的分区是否发生变化,若有变化,则将所述节点分区变化标志设置为1;
S33、重复步骤S31-S32直到选取完所有节点后进入步骤S34;
S34、若节点分区变化标志为1,则将节点分区变化标志设置为0后返回步骤S3,若节点分区变化标志为0,则进入步骤S4;
S4、舍弃所有不含节点的区域后,若每一个区域只含一个节点,得到分区数量,则执行步骤S5;否则对每一区域用一个新节点替代区域内所有节点,使得每一个区域只含一个节点,且用新节点的自环代替区域内原节点之间的连边,所述自环的权重等于区域内原节点之间的连边的权重和,且用区域之间新节点的连边代替区域之间的原节点的连边,区域之间新节点之间连边的权重等于被替代的原节点连边的权重和,采用新节点重复步骤S3-S4;
S5、将所得分区数量与目标分区数量相比,若所得分区数量等于目标分区数量,则已完成分区过程;若所得分区数量大于目标分区数量,则减少临界聚合系数,保留已获得的分区,返回步骤S3继续执行;若所得分区数量小于目标分区数量,则增大临界聚合系数,放弃已获得的分区且还原最初的节点,返回步骤S2开始执行。

2.  根据权利要求1所述的一种图结构的划分分区方法,其特征在于,所述“若所得分区数量大于目标分区数量,则减少临界聚合系数”具体为:
若所得分区数量大于目标分区数量,则从所有节点中选取出第一聚合系数 小于临界聚合系数的节点,再从选取出的节点中选取第一聚合系数最大的节点,将最终选取的节点的第一聚合系数减去预设阀值作为调节后的临界聚合系数。

3.  根据权利要求1所述的一种图结构的划分分区方法,其特征在于,所述“若所得分区数量小于目标分区数量,则增大临界聚合系数”具体为:
若所得分区数量小于目标分区数量,则从所有节点中选取出第一聚合系数大于临界聚合系数的节点,再从选取出的节点中选取第一聚合系数最小的节点,将最终选取的节点的第一聚合系数加上预设阀值作为调节后的临界聚合系数。

4.  根据权利要求2-3任意一项所述的一种图结构的划分分区方法,其特征在于,所述预设阀值为10-6。

5.  一种图结构的划分分区系统,其特征在于,包括:预设模块、划分模块、调节模块、分区模块和对比模块;
所述预设模块,用于对于给定节点间的连边和目标分区数量,预设临界聚合系数的初值;
所述划分模块,用于每个节点划分为一个独立区域,节点分区变化标志设置为0;
所述调节模块包括计算单元、第一判断单元、重复单元和第二判断单元;
所述计算单元,用于在所有节点中选取一个节点,将所述节点从所在分区中移出,分别计算所移出的节点和与其相连节点的聚合系数,得到多个聚合系数;从多个聚合系数中选取出最大值,作为所移出的节点的第一聚合系数;
所述第一判断单元,用于判断所述节点的第一聚合系数是否大于临界聚合系数,若是,则将所述节点移入所述第一聚合系数涉及的另一节点所在的区域;若否,则将所述节点移回原来所在分区;判断所述节点所在的分区是否发生变化,若有变化,则将所述节点分区变化标志设置为1;
所述重复单元,用于重复计算单元和第一判断单元直到选取完所有节点后执行第二判断单元;
所述第二判断单元,用于若节点分区变化标志为1,则将节点分区变化标志设置为0后返回调节模块,若节点分区变化标志为0,则进入分区模块;
所述分区模块,用于舍弃所有不含节点的区域后,若每一个区域只含一个 节点,得到分区数量,则执行对比模块;否则对每一区域用一个新节点替代区域内所有节点,使得每一个区域只含一个节点,且用新节点的自环代替区域内原节点之间的连边,所述自环的权重等于区域内原节点之间的连边的权重和,且用区域之间新节点的连边代替区域之间的原节点的连边,区域之间新节点之间连边的权重等于被替代的原节点连边的权重和,采用新节点重复调节模块和分区模块;
所述对比模块,用于将所得分区数量与目标分区数量相比,若所得分区数量等于目标分区数量,则已完成分区过程;若所得分区数量大于目标分区数量,则减少临界聚合系数,保留已获得的分区,返回调节模块继续执行;若所得分区数量小于目标分区数量,则增大临界聚合系数,放弃已获得的分区且还原最初的节点,返回划分模块开始执行。

6.  根据权利要求5所述的一种图结构的划分分区系统,其特征在于,所述对比模块具体用于若所得分区数量大于目标分区数量,则从所有节点中选取出第一聚合系数小于临界聚合系数的节点,再从选取出的节点中选取第一聚合系数最大的节点,将最终选取的节点的第一聚合系数减去预设阀值作为调节后的临界聚合系数。

7.  根据权利要求5所述的一种图结构的划分分区系统,其特征在于,所述对比模块具体用于若所得分区数量小于目标分区数量,则从所有节点中选取出第一聚合系数大于临界聚合系数的节点,再从选取出的节点中选取第一聚合系数最小的节点,将最终选取的节点的第一聚合系数加上预设阀值作为调节后的临界聚合系数。

8.  根据权利要求6-7任意一项所述的一种图结构的划分分区系统,其特征在于,所述预设阀值为10-6。

说明书

说明书一种图结构的划分分区方法及系统
技术领域
本发明涉及数据处理领域,尤其涉及一种图结构的划分分区方法及系统。
背景技术
在一个复杂的网络连接关系中,有大量的顶点和边构成图的结构,常常希望把整张图切成多个子图,或者是把连接的网络切分成多个区域,就可以对每个区域分别处理,从而达到分而治之地处理各种问题的目的。分区的功能广泛应用于电网数据处理、集成电路布图、社区结构发现等诸多领域。分区的要求有多种,其中一种常见的要求是:连接紧密的顶点被划分到一起,连接松散的顶点可以被划分到不同的区域。
2008年,VincentD.Blondel,Jean-LoupGuillaume,RenaudLambiotte和EtienneLefebvre几位学者给出了一种至底向上逐个顶点聚合的方法。他们的论文“Fastunfoldingofcommunitiesinlargenetworks”发表在JournalofStatisticalMechanics:TheoryandExperiment杂志上。该方法的计算效率很高,其原本的目标是得到一种层次化的分区结果,可用于互联网等领域,根据成员连接关系挖掘出社区结构。若把VincentD.Blondel等人的方法用于更多的场景时,会遇到的一个问题是,该方法得到的分区数量有时不满足需求。比如把一个网络用该方法划分成7个子网络,但是需求认为7个子网络太多了,希望只有3个子网络,这使得原有方法不能适用。
申请号为201410710163.9的中国专利申请文件,名称为基于节点聚合系数的电力通信网络构建方法,该方法包括:获取电力通信网的网络模型;其中,所述网络模型包括节点和链路,所述节点为电力通信系统中的通信设备,所述链路为连接节点的各条光缆;计算所述节点的聚合系数;获得每个节点上附加有对应的聚合系数的网络模型,对获得的网络模型进行网络拓扑分析及电力通信系统的可靠性测定,能显著提高电力通信系统的可靠性测定的准确性,但是对于图结构数据的合理分区而言,该方法是不适用的。
发明内容
本发明所要解决的技术问题是:提供一种节点聚合的方法,来完成目标数量的图结构分区。
为了解决上述技术问题,本发明采用的技术方案为:
一种图结构的划分分区方法,包括:
S1、对于给定节点间的连边和目标分区数量,预设临界聚合系数的初值;
S2、每个节点划分为一个独立区域,节点分区变化标志设置为0;
S3、对所有节点进行聚合,调节分区,具体包括步骤S31-S36:
S31、在所有节点中选取一个节点,将所述节点从所在分区中移出,分别计算所移出的节点和与其相连节点的聚合系数,得到多个聚合系数;从多个聚合系数中选取出最大值,作为所移出的节点的第一聚合系数;
S32、判断步骤S31的所述节点的第一聚合系数是否大于临界聚合系数,若是,则将所述节点移入所述第一聚合系数涉及的另一节点所在的区域;若否,则将所述节点移回原来所在分区;判断所述节点所在的分区是否发生变化,若有变化,则将所述节点分区变化标志设置为1;
S33、重复步骤S31-S32直到选取完所有节点后进入步骤S34;
S34、若节点分区变化标志为1,则将节点分区变化标志设置为0后返回步骤S3,若节点分区变化标志为0,则进入步骤S4;
S4、舍弃所有不含节点的区域后,若每一个区域只含一个节点,得到分区数量,则执行步骤S5;否则对每一区域用一个新节点替代区域内所有节点,使得每一个区域只含一个节点,且用新节点的自环代替区域内原节点之间的连边,所述自环的权重等于区域内原节点之间的连边的权重和,且用区域之间新节点的连边代替区域之间的原节点的连边,区域之间新节点之间连边的权重等于被替代的原节点连边的权重和,采用新节点重复步骤S3-S4;
S5、将所得分区数量与目标分区数量相比,若所得分区数量等于目标分区数量,则已完成分区过程;若所得分区数量大于目标分区数量,则减少临界聚合系数,保留已获得的分区,返回步骤S3继续执行;若所得分区数量小于目标 分区数量,则增大临界聚合系数,放弃已获得的分区且还原最初的节点,返回步骤S2开始执行。
本发明提供的另一技术方案为:
一种图结构的划分分区系统,包括:预设模块、划分模块、调节模块、分区模块和对比模块;
所述预设模块,用于对于给定节点间的连边和目标分区数量,预设临界聚合系数的初值;
所述划分模块,用于每个节点划分为一个独立区域,节点分区变化标志设置为0;
所述调节模块包括计算单元、第一判断单元、重复单元和第二判断单元;
所述计算单元,用于在所有节点中选取一个节点,将所述节点从所在分区中移出,分别计算所移出的节点和与其相连节点的聚合系数,得到多个聚合系数;从多个聚合系数中选取出最大值,作为所移出的节点的第一聚合系数;
所述第一判断单元,用于判断所述节点的第一聚合系数是否大于临界聚合系数,若是,则将所述节点移入所述第一聚合系数涉及的另一节点所在的区域;若否,则将所述节点移回原来所在分区;判断所述节点所在的分区是否发生变化,若有变化,则将所述节点分区变化标志设置为1;
所述重复单元,用于重复计算单元和第一判断单元直到选取完所有节点后执行第二判断单元;
所述第二判断单元,用于若节点分区变化标志为1,则将节点分区变化标志设置为0后返回调节模块,若节点分区变化标志为0,则进入分区模块;
所述分区模块,用于舍弃所有不含节点的区域后,若每一个区域只含一个节点,得到分区数量,则执行对比模块;否则对每一区域用一个新节点替代区域内所有节点,使得每一个区域只含一个节点,且用新节点的自环代替区域内原节点之间的连边,所述自环的权重等于区域内原节点之间的连边的权重和,且用区域之间新节点的连边代替区域之间的原节点的连边,区域之间新节点之间连边的权重等于被替代的原节点连边的权重和,采用新节点重复调节模块和分区模块;
所述对比模块,用于将所得分区数量与目标分区数量相比,若所得分区数量等于目标分区数量,则已完成分区过程;若所得分区数量大于目标分区数量,则减少临界聚合系数,保留已获得的分区,返回调节模块继续执行;若所得分区数量小于目标分区数量,则增大临界聚合系数,放弃已获得的分区且还原最初的节点,返回划分模块开始执行。
本发明的有益效果在于:与传统分区方法相比,本发明提供的一种图结构的划分分区方法,通过比较各节点的聚合系数与临界聚合系数的大小来进行分区的划分;再通过调节临界聚合系数的值,可以调节分区数量的增加或减少。
附图说明
图1为本发明的一种图结构的划分分区方法的步骤流程图;
图2为本发明的一种图结构的划分分区系统的结构示意图;
图3为本发明的实施例中图结构的初始节点间的连接关系示意图;
图4为本发明的实施例中第一次遍历后所有节点的分区示意图;
图5为本发明的实施例中第二次遍历后所有节点的分区示意图;
图6为本发明的实施例中最终所有节点的分区示意图;
标号说明:
10、预设模块;20、划分模块;30、调节模块;301、计算单元;302、第一判断单元;303、重复单元;304、第二判断单元;40、分区模块;50、对比模块。
具体实施方式
为详细说明本发明的技术内容、所实现目的及效果,以下结合实施方式并配合附图予以说明。
本发明最关键的构思在于:通过比较各节点的聚合系数与预设的临界聚合系数的大小来进行分区的划分,再通过调节临界聚合系数的值,可以调节分区数量的增加或减少。
请参照图1,本发明提供的一种图结构的划分分区方法,包括:
S1、对于给定节点间的连边和目标分区数量,预设临界聚合系数的初值;
S2、每个节点划分为一个独立区域,节点分区变化标志设置为0;
S3、对所有节点进行聚合,调节分区,具体包括步骤S31-S36:
S31、在所有节点中选取一个节点,将所述节点从所在分区中移出,分别计算所移出的节点和与其相连节点的聚合系数,得到多个聚合系数;从多个聚合系数中选取出最大值,作为所移出的节点的第一聚合系数;
S32、判断步骤S31的所述节点的第一聚合系数是否大于临界聚合系数,若是,则将所述节点移入所述第一聚合系数涉及的另一节点所在的区域;若否,则将所述节点移回原来所在分区;判断所述节点所在的分区是否发生变化,若有变化,则将所述节点分区变化标志设置为1;
S33、重复步骤S31-S32直到选取完所有节点后进入步骤S34;
S34、若节点分区变化标志为1,则将节点分区变化标志设置为0后返回步骤S3,若节点分区变化标志为0,则进入步骤S4;
S4、舍弃所有不含节点的区域后,若每一个区域只含一个节点,得到分区数量,则执行步骤S5;否则对每一区域用一个新节点替代区域内所有节点,使得每一个区域只含一个节点,且用新节点的自环代替区域内原节点之间的连边,所述自环的权重等于区域内原节点之间的连边的权重和,且用区域之间新节点的连边代替区域之间的原节点的连边,区域之间新节点之间连边的权重等于被替代的原节点连边的权重和,采用新节点重复步骤S3-S4;
S5、将所得分区数量与目标分区数量相比,若所得分区数量等于目标分区数量,则已完成分区过程;若所得分区数量大于目标分区数量,则减少临界聚合系数,保留已获得的分区,返回步骤S3继续执行;若所得分区数量小于目标分区数量,则增大临界聚合系数,放弃已获得的分区且还原最初的节点,返回步骤S2开始执行。
从上述描述可知,本发明的有益效果在于:与传统分区方法相比,本发明提供的一种图结构的划分分区方法,通过比较各节点的聚合系数与临界聚合系数的大小来进行分区的划分,再通过调节临界聚合系数的值,可以调节分区数量的增加或减少。
进一步的,所述“若所得分区数量大于目标分区数量,则减少临界聚合系数”具体为:
若所得分区数量大于目标分区数量,则从所有节点中选取出第一聚合系数小于临界聚合系数的节点,再从选取出的节点中选取第一聚合系数最大的节点,将最终选取的节点的第一聚合系数减去预设阀值作为调节后的临界聚合系数。
进一步的,所述“若所得分区数量小于目标分区数量,则增大临界聚合系数”具体为:
若所得分区数量小于目标分区数量,则从所有节点中选取出第一聚合系数大于临界聚合系数的节点,再从选取出的节点中选取第一聚合系数最小的节点,将最终选取的节点的第一聚合系数加上预设阀值作为调节后的临界聚合系数。
进一步的,所述预设阀值为10-6。
在步骤S31中,“分别计算所述节点和与其相连节点的聚合系数,得到多个聚合系数”,例如节点i为所述节点,与之相连的节点有j1,j2,j3…,计算相应的聚合系数pi(j1),pi(j2),pi(j3)…。聚合系数pi(j)的计算方法为
pi(j)=kco(i,Cj)2*k(i)*k(Cj)/m]]>
其中,kco(i,Cj)是节点i连接到节点j所在区域Cj的边的权重和的2倍,实际上是节点i和区域Cj连边的(带边的权重)度数和。m是所有节点度数(带边的权重)求和,即所有边的权重和的2倍。k(i)是节点(含边的权重,以及自环权重)的度数和。k(Cj)是节点j所在区域的所有节点(含边的权重,以及区域内部自环的权重)度数和。
从pi(j1),pi(j2),pi(j3)…中选出最大的pi(jk),作为i节点的第一聚合系数,记作pi,Max。计算pi,Max是否大于初始临界聚合系数pthres,如果pi,Max>pthres,则正式接受把节点i移入jk所在区域,否则节点i移回步骤S31之前节点i所在区域。
为方便步骤S4调节临界聚合系数,具体做法为:
在步骤S31的所有节点第一聚合系数p1,Max、p2,Max、p3,Max、...中,找到小等于pthres且最接近pthres的pi,Max,保存为pbelow;找到大于pthres且最接近pthres的pi,Max,保存为pabove。在后续循环中,如果出现更接近于pthres的pi,Max,则相应更新pbelow 或pabove的数值。
后来,要减少分区数量,则新的临界聚合系数设置为pthres=pbelow-ε,ε取一个程序数值精度允许的极小的正值如10-6,就满足“新的临界聚合系数pthres设为小于pi,Max的数值”。
要增加分区数量,则新的临界聚合系数设置为pthres=pabove,就满足“新的临界聚合系数设为大等于pi,Max的数值”。由于“大等于pi,Max”包括了“等于”,不用加ε。
为了增加分区数量,上述S5步骤中增大临界聚合系数的方法是,在步骤S31的所有节点第一聚合系数p1,Max、p2,Max、p3,Max、...中,找到大于pthres且最接近pthres的pi,Max,新的临界聚合系数设为大等于pi,Max的数值。
请参阅图2,本发明提供的一种图结构的划分分区系统,包括:预设模块10、划分模块20、调节模块30、分区模块40和对比模块50;
所述预设模块10,用于对于给定节点间的连边和目标分区数量,预设临界聚合系数的初值;
所述划分模块20,用于每个节点划分为一个独立区域,节点分区变化标志设置为0;
所述调节模块30包括计算单元301、第一判断单元302、重复单元303和第二判断单元304;
所述计算单元301,用于在所有节点中选取一个节点,将所述节点从所在分区中移出,分别计算所移出的节点和与其相连节点的聚合系数,得到多个聚合系数;从多个聚合系数中选取出最大值,作为所移出的节点的第一聚合系数;
所述第一判断单元302,用于判断所述节点的第一聚合系数是否大于临界聚合系数,若是,则将所述节点移入所述第一聚合系数涉及的另一节点所在的区域;若否,则将所述节点移回原来所在分区;判断所述节点所在的分区是否发生变化,若有变化,则将所述节点分区变化标志设置为1;
所述重复单元303,用于重复计算单元和第一判断单元直到选取完所有节点后执行第二判断单元;
所述第二判断单元304,用于若节点分区变化标志为1,则将节点分区变化 标志设置为0后返回调节模块,若节点分区变化标志为0,则进入分区模块;
所述分区模块40,用于舍弃所有不含节点的区域后,若每一个区域只含一个节点,得到分区数量,则执行对比模块;否则对每一区域用一个新节点替代区域内所有节点,使得每一个区域只含一个节点,且用新节点的自环代替区域内原节点之间的连边,所述自环的权重等于区域内原节点之间的连边的权重和,且用区域之间新节点的连边代替区域之间的原节点的连边,区域之间新节点之间连边的权重等于被替代的原节点连边的权重和,采用新节点重复调节模块和分区模块;
所述对比模块50,用于将所得分区数量与目标分区数量相比,若所得分区数量等于目标分区数量,则已完成分区过程;若所得分区数量大于目标分区数量,则减少临界聚合系数,保留已获得的分区,返回调节模块继续执行;若所得分区数量小于目标分区数量,则增大临界聚合系数,放弃已获得的分区且还原最初的节点,返回划分模块开始执行。
进一步的,所述对比模块50具体用于若所得分区数量大于目标分区数量,则从所有节点中选取出第一聚合系数小于临界聚合系数的节点,再从选取出的节点中选取第一聚合系数最大的节点,将最终选取的节点的第一聚合系数减去预设阀值作为调节后的临界聚合系数。
进一步的,所述对比模块50具体用于若所得分区数量小于目标分区数量,则从所有节点中选取出第一聚合系数大于临界聚合系数的节点,再从选取出的节点中选取第一聚合系数最小的节点,将最终选取的节点的第一聚合系数加上预设阀值作为调节后的临界聚合系数。
进一步的,所述预设阀值为10-6。
请参阅图3-6,本发明的实施例一为:
需要说明的是,本发明背景技术中所述的顶点即为具体实施方式中的节点。
一种图结构数据的划分分区方法,包括:
S1、对于给定节点间的连边和目标分区数量,预设临界聚合系数pthres的初值;
S2、每个节点划分为一个独立区域,节点分区变化标志置0;
S3、对所有节点进行聚合,调节分区,具体包括步骤S31-S36:
S31、在所有节点中选取1个节点,将所述节点从所在分区中移出,分别计算所述节点和与其相连节点的聚合系数,得到多个聚合系数;从多个聚合系数中选取出最大值,作为所述节点的第一聚合系数pi,Max,i为所述节点的编号;
S32、判断所述节点的第一聚合系数pi,Max是否大于临界聚合系数pthres,若是,则将所述节点移入所述第一聚合系数涉及的另一节点所在的区域;若否,把所述节点移回步骤S31之前所在分区;对比所述节点现在分区与步骤S31之前所在分区是否相同,若不同则把节点分区变化标志置1;
S33、重复步骤S31-S32直到选取完所有节点;
S34、如果节点分区变化标志为1,则把节点分区变化标志置0后重复步骤S31-S34,否则继续下述步骤;
S4、舍弃所有不含节点的区域后,如果每一个区域只含一个节点,则执行后续步骤;否则对于每一区域,用一个新节点替代该区域内所有节点,使得每一个区域只含一个节点,且用新节点的自环代替区域内部原节点之间的连边,自环的权重等于区域内部原节点之间的连边的权重和,且用区域之间新节点的连边代替区域之间的原节点的连边,区域之间新节点之间连边的权重等于被替代的原节点连边的权重和,然后重复步骤S3-S4;
S5、把所得分区数量与目标分区数量做对比,若所得分区数量等于目标分区数量,则完成了分区过程;若所得分区数量大于目标分区数量,则减少临界聚合系数,保留已获得的分区,从步骤S3开始继续执行;若所得分区数量小于目标分区数量,则增大临界聚合系数,放弃已获得的分区且还原最初的节点,重新从步骤S2开始。
上述S31步骤中聚合系数的计算是用两个节点之间(或节点与分区之间,或分区与分区之间)的实际连边数除以均值边数;上述均值边数是用两个节点(或区域)的度数乘积除以所有节点的度数和。
为了减少分区数量,上述S5步骤中减小临界聚合系数的方法是,在步骤S31的所有节点第一聚合系数p1,Max、p2,Max、p3,Max、...中,找到小于等于pthres且最接近pthres的pi,Max,新的临界聚合系数pthres设为小于pi,Max的数值。
为了增加分区数量,上述S5步骤中增大临界聚合系数的方法是,在步骤S31 的所有节点第一聚合系数p1,Max、p2,Max、p3,Max、...中,找到大于pthres且最接近pthres的pi,Max,新的临界聚合系数设为大等于pi,Max的数值。
该实例是由11个节点构成的图结构,节点间的连接关系见附图3,期望分成2个分区。
S1、预设临界聚合系数的初值pthres=1;
S2、11个节点各自成为独立区域,节点分区变化标志置0。
S3、对所有节点进行编号,然后调节分区或聚合,具体包括步骤S31-S36:
S31、从1号的节点开始依次选取节点,将所述节点从所在分区中移出,分别计算所选取的节点和与其相连节点的聚合系数,得到多个聚合系数。具体为:
1号节点已经属于独立区域,不用将其移出自成独立区域。
尝试将1号节点并入与之相连的2号节点,计算出聚合系数p1(2)
p1(2)=2*12*3*2/(2*12)=4]]>
尝试将1号节点并入与之相连的6号节点,计算出聚合系数p1(6)
p1(6)=2*12*3*1/(2*12)=8]]>
尝试将1号节点并入与之相连的11号节点,计算出聚合系数p1(11)
p1(11)=2*12*3*2/(2*12)=4]]>
从p1(2)、p1(6)、p1(11)中取出最大的p1(6),作为1号节点的第一聚合系数p1,Max=p1(6)=8,
S32、1号节点的第一聚合系数大于临界聚合系数pthres=1,因此将1号节点移入所述第一聚合系数涉及的6号节点所在区域。1号节点分区有变化,把节点分区变化标志置1。
S33、同样,对于2号节点,分别计算其与1号、4号的聚合系数,计算得p2(1)=3、p2(4)=12。2号节点的第一聚合系数p2,Max=p2(4)=12,(pthres=1),p2,Max>pthres,正式把2号节点并入4号节点的区域。2号节点分区有变化,节点分区变化标志
对于3号、4号…11号节点,以此类推,寻找它们可以并入的区域。
以上遍历11个节点后,这个过程中有节点的区域划分发生变化,在p1,Max、p2,Max、…、p11,Max中找出最接近pthres的值,更新一次最小于等于pthres的pbelow=NULL,大于pthres的pabove=2.4。pbelow=NULL是由于p1,Max、p2,Max、…、p11,Max中没有小等于pthres的值。
S34、由于节点分区变化标志为1,就要将其置0再继续重新遍历这11个节点。
一共遍历了3次,就没有节点的区域划分发生变化。在pthres=1两侧,出现的最接近pthres的值:pbelow=NULL,pabove=2.4。
S4、在舍弃不含节点的区域后,如图4所示,一共聚合成5个区域:其中3号、5号、8号节点在一个区域中,2号、4号节点在一个区域中,1号、6号节点在一个区域中,7号、10号节点在一个区域中,9号、11号节点在一个区域中。
对每个区域用一个新节点替代区域内所有节点,即用新的1号节点替代原来的3号、5号、8号节点;用新的2号节点替代原来的2号、4号节点;用新的3号节点替代原来的1号、6号节点,用新的4号节点替代原来的7号、10号节点;用新的5号节点替代原来的9号、11号节点。
相应地,每个区域内用新节点的自环替代区域内部原节点之间的连边。区域之间新的带权重的边代替区域之间的原节点的连边。新的边和自环的权重是原连边的权重和。
接下来,按新的节点,各自形成独立区域。重新开始遍历,尝试节点和区域的聚合,以减少区域,重复步骤S3-S4。
经过2次遍历后,节点的区域划分又不再产生变化了。在pthres=1两侧,出现的最接近pthres的值:pbelow=0.857143,pabove=1.33333。
这时,一共有3个区域:新的2号节点(包含着原先2号、4号节点)、3号节点(包含着原先1号、6号节点)在一个区域中,新的5号节点(包含着原先9号、11号节点)自成独立区域,新的1号节点(包含着原先3号、5号、8号节点)、4号节点(包含着原先7号、10号节点)在一个区域中。
进一步把上述3个区域浓缩成3个节点。3个节点各自形成独立区域。重新 开始遍历这3个节点,尝试节点和区域的合并,以减少区域。
经过1次遍历,发现节点的区域划分没有改变。说明以当前临界聚合系数pthres=1的分区过程执行完成。
S5、所得附图5的3个分区数量多于目标2个分区,直观上附图5的3个分区的结果也并不理想,合成2个分区更合理。为减少分区数量,找到小等于pthres且最接近pthres的pi,Max=0.857143。
令新的pthres=pbelow-ε=0.857143-0.000001=0.857142。
按新的临界聚合系数pthres=0.857142执行分区,最终得到的2个分区,效果如附图6所示。所得分区数量2与目标分区数量相同,因此分区过程结束。
综上所述,最初从pthres=1开始执行分区,得到3个分区多于目标,通过调节pthres=pbelow-ε再次执行分区,得到了目标所需的2个分区的结果,实现了可按目标调节的图结构分区。
综上所述,本发明提供的一种图结构的划分分区方法及系统,与传统分区方法相比,通过比较各节点的聚合系数与临界聚合系数的大小来进行分区的划分,再通过调节临界聚合系数的值,可以调节分区数量的增加或减少。本发明提供的预设阀值给出了临界聚合系数的最少改变量,如果临界聚合系数改变太少,分区的结果是不会改变的。为减少调节临界聚合系数的尝试次数,本发明的方法计算出临界聚合系数的有效改变量:若分区数量大于目标分区数量时,即为要减少分区数量,则pthres至少减少到pbelow-ε;若分区数量小于目标分区数量时,即为要增加分区数量,则pthres至少增加到pabove。
以上所述仅为本发明的实施例,并非因此限制本发明的专利范围,凡是利用本发明说明书及附图内容所作的等同变换,或直接或间接运用在相关的技术领域,均同理包括在本发明的专利保护范围内。

太阳城集团本文
本文标题:一种图结构的划分分区方法及系统.pdf
链接地址:http://zh228.com/p-6397624.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');