張大坤，任淑霞

天津工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387

1 引言

隨著科學(xué)技術(shù)、移動(dòng)互聯(lián)網(wǎng)、互聯(lián)網(wǎng)+、社交網(wǎng)絡(luò)、各種傳感器和可穿戴設(shè)備的迅速發(fā)展，人類已步入大數(shù)據(jù)時(shí)代，數(shù)據(jù)爆炸已成為信息科學(xué)領(lǐng)域面臨的一個(gè)巨大挑戰(zhàn)。人類在進(jìn)入大數(shù)據(jù)時(shí)代的同時(shí)，也進(jìn)入了新的“讀圖時(shí)代”。常言道“百聞不如一見”“一圖勝千言”“耳聽為虛、眼見為實(shí)”“一飽眼?！薄靶闵刹汀?，凡此種種都說明了圖形化信息的豐富性和易讀性。進(jìn)入大數(shù)據(jù)時(shí)代后，傳統(tǒng)的數(shù)據(jù)分析方法難以滿足大數(shù)據(jù)價(jià)值的快速挖掘和利用，因而數(shù)據(jù)可視化與可視分析技術(shù)受到前所未有的重視。

網(wǎng)絡(luò)大數(shù)據(jù)是非常重要的一類大數(shù)據(jù)，圖論是網(wǎng)絡(luò)和網(wǎng)絡(luò)大數(shù)據(jù)分析的重要理論基礎(chǔ)，在網(wǎng)絡(luò)研究和網(wǎng)絡(luò)大數(shù)據(jù)可視分析中發(fā)揮了重要作用。但是，由于各種網(wǎng)絡(luò)的規(guī)模越來越大，結(jié)構(gòu)越來越復(fù)雜，一般的圖論就顯得無能為力，而超圖（Hypergraph）理論卻具有得天獨(dú)厚的優(yōu)勢(shì)[1-3]。超圖的理論基礎(chǔ)是圖論和集合論，由于超圖理論較抽象和復(fù)雜，起初的研究和應(yīng)用進(jìn)展較為緩慢，但近年來各領(lǐng)域?qū)τ诔瑘D的研究越來越多，應(yīng)用越來越廣[4-8]；由于超圖的圖形化表達(dá)即可視化方法來自于不同的研究領(lǐng)域，因此超圖可視化方法有多種形式，針對(duì)目前的研究現(xiàn)狀對(duì)其進(jìn)行梳理和綜述就顯得非常必要。

2 超圖相關(guān)知識(shí)

超圖是有限集合的子集系統(tǒng)，是最一般的離散結(jié)構(gòu)。由于它能夠描述復(fù)雜的關(guān)系和結(jié)構(gòu)，因而在數(shù)學(xué)、計(jì)算機(jī)科學(xué)、工程技術(shù)、通訊、經(jīng)濟(jì)、電信、物理學(xué)、運(yùn)籌管理學(xué)、計(jì)算生物學(xué)、生物化學(xué)以及分子生物學(xué)等眾多領(lǐng)域得到了廣泛的應(yīng)用。

2.1 超圖的起源與定義

2.1.1 超圖的起源

超圖是圖論的重要擴(kuò)展。圖論起源于哥尼斯堡（Konigsberg）七橋問題。1736年，瑞典數(shù)學(xué)家歐拉（Euler）成功地解決了七橋這一數(shù)學(xué)難題，圖論由此誕生，歐拉也因此成為了圖論的創(chuàng)始人。圖論在其誕生之后的數(shù)百余年中得到了不斷的發(fā)展，其應(yīng)用范圍極為廣泛。實(shí)踐證明圖論是解決幾何、數(shù)論、運(yùn)籌學(xué)和優(yōu)化等領(lǐng)域中各種組合問題非常有效的工具。然而，隨著科學(xué)技術(shù)的發(fā)展，人類所面臨和要解決的問題越來越復(fù)雜，許多實(shí)際問題難以用一般意義上的圖來描述，即圖論能解決的問題受到局限，超圖理論應(yīng)運(yùn)而生。

把圖的概念進(jìn)行推廣來研究集簇的思想大約始于1960年前后。關(guān)于把集簇中每個(gè)集合看作“廣義的邊”，把集簇本身稱為“超圖”的思想，起初是為了推廣圖論中一些經(jīng)典的結(jié)果，如Turán定理和Konig定理；后來，人們注意到這種推廣往往會(huì)帶來不少的便利，而且可以把圖論中的定理用統(tǒng)一的、簡單的形式加以陳述[9]。1973年Berge第一次系統(tǒng)地建立了無向超圖理論,并應(yīng)用擬陣來研究超圖理論在運(yùn)籌學(xué)方面的應(yīng)用[9]。

2.1.2 超圖的定義

（1）超圖

超圖可分為無向超圖和有向超圖兩大類,在一般的文獻(xiàn)當(dāng)中,如果不加特殊說明,超圖均指無向超圖,本文中提到的超圖也指無向超圖。在超圖經(jīng)典著作“Hypergraph Combinatorics of Finite Sets”中給出了超圖的定義。

令X={x1,x2,…,xn}是一個(gè)有限集合，關(guān)于X上的一個(gè)超圖H=(E1,E2,…,Em)是X上的一個(gè)有限子集簇，使得：

一個(gè)超圖H=(E1,E2,…,Em)若還滿足EiEj?i=j，則稱H為簡單超圖（或“Sperner簇”）。

在超圖H中，X的元素x1,x2,…,xn稱為頂點(diǎn)，集合E1,E2,…,Em稱為邊（超邊）。簡單圖是一個(gè)每條邊均含兩個(gè)頂點(diǎn)的簡單超圖；一個(gè)多重圖（有環(huán)和重邊）是一個(gè)每條邊含不超過兩個(gè)頂點(diǎn)的超圖[9]。

設(shè)V={x1,x2,…,xn}是一個(gè)有限集合，ε={e1,e2,…,em}是V的一個(gè)子集合族，即ε?2V，稱H=(V,ε)是在V上的一個(gè)超圖，如果，簡單地稱ε是在V上的一個(gè)超圖。V的元素稱為頂點(diǎn)，ε的元素稱為邊（超邊）。|V|稱為V的ε階，|ε|稱為ε的規(guī)模。

如果ε的每條邊e，都有|e|=k，則稱ε是一個(gè)k-勻齊超圖。如果k=2，則ε就是一個(gè)通常的圖[9]。

（2）有向超圖

有向超圖H=(E,V)是二元對(duì)，這里的V是頂點(diǎn)集,E是有向超邊集。有向超邊e是有序?qū)?X,Y)，這里的X和Y是V的不相交子集（可以為空），稱X為有向超邊e的尾點(diǎn)集，Y為有向超邊e的頭點(diǎn)集，分別記為T(e)和H(e)[10]。

2.2 超圖的表示及相關(guān)概念

2.2.1 超圖的表示

超圖理論是圖論的推廣，超圖的表示與圖論中圖的表示相對(duì)應(yīng)，也有三類表達(dá)方法，即超圖的集合表示、矩陣表示和圖形表示。然而，一個(gè)超圖中各個(gè)超邊中所包含的頂點(diǎn)數(shù)目一般是不相同的，在不同的研究及應(yīng)用領(lǐng)域中有各種不相同的超圖表示方法，其中超圖的圖形化表示更為多樣化，在此以無向超圖為例進(jìn)行說明。

（1）超圖的集合表示

超圖H最直觀、最樸素的表達(dá)形式應(yīng)該屬超圖的集合表示，由于超圖是有限集合的子集系統(tǒng)即集簇，因此可以直接用集合來表示超圖。例如，可以用集合來定義和表示超圖H={345,58,678,237,12,7}。

（2）超圖的矩陣表示

超圖H可以由一個(gè)關(guān)聯(lián)矩陣A=(aij)來表示，A中的m列分別對(duì)應(yīng)H的m條邊E1,E2,…,Em，n行分別對(duì)應(yīng)H的n個(gè)頂點(diǎn)x1,x2,…,xn。當(dāng)時(shí)，aij=0；當(dāng)xi∈Ej時(shí)，aij=1。例如，（1）中超圖H的矩陣表示如下所示[9]：

（3）超圖的圖形表示

超圖H也可以用圖形方式來表示，即由點(diǎn)的集合表示X中的元素。當(dāng)|Ej|=2時(shí)，就用一條連接Ej中兩個(gè)元素的連續(xù)曲線表示Ej；當(dāng)|Ej|=1時(shí)，用一個(gè)包含Ej中唯一元素的環(huán)表示Ej；|Ej|≥3時(shí)，用一條包含Ej中所有元素的簡單曲線表示Ej。例如，（1）中超圖H的圖形表示如圖1所示[9]。

Fig.1 Graphical representation of hypergraph H圖1 超圖H的圖形表示

2.2.2 超圖相關(guān)概念

（1）對(duì)偶超圖

X上超圖H=(E1,E2,…,Em)的對(duì)偶超圖H*=(X1,X2,…,Xn)，其中的頂點(diǎn)對(duì)應(yīng)H中的邊，而邊為：

易見H*的關(guān)聯(lián)矩陣是H關(guān)聯(lián)矩陣的轉(zhuǎn)置，故有(H*)*=H。在第2.2.1小節(jié)（1）中給出的超圖H的對(duì)偶超圖H*如圖2所示。

（2）一致超圖

與圖類似，超圖H的頂點(diǎn)數(shù)稱為超圖的階，用n(H)表示，邊數(shù)用m(H)表示。此外，r(H)稱為上秩，s(H)稱為下秩；如果r(H)=s(H)，則稱H是一致超圖；秩為r的簡單一致超圖稱為r-一致超圖（認(rèn)為不含重邊）。

Fig.2 Dual hypergraphH*圖2 超圖H的對(duì)偶超圖H*

（3）正則超圖

對(duì)x∈X,x的度dH(x)是指H(x)的邊數(shù)，即dH(x)=m(H(x))。

超圖H的最大度記為：

所有頂點(diǎn)有相同度的超圖稱為正則超圖。

（4）度序列及其性質(zhì)

對(duì)n階超圖H，令dH(xi)=di，并按非增n-序列d1≥d2≥…≥dn來排序所成的度序列，當(dāng)H是簡單圖時(shí)，上述度序列能被刻畫。一般地，有下面的性質(zhì)成立。

一個(gè)n-序列d1≥d2≥…≥dn是一個(gè)秩為r的n階一致超圖（允許有重邊）的度序列的充要條件是：

①∑di是r的倍數(shù)(i=1,2,…,n)；

②di≥ 1(i=1,2,…,n)；

③∑di/r≥d1（文獻(xiàn)[10]中沒有此條件）。

（5）交簇

H是一個(gè)超圖，若H的邊集兩兩相交非空，則稱該邊集為一個(gè)交簇。例如，對(duì)H的一個(gè)頂點(diǎn)x,H(x)={E|E∈H,x∈E}是H的一個(gè)交簇[9]。

3 超圖可視化方法

3.1 超圖可視化流程

超圖可視化是網(wǎng)絡(luò)數(shù)據(jù)可視化的重要形式，由于超圖繪制方法的多樣性，在實(shí)現(xiàn)可視化之前需要對(duì)所要分析的數(shù)據(jù)集做全面的分析，選擇最適合的超圖表示方法，使其能夠更準(zhǔn)確地表達(dá)數(shù)據(jù)的內(nèi)涵。超圖可視化總體上也遵循信息可視化的一般流程（1999年Card等提出的信息可視化參考流程[11]如圖3所示），但超圖布局和繪制算法更為復(fù)雜。

3.2 超圖可視化表達(dá)方法

圖論中圖的定義和表達(dá)非常經(jīng)典有效，可以用類比的方法研究超圖的可視化表達(dá)方法。圖論中，圖的基本定義和表達(dá)采用了集合表達(dá)式。圖（graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成,通常表示為G(V,E)，其中G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合,E是圖G中邊的集合。而在實(shí)際應(yīng)用中圖的圖形化表達(dá)形式更為簡潔，更為直觀，是用圖論解決實(shí)際問題的有效工具，圖的集合表示和圖形化表達(dá)兩種方法相輔相成、相得益彰。圖論中，一般用一個(gè)小圓圈表示節(jié)點(diǎn)，用線表示邊，哥尼斯堡七橋問題的圖形化表示為歐拉創(chuàng)建圖論起到了至關(guān)重要的作用。超圖是研究集合簇的，超邊中有包含隨機(jī)性的節(jié)點(diǎn)，超圖的集合定義和表達(dá)形式較為簡捷直觀（如第2.2.1小節(jié)（1）所述），然而超圖可視化表達(dá)（即超圖的畫法）非常復(fù)雜，在不同的研究領(lǐng)域，所面對(duì)的實(shí)際問題多種多樣，因此超圖的畫法有許多。最經(jīng)典的畫法是文氏圖，該方法是將屬于一個(gè)超邊中的節(jié)點(diǎn)用一條封閉曲線封閉起來，該方法簡單易于理解，但當(dāng)問題規(guī)模很大時(shí)，會(huì)出現(xiàn)很多封閉曲線，就會(huì)使圖形非常混亂，失去了可視化表達(dá)的優(yōu)勢(shì)。目前有多種超圖可視化表達(dá)方法（畫法），將這些方法進(jìn)行梳理、歸納、總結(jié)，對(duì)超圖的理論研究和普及應(yīng)用都至關(guān)重要。

Fig.3 Information visualization reference process圖3 信息可視化參考流程

4 超圖可視化方法研究

超圖的可視化方法還停留在探索階段[11]。簡潔明了的超圖可視化方法對(duì)超圖的理論研究和普及應(yīng)用都會(huì)起到重要的推動(dòng)作用，也會(huì)極大地方便超圖學(xué)習(xí)者和使用者對(duì)超圖的理解。

4.1 超圖不確定性及其可視化方法的多樣性

4.1.1 超圖的不確定性

超圖的概念是集合概念的推廣，超圖是一個(gè)集合簇（集合的集合），是一種與一般意義上圖的類比，其最大差別在于超邊與邊的本質(zhì)差別，一般圖中的邊是兩個(gè)結(jié)點(diǎn)的集合（二元集），而超圖中的超邊中可以包含數(shù)量不等的集合元素（頂點(diǎn)），即各個(gè)子集合并沒有一個(gè)統(tǒng)一的勢(shì)。同時(shí)，超圖中子集合與子集合之間可以包含不同數(shù)量的集合元素，即子集合之間的交集也是不確定的。超圖的不確定性必然帶來超圖可視化方法的多樣性。

4.1.2 超圖可視化方法的多樣性

由于超圖中的超邊中包含的結(jié)點(diǎn)可以是任意多個(gè)，即超圖自身包含著不確定性，因此超圖的畫法也會(huì)多種多樣，超圖的形態(tài)比一般圖更為豐富（這也給超圖的可視化方法研究帶來更多機(jī)會(huì)）。另外，對(duì)于超圖的研究與最初對(duì)圖的研究具有一定的相似性。圖論自創(chuàng)立后，許多領(lǐng)域研究者將圖論應(yīng)用到各自的研究領(lǐng)域，從不同的角度進(jìn)行研究，逐漸地豐富了圖論的內(nèi)容，使其發(fā)展壯大成一門獨(dú)立的數(shù)學(xué)分支。超圖的可視化方法還停留在探索階段，在不同的研究領(lǐng)域有不同的表示。對(duì)已有的這些表示方法進(jìn)行研究和總結(jié)，不僅有助于對(duì)這些方法進(jìn)行比較，而且可以研究出更好的超圖可視化方法，對(duì)于超圖的規(guī)范化表達(dá)和廣泛應(yīng)用具有重要意義。

4.2 超圖可視化方法分類研究

4.2.1 超圖可視化方法分類

超圖的應(yīng)用領(lǐng)域越來越廣泛，在不同的研究領(lǐng)域中超圖的表現(xiàn)形式各不相同，目前還沒有對(duì)其進(jìn)行分類的專題研究報(bào)道。而對(duì)形形色色的超圖可視化方法進(jìn)行分類研究非常必要，它將大大方便對(duì)超圖的理解和應(yīng)用。分析比較常見的25種超圖可視化方法，根據(jù)繪制特點(diǎn)將其分為以下幾類：空間劃分超圖可視化、基于樹和圖的超圖可視化、平面型超圖可視化、規(guī)則化超圖可視化、關(guān)聯(lián)超圖可視化以及其他超圖可視化方法。

4.2.2 超圖可視化分類樹

超圖的可視化方法還停留在探索階段[11]，其分類方法更是一個(gè)值得探索的問題，將分類用一棵樹來表示更加直觀清晰，超圖可視化方法分類樹如圖4所示。

4.3 超圖可視化方法綜述

超圖可視化方法根據(jù)表達(dá)形式的不同分成了5類，現(xiàn)分類介紹各種超圖可視化方法。

4.3.1 空間劃分超圖可視化

超圖的概念是由集合引出的，超邊中含有眾多元素，這些元素根據(jù)其性質(zhì)的不同而處于不同的空間區(qū)域，空間劃分超圖可視化直接且易于理解，主要包括以下幾種。

（1）維恩圖

維恩圖（Venn diagram）也叫文氏圖，用于顯示元素集合重疊區(qū)域的圖示。1880年，英國數(shù)學(xué)家維恩（Venn）在《論命題合理的圖表化和機(jī)械化表現(xiàn)》一文中首次采用固定位置的交叉環(huán)形式，用封閉曲線（內(nèi)部區(qū)域）表示集合及其關(guān)系的圖形[12]。之后維恩圖在許多領(lǐng)域得到了廣泛的應(yīng)用。超圖是集合簇，即集合的集合，因此人們自然地采用維恩圖來表示超圖：將超圖中的超邊表示成帶顏色的簡單閉曲線或封閉區(qū)域。超圖H={12,123,24,3456}的維恩圖表達(dá)如圖5（a）所示[11]。許多研究者在超圖研究中采用了這種表示方法[13-22]，如Dharmarajan等人在基于超圖算法的圖像修復(fù)研究中，采用了文氏圖的形式表現(xiàn)超圖，如圖5（b）所示[23]。同時(shí)提出將圖像用文氏圖進(jìn)行分類表示的算法，其后檢測(cè)圖像中的噪音，最后對(duì)圖像進(jìn)行修復(fù)。

Fig.4 Hypergraph visualization classification tree圖4 超圖可視化分類樹

（2）橢圓畫法

橢圓畫法也是一種表示元素集合重疊區(qū)域的圖示方法，是由Sawilla提出的。該方法使用橢圓來實(shí)現(xiàn)超邊的表示[24]，橢圓畫法如圖6所示。但該方法能用于節(jié)點(diǎn)數(shù)量很少的超圖繪制,而且對(duì)節(jié)點(diǎn)的位置與布局有諸多限制。

（3）超圖的區(qū)域型可視化

陳紅倩等人針對(duì)超圖繪制中超邊表達(dá)困難，繪制算法復(fù)雜的問題，提出一種超圖的快速可視化方法，并稱其為超圖區(qū)域型可視化[24]。該方法將同超邊中的元素置于一個(gè)區(qū)域中，本質(zhì)上也是一種空間劃分畫法，即將超邊結(jié)點(diǎn)沿其走勢(shì)線垂線方向向兩側(cè)擴(kuò)展，獲得超邊中各結(jié)點(diǎn)的擴(kuò)展點(diǎn)。對(duì)擴(kuò)展點(diǎn)根據(jù)位置關(guān)系重新組合，使用Catmull-Rom算法連接各擴(kuò)展點(diǎn)，獲得超邊表示區(qū)域的平滑邊界曲線；將超邊表示區(qū)域劃分為對(duì)偶子段和獨(dú)立子段，并分別使用三角帶和三角扇模式填充。最后根據(jù)色相環(huán)理論對(duì)超邊表示區(qū)域進(jìn)行著色，以增強(qiáng)各條超邊的區(qū)分度，其實(shí)例如圖7所示。

4.3.2 基于樹和圖的超圖可視化

圖論中的圖G=(V,E)是一個(gè)二元組，V是結(jié)點(diǎn)集，E是邊集，E的元素是V的2-元子集。將不含回路的圖定義為樹。將基于樹和圖的超圖可視化歸為一類。

（1）斯坦納樹畫法

將斯坦納樹思想引入超圖可視化中，形成了超圖的斯坦納樹畫法[11]。該方法將超圖的每一條超邊均表示成一棵斯坦納樹，可以用最少的連線表達(dá)超圖。超圖H={12,123,24,3456}的斯坦納樹如圖8所示。

（2）交叉樹畫法

Eisner等人用交叉的樹狀圖表示超圖,并設(shè)計(jì)了一系列結(jié)點(diǎn)與布局整體動(dòng)態(tài)轉(zhuǎn)換的交互操作，其中一部分交互操作由鍵盤實(shí)現(xiàn)[25]。

（3）二分圖畫法

二分圖又稱作二部圖，是圖論中的一種特殊模型?？捎枚謭D來表示超圖，將超圖的頂點(diǎn)和超邊均表示成結(jié)點(diǎn)，將頂點(diǎn)和超邊結(jié)點(diǎn)分別平面放置在兩側(cè)，一般將超圖頂點(diǎn)放在左側(cè)（或上方），超邊結(jié)點(diǎn)放在右側(cè)（或下方），在兩部分之間根據(jù)超邊和頂點(diǎn)的包含關(guān)系連線。該方法簡單明了，布局簡單，適用規(guī)模適中，但不夠直觀，需要通過連線來找頂點(diǎn)和超邊的對(duì)應(yīng)關(guān)系。超圖二分圖畫法如圖9（a）所示[11]。Polak等人在對(duì)視覺識(shí)別的潛在模型聚類和應(yīng)用研究中，采用的超圖表達(dá)也屬于超圖二分圖畫法，如圖9（b）所示[26]。

Fig.5 Venn diagram drawing method圖5 文氏圖畫法

Fig.6 Hypergraph ellipse圖6 超圖橢圓畫法

Fig.7 Regional visualization of hypergraph圖7 超圖的區(qū)域型可視化

Fig.8 Steiner tree painting of hypergraph圖8 超圖斯坦納樹畫法

Fig.9 Hypergraph dichotomous drawing method圖9 超圖二分圖畫法

（4）海塞圖畫法

超圖的海塞圖（Hasse）是對(duì)超圖集合偏序中按傳遞關(guān)系約簡的結(jié)果，其表現(xiàn)形式也是一棵樹，因此也歸為基于樹和圖的超圖可視化。首先，對(duì)超圖的超邊依次進(jìn)行求交運(yùn)算，若求得的交集在超邊的集合中不存在，則將其擴(kuò)充到超邊的集合中并更新超邊集合。繼續(xù)進(jìn)行求交運(yùn)算，直到從新得到的超邊集合中任取兩個(gè)元素，它們的交集仍屬于這個(gè)集合。最后得到的超邊集合稱為超圖的交閉半格。超圖的海塞圖畫法實(shí)例如圖10所示[27]。

（5）有向圖畫法

Fig.10 Hasse graph圖10 海塞圖畫法

Fig.11 Hypergraph oriented graph圖11 超圖有向圖畫法

楊博等人在研究網(wǎng)格優(yōu)化有向超圖任務(wù)調(diào)度算法時(shí)應(yīng)用了有向超圖D[28]。這是一種結(jié)點(diǎn)和有向超邊的交替結(jié)構(gòu)，如圖11（a）所示。Chahuneau等人在研究cdec解碼器的Python接口時(shí)，使用有向超圖作為一種數(shù)據(jù)結(jié)構(gòu)，通過超圖數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)大量由解碼器生成的超邊和結(jié)點(diǎn)。解碼器初始化后，在翻譯任何語句時(shí)都將解碼器的搜索空間編碼為一個(gè)有向超圖，如圖11（b）所示[29]。

（6）多元關(guān)系畫法

超圖可以表達(dá)多元關(guān)系，將其稱為超圖多元關(guān)系畫法，由于表現(xiàn)形式上具有網(wǎng)狀特征，故也將其歸到基于樹和圖的超圖可視化一類中。夏菁等人使用超圖對(duì)骨生物數(shù)據(jù)之間的多元關(guān)系進(jìn)行表示，并借助于多線條來表示超圖中超邊的存在[30]，視覺上具有美觀性。Boulouard等人在研究競爭情報(bào)系統(tǒng)中，使用超圖作為分析和可視化的工具，也屬于超圖多元關(guān)系畫法，如圖12所示[31]。

Fig.12 Hypergraphic multivariate relation圖12 超圖多元關(guān)系畫法

（7）能量布線畫法

Junghans研究了固定節(jié)點(diǎn)的超圖布局方法，如圖13所示[32]，其表現(xiàn)形式具有樹（分枝）的特征，也歸類到基于樹和圖的超圖可視化?；诰垲惡蟮慕Y(jié)果采用能量方法布置連接線在一定程度上解決了視覺復(fù)雜性問題，但該方法沒有涉及結(jié)點(diǎn)不固定的情況而且只對(duì)有明顯聚類和關(guān)系較少情況效果比較好。

Fig.13 Hypergraphic energy wiring method圖13 超圖能量布線法

4.3.3 平面型超圖可視化

超圖的平面支撐和超圖的細(xì)分畫法，是兩種對(duì)偶的畫法，都是從平面角度考慮問題，因此稱之為平面型超圖可視化。

（1）超圖的平面支撐畫法

在大規(guī)模集成設(shè)計(jì)中，如何設(shè)計(jì)布線以保證不出現(xiàn)邊交叉，一直是科學(xué)家們研究的問題。超圖的支撐是超圖中結(jié)點(diǎn)構(gòu)成的布局圖，其中每一條超邊對(duì)應(yīng)結(jié)點(diǎn)布局圖中的一個(gè)連通子圖。如果這種圖具有平面性，則稱它是超圖的一個(gè)平面支撐，如圖14所示[11]。

Fig.14 Planar support of hypergraphs圖14 超圖的平面支撐

（2）超圖的細(xì)分畫法

超圖的細(xì)分是指將超圖的每一個(gè)結(jié)點(diǎn)唯一地對(duì)應(yīng)于一個(gè)細(xì)分平面，使得每一條超邊對(duì)應(yīng)的細(xì)分平面是連通的，如圖15（a）、圖15（b）所示。超圖的細(xì)分畫法與其表達(dá)的平面支撐互為對(duì)偶圖（將點(diǎn)與平面互設(shè)為對(duì)偶，兩者的可視化表達(dá)對(duì)等）。超圖H={1567,1234,136}的平面支撐（圖種的黑色點(diǎn)線圖）和細(xì)分畫法如圖15（c）所示（彩色面片），其中平面1與平面3、5、6相連通，表達(dá)了結(jié)點(diǎn)1與結(jié)點(diǎn)3、5、6之間的超邊關(guān)系[11]。

Fig.15 Planar support and subdivision method of Hypergraphs圖15 超圖的平面支撐和細(xì)分畫法

4.3.4 超圖規(guī)則化畫法

在超圖的應(yīng)用研究中，研究者根據(jù)實(shí)際問題的特殊性，在超圖應(yīng)用中采用了不同的表達(dá)形式，其中有正交畫法、線網(wǎng)模型、電路圖畫法、正交有向畫法以及結(jié)構(gòu)化畫法。這些畫法的表現(xiàn)形式都具有一定的規(guī)則性，將它們歸為超圖規(guī)則化畫法。

（1）正交畫法

正交性是幾何術(shù)語，如果兩條直線相交成直角，它們就是正交的。超圖的正交畫法是工業(yè)界比較常用的畫法，尤其在大規(guī)模集成電路設(shè)計(jì)中。與一般結(jié)點(diǎn)-鏈接布局中用直線或平滑曲線表達(dá)關(guān)系不同，正交法的邊只允許垂直彎曲，所用邊只能沿x或y兩個(gè)方向彎曲，其設(shè)計(jì)思想與集成電路中的電路走向一致。Sander在研究具有正交超邊的有向超圖布局算法時(shí)，使用超圖構(gòu)建具有正交邊的分層結(jié)構(gòu)，如圖16所示[33]。

Fig.16 Hypergraph orthogonal圖16 超圖正交畫法

（2）線網(wǎng)模型

胡云等人在研究基于概率增益的電路劃分算法時(shí)，應(yīng)用了超圖線網(wǎng)模型，如圖17所示[34]，對(duì)問題的理解和解決起到了重要作用。

Fig.17 Hypergraph model of line network圖17 超圖線網(wǎng)模型

（3）電路圖表示法

電路圖表示法模擬電路圖的布線方法對(duì)多元關(guān)系進(jìn)行布局，如圖18（a）所示[35]，可以有效地減少集合交叉重疊，但易讀性和美觀性較差。Eschbach等人在研究正交電路可視化優(yōu)化時(shí)，采用正交超圖嵌入電路，如圖18（b）所示，優(yōu)點(diǎn)是比直線嵌入圖減少交叉的數(shù)量[36]。

Fig.18 Circuit diagram圖18 電路圖表示法

（4）正交有向畫法

Sander通過布局算法來展示有向超圖，并使用正交超邊繪制有向超圖的布局研究，正交有向圖表示如圖19所示[33]。

Fig.19 Orthogonal direction painting圖19 正交有向畫法

（5）結(jié)構(gòu)化畫法

吳翔等人在基于結(jié)構(gòu)化超圖的產(chǎn)品4D信息模型結(jié)構(gòu)化研究中，介紹了零件基本記錄（PartBR）及結(jié)構(gòu)化超圖描述，如圖20所示[37]。采用結(jié)構(gòu)化超圖可以方便地實(shí)現(xiàn)對(duì)各種對(duì)象動(dòng)態(tài)變化的管理等。

4.3.5 其他超圖可視化

超圖應(yīng)用越來越廣，其表達(dá)形式也越來越多，上面歸納了四類畫法，但有些畫法還難以構(gòu)成一類，在此暫將它們歸為其他超圖可視化，隨著研究的深入歸類也會(huì)更加精準(zhǔn)。

Fig.20 Structured hypergraph圖20 結(jié)構(gòu)化超圖

（1）字串-直線畫法

王莉在研究γ無回路數(shù)據(jù)庫模式的設(shè)計(jì)方法時(shí)，采用了字符串-直線表示數(shù)據(jù)庫超圖，本文稱其為超圖的字符-直線畫法，如圖21所示[38]。

Fig.21 String-line drawing圖21 字串-直線畫法

（2）三元畫法

宗瑜等人在研究“面向標(biāo)注的局部中心度傳播聚類算法”時(shí)，將一個(gè)標(biāo)注系統(tǒng)看作為包含用戶、資源和標(biāo)注的三元超圖，圖中的結(jié)點(diǎn)分別為用戶、資源和標(biāo)注，而圖中的邊則表示三者之間的關(guān)聯(lián)關(guān)系，如圖22所示[39]。

Fig.22 Hypergraph ternary圖22 超圖三元畫法

（3）抽象符號(hào)畫法

在文檔性質(zhì)說明中，可以采用超圖來說明，利用三角、圓圈、數(shù)字、字符一起來表示超圖[40]，在此稱其為抽象符號(hào)形式表示法，如圖23所示。Mukhopadhyay等人在疾病與基因關(guān)聯(lián)研究中，使用超圖從生物學(xué)文本中抽取多路關(guān)聯(lián)信息并將其可視化[41]。

Fig.23 Hypergraph abstract symbol圖23 超圖抽象符號(hào)畫法

（4）關(guān)聯(lián)超圖

王紅軍等人在研究基于超圖理論的產(chǎn)品族規(guī)劃方法時(shí)介紹了關(guān)聯(lián)超圖（relational hypergraph，RH），對(duì)于一個(gè)進(jìn)化超圖H=(V,E,I,O)，如果每條超邊e和每個(gè)輸入結(jié)點(diǎn)v之間的關(guān)系都是主輸入和從輸入的關(guān)系，則此進(jìn)化超圖稱為關(guān)聯(lián)超圖，關(guān)聯(lián)超圖的實(shí)例如圖24所示[42]。

Fig.24 Relation painting of hypergraph圖24 超圖關(guān)聯(lián)畫法

（5）平滑曲線

陳紅倩等人針對(duì)超圖表達(dá)中超邊的可視化效果不直觀、描述不準(zhǔn)確的問題，提出了一種基于Catmull-Rom插值算法的超圖可視化方法。該方法的最大特點(diǎn)是用不同顏色的平滑曲線表示不同的超邊，因此稱其為超圖的平滑曲線畫法，如圖25（a）所示[43]。Wang等人在研究長文檔主題結(jié)構(gòu)的分層可視化中，使用主題超圖建模來描述用超圖表示的長文檔主題結(jié)構(gòu)的特征，每個(gè)超圖節(jié)點(diǎn)表示一個(gè)獨(dú)立的文檔塊，如圖25（b）所示[44]，該表達(dá)方法也屬于平滑曲線畫法。

Fig.25 Smooth curve of hypergraph圖25 超圖的平滑曲線畫法

（6）過程抽象畫法

黃麗華等人在基于規(guī)則和方法的企業(yè)過程優(yōu)化研究中，用抽象畫法表示銷售過程的超圖模型，如圖26所示[45]。

Fig.26 Hypergraph process abstraction圖26 超圖過程抽象畫法

（7）循環(huán)特征畫法

Jin等人利用現(xiàn)有的圖形排序算法來求解最佳可視化問題，在超圖表達(dá)中能夠表達(dá)出循環(huán)特征[46]，如圖27所示。

（8）層次化超圖畫法

Ducournau等人使用彩色圖像鄰域超圖表示法,采用臨近感知分組模式，提取圖像數(shù)據(jù)的所有特征和連貫性信息，并提出了多層光譜超圖劃分算法，其圖形表示如圖28所示[47]。

Fig.27 Cyclic feature representation圖27 循環(huán)特征畫法

Fig.28 Hierarchical hypergraph圖28 層次化超圖畫法

5 總結(jié)與展望

5.1 總結(jié)

5.1.1 超圖可視化方法及其特性

對(duì)超圖可視化方法及其特性分類，劃分為空間劃分超圖可視化如表1所示；基于樹和圖的超圖可視化方法如表2所示；平面型超圖可視化方法如表3所示；規(guī)則化超圖可視化方法如表4所示；其他超圖可視化方法如表5所示。

5.1.2 小結(jié)

隨著網(wǎng)絡(luò)數(shù)據(jù)規(guī)模和復(fù)雜度的增加，一般圖論難以描述各種錯(cuò)綜復(fù)雜的網(wǎng)絡(luò)數(shù)據(jù)，而超圖卻獨(dú)具優(yōu)勢(shì)，其應(yīng)用越來越廣泛，隨著大數(shù)據(jù)的增加，超圖可視化已成為分析復(fù)雜網(wǎng)絡(luò)的有效工具。文中對(duì)超圖和超圖可視化相關(guān)問題進(jìn)行了概括介紹；闡述了超圖不確定性和超圖畫法的多樣性；對(duì)超圖可視化方法進(jìn)行研究，將其劃分為五大類，給出了超圖可視化方法一覽表，對(duì)超圖初學(xué)者和研究者可以起到拋磚引玉的作用。

5.2 展望

5.2.1 超圖可視化方法研究現(xiàn)狀

超圖的應(yīng)用越來越廣泛，超圖可視化和超圖可視分析在復(fù)雜關(guān)系、復(fù)雜網(wǎng)絡(luò)以及大數(shù)據(jù)分析中變得越來越重要。目前，超圖可視化方法研究尚處于探索階段。

Table 1 Hypergraph visualization methods of space partitioning and their characteristics表1 空間劃分超圖可視化方法及其特性

Table 2 Hypergraph visualization methods based on tree and graph and their characteristics表2 基于樹和圖的超圖可視化方法及其特性

Table 3 Hypergraph visualization methods of plane type表3 平面型的超圖可視化方法及其特性

（1）超圖可視化方法形式多樣

超圖最初是從有限集合的組合學(xué)開始研究的，很多概念和表示與集合相對(duì)應(yīng)，或是從圖論中直接擴(kuò)充而來。由于有限集合組合的多樣性，就使超圖可視化方法非常豐富；超圖的應(yīng)用非常廣泛，涉及到眾多學(xué)科和研究領(lǐng)域，不同領(lǐng)域涉及的超圖本身都具有自身的特點(diǎn)，因此超圖可視化方法多種多樣。

（2）每種超圖可視化方法具有局限性

目前，所總結(jié)的超圖可視化方法來源于不同的研究領(lǐng)域，這些方法一般是特定領(lǐng)域科技人員根據(jù)本領(lǐng)域的特點(diǎn)總結(jié)的，更注重實(shí)用性。大多數(shù)超圖可視化方法都具有不同程度的局限性，難以深刻揭示超圖的內(nèi)在特性。

（3）超圖可視化繪制的成熟算法較少

目前，超圖可視化方法大多是給出繪制的原則,是一種以文字?jǐn)⑹鲂问浇o出的，為了提高超圖繪制效率，對(duì)超圖可視化繪制算法的專門研究非常必要,如陳等人對(duì)超圖繪制算法進(jìn)行了研究[24,43]，但有關(guān)這方面的研究專題報(bào)道還很少。

Table 4 Hypergraph visualization methods of regularization and their characteristics表4 規(guī)則化超圖可視化方法及其特性

Table 5 Other hypergraph visualization methods and their characteristics表5 其他超圖可視化方法及其特性

5.2.2 值得進(jìn)一步研究的課題

（1）超圖可視化方法分類完善

本文研究了超圖可視化方法，將其分為六大類，分類介紹了常見的25種超圖畫法。除此之外還存在一些超圖表示法，對(duì)這些表示方法進(jìn)行歸類是進(jìn)一步應(yīng)做的工作，它對(duì)超圖及其可視化完整知識(shí)體系的建立具有重要意義。

（2）適合于多領(lǐng)域的超圖圖形化表示方法

在不同的研究領(lǐng)域中超圖的圖形化表示方法各不相同，為深入研究超圖及其可視化，需要對(duì)目前的超圖的圖形化表示方法進(jìn)行分析，找出共性，提出一種規(guī)范的、抽象層次更高的超圖可視化方法。

（3）超圖的美感和藝術(shù)性

超圖的表示形式多種多樣，對(duì)于每一種畫法，將其美觀地繪制出來是一個(gè)難題。繪制超圖時(shí)超圖的總體布局、超圖形貌（如維恩圖中封閉曲線的形狀）設(shè)計(jì)與超圖的藝術(shù)性表現(xiàn)是重要的研究課題。

（4）大型超圖快速繪制算法

隨著數(shù)據(jù)規(guī)模的增大，網(wǎng)絡(luò)復(fù)雜程度將越來越高，超圖所要解決的問題也會(huì)越來越復(fù)雜，能夠快速地繪出大型超圖對(duì)于應(yīng)用超圖解決實(shí)際問題至關(guān)重要。因此，超圖快速繪制算法研究將是超圖可視化中最為重要的問題之一。

（5）特定領(lǐng)域的超圖可視化技術(shù)

特殊應(yīng)用領(lǐng)域中的超圖具有很強(qiáng)的自身特點(diǎn)，因此面向特定領(lǐng)域的超圖可視化、超圖可視分析技術(shù)研究也是一個(gè)值得關(guān)注的課題。

（6）超圖可視化專用軟件

超圖具有不確定性，繪制超圖面臨巨大挑戰(zhàn)。對(duì)超圖的繪制進(jìn)行專題研究，開發(fā)繪制與分析超圖的專用程序、專用軟件，對(duì)超圖可視化和超圖可視分析普及與應(yīng)用將會(huì)起到極大的推動(dòng)作用。

（7）超圖可視化與數(shù)據(jù)分析技術(shù)有機(jī)地融合

在大數(shù)據(jù)分析中，由于數(shù)據(jù)規(guī)模巨大，數(shù)據(jù)類型煩多，用單一的分析方法進(jìn)行分析難以表現(xiàn)出其中的內(nèi)在特性與價(jià)值，將超圖可視化技術(shù)與各種數(shù)據(jù)分析技術(shù)有機(jī)地融合是具有挑戰(zhàn)性的研究課題。

未來，大數(shù)據(jù)規(guī)模會(huì)越來越大，類型越來越多，結(jié)構(gòu)也會(huì)越來越復(fù)雜，大數(shù)據(jù)可視化及可視化分析面臨巨大挑戰(zhàn)。超圖可視化及其可視分析技術(shù)在大數(shù)據(jù)分析、復(fù)雜網(wǎng)絡(luò)分析、數(shù)據(jù)庫技術(shù)、知識(shí)發(fā)現(xiàn)以及生命科學(xué)等眾多領(lǐng)域?qū)?huì)發(fā)揮更大的作用。