[發明專利]一種輕量級的高效圖頂點重排方法

在審

• 申請號: 202011134445.0
• 申請日: 2020-10-21
• 公開（公告）號: CN112380397A
• 公開（公告）日: 2021-02-19
• 發明（設計）人: 劉志丹;黃保福;伍楷舜
• 申請（專利權）人: 深圳大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F17/16
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 張金福

1.一種輕量級的高效圖頂點重排方法，其特征在于，所述方法包括以下步驟：

S1：加載需進行ID重排的圖，并進行預處理，確定種子點；

S2：選擇種子點，并通過種子點生成超頂點；

S3：根據超頂點為需進行ID重排的圖的頂點分配新ID，從而實現圖頂點重排。

2.根據權利要求1所述輕量級的高效圖頂點重排方法，其特征在于，S1包括以下步驟：

S1.1：加載需要進行ID重排的圖G＝(V，E)，V表示圖的頂點集，E表示圖的邊集，|V|、|E|分別表示頂點數目與邊數目；

然后存儲整圖信息，根據頂點的入度設置該頂點的標志位is_trivial，入度大于給定閾值λ則設置is_trivial＝true，否則設置is_trivial＝false；

S1.2：設定重排規則，并選定種子點。

3.根據權利要求2所述輕量級的高效圖頂點重排方法，其特征在于，存儲整圖信息采用壓縮稀疏行的方式進行存儲。

4.根據權利要求3所述輕量級的高效圖頂點重排方法，其特征在于，S1.2具體為：設定從需要進行ID重排的圖G的原ID最小的頂點開始進行ID重排，選定種子點seed，其中，原ID最小的頂點為初始種子點。

5.根據權利要求1-4任一項所述輕量級的高效圖頂點重排方法，其特征在于，S2具體為：

以種子點seed為中心，將其k跳內的低入度且還未分配新ID的頂點合并成超頂點H。

6.根據權利要求5所述輕量級的高效圖頂點重排方法，其特征在于，超頂點的生成包括：

S2.1：初始化需進行ID重排的圖的所有頂點ID分配標志位assigned＝false，置所有頂點新ID為Φ(*)＝-1，種子點seed＝-1，設輔助變量move_id＝1，表示當前可分配的新ID；輔助變量v＝-1，表示當前可參與分配的頂點原ID；

S2.2：通過超頂點生成函數Fusion(seed)得到超頂點H。

7.根據權利要求6所述輕量級的高效圖頂點重排方法，其特征在于，S2.2包括以下步驟：

S2.2.1：輸入種子點seed，設置超頂點H＝{seed}；

S2.2.2：其中，N_Hv表示H的鄰居頂點集，檢查頂點u的標志位is_trivial，標志位is_trivial為false則跳過對該頂點的進一步操作，標志位is_trivial為true則執行S2.2.3；

S2.2.3：檢查頂點u的分配標志位assigned，分配標志位assigned為true則跳過對該頂點的進一步操作，分配標志位assigned為false則將該點添加至H中；

S2.2.4：逐個對其他相連出邊鄰居重復S2.2.1-S2.2.3，合并所有未分配鄰居頂點后，合并跳數加一；

S2.2.5：對H中新添的頂點重復執行S2.2.1-S2.2.4，直至跳數hop達到給定的合并跳數k，將種子點k跳內的低入度頂點合并入H后輸出。

8.根據權利要求7所述輕量級的高效圖頂點重排方法，其特征在于，S3包括以下步驟：

S3.1：先為S2生成的超頂點H分配連續ID，再為超頂點H的鄰居頂點分配新ID；更新以上已獲得新ID的頂點的分配標志位assigned＝true；

S3.2：從超頂點H的鄰居頂點中選擇一個頂點當成種子點seed，當種子點seed的某個連通分量的頂點全部獲得新ID后，選擇剩余連通分量中原ID最小的頂點當成種子點seed，執行S2，直至所有頂點均獲得唯一的新ID。

9.根據權利要求8所述輕量級的高效圖頂點重排方法，其特征在于，為超頂點H的鄰居頂點分配新ID的分配規則為：首先為高入度鄰居頂點分配連續ID，再為低入度鄰居頂點分配連續ID。

10.根據權利要求1或9任一項所述輕量級的高效圖頂點重排方法，其特征在于，種子點的選定方法如下：

(1)當需進行ID重排的圖的連通分量還有未分配新ID的頂點時，選擇已經分配新ID的頂點的一個未分配ID的頂點當成種子點；

(2)當需進行ID重排的圖的連通分量所有頂點均獲得了新ID，從剩下的、未進行ID分配的連通分量中選擇一個頂點當成種子點；

(3)以上(1)、(2)符合要求的頂點若有多個，則選擇原ID相對最小的頂點當成種子點；

(4)初始種子點的選取是根據以上的(2)進行的。