[發明專利]一種結構聚類的生成方法及系統

有效

• 申請號: 201710232898.9
• 申請日: 2017-04-11
• 公開（公告）號: CN107103333B
• 公開（公告）日: 2020-06-30
• 發明（設計）人: 陳亞中;李榮華;代強強;李振軍;張偉鵬
• 申請（專利權）人: 深圳大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 深圳市恒申知識產權事務所(普通合伙) 44312
• 代理人: 王利彬

1.一種結構聚類的生成方法，其特征在于，所述方法采用基于openMP多核框架的方法，實現計算結構相似性的并行算法，所述方法包括：

接收待處理的無向無權簡單圖，遍歷所述無向無權簡單圖得到所有未處理的節點；

按照結構相似性并行算法判斷當前未處理的節點是否為核心節點，若否，則判斷下一未處理的節點是否為核心節點；

若是，則生成新的聚類并編號，并將所述當前未處理的節點的所有未處理且直接可達的鄰居插入預置隊列；

判斷所述預置隊列是否為空，若為空，則執行所述按照結構相似性并行算法判斷當前未處理的節點是否為核心節點的步驟；

若不為空，則彈出所述預置隊列的隊首元素，將所述隊首元素劃分至所述新的聚類，并將所述隊首元素的所有可達且未處理的鄰居插入所述預置隊列中；

判斷所述無向無權簡單圖中是否存在未處理的節點，若存在，則執行所述按照結構相似性并行算法判斷當前未處理的節點是否為核心節點的步驟，若不存在，則結束算法，得到目標聚類；

其中，在確定當前未處理的節點是否為核心節點時，使用基于節點度的負載均衡策略，或者基于切片的負載均衡策略，其中，所述基于節點度的負載均衡策略是指將整張圖的邊的度之和按照處理器的核的數量分成了p等份，分給p個核的每塊里面所有邊的度的和是相同的，所述基于切片的負載均衡策略是指將所述無向無權簡單圖中所有的邊的集合分成等份的切片，切片大小在1000萬到5000萬之間，切片大小是指邊的條數。

2.如權利要求1所述的生成方法，其特征在于，分別以u和v表示所述無向無權簡單圖中的任意一條邊的兩個端點，則所述按照結構相似性并行算法判斷當前未處理的節點是否為核心節點包括：

分別獲取u和v按照其鄰居的節點編號排序的鄰接鏈表及鄰居節點；

分別以u和v的鄰居節點的個數表示u和v的節點度數，計算u和v的節點度數之和，并以計算得到的節點度數之和表示以u和v為兩個端點的邊的度數；

計算得到所述無向無權簡單圖中所有邊的度數和，將所述所有邊的度數和按照預置等分點平均分成若干計算任務塊，每一計算任務塊對應每一計算進程，每一所述計算進程用于遍歷每一條邊的兩個端點的鄰接鏈表，以獲取每一條邊的兩個端點的共同鄰居的個數；

獲取所有計算進程的編號，根據計算進程的編號分配計算任務塊，以使所述計算進程根據所述計算任務塊計算得到每一條邊的兩個端點的共同鄰居的個數；

計算每一條邊的兩個端點的結構相似性，其中，以Γ(v)表示v的鄰居節點的個數，以Γ(u)表示u的鄰居節點的個數，以σ(u,v)表示以u和v為端點的邊的兩個端點的結構相似性，

則：|Γ(v)∩Γ(u)|表示v和u的共同鄰居的個數，表示v和u的鄰居個數乘積的開方；

判斷計算得出的結構相似性的值是否滿足預置的結構相似性閾值，若滿足，則獲取節點v中結構相似性大于預置的結構相似性閾值的鄰居個數；

若節點v大于預置的結構相似性閾值的鄰居個數大于等于預置鄰居個數值時，則判斷v為核心節點。

3.如權利要求1所述的生成方法，其特征在于，分別以u和v表示所述無向無權簡單圖中的任意一條邊的兩個端點，則所述按照結構相似性并行算法判斷當前未處理的節點是否為核心節點包括：

獲取所述無向無權簡單圖的所有的邊，得到邊集合；

按照預置切片大小將所述邊集合分成等份的若干切片；

將切片分配給所有計算進程，以使所述計算進程計算所述切片內所有邊的結構相似性；

判斷計算得出的結構相似性的值是否滿足預置的結構相似性閾值，若滿足，則獲取節點v中結構相似性大于預置的結構相似性閾值的鄰居個數；

若節點v大于預置的結構相似性閾值的鄰居個數大于等于預置鄰居個數值時，則判斷v為核心節點。