[發明專利]圖數據強連通分量挖掘方法、裝置、設備及存儲介質

在審

• 申請號: 202110584276.9
• 申請日: 2021-05-27
• 公開（公告）號: CN113761293A
• 公開（公告）日: 2021-12-07
• 發明（設計）人: 李曉森;蔣杰;高世成;歐陽文;肖品;陶陽宇;崔斌
• 申請（專利權）人: 騰訊科技（深圳）有限公司;北京大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/9035
• 代理公司: 廣州嘉權專利商標事務所有限公司 44205
• 代理人: 譚英強;黎揚鵬

本申請公開了一種圖數據強連通分量挖掘方法、裝置、設備及存儲介質，該方法獲取包括多個節點的有向圖；然后將有向圖劃分為多個區塊圖，對各個區塊圖中節點的第一標簽進行異步的標簽傳播更新，從而大大加快第一標簽迭代的速度，并在有向圖的全部節點的第一標簽更新完成后，將更新前后對應的第一標簽相同的節點作為第一子節點，可確定出該有向圖中和第一子節點屬于同一強連通分量的節點；該方法通過異步的標簽傳播更新，能夠加速第一標簽的更新速度，從而減少標簽傳播過程中所需要的迭代次數，有效提高強連通分量挖掘的效率，有利于減少計算資源的消耗。本申請可廣泛應用于大數據技術領域。

技術領域

本申請涉及大數據技術領域，尤其是一種圖數據強連通分量挖掘方法、裝置、設備及存儲介質。

背景技術

圖作為一種數據結構，廣泛存在于自然科學以及社會科學的各個領域。例如，圖中各個節點的連通性問題，在電信電力網絡、運輸系統、計算機程序設計、故障診斷、人工智能、印刷電路板設計、用戶分析等場景中經常被考慮、分析和應用到。

當前，針對節點連通性問題的研究包括挖掘有向圖中的強連通分量的任務。相關技術中采用的挖掘算法，單機執行時受到圖數據的數據量限制，難以適應大規模的圖數據需求；而采用分布式挖掘的算法，往往需要迭代的次數過多，需要耗費大量的硬件資源。綜上，相關技術中采用的圖數據強連通分量挖掘方式實用性不高，挖掘的效果往往不太理想。

發明內容

本申請的目的在于至少一定程度上解決現有技術中存在的技術問題之一。

為此，本申請實施例的一個目的在于提供一種圖數據強連通分量挖掘方法，該方法能夠提高強連通分量挖掘的效率，有利于減少計算資源的消耗。

為了達到上述技術目的，本申請實施例中所采取的技術方案包括：

一方面，本申請實施例提供一種圖數據強連通分量挖掘方法，該方法包括以下步驟：

獲取有向圖；所述有向圖中包括多個節點，各個所述節點對應有第一標簽，所述第一標簽包括第一入度屬性值和第一出度屬性值；不同的所述節點對應的所述第一入度屬性值不同，不同的所述節點對應的所述第一出度屬性值不同；

將所述有向圖劃分為多個區塊圖；

對所述有向圖中各個節點的所述第一標簽進行存儲，根據存儲的所述第一標簽對各個所述區塊圖中節點的所述第一標簽進行異步的標簽傳播更新，并根據所述標簽傳播更新的結果更新存儲的所述第一標簽；

當所述有向圖中全部節點更新完成后，確定與第一子節點攜帶有相同第一標簽的節點屬于同一強連通分量；所述第一子節點為更新前后對應的第一標簽相同的節點。

另一方面，本申請實施例提供一種圖數據強連通分量挖掘裝置，該裝置包括：

獲取模塊，用于獲取有向圖；所述有向圖中包括多個節點，各個所述節點對應有第一標簽，所述第一標簽包括第一入度屬性值和第一出度屬性值；不同的所述節點對應的所述第一入度屬性值不同，不同的所述節點對應的所述第一出度屬性值不同；

劃分模塊，用于將所述有向圖劃分為多個區塊圖；

存儲與更新模塊，用于對所述有向圖中各個節點的所述第一標簽進行存儲，根據存儲的所述第一標簽對各個所述區塊圖中節點的所述第一標簽進行異步的標簽傳播更新，并根據所述標簽傳播更新的結果更新存儲的所述第一標簽；

處理模塊，用于當所述有向圖中全部節點更新完成后，確定與第一子節點攜帶有相同第一標簽的節點屬于同一強連通分量；所述第一子節點為更新前后對應的第一標簽相同的節點。

可選地，在一些實施例中，所述裝置還包括：