[發明專利]一種考慮節點局部標注特性的符號預測方法

在審

• 申請號: 201611156336.2
• 申請日: 2016-12-14
• 公開（公告）號: CN106780067A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 蘇曉萍;宋玉蓉
• 申請（專利權）人: 南京工業職業技術學院
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 南京瑞弘專利商標事務所(普通合伙)32249
• 代理人: 賈郡

技術領域

本發明涉及一種互聯網技術，特別是一種考慮節點局部標注特性的符號預測方法。

背景技術

符號網絡是指邊具有正或負符號屬性的網絡，符號為正表示網絡中兩用戶間具有相互信任的、積極的朋友關系，負邊則表示不信任的、消極的敵對關系。具有符號屬性的網絡普遍存在，因為在許多復雜系統中都存在對立關系：在線社交網絡中的用戶可以對其他用戶表達信任或不信任的態度、標注朋友或敵人關系，對某一問題給出不同的觀點；生物系統中，神經元之間存在促進和抑制作用；國際關系中更是存在合作與敵對關系，研究網絡的符號屬性有利于理解網絡的基本結構特征、理解信任和不信任的傳播方式。這些復雜系統用現有針對無符號的二值網絡建模不能準確反映節點間的關系，簡單網絡的研究思路和方法并不適用于符號網絡。符號網絡的研究始于Heider基于社會心理學對人類關系的研究，隨著復雜網絡研究的逐步展開，符號網絡的結構特征與演化規律受到研究者的關注。

在符號網絡中，由于邊的符號屬性能夠直接反映節點間的態度，因此在推薦系統、輿情分析與觀點形成、網絡欺凌與社會排斥等問題中都有應用。于是，如何通過部分觀測到的網絡符號預測未知的邊符號成為符號網絡中非常重要的研究方向，關于它的研究近幾年受到來自復雜網絡、機器學習等領域的重視，并提出了許多有效方法。

符號預測方法根據考慮網絡結構特征的不同大致可以分為兩類：①考慮網絡局部特征的方法；②考慮網絡全局特征的方法。考慮網絡局部特征的方法主要利用節點的鄰域特征如：節點的出度、入度以及三元組結構特征進行符號預測。這類方法主要基于節點鄰居的統計特征以及社會學相關理論：結構平衡理論(弱結構平衡)和地位理論通過分析節點鄰居間的標注特征實現邊符號的預測，所有基于結構平衡和地位理論的預測方法均要求兩節點間必須具有共同鄰居，否則無法構成三元組。例如：Guha等最早研究了網絡模型上的符號預測問題，他們將信任網絡表示為矩陣并運用不同的矩陣運算代表信任關系在網絡上的不同傳播方式，成功實現了信任關系的預測。Leskove c等首先采用機器學習的方法對符號預測問題進行了研究。他們利用節點的出度、入度、節點的嵌入性以及基于地位理論的所有16種待預測邊所處的三角形的關系模式作為特征采用邏輯回歸模型訓練分類器，得到了較高的預測精度。文獻則通過網絡局部特征和地位理論為特征采用SVM算法進行二值分類實現符號預測。相對于Leskovec考慮長度為3的有序環構建的網絡特征，Chiang等，利用Katz指標提出一個不平衡測度指標并通過長度為

的環的平衡程度構建特征集，然后使用邏輯回歸模型進行符號預測，當環的長度從3增加到5時，預測精度有所提高，但是當>5后對預測精確度的影響不大。事實上能夠反映符號網絡不平衡程度的測度都可以用于符號預測，因為對于未知符號的預測就是使圖的不平衡程度最小。文獻通過分析兩節點間不同的連接形式，提出符號預測的方法，使得在沒有共同鄰居的情形下的預測精度有所提高。

研究發現符合結構平衡(弱結構平衡)的局部結構特征反過來會促使一些有趣的全局特征的出現，當然也就催生了利用網絡全局結構進行符號預測的方法。文獻就從譜分析的角度出發進行符號預測并指出許多基于譜分析的方法可以從簡單的二值網絡擴展到符號網絡。他們將拉普拉斯矩陣的定義擴充到符號網絡，通過拉普拉斯矩陣的核函數進行網絡符號的預測。Hsieh等發現滿足弱結構平衡理論的符號網絡其鄰接矩陣具有低秩特征于是將符號預測問題轉化為矩陣填充問題，用低秩填充法有效地進行了符號預測。他們還將符號預測近似為低秩矩陣分解問題進行了符號預測。文獻也研究了矩陣分解在符號預測中的應用并解決了數據不平衡對預測精度的影響。文獻提出了一種區別于Hsieh以逐點誤差衡量原矩陣與結果矩陣誤差的方法，他們將成對誤差應用到矩陣分解的損失函數中，給出的算法MF-LiSP取得了較高精確度。另外，為提高矩陣填充、矩陣分解的效率也提出相應方法。另外，符號網絡中除了結構信息外還有豐富的元數據信息，它們代表用戶的熟識度、聲譽、語義與態度等，運用元數據與網絡結構信息共同進行符號預測也受到關注。通過以上介紹發現，符號網絡的局部結構特征反過來會促使全局特征的出現，可見兩者間聯系緊密，因此符號預測方法僅使用局部特征或全局特征都不夠全面，在預測算法中如何同時利用局部和全局特征是一個需要進一步研究的問題。另外，對于局部特征目前的依據只有結構平衡(弱結構平衡理論)和地位理論，需要進一步豐富。

發明內容

本發明的目的在于提供一種考慮節點局部標注特性的符號預測方法，用合適的模型描述在線社會網絡中用戶間友好或敵對的態度，從全局和局部兩個角度共同考察用戶的標注行為。