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

有效

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

1.一種圖數據中最小K派系檢測方法，其特征在于，所述方法包括：

加載圖數據，所述圖數據中的各個頂點對應各自的頂點標識ID；

計算所述圖數據中各個頂點各自對應的鄰居頂點集合，所述鄰居頂點集合中包含頂點對應的鄰居頂點，且所述鄰居頂點的頂點ID大于所述頂點的頂點ID；

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

根據所述圖數據中各條邊上兩個頂點以及所述共同鄰居頂點，確定所述圖數據中的最小K派系；

其中，當所述圖數據為有向圖數據時，各個頂點對應的所述鄰居頂點集合包括入度鄰居頂點集合和出度鄰居頂點集合；

所述計算所述圖數據中各個頂點各自對應的鄰居頂點集合，包括：并行遍歷所述圖數據中的各個頂點；對于所述圖數據中的每個頂點，獲取所述頂點對應的候選入度鄰居頂點和候選出度鄰居頂點，所述候選入度鄰居頂點與所述頂點之間的有向邊指向所述頂點，所述頂點與所述候選出度鄰居頂點之間的有向邊指向所述候選出度鄰居頂點；若所述候選入度鄰居頂點的頂點ID小于所述頂點的頂點ID，則過濾所述候選入度鄰居頂點；若所述候選出度鄰居頂點的頂點ID小于所述頂點的頂點ID，則過濾所述候選出度鄰居頂點；根據過濾后的所述候選入度鄰居頂點生成所述頂點對應的所述入度鄰居頂點集合，并根據過濾后的所述候選出度鄰居頂點生成所述頂點對應的出度鄰居頂點集合。

2.根據權利要求1所述的方法，其特征在于，所述圖數據為無向圖數據；

所述計算所述圖數據中各個頂點各自對應的鄰居頂點集合，包括：

并行遍歷所述圖數據中的各個頂點；

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

若所述候選鄰居頂點的頂點ID小于所述頂點的頂點ID，則過濾所述候選鄰居頂點；

根據過濾后的所述候選鄰居頂點生成所述頂點對應的所述鄰居頂點集合。

3.根據權利要求2所述的方法，其特征在于，所述根據所述鄰居頂點集合，計算所述圖數據中各條邊上兩個頂點的共同鄰居頂點，包括：

并行遍歷所述圖數據中的各條無向邊；

對于所述圖數據中的每條無向邊，確定所述無向邊上的第一頂點和第二頂點；

獲取所述第一頂點對應的第一鄰居頂點集合，以及所述第二頂點對應的第二鄰居頂點集合；

計算所述第一鄰居頂點集合和所述第二鄰居頂點集合的交集，并將所述交集確定為所述第一頂點和所述第二頂點的所述共同鄰居頂點。

4.根據權利要求1所述的方法，其特征在于，所述根據所述鄰居頂點集合，計算所述圖數據中各條邊上兩個頂點的共同鄰居頂點，包括：

并行遍歷所述圖數據中的各條有向邊；

對于所述圖數據中的每條有向邊，獲取所述有向邊上的源頂點和目標頂點，所述有向邊由所述源頂點指向所述目標頂點；

獲取所述源頂點的入度鄰居頂點集合，以及所述目標頂點的出度鄰居頂點集合；

計算所述源頂點的入度鄰居頂點集合與所述目標頂點的出度鄰居頂點集合的交集，并將所述交集確定為所述源頂點和所述目標頂點的所述共同鄰居頂點。