[發明專利]一種大規模圖分割方法及系統

在審

• 申請號: 201510047749.6
• 申請日: 2015-01-29
• 公開（公告）號: CN104598927A
• 公開（公告）日: 2015-05-06
• 發明（設計）人: 劉志超;李紅娜;寧立;張涌
• 申請（專利權）人: 中國科學院深圳先進技術研究院
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 深圳中一專利商標事務所 44237
• 代理人: 張全文

1.一種大規模圖分割方法，其特征在于，所述方法包括：

輸入大規模圖；

計算所述大規模圖中各節點之間的最短路徑，并對各節點之間的邊設置標記值；

對所述最短路徑進行隨機抽樣；

基于隨機抽樣的最短路徑對所述大規模圖進行分割，若分割后存在節點之間的邊的標記值大于預設參數值，則刪除該邊。

2.如權利要求1所述的方法，其特征在于，所述基于隨機抽樣的最短路徑對所述大規模圖進行分割，若分割后存在節點之間的邊的標記值大于預設參數值，則刪除該邊包括：

步驟1：設置參數值m，所述m為大于零的整數；

步驟2：將各邊的標記值初始化為零；

步驟3：從所述大規模圖中隨機選擇兩節點，并將所述兩節點間的所有最短路徑上的邊的標記值加1；

步驟4：如果存在某條邊的標記值大于m，則刪除該邊；

步驟5：判斷該邊刪除后，所述大規模圖是否連通，若連通，則返回步驟3；若刪除該邊后存在多個獨立子圖，則對于大于預設規模的獨立子圖，遞歸執行步驟1、2、3、4和5；對于小于或等于預設規模的獨立子圖，將該獨立子圖上的節點作為所述大規模圖分割后的一個子集，并輸出該子集。

3.如權利要求1所述的方法，其特征在于，所述計算兩節點之間的最短路徑具體為：

設D_{i,j,k}為從節點i到節點j的只以(1,…,K)集合中的節點為中間節點的最短路徑的長度；

若最短路徑經過節點k，則D_{i,j,k}＝D_{i,k,k-1}+D_{k,j,k-1}；

若最短路徑不經過節點k，則D_{i,j,k}＝D_{i,j,k-1}；

其中，i、j、k為大于零的整數。

4.一種大規模圖分割系統，其特征在于，所述系統包括：

大規模圖輸入單元，用于輸入大規模圖；

計算單元，用于計算所述大規模圖中各節點之間的最短路徑，并對各節點之間的邊設置標記值；

隨機抽樣單元，用于對所述最短路徑進行隨機抽樣；

處理單元，用于基于隨機抽樣的最短路徑對所述大規模圖進行分割，若分割后存在節點之間的邊的標記值大于預設參數值，則刪除該邊。

5.如權利要求4所述的系統，其特征在于，所述處理單元包括：

設置模塊，用于設置參數值m，所述m為大于零的整數；

初始化模塊，用于將各邊的標記值初始化為零；

第一處理模塊，用于從所述大規模圖中隨機選擇兩節點，并將所述兩節點間的所有最短路徑上的邊的標記值加1；

第二處理模塊，用于如果存在某條邊的標記值大于m，則刪除該邊；

第三處理模塊，用于判斷該邊刪除后，所述大規模圖是否連通，若連通，則返回第一處理模塊繼續執行；若刪除該邊后存在多個獨立子圖，則對于大于預設規模的獨立子圖，遞歸執行設置模塊、初始化模塊、第一處理模塊、第二處理模塊以及第三處理模塊；對于小于或等于預設規模的獨立子圖，將該獨立子圖上的節點作為所述大規模圖分割后的一個子集。

6.如權利要求4所述的系統，其特征在于，所述計算單元具體用于：

設D_{i,j,k}為從節點i到節點j的只以(1,…,K)集合中的節點為中間節點的最短路徑的長度；

若最短路徑經過節點k，則D_{i,j,k}＝D_{i,k,k-1}+D_{k,j,k-1}；

若最短路徑不經過節點k，則D_{i,j,k}＝D_{i,j,k-1}；

其中，i、j、k為大于零的整數。