[發明專利]基于MLkP/CR算法的無向圖分割方法

有效

• 申請號: 200910073338.9
• 申請日: 2009-12-03
• 公開（公告）號: CN101741611A
• 公開（公告）日: 2010-06-16
• 發明（設計）人: 何慧;張偉哲;張宏莉;楊志;王星;楊賢青
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 張宏威

技術領域

本發明涉及到網絡拓撲圖的可視化技術領域，具體涉及到網絡拓撲圖的劃 分。

背景技術

網絡拓撲圖對網絡管理有著巨大的作用，網絡管理大多都是以網絡拓撲圖 為操作核心的，即以圖形化的方式顯示網絡、路由器等網絡設備的邏輯連接關 系和其它信息，操作員可以在網絡拓撲中直接進行配置、性能、故障、計費、 安全等管理操作。

互聯網絡拓撲一般是由幾萬個路由器組成，即其對應的網絡拓撲圖點和邊 的個數多，連接關系復雜，在這種規模下要想直接對它進行平面化異常困難， 時空復雜度會非常高，效果也不會很好。要想使網絡拓撲圖清晰的顯示，要對 點合理的布局，使圖形中的點盡可能的布局均勻，邊交叉少。對于規模小的網 絡，由于點的個數少，拓撲結構簡單，我們可以很容易的對它布局。而對規模 很大的網絡，點和邊數量很大，拓撲結構復雜。因此，需要使其在利用其它可 視化技術進行顯示之前，根據其拓撲連接圖的特點，對其進行預處理-劃分優 化。

國內的研究工作主要是針對小規模網絡(局域網絡)進行可視化，這種網 絡規模對于平面可視化來說也是比較容易處理的，不需要進行拓撲的劃分優化 處理。國內外，尚未有針對這種互聯網的大規模的網絡拓撲圖進行可視化，更 沒有針對這一目的而進行邏輯拓撲圖劃分。另外，在已有的劃分技術中，沒有 考慮到劃分后的子圖的連通性。針對于互聯網絡的實際，網絡的連通性是一個 很重要的要素需要考慮，尤其是在分割劃分的時候。

現有的無向圖分割方法中，解決圖形分割問題經典算法是metis算法，它 先給圖一個隨機的初始劃分，然后對劃分結果逐步求精優化來達到圖形分割問 題的目標。

現有的Multilevel?k-way?Graph?Partitioning(MLkP)算法是一種基于metis思 想求解圖形分割問題算法，它不再采用傳統的二分法。二分法是先將一個圖分 成兩部分，這兩部分求精優化后，再分別把每一部分繼續分割成兩個部分后再 次求精優化，如此直到最后分解為k個部分。而MLkP則初始就將圖分割為k 個部分，然后在這k各部分之間對劃分結果求精優化。這樣就具有較高的速度， 而且適合于并行計算。

Kirk?Schloegel?and?George?Kargpis.Multilevel?k-way?Partitioning Scheme?for?Irregular?Graphs.Journal?of?Parallel?and?Distributed Computing(不規則圖形的多級k劃分策略).1998：45-60。

大規模無向圖平面可視化算法的第一個階段分解階段中，對圖劃分后的結 果必須滿足三個特性，其中前兩個特性是與圖形劃分問題相同的，但第三個特 性-自連通性是圖形劃分問題所沒有的，現有的無向圖分割方法中所采用的 MLkP算法和其他的metis算法都不能保證這一特性。

發明內容

為了解決現有無向圖分割方法中存在的不能夠保證圖形的自連通性的問 題，本發明提出一種基于MLkP/CR算法的無向圖分割方法。

基于MLkP/CR算法的無向圖分割方法，所述方法分為下述三個階段：

規約階段(Coarsening?Phase)：對待分割的無向圖G₀(V₀，E₀)進行規約，將 無向圖G₀(V₀，E₀)中的若干點合成一個點，規約成無向圖G_n(V_n，E_n)，降低拓撲圖 的規模，其中V₀是無向圖G₀中的頂點的集合，E₀是無向圖G₀中邊的集合， V_n是無向圖G_n中的頂點的集合，E_n是無向圖G_n中邊的集合；