一種基於拓撲勢的重疊複雜網絡社區發現方法及系統的製作方法
2023-05-26 15:24:36
一種基於拓撲勢的重疊複雜網絡社區發現方法及系統的製作方法
【專利摘要】本發明提供一種基於拓撲勢的重疊複雜網絡社區發現方法及系統，該方法包括：根據給定的重疊複雜網絡，建立拓撲勢場，計算網絡中各個節點的拓撲勢值；搜索獲得拓撲勢場中的所有峰位節點，從所有峰位節點中選取每個社區的代表節點；以每個代表節點為中心按廣度優先向外擴展，若擴展節點位於拓撲勢場的谷位，則為該社區與其他社區的重疊節點，擴展停止；若擴展節點位於拓撲勢場的斜坡位，則為該社區的內部節點，擴展繼續；全部代表節點的擴展結束後，未被訪問過的節點位於邊緣位，是不屬於任何社區的孤立節點。本發明考慮了節點質量的差異性，利用了拓撲勢場的峰谷結構，根據節點在拓撲勢場中的位置進行重疊複雜網絡社區發現，社區劃分準確，效率高。
【專利說明】一種基於拓撲勢的重疊複雜網絡社區發現方法及系統【技術領域】[0001]本發明屬於網絡識別【技術領域】，涉及一種網絡社區發現方法，特別是涉及一種基 於拓撲勢的重疊複雜網絡社區發現方法及系統。【背景技術】[0002]現實世界中的諸多系統都以複雜網絡的形式存在，如科技系統中的網際網路，社會 系統中的人際關係網，生態環境中的食物鏈網，以及電力網絡和交通網絡。社區發現是複雜 網絡的一項重要研究內容，對於分析複雜網絡的拓撲結構，理解複雜系統的功能，發現複雜 網絡中的隱藏規律、演化趨勢以及預測複雜網絡的行為都具有重要的意義。[0003]目前已存在多種複雜網絡社區發現方法，拓撲勢方法是這些方法中的一個重要分 支，該類方法具有時間複雜度低，無需領域或專家知識等優勢。淦文燕等人在發表於2009 年《軟體學報》期刊的文章「一種基於拓撲勢的網絡社區發現方法」中首次引入拓撲勢描 述複雜網絡節點間的作用與聯繫，將每個社區視為拓撲勢場的局部高勢區，通過效益函數 確定每個複雜網絡節點的社區歸屬。該方法對重疊節點的確定條件比較嚴苛，從而導致 重疊節點數量過於稀少，缺乏現實合理性。韓言妮等人在發表於2011年《Frontiers of Computer Science of China〉〉期幹丨J的文章 「 Identifying different community members in complex networks based on topology potential」中提出基於拓撲勢的複雜網絡節點 類型識別和重疊社區發現。該方法僅僅藉助拓撲勢找出社區代表節點，即局部極值點，在以 局部極值節點為中心往外擴展劃分社區過程中，判斷節點社區歸屬的主要依據是節點度等 有關節點連接關係的統計信息。張建沛等人在發表於2012年《電子學報》期刊的文章「基 於歸屬不確定性的變規模網絡重疊社區識別」中提出一種出基於歸屬不確定性的變規模網 絡重疊社區識別方法。該方法首先根據節點拓撲勢值的構成定義重疊節點社區歸屬不確定 性側度公式，然後進行變規模社區發現。在該方法中，社區的規模及節點社區歸屬完全依賴 於預設的調節參數I。對於實際的複雜網絡，很難預先判斷每個社區的規模，因此預設一個 合理的調節參數ξ十分困難。[0004]綜上所述，現有基於拓撲勢理論的重疊複雜網絡社區發現方法存在以下不足:(I)在節點拓撲勢計算過程中，假設所有複雜網絡節點質量相同，忽略節點間的質量差異， 缺乏現實合理性；(2)在社區發現過程中，沒有利用拓撲勢場本身所呈現的峰谷結構這一 固有特性，而是通過效益函數等額外手段進行判斷，增加了社區發現的複雜性。
【發明內容】
[0005]鑑於以上所述現有技術的缺點，本發明的目的在於提供一種基於拓撲勢的重疊復 雜網絡社區發現方法及系統，用於解決現有基於拓撲勢的網絡社區發現方法忽略網絡節點 間的質量差異及沒有利用拓撲勢場本身所呈現的峰谷結構這一固有特性，而是通過效益函 數等額外手段進行節點社區歸屬判斷等問題。[0006]為實現上述目的及其他相關目的，本發明提供一種基於拓撲勢的重疊複雜網絡社區發現方法及系統。
[0007]—種基於拓撲勢的重疊複雜網絡社區發現方法，包括:根據給定的重疊複雜網絡，建立拓撲勢場，計算網絡中各個節點的拓撲勢值；根據所述各節點的拓撲勢值搜索獲得拓撲勢場中的所有峰位節點，從所有峰位節點中選取每個社區的代表節點；依次訪問各個代表節點，分別以每個代表節點為中心按廣度優先向外擴展，確定擴展節點的社區歸屬；若擴展節點位於拓撲勢場的谷位，則為該社區與其他社區的重疊節點，擴展停止；若擴展節點位於拓撲勢場的斜坡位，則為該社區的內部節點，擴展繼續；全部代表節點的擴展過程結束後，未被訪問過的節點均位於拓撲勢場的邊緣位，是不屬於任何社區的孤立節點。
[0008]優選地，所述網絡中各個節點u i的拓撲勢值的計算過程為:
[0009]
【權利要求】
1.一種基於拓撲勢的重疊複雜網絡社區發現方法，其特徵在於，所述基於拓撲勢的重疊複雜網絡社區發現方法包括: 根據給定的重疊複雜網絡，建立拓撲勢場，計算網絡中各個節點的拓撲勢值； 根據所述各節點的拓撲勢值搜索獲得拓撲勢場中的所有峰位節點，從所有峰位節點中選取每個社區的代表節點； 依次訪問各個代表節點，分別以每個代表節點為中心按廣度優先向外擴展，確定擴展節點的社區歸屬；若擴展節點位於拓撲勢場的谷位，則為該社區與其他社區的重疊節點，擴展停止；若擴展節點位於拓撲勢場的斜坡位，則為該社區的內部節點，擴展繼續； 全部代表節點的擴展過程結束後，未被訪問過的節點位於拓撲勢場的邊緣位，是不屬於任何社區的孤立節點。
2.根據權利要求1所述的基於拓撲勢的重疊複雜網絡社區發現方法，其特徵在於，所述網絡中各個節點 ' 的拓撲勢值供(H)的計算過程為:
3.根據權利要求2所述的基於拓撲勢的重疊複雜網絡社區發現方法，其特徵在於，所述節點υ i的質量m( υ J的計算過程為:
4.根據權利要求1所述的基於拓撲勢的重疊複雜網絡社區發現方法，其特徵在於，所述峰位節點的搜索過程包括: 比較每個節點的拓撲勢值與自身下一跳鄰居節點的拓撲勢值的大小； 若當前節點的拓撲勢值大於自身所有鄰居節點的拓撲勢值，則當前節點位於拓撲勢場的峰位，為峰位節點；若兩個峰位節點的距離，即跳數，小於
5.根據權利要求4所述的基於拓撲勢的重疊複雜網絡社區發現方法，其特徵在於，所述谷位和斜坡位的判斷依據為當前待判斷的節點與自身下一跳節點的拓撲勢值的大小；具體判斷過程包括:若當前節點的下一跳所有節點的拓撲勢值均上升，且當前節點所屬社區無合併峰位節點，則當前節點位於谷位；若當前節點的下一跳節點的拓撲勢值部分上升部分下降，且當前節點在多個峰位節點的影響範圍內，貝1J當前節點位於谷位；若當前節點的下一跳所有節點的拓撲勢值均下降，則當前節點位於斜坡位；若當前節點的下一跳所有節點的拓撲勢值均上升，但當前節點所屬社區存在合併峰位節點，且合併峰位節點是除代表節點外距離當前節點最近的峰位節點，則當前節點位於斜坡位；若當前節點的下一跳節點的拓撲勢值部分上升部分下降，但當前節點只在自身所屬社區的峰位節點的影響範圍內，則當前節點位於斜坡位。
6.一種基於拓撲勢的重疊複雜網絡社區發現系統，其特徵在於，所述系統包括:拓撲勢場建立模塊，根據給定的重疊複雜網絡建立拓撲勢場，並計算出網絡中各個節點的拓撲勢值；搜索模塊，與所述拓撲勢場建立模塊相連，根據所述各節點的拓撲勢值搜索獲得拓撲勢場中的所有峰位節點，從所有峰位節點中選取每個社區的代表節點；擴展模塊，與所述搜索模塊相連，依次訪問各個代表節點，分別以每個代表節點為中心按廣度優先向外擴展，擴展到的節點稱為擴展節點；歸屬確定模塊，與所述擴展模塊相連，確定擴展節點的社區歸屬；若擴展節點位於拓撲勢場的谷位，則為該社區與其他社區的重疊節點，擴展停止；若擴展節點位於拓撲勢場的斜坡位，則為該社區的內部節點，擴展繼續；全部代表節點的擴展過程結束後，未被訪問過的節點均位於拓撲勢場的邊緣位，是不屬於任何社區的孤立節點。
7.根據權利要求6所述的基於拓撲勢的重疊複雜網絡社區發現系統，其特徵在於，所述拓撲勢場建立模塊包括:節點質量獲取單元，計算獲得網絡中各個節點的質量；所述節點質量獲取單元的數學模型為:
8.根據權利要求7所述的基於拓撲勢的重疊複雜網絡社區發現系統，其特徵在於，所述搜索模塊包括: 比較單元，與所述拓撲勢值獲取單元相連，比較每個節點的拓撲勢值與自身下一跳鄰居節點的拓撲勢值的大小； 峰位節點判斷單元，與所述比較單元相連，若當前節點的拓撲勢值大於自身所有鄰居節點的拓撲勢值，則當前節點位於拓撲勢場的峰位，為峰位節點；代表節點判斷單元，與所述峰位節點判斷單元相連，從所有峰位節點中選取每個社區的代表節點；若兩個峰位節點的距離，即跳數，小於匕3σ/，則在所述兩個峰位節點中選擇拓撲勢值較大的節點作為社區的代表節點，另一個拓撲勢值較小的節點稱為合併峰位節點；否則每個峰位節點均為各自社區的代表節點。
9.根據權利要求8所述的基於拓撲勢的重疊複雜網絡社區發現系統，其特徵在於，所述歸屬確定模塊包括: 谷位判斷單元，與所述擴展模塊相連，若當前擴展節點的下一跳所有節點的拓撲勢值均上升，且當前擴展節點所屬社區無合併峰位節點，則判定當前擴展節點位於谷位；若當前擴展節點的下一跳節點的拓撲勢值部分上升部分下降，且當前擴展節點在多個峰位節點的影響範圍內，則判定當前擴展節點位於谷位； 斜坡位判斷單元，與所述擴展模塊相連，若當前擴展節點的下一跳所有節點的拓撲勢值均下降，則判定當前擴展節點位於斜坡位；若當前擴展節點的下一跳所有節點的拓撲勢值均上升，但當前擴展節點所屬社區存在合併峰位節點，且合併峰位節點是除代表節點外距離當前擴展節點最近的峰位節點，則判定當前擴展節點位於斜坡位；若當前擴展節點的下一跳節點的拓撲勢值部分上升部分下降，但當前擴展節點只在自身所屬社區的峰位節點的影響範圍內，則判定當前擴展節點位於斜坡位； 邊緣位判斷單元，與所述擴展模塊相連，若當前擴展節點既非位於峰位或谷位，也非位於斜坡位，則當前擴展節點位於邊緣位。
【文檔編號】G06F17/30GK103500168SQ201310392149
【公開日】2014年1月8日 申請日期:2013年9月2日 優先權日:2013年9月2日
【發明者】王志曉, 趙亞, 陳昭彤 申請人:中國礦業大學