[發明專利]基于動力距離更新的社區檢測方法

在審

• 申請號: 201711403013.3
• 申請日: 2017-12-22
• 公開（公告）號: CN108280771A
• 公開（公告）日: 2018-07-13
• 發明（設計）人: 黃健斌;邊青全;周瑜
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

本發明公開一種基于動力同步距離更新的社區檢測方法，實現步驟包括：構建社會網絡；初始化社會網絡中的社區；初始化社會網絡中相鄰節點之間邊的距離；根據邊上已有的距離合并與分裂社區；更新社會網絡中每條邊的距離；判斷社會網絡中每條邊的距離是否全部為0或者1，若是確定社會網絡中最終社區，否則返回根據邊上已有的距離合并與分裂社區。本發明的檢測社區方法將距離動力學與層次聚類中的合并與分裂的思想相融合，能夠有效應用于社會網絡社區的檢測，提高了社會網絡社區檢測結果的準確度。

技術領域

本發明屬于計算機技術領域，更進一步涉及社會網絡計算技術領域中的一種基于動力距離更新的社區檢測方法。本發明可以在不需要任何額外輸入參數的情況下，快速高效地從大規模社會網絡中檢測出有意義的社區結構，為進一步挖掘具有商業價值的信息提供技術支持。

背景技術

由于社會網絡的實用性和普遍性，使得對大規模社會網絡的研究成為現階段一個熱點的科學問題，在社會網絡中最顯著的特征是社區，即社團結構。在研究過程中，我們把社交關系建模成圖結構，社交關系中的人對應著圖中的節點，社交關系中人與人之間的朋友關系對應著圖中的邊，這樣我們可以利用圖進一步進行深入地分析，發現社會網絡中的社區結構。在DBLP論文合著網絡中，論文作者代表節點，作者之間的合著關系用邊表示，網絡中的一個社區表示這些作者之間的論文合著數量較多，他們研究領域更為相近。在線社交媒體中，用戶被視為節點，用戶與用戶之間的好友關系被視為邊，位于同一社區內的好友之間關系更為密切。

邵俊明等人在其發表的論文“CommunityDetection based on DistanceDynamics”(ACMSIGKDD Conferences on Knowledge Discovery andData Mining2015)中公開了一種基于動力學的社團檢測方法Attractor。該方法以迭代地方式不斷更新網絡中邊的距離。該方法的步驟為：步驟1，輸入網絡緊湊參數；步驟2，計算網絡中每條邊的就初始距離；步驟3，掃描網絡中的每一條邊，根據網絡的拓撲結構和緊湊參數計算與該邊的兩個端點相鄰的鄰居節點對該邊距離的影響，從而更新邊的距離；步驟4、重復步驟(3)直到圖中每條邊的距離不再發生變化。該方法存在不足之處是：Attractor最終的檢測出的社區個數以及社區的大小依賴于一個手動輸入參數，這使得該方法缺乏自動性。由于Attractor過度依賴于局部結構會產生距離震蕩的現象，使得迭代次數過多，該方法較為耗時。通常情況下，Attractor總是將網絡劃分為很多的小社區。

西安電子科技大學在其申請的專利文獻“基于振蕩器相位同步的符號網絡社區檢測方法”(專利申請號201310392893.4，公開號CN103475539)中公開一種基于改進的Kuramoto動力學模型的社區檢測方法。該方法的步驟為：步驟1，根據待網絡中節點之間的關系生成鄰接矩陣；步驟2，隨機產生N個服從均勻分布的隨機數，將所產生的隨機數一一對應地設為網絡中N個節點的初始相位；步驟3，使用改進的Kuramoto動力學模型更新節點的相位；步驟4，根據每個節點更新前后的相位值差判斷節點的相位達到穩定；步驟5，統計各個子區間節點個數。若子區間節點個數大于等于閾值M，則將該組內所有子區間對應的節點作為網絡的一個社區；否則，該組內所有節點為網絡的重疊節點。該方法存在的不足在于，對于社區間有正連接的網絡最終穩定節點相位不能達到一致，導致社區檢測的速度慢。另外，該方法檢測出來的社區個數依賴于閾值M，這樣的閾值會影響到最終檢測結果的準確性。

發明內容

本發明的目的在于針對上述已有技術的不足，提出一種基于動力同步距離更新的社區檢測方法，在社會網絡數據上檢測社區，得到能夠滿足一定正確率的社區結構。