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

在審

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

技術領域

本發明屬于網絡技術領域，尤其涉及一種大規模圖分割方法及系統。

背景技術

圖分割是指將圖的節點分成用戶指定數量的獨立群組，用于優化與切分邊相關的標準。

圖分割的方法主要集中于尋找復雜網絡中全局的社區結構，傳統算法的一個重要前提是需要知道整個圖的拓撲結構。但是，當圖的大小增長到大規模級別時，新的問題出現了，例如：(1)復雜網絡已經變成巨網絡，基于傳統的復雜網絡分析方法難以滿足需求；(2)圖的規模逐漸變大，將全部路徑計算一遍不現實；(3)大規模圖中節點數目眾多、變化頻繁，判斷一條邊是否處于足夠多條最短路徑十分耗費資源。

發明內容

鑒于此，本發明實施例提供一種大規模圖分割方法及系統，以解決現有技術存在的上述問題。

本發明實施例是這樣實現的，一種大規模圖分割方法，所述方法包括：

輸入大規模圖；

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

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

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

本發明實施例的另一目的在于提供一種大規模圖分割系統，所述系統包括：

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

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

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

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

本發明實施例與現有技術相比存在的有益效果是：本發明實施例通過計算節點之間的最短路徑，并隨機抽樣最短路徑，基于隨機抽樣的最短路徑對大規模圖進行分割，可有效解決現有大規模圖中節點數目眾多、變化頻繁，判斷一條邊是否處于足夠多條最短路徑十分耗費資源的問題。通過本發明實施例可有效提高大規模圖分割的效率，具有較強的易用性和實用性。

附圖說明

為了更清楚地說明本發明實施例中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發明的一些實施例，對于本領域普通技術人員來講，在不付出創造性勞動性的前提下，還可以根據這些附圖獲得其他的附圖。

圖1是本發明實施例一提供的大規模圖分割方法的實現流程圖；

圖2是本發明實施例二提供的大規模圖分割系統的組成結構圖。

具體實施方式

以下描述中，為了說明而不是為了限定，提出了諸如特定系統結構、技術之類的具體細節，以便透切理解本發明實施例。然而，本領域的技術人員應當清楚，在沒有這些具體細節的其它實施例中也可以實現本發明。在其它情況中，省略對眾所周知的系統、裝置、電路以及方法的詳細說明，以免不必要的細節妨礙本發明的描述。

為了說明本發明所述的技術方案，下面通過具體實施例來進行說明。

實施例一：

圖1示出了本發明實施例一提供的大規模圖分割方法的實現流程，該方法過程詳述如下：

在步驟S101中，輸入大規模圖。

在本發明實施例中，所述大規模圖是指節點數目眾多、變化頻繁的圖，例如節點數目超過5000，每隔一分鐘節點數目就會發生變化的圖。

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

其中，所述計算兩節點之間的最短路徑具體為：

設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}；

因此，D_{i,j,k}＝/mbox{min}(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})。其中，i、j、k為大于零的整數。

在實際應用中，為了節約空間，可以直接在原有空間上進行迭代，這樣空間可降至二維。將計算出來的最短路徑上的邊標記值加1，如果有邊同時處于多條由節點i到節點j的最短路徑，則該邊的標記值只增加1次。

在步驟S103中，對所述最短路徑進行隨機抽樣。