[發明專利]社交網絡中潛在好友查詢方法

有效

• 申請號: 201210179600.X
• 申請日: 2012-06-04
• 公開（公告）號: CN102722566A
• 公開（公告）日: 2012-10-10
• 發明（設計）人: 田秀霞;宋羊力;王曉玲;周傲英
• 申請（專利權）人: 上海電力學院
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海申匯專利代理有限公司 31001
• 代理人: 吳寶根

1.一種社交網絡中潛在好友查詢方法，其特征在于，包括如下具體步驟：

1）建立社交網絡圖：將各個用戶的信息建模成圖???????????????????????????????????????????????的結點，其中是圖中結點的集合，是圖中無向邊的集合，表示兩個用戶之間的直接連接，用戶鄰接關系矩陣中對應用戶之間的連接關系，有連接關系相應的單元設置為，否則設置為；

2）在社交網絡圖的基礎上，進行前K條最優路徑查詢算法：

第一步：根據用戶社交網絡圖找到一條指定結點間的最短路徑，首先利用路徑關系矩陣輔助存儲兩個結點之間最短路徑的途經結點，初始設置為空，以用戶鄰接關系矩陣為基礎，將任意一個用戶結點C插入到另外兩個用戶結點A和B之間，檢查是否為最短路徑，即是否滿足，如果這樣的結點存在，則將結點存儲在路徑關系矩陣，中，直到所有結點全部被遍歷則循環結束；

第二步：根據啟發式的剪枝策略得到指定結點間前K條最優最短路徑，存儲在路徑用戶矩陣PUA中，具體方法步驟：

A：結點之間的邊刪除：將兩用戶鄰接關系之間的權值設置為，設置一個大小為2的一維字符串數組臨時存儲此兩用戶對應兩個結點的信息，同時更新用戶鄰接關系矩陣；

B：再次執行第一步指定結點間的最短路徑，并將獲取的路徑結點序列保存在路徑用戶矩陣為起始地址的二維數組中，；

C：從臨時一維字符串數組中獲取步驟A中選擇的兩個結點的信息，并將連接邊的權值恢復為，同時更新用戶鄰接關系矩陣；

D：針對最短路徑中的各個相鄰結點進行同樣的刪除、查詢與恢復操作，直到所有的前條最優路徑全部找到；

3）基于ELCS的潛在好友發現：首先通過前條最短路徑查詢前條最短路徑，將每條最短路徑構造成一個字符串數組作為求解公共子序列的一條母串，然后依次從前條最短路徑中取出不同的兩條母串，執行算法，進行字串比較，并將比較結果記錄在公共子項序列矩陣中，最后通過查詢出兩組最短路徑中存在的潛在好友。

2.根據權利要求1所述社交網絡中潛在好友查詢方法，其特征在于，所述步驟3）中的算法包括兩部分：

第一部分：將字符比較擴展到字符串比較，將其中一組用戶字符串數組作為基準項，獲取其長度length，構造一個大小的數組空間，將另外一組用戶字符串數組作為比較項，，且，對基準項的每一項字符串進行比較，并逐次刷新數組內容，如果發現相同的字符串則引入標記變量以斜向增加方式進行數組內容更新，反之則順向地映射為臨近的最大值，直到對基準項中的所有字符串元素遍歷完畢；

第二部分：字符串匹配的標記方法改進，在字符串比較過程中，引入兩個標記變量來標記矩陣中值最大元素的位置，在矩陣生成的過程中來判斷當前生成元素的值是不是最大的，據此來改變標記變量的值，最后在矩陣生成的同時，最長公共子序列的位置和長度也可以同步計算出來。

3.根據權利要求2所述社交網絡中潛在好友查詢方法，其特征在于，所述兩條最短路徑中字符串比較的具體步驟如下：

A：假設從前條最優最短路徑查詢算法獲得的所有字符串中任取兩個字符串為和，為的長度，為的長度，，初始化為0，設置等于0，等于0；

B：如果大于，則設置等于0和等于1，跳轉至步驟6，否則跳轉到步驟C；

C：如果大于，則跳轉到步驟B，且等于，否則跳轉到步驟D；

D：如果，則，且，，跳轉到步驟C，反之跳轉到步驟E；

E：設置，而且，，跳轉到步驟C；

F：如果則算法模塊結束，否則跳轉到步驟G；

G：如果，則輸出，而且，

跳轉到步驟F，否則，跳轉到步驟F。