文/張慧軍

1 引言

社團發(fā)現(xiàn)是一種研究網(wǎng)絡的重要技術(shù)，目前被廣泛應用于生物網(wǎng)絡、社交網(wǎng)絡以及技術(shù)網(wǎng)絡的分析中，然而在當前的相關研究中，大部分工作主要是針對網(wǎng)絡的拓撲結(jié)構(gòu)來研究如何提高社團發(fā)現(xiàn)算法的效率以及準確性等。隨著當前信息的多樣化，很多真實的網(wǎng)絡數(shù)據(jù)除了拓撲信息還兼具語義信息，其中語義信息不僅能夠幫助用戶進一步解釋社團，還能為社團結(jié)構(gòu)的調(diào)整提供了語義依據(jù)。如在電子郵件網(wǎng)絡數(shù)據(jù)中，拓撲結(jié)構(gòu)主要指郵件聯(lián)系人以及他們之間的郵件收發(fā)關系，而語義信息主要是指郵件的主題和內(nèi)容等。從網(wǎng)絡的拓撲結(jié)構(gòu)來看，社團內(nèi)的節(jié)點之間有緊密的聯(lián)系，而社團之間的連接相對稀疏；從網(wǎng)絡的語義信息來看，社團內(nèi)的節(jié)點語義信息相似，而社團之間的語義信息差別較大。在社團分析中融合拓撲信息與語義信息有利于發(fā)現(xiàn)更加準確以及更具解釋性的社團結(jié)構(gòu)。

可視分析技術(shù)將以人為中心的交互式可視化和以機器為中心的自動算法結(jié)合起來，逐漸成為了一種有效的決策手段。本文提出了一種社團可視分析方法，在該方法通過拓撲空間和語義空間的可視化及其交互技術(shù)，來幫助用戶更好的解釋、調(diào)整社團結(jié)構(gòu)。

2 相關研究

本文將交互式可視分析方法和社團發(fā)現(xiàn)算法結(jié)合起來幫助用戶理解和調(diào)整社團結(jié)構(gòu)，所以本文的相關研究主要包括社團發(fā)現(xiàn)算法的研究和網(wǎng)絡數(shù)據(jù)可視化方法研究兩個方面。

2.1 社團發(fā)現(xiàn)算法的研究

圖1：社團可視分析研究框架

社團發(fā)現(xiàn)算法按照其思想可以分為基于圖劃分、基于聚類、基于模塊度優(yōu)化、重疊社團發(fā)現(xiàn)算法等多種方法。基于圖劃分的算法將圖劃分為預定義大小的多個簇，簇內(nèi)的連接比簇之間的連接更多。基于圖劃分的代表算法有譜分區(qū)算法和 Kernighan-Lin算法?；诰垲惖乃惴òɑ趯哟尉垲惖乃惴ā⒒趧澐志垲惖乃惴?、基于譜聚類的算法等。模塊度是社團質(zhì)量的一種衡量函數(shù)，模塊度越大，分區(qū)越好。基于模塊優(yōu)化的代表性算法有Newman算法及其變種。重疊社團發(fā)現(xiàn)算法包括Top Graph Clusters，SVINET和標簽傳播算法等。

2.2 網(wǎng)絡數(shù)據(jù)可視化方法研究

網(wǎng)絡數(shù)據(jù)常用的可視化方法主要有節(jié)點鏈接法、鄰接矩陣法等。節(jié)點鏈接法是網(wǎng)絡數(shù)據(jù)中最常用的一種圖形表示，其中每個節(jié)點均顯示為一個點、圓、多邊形或其他圖形對象，而每條邊均顯示為連接兩個節(jié)點的線段或曲線。在節(jié)點鏈接圖中，存在許多用于計算節(jié)點和邊的位置的復雜算法，如Sugiyama-Tagawa-Toda算法，該算法將節(jié)點定位在分層布局的級別上。在基于力導向布局的一類算法中，節(jié)點被想象為物理粒子，它們位置初始化為的隨機位置，然后在各種力的作用下逐漸位移，直至到達最終位置。不同算法對作用力的定義不同。

鄰接矩陣法是另一種常用的網(wǎng)絡數(shù)據(jù)可視化方法。在鄰接矩陣中，網(wǎng)絡中的每個節(jié)點都對應一個行和一個列。對于給定的兩個節(jié)點i和j，矩陣中位于(i,j)和(j,i)位置上的單元格包含了這兩個節(jié)點之間連接邊的信息。通常，每個單元格都包含一個布爾值，來指示兩個節(jié)點之間是否存在邊。如果網(wǎng)絡是無向的，則鄰接矩陣是對稱的，即兩個單元格(i,j)和(j,i)對應同一條邊。但是，如果網(wǎng)絡是有向的，則鄰接矩陣是不對稱的。

綜上所述，在社團發(fā)現(xiàn)算法的研究中，用戶很難理解算法為什么會把一些節(jié)點劃分在同一社團內(nèi)，某個社團的節(jié)點之間到底有什么共性；在網(wǎng)絡數(shù)據(jù)可視化方法研究中，大部分工作主要集中在網(wǎng)絡拓撲結(jié)構(gòu)的可視化上，對社團的語義解釋以及社團結(jié)構(gòu)的優(yōu)化調(diào)整方面的研究還比較缺乏。本文的目的是使用可視分析技術(shù)打通拓撲空間和語義空間之間的通道，幫助用戶解釋和調(diào)整社團結(jié)構(gòu)。

3 社團可視分析框架

本文提出的社團可視分析框架主要包括拓撲空間與語義空間兩部分（如圖1所示）。拓撲空間包括社團發(fā)現(xiàn)算法、網(wǎng)絡及其社團結(jié)構(gòu)的可視化表示等。語義空間主要指節(jié)點或邊的語義信息可視化。在本文中，語義主要是指網(wǎng)絡數(shù)據(jù)的節(jié)點或者邊所包括的屬性，文中更多關注于文本類屬性值的分析。社團可視分析框架的這兩個空間通過豐富的交互技術(shù)相互聯(lián)動與協(xié)調(diào)來支持用戶對社團的解釋和調(diào)整。

社團解釋是從拓撲空間到語義空間的操作，用戶從算法所發(fā)現(xiàn)的社團結(jié)構(gòu)、社團內(nèi)部及社團之間的拓撲連接關系出發(fā)，分析社團的語義信息，來進一步解釋社團。社團調(diào)整是從語義空間到拓撲空間的操作，用戶從社團的語義信息出發(fā)，發(fā)現(xiàn)語義信息與社團結(jié)構(gòu)之間的沖突，并通過調(diào)整節(jié)點所處的社團以及合并社團等操作來調(diào)整社團結(jié)構(gòu)。

圖2：社團可視分析系統(tǒng)界面

4 社團可視分析系統(tǒng)的設計

社團可視分析系統(tǒng)主要包括網(wǎng)絡拓撲結(jié)構(gòu)及社團可視化概覽圖、社團內(nèi)部拓撲連接視圖、社團之間拓撲連接視圖、語義視圖等四個主要視圖，其系統(tǒng)界面如圖2所示。

4.1 拓撲空間

社團可視分析系統(tǒng)的拓撲空間主要包括了社團發(fā)現(xiàn)算法、網(wǎng)絡拓撲結(jié)構(gòu)及社團可視化概覽圖（圖2a）、社團內(nèi)部拓撲連接視圖（圖2b）以及社團之間的拓撲連接視圖（圖2c）。

4.1.1 社團發(fā)現(xiàn)算法

社團可視分析系統(tǒng)中采用了Fast Unfolding算法，選擇該算法是由于它適用于挖掘較大網(wǎng)絡數(shù)據(jù)中的社團結(jié)構(gòu)。它是一種基于模塊度優(yōu)化的算法，該類算法的目標就是通過不斷地迭代來劃分社團，使得模塊度不斷增大。Fast Unfolding算法主要包括以下兩個主要步驟：

第一個步驟是模塊優(yōu)化，它通過將網(wǎng)絡中的每個節(jié)點劃分到與其連接的節(jié)點所在的社團中，使得模塊度不斷增大；

第二個步驟是社團聚合，它將第一個步驟中劃分出的社團聚合成為一個節(jié)點，重新構(gòu)造網(wǎng)絡。

算法不斷迭代重復以上過程，直到網(wǎng)絡的結(jié)構(gòu)不再變化為止。

本文在拓撲空間中采用了Fast unfolding社團發(fā)現(xiàn)算法，但是本文的方法也同樣適用于其他類似的社團發(fā)現(xiàn)算法。然而不同算法的運行效率各不相同，進而有可能會對系統(tǒng)的響應時間有所影響。

4.1.2 網(wǎng)絡拓撲結(jié)構(gòu)及社團可視化概覽圖

本系統(tǒng)的拓撲空間設計遵循了“總覽為先，縮放過濾，按需查看細節(jié)”的原則。網(wǎng)絡拓撲結(jié)構(gòu)及社團可視化概覽圖（圖2a）為用戶提供了社團分析的總覽及上下文，社團內(nèi)部拓撲連接視圖（圖2b）以及社團之間拓撲連接視圖（圖2c）提供了分析過程中的細節(jié)信息。

網(wǎng)絡整體的拓撲結(jié)構(gòu)在本系統(tǒng)中采用了節(jié)點鏈接表示法，為了能夠適應大圖的布局，本文采用了YiFan Hu力導向布局方法，該布局不僅時間效率較高而且能夠很好地將分屬于不同社團的節(jié)點分散開來。同時，為了在概覽圖中區(qū)分不同的社團，系統(tǒng)中對社團使用顏色進行編碼。

4.1.3 社團內(nèi)部拓撲連接視圖

在網(wǎng)絡拓撲空間的設計中，系統(tǒng)采用節(jié)點鏈接圖和鄰接矩陣結(jié)合的布局方式，由于社團內(nèi)部節(jié)點之間的聯(lián)系緊密，所以用戶很難在節(jié)點鏈接圖中快速、準確地查看它們之間的聯(lián)系。鄰接矩陣在表達緊密連接的圖形數(shù)據(jù)時，空間利用率也比較高。

社團可視分析系統(tǒng)中設計了社團內(nèi)部拓撲連接視圖來查看焦點社團內(nèi)節(jié)點之間連接邊的具體細節(jié)信息，該視圖采用了鄰接矩陣的可視化技術(shù)。鄰接矩陣的每一行和每一列都表示一個節(jié)點，每一個單元都表示兩個節(jié)點之間連接情況。該視圖還提供了豐富的交互功能。用戶可以通過點擊每個節(jié)點來查看該節(jié)點相關的語義信息。用戶也可以通過點擊一個單元格來查看與邊相關聯(lián)的語義信息。

4.1.4 社團之間拓撲連接視圖

社團之間拓撲連接視圖顯示了不同社團之間的關系。社團之間的關系在社團的分析過程中也非常重要，用戶通過分析社團之間的關系可以獲得下一步調(diào)整社團的見解。如用戶發(fā)現(xiàn)兩個社團之間的聯(lián)系比較緊密，而且他們的語義也相近，則可以合并這兩個社團。用戶通過社團之間的聯(lián)系還可以找到了那些社團邊界上的關鍵節(jié)點，正式這些關鍵節(jié)點促進了社團之間的聯(lián)系。

4.2 語義空間

語義空間的語義可視化視圖顯示了網(wǎng)絡數(shù)據(jù)的相關語義信息，如在電子郵件網(wǎng)絡中，語義信息可以指用戶之間收發(fā)電子郵件的主題信息。在該視圖中，系統(tǒng)采用了氣泡圖來表示不同的語義信息，氣泡的大小表示語義主題詞出現(xiàn)的頻率。用戶可以通過交互在如下所示的不同層次下查看網(wǎng)絡數(shù)據(jù)的語義信息。

在全局層次下，用戶可以查看整個網(wǎng)絡中的語義信息，如整個電子郵件數(shù)據(jù)的主題。

在社團層次下，用戶可以查看每一個社團的語義信息，如技術(shù)部工作人員之間的電子郵件主題。

在跨社團層次下，用戶可以查看社團之間聯(lián)系的信息，如查看技術(shù)部和財務部之間收發(fā)電子郵件的主題。

在節(jié)點層次下，用戶可以查看每一個節(jié)點相關的信息，如查看某個部門的某個工作人員收發(fā)電子郵件的主題。

在跨節(jié)點層次下，用戶可以看兩個鄰接的節(jié)點之間聯(lián)系的信息，如查看網(wǎng)絡中兩個工作人員之間收發(fā)電子郵件的主題。

在不同層次上分析網(wǎng)絡的語義信息，可以幫助用戶解釋社團結(jié)構(gòu)。除此之外，用戶點擊每個主題相應的氣泡也可以查看與該主題相關的節(jié)點和社團，即實現(xiàn)從語義信息到拓撲信息的分析。這種從語義到拓撲的分析還可以幫助用戶進一步調(diào)整社團，如在某個社團中發(fā)現(xiàn)了某個節(jié)點與其他節(jié)點相關的語義不同，則這個節(jié)點有可能不屬于這個社團。

5 結(jié)論與展望

本文將網(wǎng)絡的拓撲信息與語義信息融合起來，提出了一種網(wǎng)絡社團結(jié)構(gòu)可視分析的方法，該方法支持用戶對社團結(jié)構(gòu)的解釋和調(diào)整。本文主要是針對靜態(tài)社團，很多網(wǎng)絡數(shù)據(jù)通常還包括時間戳，我們可以將本文的方法進一步延伸至動態(tài)社團的可視分析上。

更正

茲有盧云宏、周世平、于京艷同志發(fā)表在《電子技術(shù)與軟件工程》雜志2019年12月上半月刊第233頁中《新教育模式下程序設計課程體系的構(gòu)建與實踐》一文，原基金項目：煙臺大學校級教改項目“計算機專業(yè)試題庫建設與應用”（jyxm2016022）更正為：煙臺大學校級教改項目“新教育模式下程序設計項目實訓課程的教學運行模式研究”（jyxm2019023）。

《電子技術(shù)與軟件工程》編輯部

2019年12月