一種基于網絡圖的計算機算法研究

敖卓緬

（陽江職業技術學院 廣東省陽江市 529566）

分層結構網絡圖，一種基于網絡圖的計算機算法，它由時間差層組成，算法中運用一個名為“NeL2”的工具來處理分層結構網絡圖。分層結構網絡圖具有多個累積層，不是單一的網絡圖，利用這種分層結構，時間差可以包含在一幅圖中。此外，各種類型的信息，例如圖表在特定時間段內的總體趨勢，都可以可視化顯示；再如利用分層結構的網絡圖來表示學術文獻的合著網絡，使用分層結構網絡圖就可以看到合著網絡中的變化，閱讀各種信息，比如活躍研究群體的變化和其他現象。除了合著網絡外，分層結構網絡圖還可以應用于各種數據的可視化，如思想處理器、網站變更等。

1 分層結構的網絡圖

網絡圖表示具有網絡形式的數據，例如組織結構、計算機網絡或學術文獻的合著者。為了便于理解，經常要將這些數據可視化，這些可視化的網絡圖表示網絡在某個時間點的狀態（快照）。因此，為了確定一段時間內的“變化（差異）”，必須安排和比較幾個快照，例如從去年到現在網絡狀態的變化，或者過去十年網絡狀態的變化等。此外，當使用只顯示一個網絡圖的工具時，如果要仔細查看網絡變化時，用戶必須創建與快照的差異。分層結構的網絡圖就是把一個網絡的演化看作是一系列的差異，再將差異序列表示為一個分層結構。為了處理此類圖，創建開發一個名為“NeL2”的工具，它用Java（jdk5.0）顯示和操作分層結構化網絡圖，其表達方法不是把一個網絡圖看作一個圖形，而是把它看作幾個層次的積累。舉例來說，如果要參考過去一年網絡的變化，所要觀察的只是表示“去年數據”的圖層，而要查看過去十年的變化，可以看到過去十年的變化堆積和圖層。以同樣的方式，堆積所有層可以讓用戶了解網絡的當前狀態。使用分層結構，可以有效地處理網絡的差異。分層結構網絡圖算法研究如何從數學上定義分層結構網絡，并解釋工具“NeL2”，并以學術文獻的合著網絡為例，給出分層結構的網絡圖。此外，也假設其他類型的應用程序[1]。

2 網絡圖的分層表達

先引入一種分層結構來表達隨時間變化的網絡圖。網絡數據作為多個層單獨管理，而不是作為一個單一的圖表，每一層都取決于更新時間。網絡圖以靈活的方式顯示數據并對其進行著色，這種方法可以幫助用戶從網絡圖中讀取大量信息[2]。

2.1 分層結構的概念

分層結構網絡圖算法研究處理的網絡圖具有分層結構的概念。這種結構類似于透明膠片（如OHP 片材），特定時間的更新保存在單個圖紙（圖層）上，在下一階段完成的后續更新通過在現有圖層上堆積新圖層來保存。每次更新的更改都保存在每個圖層上。使用分層結構可以實現以下操作：可以通過在某些點之間堆疊所有層來查看網絡圖，可以追蹤網絡的變化；當堆疊圖層時，可以按時間順序從過去追蹤到未來；當按順序移除圖層時，可以按時間順序從未來追蹤到過去?？梢酝ㄟ^單獨閱讀可選層，看到網絡在這一層上的變化。通過多層疊加，可以看到網絡在一定時期內的變化[3]。

圖1：XML 中分層結構網絡數據的描述實例

圖2：滑塊

2.2 使用分層結構的優點

使用分層結構的網絡圖有如下優點：

（1）當使用分層結構時，只需要一個網絡圖。以前，必須排列和比較多個圖表，以查看網絡中的差異。分層結構可以在一個網絡圖中表達這些變化，因為網絡數據是由層與層之間信息的“差異集合”組成的，分層結構的網絡可視化方法顯示的是各種網絡數據的差異。另一方面，“NeL2”在數據級別確定差異表達式，并通過集成這些差異來表示所有數據，該方法適用于網絡演化的可視化。

（2）分層結構使網絡圖的操作更易于理解和直觀。計算機應用通常執行與分層結構類似的操作，例如“從文檔（論文）堆棧中提取第10-16 頁”，在分層結構的網絡圖中也可以用同樣的方法執行這些操作。

（3）分層結構有助于用戶輕松掌握網絡的特點。因為所有元素都同時顯示在一個圖中，用戶可以在劃分為層的網絡圖中看到隨時間的變化。通過引入分層結構，用戶還可以改變每一層節點和邊緣的表示[4]。

2.3 網絡數據格式

由于原始的XML 文檔數據格式沒有層的概念，如果用其來描述表示網絡圖的數據，就不能實現分層結構網絡圖要有效處理網絡差異的要求。因此，要設計一種新的數據格式來表達圖層信息，即具有分層結構的網絡數據——層元素，其定義格式為（ID，node，edge，label，position，from，to）。我們用原始XML 文檔格式描述了表示網絡圖的數據。與我們的技術不同，現有網絡可視化技術使用的數據格式沒有層的概念。因此，我們設計了一種新的數據格式來表達圖層信息。具有分層結構的網絡數據示例如圖1所示。

因為每次添加層時網絡圖都會更新，所以層元素有一個ID 來表示更新日期。層元素中的節點元素（node），其表示一個節點，對應于數學定義中的v∈N。節點元素有兩個屬性：節點ID 和節點所屬層的ID。層元素還包括邊元素edge、label 元素和position 元素，其中邊元素定義連接兩個節點的邊，它對應于數學定義中的e∈e，邊元素也有兩個屬性：邊ID 和邊所屬層的ID；label 元素和position 元素分別表示節點的標簽和位置（x，y）坐標。層元素還有from 元素和to 元素，分別表示兩端連接的節點，網絡圖更新時，節點或邊可以根據實際情況增減。在這種情況下，將添加節點事件或邊緣事件元素，而不是修改與已刪除元素對應的節點或邊緣元素。這些元素分別對應于數學定義中的N-和E-元素。節點和邊的操作記錄在這些元素上。當工具繪制圖形時，這些元素會覆蓋節點和邊本身。使用這個數據格式的優點是，即使刪除節點或邊，也可以保存過去的狀態。數據在操作系統加載后的狀態下，無論它們屬于哪一層，XML 文檔、所有節點和邊都是可見的?？梢栽O計滑塊來改變“NeL2”工具中的界面可見層，這樣用戶可以直觀地操作網絡圖?？稍谠O計中準備三個滑塊，右邊的兩個滑塊指定了可見層的范圍，分別表示高層和低層的范圍，用戶可以使用左側的滑塊指定關注的層（關鍵層），網絡圖能夠高亮顯示指定關鍵層的節點和邊（圖2）[5]。

該工具左邊滑塊所示的關鍵層，加載數據之后自動生成，而且，所有的圖層都是可見的，右邊的兩個滑塊分別表示最新和最舊的圖層數據。當要查看以某個網絡演化為基礎節點的網絡圖時，可以在頂部、右側和底部看到相對較大的集群。但是，從網絡視圖中無法了解哪個集群是活動的，或者它什么時候是活動的。因此，需要操作兩個右滑塊，并由用戶定義限制可見層。如通過操作左滑塊將關鍵層設置為較低數值，表示不需要復雜的操作，只要簡單的解釋就可以自然地使用，可以看到修改指示的結果為節點連接到屬于頂部集群的節點，而不是連接到底部集群的節點。當將關鍵層設置為很高數值時，位于左側下方的許多節點被高亮顯示，表明與最高群體對應的群體密切合作，而它與代表最低群體的群體的聯系相對較遠，在這一時期，與左下方的這個集群相對應的社區非?；钴S[5]。

利用此工具使比較關鍵層和其它層變得容易?？梢暬现W絡的應用分層結構的網絡圖可以應用于此類情況，如可視化科學文獻的合著網絡[6]，科研合著網絡的可視化，了解合著網絡的這些變化有助于解釋不斷變化的環境、研究人員或研究領域內的趨勢，以及其它狀況的演化。通常合著是用數學方法定量分析的，然而，為了理解網絡數據中的趨勢，用直觀的圖表推測比用數學公式推測更為方便，有助于分析。分層結構網絡圖在這種情況下變得很有用[7]。

因此，分層結構的概念的引入有助于用戶更容易地改變網絡圖的視圖，并且可以假定合著網絡的特征。其它應用實例分層結構化網絡圖也可以應用于各種數據的可視化，如網站的變化由于博客和相關工具的傳播，擁有個人網站的人數正在迅速增加，這些網站每天都會被創建、修改或刪除，分層結構網絡圖就可以在很好應用在這些場合。通過定期在圖層上保存網站的更改，用戶可以方便地檢查任何時期的網站狀態，或者如何加強或削弱網站之間的關系。利用可視化調試器的管理變更日志，將每次調試器使用數據流圖保存為快照，并根據它們進行差異，使用“NeL2”工具，可以把差異指示程度通過指定特定層來實現[8]。

3 處理器

創意處理器是一類幫助重新排列思想和文檔的軟件。一些工具將想法標記為標簽或節點，重新排列并在它們之間建立關系（用線連接它們）。當標簽被視為節點，關系被視為邊時，可以制作成一個層次結構網絡圖。將層次結構網絡圖用于idea 處理器的一些功能，如保存和播放，用戶可以很容易地理解創意（ideas）的設計或修改。用戶還可以看到創意的演變，因為它們是使用分層結構按時間順序保存的。通過將這種過去的記錄管理引入到idea 處理器中，可以很容易地遵循創意的安排和發展。

4 結束語

本文提出了網絡圖分層結構的概念，并給出了數學上的定義。使用層作為單位來表示網絡隨時間的變化，利用創建開發的“NeL2”的工具，用于處理分層結構化網絡圖。此外，它還提供自然操作，以便獲得預期的圖表。利用分層結構的網絡圖，可以掌握網絡中的各種信息，如演化趨勢和過程。采用分層結構，將合作作者網絡的變化形象化，社區的形成和活動的活躍程度得到了明確的體現。