[發明專利]一種在線社交網絡中朋友關系預測的方法

有效

• 申請號: 201410025336.3
• 申請日: 2014-01-16
• 公開（公告）號: CN103795613B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 郭斌;於志文;羅惠;周興社;倪紅波;王柱
• 申請（專利權）人: 西北工業大學
• 主分類號: H04L12/58
• 分類號: H04L12/58;G06F17/30;G06Q10/04
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及社會計算技術領域，尤其涉及一種在線社交網絡中朋友關系預測的方法。

背景技術

近年來社交網絡得到了迅猛的發展，人們對信息的獲取和消息的傳遞開始變得越來越依賴于網絡，用戶可以通過分享新聞、日志、視頻、音樂及相片等方法，維持和開拓人際關系。在線社交網絡是虛擬和現實的結合，人們在現實生活中的行為和他們在社交網絡中的行為有很大程度的相似性，這些行為相似的并且在地理上相距比較近的人更有可能成為朋友。

在線社交網絡基于六度分割理論運作，即你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過六個人你就能夠認識任何一個陌生人。這就是六度分割理論，也叫小世界理論。每個個體的社交圈不斷放大，最后形成一個大型的社交拓撲網絡。

專利200610157496.9提出了一種社交網絡社區的推薦朋友的方法，但其沒有考慮用戶的社交圈子以及用戶之間的距離。專利200910213921.5只公開了社交網絡中社區推薦異性朋友的方法，其只考慮了用戶的特征信息，沒有用戶的行為信息。專利200810009403.7提出了社會網絡的競爭性朋友排名的方法，強調朋友之間的互動，忽略了用戶本身的行為和地域等信息。

鑒于上述缺陷，本發明創作者經過長時間的研究和實踐終于獲得了本創作。

發明內容

本發明的目的在于提供一種在線社交網絡中朋友關系預測的方法，用以克服上述技術缺陷。

為實現上述目的，本發明提供一種在線社交網絡中朋友關系預測的方法，該具體過程為：

步驟101，基于社交網站提供的API接口采集用戶在社交網絡上的簽到數據及朋友關系；

步驟102，根據采集的數據提取特征來表征用戶之間的關系，以信息增益為標準，衡量選取特征的信息含量，選取信息增益最大的三個特征來表征用戶之間的朋友關系；

步驟103，按城市選取社交網絡中在的所有在該城市有簽到數據及有簽到數據的用戶的朋友關系作為訓練數據，將朋友關系數據和非朋友關系數據比例定為1∶3，按選取的三個特征采用分類算法建立朋友關系模型；

步驟104，選取要預測用戶的簽到和朋友關系數據作為測試數據，對選取的每個用戶，預測其與測試數據中其他所有用戶之間的關系。

進一步，上述步驟102中選取用戶社交拓撲、用戶簽到地點類型和用戶簽到地點三個特征；上述特征的具體計算方法如下：

定義社交網絡G_s(U_s，E_s)，節點u_s表示用戶，假定G_s為完全圖，若兩用戶u_i，u_j是朋友，則用一條朋友邊連接；若他們為非朋友，則用一條非朋友邊連接，當去掉用戶u_i，u_j之間的朋友邊后，他們之間即為非朋友邊，非朋友邊不能被刪除。

進一步，所述用戶社交網絡的計算方法如下：

在社交網G_s中，去掉社交網G_s中用戶i和用戶j之間的朋友邊，用戶i和用戶j拓撲網絡中的最短距離即為他們在用戶拓撲網絡中的社交距離；若用戶之間為朋友邊，則其距離為1，否則為無窮大；在計算用戶i和用戶j社交距離之前，若用戶i和用戶j之間為朋友邊則先在社交網Gs中刪除該邊e_ij，若為非朋友邊則直接計算；

設用戶i和用戶j之間的用戶邊在社交網絡結構中的社交距離為屬性a_s，其計算方法如公式1所示；

a_s(i，j)=shortest_dis?tan?ce(u_i，u_j)inG′_s(U_s，E_s-e_ij)???(1)

最短距離的計算方法可采用Dijkstra算法或Floyd算法。

進一步，所述用戶簽到地點類型的計算方法如下：