一种基于GPU多序列比对算法的社交网络关联搜索方法

摘要

本发明公开了一种基于GPU多序列比对算法的社交网络关联搜索方法，包括以下步骤：CPU对个体网页进行网络爬虫，以提取社交网络中的个体特征信息向量，CPU过滤个体特征信息向量中的冗余特征信息，以生成统一个体特征信息向量库，GPU根据统一个体特征信息向量库计算社交网络个体距离矩阵和矫正距离矩阵，GPU根据矫正距离矩阵构建社交网络关联路线指导树，GPU遍历社交网络关联路线指导树，以进行最优关联路线搜索。本发明充分利用GPU适合处理大量密集型数据的优势，将多序列比对算法解决关联搜索问题进行并行化，利用GPU完成矩阵及关联路线指导树的形成和遍历等复杂耗时操作，解决了社交网络数据量大和操作复杂性所带来的耗时长问题。

主权项

一种基于GPU多序列比对算法的社交网络关联搜索方法，其特征在于，包括以下步骤：（1）CPU对个体网页进行网络爬虫，以提取社交网络中的个体特征信息向量（T1，T2，T3，…，Tn）；（2）CPU过滤所述个体特征信息向量（T1，T2，T3，…，Tn）中的冗余特征信息，以生成统一个体特征信息向量库：CPU对所述个体特征信息向量（T1，T2，T3，…，Tn）的特征属性进行语义分析，以得出所述个体特征向量对应的特征属性集{P1，P2，P3，…，Pn}；CPU对所述特征属性集{P1，P2，P3，…，Pn}的属性元素进行模拟训练，计算所述属性元素对个体间关联度的贡献因子，并得出与所述特征属性集{P1，P2，P3，…，Pn}对应的特征贡献因子分数集{S1，S2，S3，…，Sn}；CPU根据网络聚焦算法，对所述特征贡献因子分数集{S1，S2，S3，…，Sn}进行模拟评估处理，计算得出贡献因子分数阈值（Smin，Smax）；设置计数器c，并初始化c=1，c的取值范围是[1，社交网络中个体的总数]；CPU判断所述特征贡献因子分数集{S1，S2，S3，…，Sn}中的元素Sc是否在所述贡献因子分数阈值（Smin，Smax）范围内；若元素Sc在贡献因子分数阈值（Smin，Smax）范围内，则保留Sc，并保留与Sc对应的属性Pc；判断c是否大于等于n；若c大于等于n，则CPU得出统一特征贡献因子分数集{S1，S2，S3，…，Sm}和统一标准的特征属性集{PU1，PU2，PU3，…，PUm}，并根据统一标准的特征属性集{PU1，PU2，PU3，…，PUm}对个体特征信息向量（T1，T2，T3，…，Tn）进行批量过滤处理，以得到与统一标准特征属性集{PU1，PU2，PU3，…，PUm}对应的统一个体特征信息向量（TU1，TU2，TU3，…，TUm），并形成统一个体特征信息向量库；CPU将统一特征信息向量（TU1，TU2，TU3…，TUm）和统一特征贡献因子分数集{S1，S2，S3，…，Sm}传入GPU；（3）GPU根据所述统一个体特征信息向量库计算社交网络个体距离矩阵和矫正距离矩阵：GPU根据所述统一特征贡献因子分数集{S1，S2，S3，…，Sm}计算社交网络中两两个体间的距离，并构成社交网络个体距离矩阵D；GPU获取社交网络中个体的总数C，设置计数器k，并初始化为k=C，且设置社交网络的个体集合为{E1，E2，E3，…，Ek}；GPU根据多序列比对算法，对社交网络个体距离矩阵D进行关联计算，即对某一个体距离值和其他所有个体距离值进行关联处理，以得出更能真实反映个体间距离的矫正距离矩阵M；（4）GPU根据所述矫正距离矩阵M，构建社交网络关联路线指导树：GPU将所有个体的结点构成星形初始树；GPU根据星形初始树遍历矫正距离矩阵M，以找出矫正距离矩阵M中最大的元数据对应的两个个体；GPU根据找到的两个个体生成虚拟父结点，并计算虚拟父结点到两个个体结点的距离；GPU根据所述计算方法计算出虚拟父结点到两个个体结点的距离后，将被合并的两个个体结点去除，并计算新的结点集合对应的距离矩阵和矫正距离矩阵；设置k=k‑1，即每合并两个结点生成一个新结点后，结点个体集合{E1，E2，E3，…，Ek}中结点个数减1；判断k是否小于等于2；若k小于等于2，则进入步骤（5）；（5）GPU遍历所述社交网络关联路线指导树，以确定最优关联路线：GPU查找社交网络关联路线指导树中待搜索的源个体及目标个体，并建立源个体和目标个体之间的关联路线；GPU根据关联路线进行最短路径优先计算，以筛选出最短的关联路线，即得出社交网络中源个体和目标个体间最优关联路径。