[發明專利]圖數據中最小K派系檢測方法、裝置及設備

有效

• 申請號: 201710903872.2
• 申請日: 2017-09-29
• 公開（公告）號: CN107729430B
• 公開（公告）日: 2020-03-10
• 發明（設計）人: 曹莉;呂倩楠;劉秀敏
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 北京三高永信知識產權代理有限責任公司 11138
• 代理人: 黎雷

本申請提供了一種圖數據中最小K派系檢測方法、裝置及設備，涉及數據挖掘領域，所述方法包括：加載圖數據，所述圖數據中的各個頂點對應各自的頂點ID；計算圖數據中各個頂點各自對應的鄰居頂點集合，鄰居頂點集合中包含頂點對應的鄰居頂點，且鄰居頂點的頂點ID大于該頂點的頂點ID；根據鄰居頂點集合，計算圖數據中各條邊上兩個頂點的共同鄰居頂點；根據圖數據中各條邊上兩個頂點以及共同鄰居頂點，確定圖數據中的最小K派系。本申請基于極大值原則，僅保留頂點ID大于自身頂點ID的鄰居頂點，相較于相關技術中鄰居頂點集合的計算方式，其中間數據量縮小至一半，從而減少后續的無用計算，降低了計算量，提高了計算效率。

技術領域

本申請涉及數據挖掘領域，特別涉及一種圖數據中最小K派系檢測方法、裝置及設備。

背景技術

圖數據挖掘(又稱為圖計算(graph compute))作為大數據時代下一種常見的數據挖掘方式，被廣泛應用于社團結構挖掘、邊聚集系數計算、頂點親密度計算和頂點相似度計算等領域。

進行圖數據挖掘時，待挖掘的數據以圖數據的形式存儲，其中，圖數據中采用頂點(vertex)存儲頂點值，采用邊(edge)表示頂點之間的關系，且通過一條邊相連的兩個頂點互為鄰居頂點。在圖數據中，任意兩個頂點都相連的頂點集合被稱為派系(clique)，而3派系(3-clique)則被稱為最小K派系。在進行圖數據挖掘時，最小K派系檢測(即檢測圖數據中的3-clique)是最基礎的檢測算法。

相關技術中，對圖數據進行最小K派系檢測時，首先需要計算圖數據中每個頂點的鄰居頂點集合，然后通過頂點消息傳遞的方式計算每個頂點與其鄰居頂點的共同鄰居頂點，從而確定出由三個頂點構成的三角形(即最小K派系)，進而對構成的三角形進行去重，最終確定出圖數據中的最小K派系。

然而，采用上述方法進行最小K派系檢測時，由于計算過程中中間數據膨脹率較高，在原始數據量較大的情況下計算量過大，影響計算效率，甚至導致無法完成計算。

發明內容

本申請的實施例提供了一種圖數據中最小K派系檢測方法、裝置及設備，可以解決進行最小K派系檢測過程中，由于計算過程中中間數據膨脹率較高，在原始數據量較大的情況下計算量過大，影響計算效率，甚至導致無法完成計算的問題。

第一方面，提供了一種圖數據中最小K派系檢測方法，該方法包括：

圖數據處理設備加載圖數據，圖數據中的各個頂點對應各自的頂點標識(Identity，ID)；

圖數據處理設備計算圖數據中各個頂點各自對應的鄰居頂點集合，鄰居頂點集合中包含頂點對應的鄰居頂點，且鄰居頂點的頂點ID大于該頂點的頂點ID；

圖數據處理設備根據鄰居頂點集合，計算圖數據中各條邊上兩個頂點的共同鄰居頂點；

圖數據處理設備根據圖數據中各條邊上兩個頂點以及共同鄰居頂點，確定圖數據中的最小K派系。

本申請實施例提供的方法中，在計算圖數據中各個頂點的鄰居頂點集合時，圖數據處理設備基于極大值原則，將頂點ID小于自身頂點ID的鄰居頂點過濾，僅保留頂點ID大于自身頂點ID的鄰居頂點，相較于相關技術中鄰居頂點集合的計算方式，其中間數據量縮小至一半，從而減少后續的無用計算，降低了計算量，提高了計算效率；同時，采用上述方法能夠有效過濾各個頂點形成最小K派系的重復結果，避免進行額外的去重處理。

在一種可能的實現方案中，圖數據為無向圖數據；

圖數據處理設備計算圖數據中各個頂點各自對應的鄰居頂點集合，包括：

圖數據處理設備并行遍歷圖數據中的各個頂點；

對于圖數據中的每個頂點，圖數據處理設備獲取頂點對應的候選鄰居頂點，候選鄰居頂點與頂點之間通過無向邊直接相連；