[發明專利]一種基于博弈論的增量式異構圖聚類方法

有效

• 申請號: 201810271526.1
• 申請日: 2018-03-29
• 公開（公告）號: CN108399268B
• 公開（公告）日: 2022-04-29
• 發明（設計）人: 高云君;陳璐;浦世亮;張遠亮
• 申請（專利權）人: 浙江大學;杭州海康威視數字技術股份有限公司
• 主分類號: G06F16/35
• 分類號: G06F16/35
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 邱啟旺

1.一種基于博弈論的增量式異構圖聚類方法，其特征在于，該方法包括如下步驟：

步驟(1)：對DBLP數據集進行預處理，構建異構圖模型，將論文作為異構圖的主類結點，將會議，作者，關鍵詞作為屬性結點；

步驟(2)：對異構圖模型中的每一個論文，基于Personalized Pagerank算法進行回退時，只處理主類結點，即論文，然后將所有結點的殘留值和儲存值保存在外存中，用于步驟(3)的更新使用；

步驟(3)：根據當前邊的權重，對異構圖模型中的每一個論文，重新計算轉移概率矩陣，讀取步驟(2)保存的殘留值和儲存值，對所有結點進行回退操作，計算出每個論文到圖結構中其他論文的Personalized Pagerank得分；

步驟(4)：對任意兩個論文之間的兩個Personalized Pagerank得分，取兩者之間的較小值作為兩個結點的相似性度量；

步驟(5)：基于DBSCAN算法對所有論文進行聚類；

步驟(6)：基于博弈論對步驟(5)的聚類結果進行調整，得到新的聚類結果；

步驟(7)：基于步驟(6)獲得的新的聚類結果的信息熵對論文之間的邊權重進行更新，如果當前邊權重和上一輪邊權重的均方誤差小于設定的誤差限，則得到最終聚類結果，即論文的聚類結果，否則返回步驟(3)重復迭代計算。

2.根據權利要求1所述的一種基于博弈論的增量式異構圖聚類方法，其特征在于：所述步驟(1)中構建異構圖模型的步驟如下：

對DBLP數據集進行預處理，預處理后為一個無向有權圖G＝(V,E,ω)，圖模型同時包含一個結點類型映射函數V→A和一個邊類型映射函數ψ∶E→R，其中V是結點集合，E是邊集合，|A|1,|R|1，ω是一個邊權重映射函數；此外，將A₀作為主類結點類型，A_i(1≤i≤|A|-1)作為屬性結點類型；

一個異構圖模型G可以用一個|V|×|V|的關聯矩陣表示，其中矩陣元素h(v,u)表示為：

對于每一個論文v，從v到與它相連的結點u∈A_i的權重和等于一個常數c_i，也就是：

其中ω(v,u)表示邊(v,u)對應的權重；

同時，假設ω(v,u_i)＝ω(v,u_j)(u_i∈A_i,u_j∈A_i)；因此，將邊e＝(v,u)的權重ω(v,u)定義為：

圖的轉移概率矩陣，用P來表示，則P中的元素p[v,u]表示從論文結點v到論文結點u的轉移概率，其可以使用如下公式進行計算：

其中c₀＝1，c是一個常數。

3.根據權利要求1所述的一種基于博弈論的增量式異構圖聚類方法，其特征在于：所述的步驟(3)中重新計算轉移概率矩陣具體為：

論文結點u到論文結點v在第y^th輪迭代中的轉移概率p^y[u,v]定義為：