[發明專利]一種基于節點連接和屬性相似度的社團發現方法和系統

在審

• 申請號: 202010948386.4
• 申請日: 2020-09-10
• 公開（公告）號: CN112084425A
• 公開（公告）日: 2020-12-15
• 發明（設計）人: 張能鋒;張俊;胡倫
• 申請（專利權）人: 深圳市萬佳安人工智能數據技術有限公司
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06F17/11;G06F17/16;G06Q50/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明提出了一種基于節點連接和屬性相似度的社團發現方法和系統，包括網絡構建模塊、數據初始化模塊、模型構建模塊、模型求解模塊、社團發現模塊以及結果展示模塊，其中，所述網絡構建模塊將社交網絡數據構建為基于鏈接的網絡，數據初始化模塊執行服務器計算指令，獲得網絡的鄰接矩陣、屬性相似度矩陣和拓撲結構矩陣，并初始化相似度矩陣，模型構建模塊獲取輸入參數后在服務器構建關于相似度矩陣的最優化問題，模型求解模塊在得到模型構建模塊構建完成的指令后開始對最優化問題進行迭代求解，計算獲得最優的相似度矩陣，社團發現模塊在得到最優的相似度矩陣后執行社團發現指令，最后將社團發現結果通過展示模塊進行輸出展示。本發明直接作用于帶有節點屬性的社交網絡數據集合，能夠針對社交網絡中重疊社團進行發現，效果準確度高，能夠解決社交網絡中的社團發現問題。

技術領域

本發明涉及計算機數據處理技術領域，特別涉及到社交網絡中的社團發現問題。

背景技術

近年來社交網絡快速發展，例如新浪微博、微信、各種在線論壇等，這類網絡是互聯網重要的組成部分。由于社團在網絡系統中扮演著重要的角色，近年來對社交網絡分析的社團檢測研究激增。社交網絡由用戶和用戶之間相互關系構成，把網絡中的用戶抽象為節點，用戶之間的關系抽象成邊，這樣可以把社交網絡抽象為圖的形式進行研究。

然而，許多真實的網絡具有更復雜的重疊社團結構，以及社團中用戶包含著各種屬性，所以傳統的基于社交網絡的拓撲結構的社團發現方法不能很好的識別重疊社團結構，同時忽視了用戶相關聯的屬性信息在社團發現工作中起到的重要作用。例如，某社交平臺中，某用戶和他不同的好友分別在不同的群組里，如果僅基于網絡拓撲結構，當該用戶被識別在某個群組里時，可能就會忽視該用戶也在其他群組里的情況。

發明內容

針對上述缺陷和不足，本發明的目的在于提供一種基于鏈接和節點屬性相似度社交網絡社團發現方法和系統，通過綜合考慮社交網絡中重疊社團及節點屬性相似度程度實現社團發現。

本發明通過以下技術方案來實現：

本發明公開了一種基于節點連接和屬性相似度的社團發現方法，包括以下步驟：

步驟一，通常將社交網絡中的用戶抽象為網絡中節點，兩個用戶之間的聯系構成邊，現在將此網絡轉換了基于鏈接的新網絡，邊作為新網絡中的節點，相鄰的邊作為新網絡中的邊,如圖2所示。對新網絡中的數據進行預處理，其中包括：所有節點的集合，兩節點之間邊構成的集合，與節點相關聯的所有屬性的集合；

步驟二，根據步驟一預處理的結果求出所述網絡的鄰接矩陣、屬性相似度矩陣和拓撲結構矩陣，定義并初始化相似度矩陣；

步驟三，基于步驟二所得節點的鄰接矩陣、屬性相似度矩陣、拓撲結構矩陣和初始化的相似度矩陣，構建關于相似度矩陣的最優化問題；

步驟四，求解步驟三中構建的最優化問題，得出相似度矩陣的最優解；

步驟五，根據步驟四所得相似度矩陣，經過處理后獲取所發現的社團。

步驟二在求解屬性相似度矩陣時用到了Jaccard相似度，求解拓撲結構矩陣時用到了Simrank。步驟四在求解最優化問題時，采用交替優化的策略，構建Karush-Kuhn-Tucker(KKT)條件來獲得更新公式。在初始化相似度矩陣的情況下，根據更新公式不斷地更新迭代，直到步驟五所得最優化問題的目標函數收斂。此時的相似度矩陣作即為最佳的相似度矩陣。

本發明公開了一種基于節點連接和屬性相似度的社團發現系統，該系統包括：

網絡構建模塊，將包含了大量屬性信息的社交網絡構建成為一個基于鏈接的網絡；

數據初始化模塊，根據前一個模塊中的得到的網絡進行數據處理獲得節點的鄰接矩陣、節點屬性相似度矩陣和拓撲結構矩陣，初始化對于網絡的相似度矩陣；