□ 李世亮

JUNG：一種實現(xiàn)社會網(wǎng)絡(luò)分析自動化分析的框架

□ 李世亮

社會網(wǎng)絡(luò)分析在許多研究領(lǐng)域開始用于網(wǎng)絡(luò)社區(qū)中人際交流的研究，但目前的研究大多是基于手工數(shù)據(jù)收集和分析，只能進行靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)的分析。JUNG提供了一種公共和可擴展的框架來實現(xiàn)數(shù)據(jù)的建模，分析和可視化展示并能夠被繪制成圖形或網(wǎng)絡(luò)，可以用于社會網(wǎng)絡(luò)分析、Web流量分析、圖論的理論推導(dǎo)以及關(guān)系類型數(shù)據(jù)的數(shù)據(jù)挖掘等等。文章介紹了JUNG的基本原理，以及如何利用JUNG在網(wǎng)絡(luò)社區(qū)中實現(xiàn)自動化的社會網(wǎng)絡(luò)分析和可視化。

JUNG；社會網(wǎng)絡(luò)分析；可視化；聚類；最短路徑

一、研究背景

自從人類學(xué)家Barnes（1954）首次使用“社會網(wǎng)絡(luò)”的概念分析挪威某漁村的社會結(jié)構(gòu)以來，社會網(wǎng)絡(luò)分析就被視為是研究社會結(jié)構(gòu)的最簡單明了、最具有說服力的研究視角之一（丁晉，2008）。

社會網(wǎng)絡(luò)分析來自社會計量學(xué)、群體動力學(xué)和圖論三個方面的基礎(chǔ)理論（王陸，2008）。上個世紀(jì)30年代，莫雷諾首先發(fā)明了利用社群圖(Sociogram)來表達社會結(jié)構(gòu)和形式特征的方法，區(qū)分領(lǐng)導(dǎo)者和孤立者，揭示出不對稱性和互惠性，并用圖來展示關(guān)聯(lián)渠道。Lewin等人認為，社會空間的結(jié)構(gòu)特征是可以用拓撲學(xué)(Topology)和集合論(SetTheory)中的數(shù)學(xué)分析技術(shù)來分析的。由此發(fā)展起來的群體動力學(xué)認為，全部社會場都是由各種力量構(gòu)成的場，這些力量作用于群體的成員，并塑造著他們的行動和經(jīng)驗。卡特賴特(Cartwright)和數(shù)學(xué)家哈拉里 (Harary)共同開創(chuàng)了圖論(Graph Theory)，并開展了圖論在群體行為方面的系列研究，突破了認知心理學(xué)以個體認知平衡為核心的研究，而轉(zhuǎn)向以社會群體中的人際關(guān)系平衡為核心的研究。社群圖、小團體分析等是社會網(wǎng)絡(luò)分析的常用方法（王陸，2009）。

近年來，很多學(xué)者運用社會網(wǎng)絡(luò)分析方法分析基于網(wǎng)絡(luò)的虛擬學(xué)習(xí)社區(qū)和學(xué)習(xí)共同體成員的行為關(guān)系與活動，如胡勇等(2006)對異步網(wǎng)絡(luò)協(xié)作學(xué)習(xí)知識構(gòu)建的研究、陳向東等(2008)對在線協(xié)作學(xué)習(xí)的研究、馮銳 （2009） 對攝影社群的研究以及易明（2010）對社會化標(biāo)簽網(wǎng)絡(luò)的研究等。社會網(wǎng)絡(luò)作為一個資源和知識交換的主要渠道，在虛擬學(xué)習(xí)社區(qū)中扮演了支撐的角色 (Cho，Stefanone， &Gay，2002)。社會網(wǎng)絡(luò)改變了人們將社會看作是由離散的行動者所組成的認識，而將社會看做由行動者及其擁有的關(guān)系組成的，這一關(guān)系范式使得對關(guān)系的研究從直接陳述的方法轉(zhuǎn)變?yōu)楦鷦拥膶ι鐣拥拿枋?Felmlee，2003)。社會網(wǎng)絡(luò)分析方法可以使研究者更關(guān)注虛擬學(xué)習(xí)社區(qū)中的參與者及其關(guān)系圖式，更加清晰的理解在已經(jīng)完成的教育模式中發(fā)生了什么，方便地發(fā)現(xiàn)社區(qū)成員新的行為圖式、社會應(yīng)用和結(jié)構(gòu)成果。社會網(wǎng)絡(luò)分析甚至可以支持預(yù)測、計劃和設(shè)計更好的虛擬學(xué)習(xí)社區(qū)社會或技術(shù)功能與環(huán)境的實現(xiàn)（王陸，2009）。

然而，在社會網(wǎng)絡(luò)分析方法的應(yīng)用中也發(fā)現(xiàn)了一些不足。由于整體網(wǎng)絡(luò)數(shù)據(jù)收集難度很大，所以一般社會網(wǎng)絡(luò)分析都無法采用大樣本隨機抽樣，只能采用便利抽樣 (Convenient Sampling)，從而造成社會網(wǎng)絡(luò)分析研究具有很強的個案特征，很難推論出普遍適用的原理和原則（王陸，2009）。在實現(xiàn)手段上，社會網(wǎng)絡(luò)分析常常因只進行靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)的分析而受到批評。盡管有研究進行了基于時間序列的社會網(wǎng)絡(luò)分析模型的嘗試，但是仍然無法獲得持續(xù)的網(wǎng)絡(luò)變化數(shù)據(jù)。實現(xiàn)容易使用的動態(tài)網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的收集是社會網(wǎng)絡(luò)分析研究的一個重要發(fā)展方向（Wesserman and Faust，1994）。

二、JUNG概述

JUNG（ Java Universal Network/Graph Framework）是一個軟件包，最初由加利福尼亞大學(xué)的三位博士（Joshua O'Madahain，Danyel Fisher，Scott White）開發(fā)，它提供了一種公共和可擴展的框架來實現(xiàn)數(shù)據(jù)的建模，分析和可視化數(shù)據(jù)并能夠?qū)⑵淅L制成圖形或網(wǎng)絡(luò)。JUNG是一個基于Java的開源項目，其目的在于為開發(fā)關(guān)于圖（Graph）或網(wǎng)絡(luò)結(jié)構(gòu)（Network）的應(yīng)用程序提供一個易用、通用的基礎(chǔ)架構(gòu)。JUNG使用BSD開放源碼協(xié)議發(fā)布，使用JUNG功能調(diào)用，可以方便的構(gòu)造圖或網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用經(jīng)典算法（如聚類、最短路徑等），操作、計算并可視化數(shù)據(jù)的網(wǎng)絡(luò)圖。JUNG可以用于社會網(wǎng)絡(luò)分析、Web流量分析、圖論的理論推導(dǎo)以及關(guān)系型數(shù)據(jù)的數(shù)據(jù)挖掘等方面。

JUNG的主要特性包括以下幾個方面（O'Madahain et al.，2005）：

1.支持多種實體以及它們之間關(guān)系的表示，如有向圖、無向圖、多模圖（圖中包含一種以上的節(jié)點或者邊）、多重圖（具有重邊的圖）以及超圖（圖中包含有超邊，每一條超邊可以包含任意多個節(jié)點）。

2.支持多種機制來標(biāo)識圖、實體和關(guān)系的元數(shù)據(jù)。這一特性有助于創(chuàng)建分析工具來研究實體之間的關(guān)系，同樣也可以研究實體和關(guān)系的元數(shù)據(jù)。

3.實現(xiàn)了多個來自圖論、探索性數(shù)據(jù)分析、社會網(wǎng)絡(luò)分析和機器學(xué)習(xí)中的算法。這些算法包括常規(guī)的聚類、分解、優(yōu)化、隨機圖的生成、統(tǒng)計分析、網(wǎng)絡(luò)距離的計算、流量以及排名計算（如中心度、PageRank、HITS等）。

4.實現(xiàn)了一個可視化的框架，可以支持交互式的網(wǎng)絡(luò)數(shù)據(jù)瀏覽。用戶可以自行選擇圖的布局和渲染的算法，或者利用框架來生成自己的渲染算法。

5.JUNG過濾機制可以支持抽取網(wǎng)絡(luò)數(shù)據(jù)集的某個子集，這一特性允許用戶在整個網(wǎng)絡(luò)數(shù)據(jù)集中呈現(xiàn)他們所關(guān)注的那部分?jǐn)?shù)據(jù)，或者特定算法的篩選結(jié)果。

以上特性使得JUNG成為了一個理想的呈現(xiàn)和分析關(guān)系數(shù)據(jù)集的平臺。利用JUNG可以開發(fā)獨立程序或者作為嵌入在某個網(wǎng)絡(luò)平臺上的工具來操作關(guān)系圖或者網(wǎng)絡(luò)數(shù)據(jù)。它可以用簡單的代碼片段來測試一個想法，或者搭建一個擁有復(fù)雜圖形界面的分析工具。JUNG是一個可以支持不同工具的Java庫，如果要使用JUNG需要具備一定的Java編程知識。使用一個庫而不是現(xiàn)成的軟件工具的優(yōu)勢在于網(wǎng)絡(luò)分析過程可以根據(jù)不同的目的來自行編程。這個優(yōu)點使得JUNG適合構(gòu)建基于Web的Java Applet小程序，從而可以動態(tài)的從網(wǎng)絡(luò)中讀取并分析和顯示關(guān)系數(shù)據(jù)。

圖1 JUNG中圖的繼承關(guān)系

三、JUNG的設(shè)計原則

JUNG使用Java語言來設(shè)計，利用了Java的接口、抽象類和實現(xiàn)類來進行圖的原型定義。這樣進行抽象設(shè)計有三方面優(yōu)勢：

1.可以將設(shè)計與實現(xiàn)分離，這使得JUNG成為一種處理關(guān)系數(shù)據(jù)的通用語言。例如，Archetype-Graph接口指定了所有圖都具備的特性，但是不包含這些特性如何實現(xiàn)具體算法。

2.利用Java面向?qū)ο蟮奶匦裕贸橄箢惡徒涌趤韺崿F(xiàn)繼承關(guān)系。例如，Graph類定義了所有圖的通用接口，它包含由兩個節(jié)點連接的邊。Graph是ArchetypeGraph的子接口，這意味著它包含所有ArchetypeGraph的屬性，并且它還具有一些自己獨特的屬性。

3.使用方法簽名來避免用戶傳入錯誤的參數(shù)，允許用戶在編譯階段就發(fā)現(xiàn)類似的錯誤，而不是等到代碼運行時才發(fā)現(xiàn)。JUNG提供的方法避免了限定在某個內(nèi)部方法上，用戶可以使用自己的實現(xiàn)方法。

圖、節(jié)點、邊都有一些抽象出來的屬性和它們可以進行的操作。如圖1所示，JUNG定義了圖的繼承關(guān)系。JUNG定義的節(jié)點和邊只能屬于一個圖，這樣可以方便用戶查詢某個節(jié)點的鄰居節(jié)點。同時意味著節(jié)點和邊的屬性中有圖的標(biāo)識符，這種屬性可以被用來計算兩個指定節(jié)點之間的最短路徑。

接口ArchetypeGraph定義了包含節(jié)點和邊的圖，并且定義了若干訪問和修改這些集合的方法。Hypergraph和Graph接口繼承了ArchetypeGraph接口，并且相應(yīng)的定義了它們的邊只能包含兩個節(jié)點。這兩個接口中還定義了增加節(jié)點和邊的方法，這些方法被定義在這里而不是ArchtypeGraph中，主要原因是為了在編譯環(huán)節(jié)中檢查節(jié)點和邊的類型是否正確。Graph還有一些子接口，定義了只包含有向邊和無向邊的特殊圖。SparseGraph類實現(xiàn)了Graph接口中定義的方法，適合于稀疏圖的相關(guān)運算。

四、JUNG的算法

JUNG提供了多種關(guān)系網(wǎng)絡(luò)的算法，下面分類進行簡單的介紹。

1.排序

排序算法可以為某個節(jié)點或者邊通過某種法則計算出能夠反應(yīng)在網(wǎng)絡(luò)中的結(jié)構(gòu)特性的一個屬性值。這些法則通常用于測量某個節(jié)點或邊的影響力、權(quán)威度或者中心度。這些算法將輸入解釋為馬爾可夫網(wǎng)，即一個有向權(quán)重圖。圖中的節(jié)點表示狀態(tài)，邊表示可能的狀態(tài)轉(zhuǎn)移，邊的權(quán)重表示轉(zhuǎn)移的概率。

JUNG中提供的排序算法包括（O'Madahain et al.， 2005） 四類：BetweennessCentrality算法通過計算通過該節(jié)點和邊的最短路徑數(shù)作為排序依據(jù)；PageRank算法通過改進的馬爾可夫網(wǎng)絡(luò)方法計算節(jié)點的平穩(wěn)概率；HITS算法根據(jù)節(jié)點在圖中的中心性來評分；VoltageRanker算法將網(wǎng)絡(luò)看做是電子線路，并給出每個節(jié)點在該電路中的剩余電壓值。

2.聚類和區(qū)塊模型

對某些對象進行聚類通常是通過這些對象的某些相似屬性來進行。在社會網(wǎng)絡(luò)中，相似性是指圖的拓撲屬性，例如連接性，也可能是網(wǎng)絡(luò)中節(jié)點或邊的屬性。JUNG提供的聚類算法包括四類：EdgeBetweennessCluster算法通過計算邊的中介性來進行聚類；WeakComponentCluster算法主要用來找出一個給定圖中所有弱對象，弱對象是指某個子圖中至少包含有一條無向邊；VoltageCluster算法通過找出網(wǎng)絡(luò)中擁有相近“電壓”值的節(jié)點來進行聚類。

在社會網(wǎng)絡(luò)分析領(lǐng)域中，如果兩個節(jié)點同時與某些節(jié)點相接，那么它們被認為是結(jié)構(gòu)相等的。JUNG提供了BlockModelling算法，該算法可以找出圖中結(jié)構(gòu)相等的節(jié)點。這些算法可用來在圖中找出重復(fù)對象，或者簡化圖形的顯示（例如可以將某個大型復(fù)雜網(wǎng)絡(luò)進行聚類，把同類的節(jié)點顯示為一個節(jié)點）。

3.拓撲算法及最短路徑

此類算法主要針對圖的拓撲屬性進行計算。JUNG提供的BFSDistanceLabeler拓撲算法用來標(biāo)識出每個節(jié)點到圖中某個節(jié)點的無權(quán)重最短路徑；KNeighborhoodExtractor算法返回某個節(jié)點的k階鄰居節(jié)點的集合；DijkstraShortestPath算法能夠計算出圖中從某個節(jié)點到其他節(jié)點的帶權(quán)重的最短路徑。

在社會網(wǎng)絡(luò)分析中，最短路徑算法可以方便的找出網(wǎng)絡(luò)社區(qū)中任意兩個人之間的最短認識路徑，從而為網(wǎng)絡(luò)社區(qū)的交友提供有效的工具。

五、利用JUNG來進行社會網(wǎng)絡(luò)分析

1.關(guān)系數(shù)據(jù)的輸入

JUNG框架本身提供了隨機圖的生成算法，包括BarabasiAlbertGenerator、EppsteinPowerLaw-Generator、 KleinbergSmallWorldGenerator， 這 些隨機圖可以用于某些理論的驗證和推演。除此之外，JUNG還支持文本格式和數(shù)據(jù)庫的關(guān)系數(shù)據(jù)，其中文本格式支持Pajek的文件格式和GraphML格式。

在實際應(yīng)用中可以采用文本方式來輸入關(guān)系數(shù)據(jù)，如在某個學(xué)習(xí)論壇中，采集發(fā)帖和回帖的數(shù)據(jù)后，通過一個后臺的Servlet輸出如下格式的關(guān)系數(shù)據(jù)：

上面的例子中包含了6個節(jié)點（參與討論的人）和6條邊（論壇回復(fù)關(guān)系）。

2.關(guān)系數(shù)據(jù)的分析與可視化

由于JUNG是用Java語言實現(xiàn)的，因此可以方便的利用Java語言的網(wǎng)絡(luò)功能獲得關(guān)系數(shù)據(jù)。下面是獲得上述關(guān)系數(shù)據(jù)的方法示例。

圖的可視化表現(xiàn)是JUNG最為吸引人的地方。JUNG可視化功能的基本組件是BasicVisualization-Server類，該類是Swing Jpanel的一個子類，可以放置到任何一個Swing的容器對象中。要構(gòu)造一個BasicVisualizationServer類，首先需要了解JUNG中“布局（Layout）”的概念。一個Layout接口的實現(xiàn)，實際上就是要告訴JUNG如何來繪制圖的頂點和邊，即確定其在圖形界面上的坐標(biāo)位置(x， y)。使用預(yù)定義的Layout（例如CircleLayout）可以方便的完成這個工作而不需要繁雜的手工編碼。圖g的可視化表現(xiàn)可以分以下4個步驟完成：

//1.初始化圖g

//2.使用該圖創(chuàng)建布局對象

Layout

//3.使用布局對象創(chuàng)建BasicVisualizationServer對象

BasicVisualizationServer

//4.將上述對象放置在一個Swing容器中并顯示之

在網(wǎng)絡(luò)社區(qū)中可以通過嵌入Java Applet小程序的方式來呈現(xiàn)社會網(wǎng)絡(luò)分析的結(jié)果。嵌入Applet的示例代碼如下：

3.利用JUNG進行社會網(wǎng)絡(luò)分析的幾個例子

（1） 聚類分析。如圖2所示，通過聚類分析，我們可以發(fā)現(xiàn)在社區(qū)中的哪些成員形成了小團體，并且可以找到在小團體中誰處于中心位置。

圖2 聚類分析

（2）集中度分析。在圖3中，通過集中度分析，我們可以給出某個團體成員的集中度分布情況，這對于社區(qū)管理者、研究者和參與者本身都是很有價值的工具。

圖3 集中度分析

（3）最短路徑分析。如圖4所示，最短路徑分析可以自動找到某兩個用戶之間的最短路徑，從而可以為社區(qū)成員的交友提出了很好的建議。

圖4 最短路徑分析

以上社會網(wǎng)絡(luò)分析都是內(nèi)建在網(wǎng)絡(luò)社區(qū)內(nèi)部的，隨著成員交互關(guān)系的演進可以持續(xù)的呈現(xiàn)社區(qū)的交互關(guān)系，也可以根據(jù)不同的目的設(shè)計和實現(xiàn)更多的關(guān)系可視化工具。通過以上分析，可以得出如下結(jié)論：利用JUNG框架可以實現(xiàn)網(wǎng)絡(luò)社區(qū)內(nèi)全關(guān)系集合的社會網(wǎng)絡(luò)分析，即網(wǎng)絡(luò)社區(qū)內(nèi)的全部交互關(guān)系都可以作為JUNG的數(shù)據(jù)源，利用程序自動的實現(xiàn)社會網(wǎng)絡(luò)分析。其次，JUNG框架可以通過編程來呈現(xiàn)社會網(wǎng)絡(luò)關(guān)系隨著時間演變的過程。第三，通過聚類分析可以發(fā)現(xiàn)群組和核心參與者，有利于社區(qū)管理者進行活動的組織。最后，通過最短路徑分析可以幫助找到好友的最短途徑，進而增強社區(qū)成員的社區(qū)感并方便地找到同伴。

[1]Barnes,J.A.,Class and committees in a Norwegian island parish[J].Human relations,7(1),1954.pp.39.

[2]Cho,H.,Stefanone,M.,Gay,G..Social information sharing in a CSCL community[A].In Proceedings of 2002 ACM CSCL conference[C].Boulder,USA:Lawrence Elbaum Associates,2002.pp43-53.

[3]J.O’Madadhain，D.Fisher，P.Smyth，S.White，and Y.B.Boey，Analysis and visualization of network data using JUNG[J]，Journal of Statistical Software，vol.10，2005，pp.1–35.

[4]Wesserman and Faust，Social Network Analysis:Methods and Applications[M]， Cambridge:Cambridge University Press，1994，pp.730.

[5]陳向東.基于社會網(wǎng)絡(luò)分析的在線協(xié)作學(xué)習(xí)研究[J].中國電化教育，2006，（10）：27.

[6]丁晉.教師遠程研修共同體研究——以2006年教育部“中小學(xué)教師新課程國家級遠程培訓(xùn)”為例[D].碩士，南京：南京師范大學(xué)，2008：9.

[7]馮銳.博聯(lián)社攝影社群的社會網(wǎng)絡(luò)分析[J].中國電化教育，2006，（9）：100.

[8]胡勇，王陸.異步網(wǎng)絡(luò)協(xié)作學(xué)習(xí)中知識建構(gòu)的內(nèi)容分析和社會網(wǎng)絡(luò)分析[J].電化教育研究，2006，（11）：30-31.

[9]王陸.信息化教育研究中的新內(nèi)容：互動關(guān)系研究[J].電化教育研究，2008（1）：17.

[10]王陸.虛擬學(xué)習(xí)社區(qū)的社會網(wǎng)絡(luò)分析[J].中國電化教育，2009，（2）：5-9.

[11]易明.基于社會網(wǎng)絡(luò)分析的社會化標(biāo)簽網(wǎng)絡(luò)分析與個性化信息服務(wù)研究[J].中國圖書館學(xué)報，2010，（2）：110.

2011－02－25

李世亮，在讀博士，助理研究員，北京師范大學(xué)遠程教育研究中心（100875）。

責(zé)任編輯 柯 南

G434

B

1009—458x（2011）05—0086—05