社交网络中潜在好友查询方法

摘要

本发明涉及一种社交网络中潜在好友查询方法，首先建立社交网络图，然后将前                                               条最优路径查询算法和基于扩展LCS的字符串比较有效融合的方法相结合实现对社交网络中用户潜在好友进行快速查询，使得社交网络更加有效地服务于不同网络用户，如推荐商业潜在客户或用户潜在好友。不仅可以支持社交网络拓扑结构中存在好友的有效查询，更能够支持为指定用户找出其潜在好友或为无直接连接用户推荐潜在好友，很好地弥补了之前查询方法中，只能查询存在好友方法的缺点。

主权项

一种社交网络中潜在好友查询方法，其特征在于，包括如下具体步骤：1)建立社交网络图：将各个用户的信息建模成图G<V,E>的结点，其中V是图中结点的集合，E是图中无向边的集合，表示两个用户之间的直接连接，用户邻接关系矩阵NRM对应用户之间的连接关系，有连接关系相应的单元设置为true(1)，否则设置为false(0)；2)在社交网络图的基础上，进行前K条最优最短路径查询算法：第一步：根据用户社交网络图找到一条指定结点间的最短路径，首先利用路径关系矩阵PRM辅助存储两个结点之间最短路径的途经结点，PRM初始设置为空，以用户邻接关系矩阵NRM为基础，将任意一个用户结点C插入到另外两个用户结点A和B之间，检查是否为最短路径，即是否满足L_AC+L_CB<L_AB，其中L_AC、L_CB表示结点之间的路径，如果满足L_AC+L_CB<L_AB条件的结点C存在，则将结点C存储在路径关系矩阵PRM[i][A][B]，1≤i≤K中，直到所有结点全部被遍历则循环结束；第二步：根据启发式的剪枝策略得到指定结点间前K条最优最短路径，存储在路径用户矩阵PUA中，具体方法步骤：A：结点之间的边删除：将两用户邻接关系之间的权值设置为false(0)，设置一个大小为2的一维字符串数组temp临时存储此两用户对应两个结点的信息，同时更新用户邻接关系矩阵NRM；B：再次执行第一步指定结点间的最短路径，并将获取的路径结点序列保存在路径用户矩阵PUA[k_i]为起始地址的二维数组中，1≤i≤K；C：从临时一维字符串数组temp中获取步骤A中选择的两个结点的信息，并将连接边的权值恢复为true(1)，同时更新用户邻接关系矩阵NRM；D：针对最短路径中各个相邻结点之间连接关系进行相同形式的删除‑执行操作A，之后重新执行指定结点之间的路径查询‑执行操作B，最后恢复原有的结点间路径关系‑执行操作C，当对最短路径中的所有相邻节点完成操作后即可得到前K条最优最短路径；3)基于ELCS的潜在好友发现：对步骤2)所得存储在路径用户矩阵PUA中的前K条最优最短路径，执行ELCS算法，提取路径用户矩阵PUA中的第i项用户字符串数组，作为执行ELCS的基准项，即为PUA[i]，获取其长度length，构造一个2*length大小的数组空间，将其作为求解公共子序列的一条母串，然后依次从路径用户矩阵PUA中取出另外一组第j项用户字符串数组PUA[j]作为比较项，其中1≤i,j≤K，且i≠j，执行ELCS算法，对基准项的每一项字符串进行比较，比较结果记录在公共子项序列矩阵PIM中，如果发现相同的字符串则引入标记变量tag以斜向增加方式进行数组内容更新，反之则顺向地映射为临近的最大值，直到对基准项中的所有字符串元素遍历完毕；引入两个标记变量来标记矩阵PIM中值最大元素的位置，在矩阵生成的过程中来判断当前生成元素的值是不是当前最大值，据此来改变标记变量的值；在矩阵PIM生成的同时，最长公共子序列的位置和长度也同步计算出来，最后通过PIM查询出PUA中两组最短路径存在的潜在好友。