一種基于網(wǎng)絡(luò)圖的計(jì)算機(jī)算法研究

敖卓緬

（陽江職業(yè)技術(shù)學(xué)院 廣東省陽江市 529566）

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

1 分層結(jié)構(gòu)的網(wǎng)絡(luò)圖

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

2 網(wǎng)絡(luò)圖的分層表達(dá)

先引入一種分層結(jié)構(gòu)來表達(dá)隨時(shí)間變化的網(wǎng)絡(luò)圖。網(wǎng)絡(luò)數(shù)據(jù)作為多個(gè)層單獨(dú)管理，而不是作為一個(gè)單一的圖表，每一層都取決于更新時(shí)間。網(wǎng)絡(luò)圖以靈活的方式顯示數(shù)據(jù)并對其進(jìn)行著色，這種方法可以幫助用戶從網(wǎng)絡(luò)圖中讀取大量信息[2]。

2.1 分層結(jié)構(gòu)的概念

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

圖1：XML 中分層結(jié)構(gòu)網(wǎng)絡(luò)數(shù)據(jù)的描述實(shí)例

圖2：滑塊

2.2 使用分層結(jié)構(gòu)的優(yōu)點(diǎn)

使用分層結(jié)構(gòu)的網(wǎng)絡(luò)圖有如下優(yōu)點(diǎn)：

（1）當(dāng)使用分層結(jié)構(gòu)時(shí)，只需要一個(gè)網(wǎng)絡(luò)圖。以前，必須排列和比較多個(gè)圖表，以查看網(wǎng)絡(luò)中的差異。分層結(jié)構(gòu)可以在一個(gè)網(wǎng)絡(luò)圖中表達(dá)這些變化，因?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)是由層與層之間信息的“差異集合”組成的，分層結(jié)構(gòu)的網(wǎng)絡(luò)可視化方法顯示的是各種網(wǎng)絡(luò)數(shù)據(jù)的差異。另一方面，“NeL2”在數(shù)據(jù)級別確定差異表達(dá)式，并通過集成這些差異來表示所有數(shù)據(jù)，該方法適用于網(wǎng)絡(luò)演化的可視化。

（2）分層結(jié)構(gòu)使網(wǎng)絡(luò)圖的操作更易于理解和直觀。計(jì)算機(jī)應(yīng)用通常執(zhí)行與分層結(jié)構(gòu)類似的操作，例如“從文檔（論文）堆棧中提取第10-16 頁”，在分層結(jié)構(gòu)的網(wǎng)絡(luò)圖中也可以用同樣的方法執(zhí)行這些操作。

（3）分層結(jié)構(gòu)有助于用戶輕松掌握網(wǎng)絡(luò)的特點(diǎn)。因?yàn)樗性囟纪瑫r(shí)顯示在一個(gè)圖中，用戶可以在劃分為層的網(wǎng)絡(luò)圖中看到隨時(shí)間的變化。通過引入分層結(jié)構(gòu)，用戶還可以改變每一層節(jié)點(diǎn)和邊緣的表示[4]。

2.3 網(wǎng)絡(luò)數(shù)據(jù)格式

由于原始的XML 文檔數(shù)據(jù)格式?jīng)]有層的概念，如果用其來描述表示網(wǎng)絡(luò)圖的數(shù)據(jù)，就不能實(shí)現(xiàn)分層結(jié)構(gòu)網(wǎng)絡(luò)圖要有效處理網(wǎng)絡(luò)差異的要求。因此，要設(shè)計(jì)一種新的數(shù)據(jù)格式來表達(dá)圖層信息，即具有分層結(jié)構(gòu)的網(wǎng)絡(luò)數(shù)據(jù)——層元素，其定義格式為（ID，node，edge，label，position，from，to）。我們用原始XML 文檔格式描述了表示網(wǎng)絡(luò)圖的數(shù)據(jù)。與我們的技術(shù)不同，現(xiàn)有網(wǎng)絡(luò)可視化技術(shù)使用的數(shù)據(jù)格式?jīng)]有層的概念。因此，我們設(shè)計(jì)了一種新的數(shù)據(jù)格式來表達(dá)圖層信息。具有分層結(jié)構(gòu)的網(wǎng)絡(luò)數(shù)據(jù)示例如圖1所示。

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

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

利用此工具使比較關(guān)鍵層和其它層變得容易?？梢暬现W(wǎng)絡(luò)的應(yīng)用分層結(jié)構(gòu)的網(wǎng)絡(luò)圖可以應(yīng)用于此類情況，如可視化科學(xué)文獻(xiàn)的合著網(wǎng)絡(luò)[6]，科研合著網(wǎng)絡(luò)的可視化，了解合著網(wǎng)絡(luò)的這些變化有助于解釋不斷變化的環(huán)境、研究人員或研究領(lǐng)域內(nèi)的趨勢，以及其它狀況的演化。通常合著是用數(shù)學(xué)方法定量分析的，然而，為了理解網(wǎng)絡(luò)數(shù)據(jù)中的趨勢，用直觀的圖表推測比用數(shù)學(xué)公式推測更為方便，有助于分析。分層結(jié)構(gòu)網(wǎng)絡(luò)圖在這種情況下變得很有用[7]。

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

3 處理器

創(chuàng)意處理器是一類幫助重新排列思想和文檔的軟件。一些工具將想法標(biāo)記為標(biāo)簽或節(jié)點(diǎn)，重新排列并在它們之間建立關(guān)系（用線連接它們）。當(dāng)標(biāo)簽被視為節(jié)點(diǎn)，關(guān)系被視為邊時(shí)，可以制作成一個(gè)層次結(jié)構(gòu)網(wǎng)絡(luò)圖。將層次結(jié)構(gòu)網(wǎng)絡(luò)圖用于idea 處理器的一些功能，如保存和播放，用戶可以很容易地理解創(chuàng)意（ideas）的設(shè)計(jì)或修改。用戶還可以看到創(chuàng)意的演變，因?yàn)樗鼈兪鞘褂梅謱咏Y(jié)構(gòu)按時(shí)間順序保存的。通過將這種過去的記錄管理引入到idea 處理器中，可以很容易地遵循創(chuàng)意的安排和發(fā)展。

4 結(jié)束語

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