一种结构聚类的生成方法及系统

1.一种结构聚类的生成方法，其特征在于，所述方法采用基于openMP多核框架的方法，实现计算结构相似性的并行算法，所述方法包括：接收待处理的无向无权简单图，遍历所述无向无权简单图得到所有未处理的节点；按照结构相似性并行算法判断当前未处理的节点是否为核心节点，若否，则判断下一未处理的节点是否为核心节点；若是，则生成新的聚类并编号，并将所述当前未处理的节点的所有未处理且直接可达的邻居插入预置队列；判断所述预置队列是否为空，若为空，则执行所述按照结构相似性并行算法判断当前未处理的节点是否为核心节点的步骤；若不为空，则弹出所述预置队列的队首元素，将所述队首元素划分至所述新的聚类，并将所述队首元素的所有可达且未处理的邻居插入所述预置队列中；判断所述无向无权简单图中是否存在未处理的节点，若存在，则执行所述按照结构相似性并行算法判断当前未处理的节点是否为核心节点的步骤，若不存在，则结束算法，得到目标聚类；其中，在确定当前未处理的节点是否为核心节点时，使用基于节点度的负载均衡策略，或者基于切片的负载均衡策略，其中，所述基于节点度的负载均衡策略是指将整张图的边的度之和按照处理器的核的数量分成了p等份，分给p个核的每块里面所有边的度的和是相同的，所述基于切片的负载均衡策略是指将所述无向无权简单图中所有的边的集合分成等份的切片，切片大小在1000万到5000万之间，切片大小是指边的条数。 2.如权利要求1所述的生成方法，其特征在于，分别以u和v表示所述无向无权简单图中的任意一条边的两个端点，则所述按照结构相似性并行算法判断当前未处理的节点是否为核心节点包括：分别获取u和v按照其邻居的节点编号排序的邻接链表及邻居节点；分别以u和v的邻居节点的个数表示u和v的节点度数，计算u和v的节点度数之和，并以计算得到的节点度数之和表示以u和v为两个端点的边的度数；计算得到所述无向无权简单图中所有边的度数和，将所述所有边的度数和按照预置等分点平均分成若干计算任务块，每一计算任务块对应每一计算进程，每一所述计算进程用于遍历每一条边的两个端点的邻接链表，以获取每一条边的两个端点的共同邻居的个数；获取所有计算进程的编号，根据计算进程的编号分配计算任务块，以使所述计算进程根据所述计算任务块计算得到每一条边的两个端点的共同邻居的个数；计算每一条边的两个端点的结构相似性，其中，以Γ(v)表示v的邻居节点的个数，以Γ(u)表示u的邻居节点的个数，以σ(u,v)表示以u和v为端点的边的两个端点的结构相似性，则： |Γ(v)∩Γ(u)|表示v和u的共同邻居的个数， 表示v和u的邻居个数乘积的开方；判断计算得出的结构相似性的值是否满足预置的结构相似性阈值，若满足，则获取节点v中结构相似性大于预置的结构相似性阈值的邻居个数；若节点v大于预置的结构相似性阈值的邻居个数大于等于预置邻居个数值时，则判断v为核心节点。 3.如权利要求1所述的生成方法，其特征在于，分别以u和v表示所述无向无权简单图中的任意一条边的两个端点，则所述按照结构相似性并行算法判断当前未处理的节点是否为核心节点包括：获取所述无向无权简单图的所有的边，得到边集合；按照预置切片大小将所述边集合分成等份的若干切片；将切片分配给所有计算进程，以使所述计算进程计算所述切片内所有边的结构相似性；判断计算得出的结构相似性的值是否满足预置的结构相似性阈值，若满足，则获取节点v中结构相似性大于预置的结构相似性阈值的邻居个数；若节点v大于预置的结构相似性阈值的邻居个数大于等于预置邻居个数值时，则判断v为核心节点。 4.如权利要求3所述的生成方法，其特征在于，所述将切片分配给所有计算进程，以使所述计算进程计算所述切片内所有边的结构相似性包括：获取所有计算进程的运行状态；将切片随机分配给运行状态为空闲的计算进程，以使所述计算进程计算所述切片内所有边的结构相似性；当接收到计算进程发送的任务申请指令时，发送新的切片给对应的计算进程；判断是否存在未计算的切片，若存在，则执行所述将切片随机分配给运行状态为空闲的计算进程的步骤，若不存在，则结束计算。 5.如权利要求4所述的生成方法，其特征在于，所述将切片随机分配给运行状态为空闲的计算进程具体包括：将切片和上锁指令发送给运行状态为空闲的计算进程，以使所述计算进程计算所述切片内所有边的结构相似性并进行上锁；则所述当接收到计算进程发送的任务申请指令时，发送新的切片给对应的计算进程包括：当接收到计算进程发送的任务申请指令时，发送解锁指令给发送任务申请指令的计算进程，以使所述发送任务申请指令的计算进程进行解锁；接收所述发送任务申请指令的计算进程发送的解锁完毕信息，将新的切片和上锁指令发送给所述发送任务申请指令的计算进程，以使计算进程计算所述新的切片内所有边的结构相似性并重新上锁。 6.一种结构聚类的生成系统，其特征在于，所述系统采用基于openMP多核框架的方法，实现计算结构相似性的并行算法，所述系统包括：图像遍历单元，用于接收待处理的无向无权简单图，遍历所述无向无权简单图得到所有未处理的节点；节点判断单元，用于按照结构相似性并行算法判断当前未处理的节点是否为核心节点，若否，则判断下一未处理的节点是否为核心节点，若是，则生成新的聚类并编号，并将所述当前未处理的节点的所有未处理且直接可达的邻居插入预置队列；队列判断单元，用于判断所述预置队列是否为空，若为空，则激活所述节点判断单元执行所述按照结构相似性并行算法判断当前未处理的节点是否为核心节点的步骤，若不为空，则弹出所述预置队列的队首元素，将所述队首元素划分至所述新的聚类，并将所述队首元素的所有可达且未处理的邻居插入所述预置队列中；进程判断单元，用于判断所述无向无权简单图中是否存在未处理的节点，若存在，则激活所述节点判断单元执行所述按照结构相似性并行算法判断当前未处理的节点是否为核心节点的步骤，若不存在，则结束算法，得到目标聚类；其中，在确定当前未处理的节点是否为核心节点时，使用基于节点度的负载均衡策略，或者基于切片的负载均衡策略，其中，所述基于节点度的负载均衡策略是指将整张图的边的度之和按照处理器的核的数量分成了p等份，分给p个核的每块里面所有边的度的和是相同的，所述基于切片的负载均衡策略是指将所述无向无权简单图中所有的边的集合分成等份的切片，切片大小在1000万到5000万之间，切片大小是指边的条数。 7.如权利要求6所述的生成系统，其特征在于，分别以u和v表示所述无向无权简单图中的任意一条边的两个端点，则所述节点判断单元具体用于：分别获取u和v的按照其邻居的节点编号排序的邻接链表及邻居节点；分别以u和v的邻居节点的个数表示u和v的节点度数，计算u和v 的节点 度数之和并以计算得到的节点度数之和表示以u和v为两个端点的边的度数；计算得到所述无向无权简单图中所有边的度数和，将所述所有边的度数和按照预置等分点平均分成若干计算任务块，每一计算任务块对应每一计算进程，每一所述计算进程用于遍历每一条边的两个端点的邻接链表，以获取每一条边的两个端点的共同邻居的个数；获取所有计算进程的编号，根据计算进程的编号分配计算任务块，以使所述计算进程根据所述计算任务块计算得到每一条边的两个端点的共同邻居的个数；计算每一条边的两个端点的结构相似性，其中，以Γ(v)表示v的邻居节点的个数，以Γ(u)表示u的邻居节点的个数，以σ(u,v)表示以u和v为端点的边的两个端点的结构相似性，则： |Γ(v)∩Γ(u)|表示v和u的共同邻居的个数， 表示v和u的邻居个数乘积的开方；判断计算得出的结构相似性的值是否满足预置的结构相似性阈值，若满足，则获取节点v中结构相似性大于预置的结构相似性阈值的邻居个数；若节点v大于预置的结构相似性阈值的邻居个数大于等于预置邻居个数值时，则判断v为核心节点。 8.如权利要求6所述的生成系统，其特征在于，分别以u和v表示所述无向无权简单图中的任意一条边的两个端点，则所述节点判断单元包括：切片分配模块，用于获取所述无向无权简单图的所有的边，得到边集合，按照预置切片大小将所述边集合分成等份的若干切片，将切片分配给所有计算进程，以使所述计算进程计算所述切片内所有边的结构相似性；节点判断模块，用于判断计算得出的结构相似性的值是否满足预置的结构相似性阈值，若满足，则获取节点v中结构相似性大于预置的结构相似性阈值的邻居个数，若节点v大于预置的结构相似性阈值的邻居个数大于等于预置邻居个数值时，则判断v为核心节点。 9.如权利要求8所述的生成系统，其特征在于，所述切片分配模块具体包括：切片分配子模块，用于获取所有计算进程的运行状态，将切片随机分配给运行状态为空闲的计算进程，以使所述计算进程计算所述切片内所有边的结构相似性；进程判断子模块，用于当接收到计算进程发送的任务申请指令时，发送新的切片给对应的计算进程，判断是否存在未计算的切片，若存在，则执行所述将切片随机分配给运行状态为空闲的计算进程的步骤，若不存在，则结束计算。 10.如权利要求9所述的生成系统，其特征在于，所述切片分配子模块具体用于：将切片和上锁指令发送给运行状态为空闲的计算进程，以使所述计算进程计算所述切片内所有边的结构相似性并进行上锁；则进程判断子模块具体用于：当接收到计算进程发送的任务申请指令时，发送解锁指令给发送任务申请指令的计算进程，以使所述发送任务申请指令的计算进程进行解锁；接收所述发送任务申请指令的计算进程发送的解锁完毕信息，将新的切片和上锁指令发送给所述发送任务申请指令的计算进程，以使计算进程计算所述新的切片内所有边的结构相似性并重新上锁。