[發明專利]一種基于密度峰的動態圖聚類方法

在審

• 申請號: 201910080266.4
• 申請日: 2019-01-28
• 公開（公告）號: CN109886313A
• 公開（公告）日: 2019-06-14
• 發明（設計）人: 谷峪;吳長發;于戈
• 申請（專利權）人: 東北大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 沈陽東大知識產權代理有限公司 21109
• 代理人: 李在川

1.一種基于密度峰的動態圖聚類方法，其特征在于，包括以下步驟：

步驟1：對圖中的每對鄰接頂點計算結構相似度，所采用的結構相似度公式為：

其中，N[u]表示頂點u的結構鄰居，對于一個圖G(V，E)，即N[u]＝{v∈|(u，v)∈E}∪{u}，N[v]表示頂點v的結構鄰居，deg[u]表示頂點u的度數，頂點u的度數為頂點u結構鄰居的個數，deg[v]表示頂點v的度數；

之后對所有頂點之間的結構相似度進行降序排列，取結構相似度降序排列20％處的值為相似度閾值σ_t，用m表示圖中所有邊的個數，設標號k表示相似度閾值在結構相似度降序排列后所對應的結構相似度序號，則k應該滿足：

步驟2：依次計算圖中每個頂點的三個度量：局部密度，依賴頂點以及依賴相似度；

步驟2-1：局部密度公式作為整個算法的基礎，是能否實現在圖上實現聚類的關鍵因素，本專利作為基于結構的圖聚類算法，首先要考慮頂點的局部結構，定義任意一個頂點的局部密度包括該頂點與其所有結構鄰居之間的結構相似度，設計連續化函數并將標準正態分布作為μ_uv在局部密度公式中的權重，將μ_uv的取值范圍設為0＜μ_uv≤2，以排除不滿足此取值范圍的結構相似度，根據結構相似度，局部密度計算公式為：

步驟2-2：將頂點u的鄰居頂點中局部密度比u大且與u結構相似度最高的頂點稱為u的依賴頂點，記為將u與之間的結構相似度稱為依賴相似度，記為δ_u，計算公式為：

其中N(u)表示頂點u的開放鄰居，對于一個圖G(V，E)，即N(u)＝{v∈V|(u，v)∈E}，如果頂點u的鄰居頂點中不存在局部密度比u大的頂點，則設δ_u＝0，且對于一個頂點u，如果有兩個甚至更多的依賴頂點，那算法將從中隨機挑選一個作為頂點u的依賴頂點；

步驟3：根據每個頂點的三個度量對整個圖建立DP-Index索引，DP-Index索引包括圖中的每個頂點以及每個頂點的局部密度、依賴頂點以及依賴相似度，最后對索引中的頂點根據它們的局部密度進行降序排列，基于DP-Index索引，本專利中靜態圖聚類算法的時間復雜度為O(n)，其中n為頂點的數量；

步驟4：根據步驟2-1以及2-2中定義的局部密度ρ以及依賴相似度δ，以ρ為橫坐標，δ為縱坐標，生成為圖設計的決策圖，然后根據決策圖將局部密度大于等于ξ且依賴相似度小于γ的頂點選入密度峰頂點集，將局部密度小于ξ的頂點選入噪聲頂點集；

步驟5：首先為密度峰頂點集中每個頂點分配一個簇，然后對于不屬于密度峰頂點集以及噪聲頂點集的每一個頂點，按照頂點的局部密度的降序排列順序進行遍歷，并將每個頂點分配到鄰居頂點中局部密度比其大、結構相似度最高的頂點所屬的簇中，最終得到簇結果集；

步驟6：對噪聲頂點集中的頂點進行進一步劃分，如果噪聲頂點集中某頂點u的鄰居屬于不同的簇，那么這個頂點u就被選入到橋頂點集，否則就被選入到異常頂點集；

步驟7：根據DP-Index索引、密度峰頂點集和噪聲頂點集獲得依賴圖，首先初始化一個依賴圖G′(V′，E′)，設頂點集V′和邊集E′為空，之后如果原圖G(V，E)中一個頂點u屬于密度峰頂點集或噪聲頂點集，則將頂點u加入到依賴圖G′中，否則將這個頂點u以及邊加入到依賴圖G′中；此時，依賴圖中的每個連通分量都對應著一個簇，每一個孤立的頂點均屬于噪聲頂點；

步驟8：在動態檢測階段，考慮動態圖的四種變化：增加或刪除邊以及增加或刪除頂點，根據上述四類變化分別實時更新DP-Index索引；

增加邊：當增加邊(u，v)時，頂點u和頂點v的頂點度數加1，然后對頂點u和頂點v進行進一步的更新操作，對于頂點u，重新計算頂點u與鄰居頂點的結構相似度，更新頂點u和鄰居頂點的局部密度，之后更新頂點u、鄰居頂點以及鄰居頂點的鄰居頂點的依賴頂點以及依賴相似度，最后根據頂點變化后的度量對DP-Index進行更新；頂點v的更新操作同頂點u；

刪除邊：當刪除邊(u，v)時，操作類似于增加邊，頂點u和頂點v的頂點度數減1，然后對頂點u和頂點v進行進一步的更新操作，對于頂點u，重新計算頂點u與鄰居頂點的結構相似度，更新頂點u與鄰居頂點的局部密度，之后更新頂點u、鄰居頂點以及鄰居頂點的鄰居頂點的依賴頂點以及依賴相似度，最后根據頂點變化后度量對DP-Index進行更新；頂點v的更新操作同頂點u；

增加頂點：當增加頂點u時，初始化頂點u的局部密度，依賴頂點和依賴相似度，并加入到DP-Index索引中；

刪除頂點：當刪除頂點u時，對每一個頂點u與鄰居頂點v之間的邊(u，v)執行刪除邊操作，之后將頂點u從DP-Index索引中刪除；

步驟9：根據DP-Index索引發生的變化，對依賴圖進行更新，依賴圖的更新主要分為以下5種情況：

非噪聲頂點變成噪聲頂點：當非噪聲頂點u變成噪聲頂點時，如果在依賴圖中存在邊則刪除邊

噪聲頂點變成非噪聲頂點：當噪聲頂點u變成非噪聲頂點時，如果頂點u變化后不為密度峰頂點，在依賴圖中加入邊

密度峰頂點變成非密度峰頂點：密度峰頂點u變成非密度峰頂點時，如果頂點u變化后不為噪聲頂點，在依賴圖中加入邊

非密度峰頂點變成密度峰頂點：如果非密度峰頂點u不為噪聲頂點，頂點u變成密度峰頂點時，在依賴圖中刪除邊

頂點的依賴頂點發生變化：如果頂點u不為噪聲頂點或密度峰頂點，且頂點u的依賴頂點從變成則在依賴圖中刪除邊加入邊

最后，通過獲取依賴圖中的連通分量就可以得到實時聚類結果；監控依賴圖中連通分量的變化便可以獲得簇演化事件。