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

摘要

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

主权项

1.一种社交网络中潜在好友查询方法，其特征在于，包括如下具体步骤：1）建立社交网络图：将各个用户的信息建模成图的结点，其中是图中结点的集合，是图中无向边的集合，表示两个用户之间的直接连接，用户邻接关系矩阵中对应用户之间的连接关系，有连接关系相应的单元设置为，否则设置为；2）在社交网络图的基础上，进行前K条最优路径查询算法：第一步：根据用户社交网络图找到一条指定结点间的最短路径，首先利用路径关系矩阵辅助存储两个结点之间最短路径的途经结点，初始设置为空，以用户邻接关系矩阵为基础，将任意一个用户结点C插入到另外两个用户结点A和B之间，检查是否为最短路径，即是否满足，如果这样的结点存在，则将结点存储在路径关系矩阵，中，直到所有结点全部被遍历则循环结束；第二步：根据启发式的剪枝策略得到指定结点间前K条最优最短路径，存储在路径用户矩阵PUA中，具体方法步骤：A：结点之间的边删除：将两用户邻接关系之间的权值设置为，设置一个大小为2的一维字符串数组临时存储此两用户对应两个结点的信息，同时更新用户邻接关系矩阵；B：再次执行第一步指定结点间的最短路径，并将获取的路径结点序列保存在路径用户矩阵为起始地址的二维数组中，；C：从临时一维字符串数组中获取步骤A中选择的两个结点的信息，并将连接边的权值恢复为，同时更新用户邻接关系矩阵；D：针对最短路径中的各个相邻结点进行同样的删除、查询与恢复操作，直到所有的前条最优路径全部找到；3）基于ELCS的潜在好友发现：首先通过前条最短路径查询前条最短路径，将每条最短路径构造成一个字符串数组作为求解公共子序列的一条母串，然后依次从前条最短路径中取出不同的两条母串，执行算法，进行字串比较，并将比较结果记录在公共子项序列矩阵中，最后通过查询出两组最短路径中存在的潜在好友。