公开(公告)号：CN112948712B

公开(公告)日：2022-03-25

申请号：CN202110326914.7

申请日：2021-03-26

Applicant: 北京理工大学

Inventor： 任泽槟 ,  李荣华 ,  王国仁 ,  秦宏超 ,  金福生

IPC: G06F16/9536 ,  G06F16/901

Abstract: 本发明公开了一种可重叠的社群发现方法，步骤如下：S1分布式计算图G中的所有极大团，统计极大团的数量信息并将极大团的数量信息发送到所有计算节点中；S2对所有的极大团进行排序和编码，给每个极大团分配唯一的编码确定极大团；S3计算极大团中的子团，将子团发送到不同计算节点中；S4在每个计算节点内，构建反向索引；S5对每个极大团，利用反向索引，计算与每个极大团与其同一个计算节点内有k‑1个共享顶点的极大团，使用并查集将极大团的I D保存在同一个集合中；S6合并不同集群中的并查集，求出相应的派系。采用上述结构的一种可重叠的社群发现方法，增加了系统对大图的处理能力，横向扩展更加容易且成本更低。

公开(公告)号：CN112948712A

公开(公告)日：2021-06-11

申请号：CN202110326914.7

申请日：2021-03-26

Applicant: 北京理工大学

Inventor： 任泽槟 ,  李荣华 ,  王国仁 ,  秦宏超 ,  金福生

IPC: G06F16/9536 ,  G06F16/901

Abstract: 本发明公开了一种可重叠的社群发现方法，步骤如下：S1分布式计算图G中的所有极大团，统计极大团的数量信息并将极大团的数量信息发送到所有计算节点中；S2对所有的极大团进行排序和编码，给每个极大团分配唯一的编码确定极大团；S3计算极大团中的子团，将子团发送到不同计算节点中；S4在每个计算节点内，构建反向索引；S5对每个极大团，利用反向索引，计算与每个极大团与其同一个计算节点内有k‑1个共享顶点的极大团，使用并查集将极大团的I D保存在同一个集合中；S6合并不同集群中的并查集，求出相应的派系。采用上述结构的一种可重叠的社群发现方法，增加了系统对大图的处理能力，横向扩展更加容易且成本更低。

公开(公告)号：CN112950451B

公开(公告)日：2022-03-11

申请号：CN202110325537.5

申请日：2021-03-26

Applicant: 北京理工大学

Inventor： 任泽槟 ,  李荣华 ,  王国仁 ,  潘敏佳 ,  高森 ,  蒋佳祺

IPC: G06T1/20 ,  G06F9/50 ,  G06F9/54

Abstract: 本发明公开了一种基于GPU的极大k‑truss发现算法，步骤如下：(1)首先输入图G、k，求出图G中的k‑core，并将求得k‑core复制到显存中，初始化一个集合D为空集；(2)在显卡中使用多个线程进行处理；(3)在每个流多处理器中，对顶点v执行操作；(4)对于顶点v的邻居复制到当前流多处理器对应的共享内存中；(5)对于顶点中的每个邻居n，分配一个线程t进行处理；(6)当v的所有邻居处理完毕时，将步骤(5)中的寄存器的值求和。本发明采用上述的一种基于GPU的极大k‑truss发现算法，充分利用了CPU的并行性，运行速度快，并且，运行成本低。

公开(公告)号：CN112950451A

公开(公告)日：2021-06-11

申请号：CN202110325537.5

申请日：2021-03-26

Applicant: 北京理工大学

Inventor： 任泽槟 ,  李荣华 ,  王国仁 ,  潘敏佳 ,  高森 ,  蒋佳祺

IPC: G06T1/20 ,  G06F9/50 ,  G06F9/54

Abstract: 本发明公开了一种基于GPU的极大k‑truss发现算法，步骤如下：(1)首先输入图G、k，求出图G中的k‑core，并将求得k‑core复制到显存中，初始化一个集合D为空集；(2)在显卡中使用多个线程进行处理；(3)在每个流多处理器中，对顶点v执行操作；(4)对于顶点v的邻居复制到当前流多处理器对应的共享内存中；(5)对于顶点中的每个邻居n，分配一个线程t进行处理；(6)当v的所有邻居处理完毕时，将步骤(5)中的寄存器的值求和。本发明采用上述的一种基于GPU的极大k‑truss发现算法，充分利用了CPU的并行性，运行速度快，并且，运行成本低。