基于LabVIEW的社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件

周 茜，劉海洋, 周煜南，陳祺盈, 劉歌群

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

基于LabVIEW的社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件

周 茜，劉海洋, 周煜南，陳祺盈, 劉歌群

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

社團(tuán)結(jié)構(gòu)識(shí)別是網(wǎng)絡(luò)結(jié)構(gòu)分析的基本環(huán)節(jié)，文中基于LabVIEW開(kāi)發(fā)了一種具有識(shí)別結(jié)果演示功能的社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件。該軟件利用LabVIEW組織實(shí)驗(yàn)數(shù)據(jù)、規(guī)劃人機(jī)界面、顯示識(shí)別結(jié)果并管理操作流程，利用Matlab進(jìn)行社團(tuán)結(jié)構(gòu)識(shí)別算法的計(jì)算。在軟件的開(kāi)發(fā)過(guò)程中，識(shí)別結(jié)果的顯示采用屬性節(jié)點(diǎn)技術(shù)，操作流程的管理采用有限狀態(tài)機(jī)技術(shù)，社團(tuán)結(jié)構(gòu)識(shí)別算法的計(jì)算采用LabVIEW與Matlab混合編程技術(shù)。該軟件實(shí)現(xiàn)了譜平分法、GN算法和Newman算法共3種典型算法的計(jì)算與結(jié)果顯示，給出了軟件的運(yùn)行效果和算法之間的對(duì)比圖。

LabVIEW；社團(tuán)結(jié)構(gòu)；譜平分法；GN算法；Newman算法

隨著對(duì)網(wǎng)絡(luò)科學(xué)研究的深入，研究者發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有一個(gè)相同的性質(zhì)，即社團(tuán)結(jié)構(gòu)，也就是說(shuō)整個(gè)網(wǎng)絡(luò)是由若干個(gè)“群(Group)”或“團(tuán)(Cluster)”構(gòu)成[1]。每一個(gè)群內(nèi)部的節(jié)點(diǎn)之間連接相對(duì)緊密，但各個(gè)群之間的連接相對(duì)稀疏。由于網(wǎng)絡(luò)規(guī)模的龐大和系統(tǒng)連接的多樣性使得研究其結(jié)構(gòu)和功能變得復(fù)雜，因此揭示網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，是了解網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)和功能之間的對(duì)應(yīng)關(guān)系，降低對(duì)復(fù)雜系統(tǒng)認(rèn)識(shí)難度的方法[2-4]。目前，社團(tuán)結(jié)構(gòu)分析已廣泛應(yīng)用于生物學(xué)、計(jì)算機(jī)科學(xué)和社會(huì)學(xué)等多個(gè)領(lǐng)域中。

目前針對(duì)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的分析，多借助Pajek、NetworkX、CFinder和Igraph等仿真軟件。然而這些仿真軟件并不能動(dòng)態(tài)地演示社團(tuán)結(jié)構(gòu)識(shí)別的過(guò)程，因此提供一種面向社團(tuán)結(jié)構(gòu)識(shí)別過(guò)程可視化的展示工具已成為一種需要[5]。

本文設(shè)計(jì)開(kāi)發(fā)了基于LabVIEW的社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件，不僅能直觀展示社團(tuán)結(jié)構(gòu)識(shí)別的動(dòng)態(tài)過(guò)程，而且還能體現(xiàn)社團(tuán)結(jié)構(gòu)參數(shù)對(duì)社團(tuán)結(jié)構(gòu)識(shí)別的影響，為社團(tuán)結(jié)構(gòu)識(shí)別過(guò)程可視化提供了一種較好的展示工具。

1 社團(tuán)結(jié)構(gòu)識(shí)別算法

社團(tuán)結(jié)構(gòu)的研究已有較長(zhǎng)的歷史，研究者提出了一系列算法來(lái)尋找復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。其中經(jīng)典的社團(tuán)結(jié)構(gòu)識(shí)別算法[6]有：Kernighan-Lin算法、譜平分法、GN算法、Newman算法和派系過(guò)濾算法等。本文著重分析了譜平分法、GN算法和Newman算法。

1.1 譜平分法

譜平分法是Pothen等人基于圖的Laplace矩陣的譜特征提出的一種將網(wǎng)絡(luò)劃分為兩個(gè)社區(qū)的二分算法[7]。譜平分法基礎(chǔ)理論是[8-9]：假設(shè)G是一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向圖，則G的Laplace矩陣是一個(gè)n×n維的對(duì)稱矩陣L。矩陣L表示成L=K-A，其中K是一個(gè)對(duì)角矩陣，其對(duì)角線上的元素就對(duì)應(yīng)各個(gè)節(jié)點(diǎn)的度，而A則為該網(wǎng)絡(luò)的連接矩陣。Laplace矩陣L是實(shí)對(duì)稱矩陣，其非退化的特征值對(duì)應(yīng)的特征向量總是正交的。因此除去最小特征值，矩陣L的其他特征值對(duì)應(yīng)的特征向量總是包含正負(fù)兩種元素。當(dāng)網(wǎng)絡(luò)只有兩個(gè)社團(tuán)時(shí)，根據(jù)第二小特征值對(duì)應(yīng)的特征向量中的元素對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分類。其中，正元素對(duì)應(yīng)的節(jié)點(diǎn)屬于一個(gè)社團(tuán)，負(fù)元素對(duì)應(yīng)的節(jié)點(diǎn)則屬于另一個(gè)社團(tuán)。

基于上述譜平分法的基礎(chǔ)理論，該實(shí)驗(yàn)軟件實(shí)現(xiàn)譜平分法的基本流程是：

步驟1構(gòu)建圖G的 Laplace矩陣L；

步驟2計(jì)算矩陣L的特征值和特征向量，求取除0外的最小特征值對(duì)應(yīng)的特征向量l；

步驟3將特征向量l中正元素對(duì)應(yīng)的節(jié)點(diǎn)放入一個(gè)數(shù)組，負(fù)元素對(duì)應(yīng)的節(jié)點(diǎn)放入另一個(gè)數(shù)組，生成兩個(gè)社團(tuán)；

步驟4根據(jù)模塊度公式[10]，計(jì)算兩個(gè)社團(tuán)的模塊度。公式中 表示模塊度； 表示矩陣L對(duì)角線元素； 表示與第 個(gè)社團(tuán)中的節(jié)點(diǎn)相連的邊在所有邊中所占的比例；

步驟5對(duì)Q值較大的社團(tuán)進(jìn)行平分，重復(fù)步驟1～步驟4，直至完成要求的社團(tuán)結(jié)構(gòu)識(shí)別個(gè)數(shù)。

1.2 GN算法

GN算法是一種分裂算法，不斷從網(wǎng)絡(luò)中移除邊，直至將所有的邊都刪除。GN算法的基本思想[10-11]是：

(1)計(jì)算網(wǎng)絡(luò)中所有邊的介數(shù)；

(2)找到介數(shù)最大的邊并將它從網(wǎng)絡(luò)中移除；

(3)重復(fù)步驟(2)，直至網(wǎng)絡(luò)中所有的邊均被移除。

基于上述GN算法的基礎(chǔ)思想，該實(shí)驗(yàn)軟件實(shí)現(xiàn)GN算法的基本流程為：

步驟1初始化。初始化網(wǎng)絡(luò)為一個(gè)社團(tuán)，構(gòu)建網(wǎng)絡(luò)的鄰接矩陣A和n×n維的零數(shù)組B；

步驟2移除邊。計(jì)算網(wǎng)絡(luò)中所有邊的介數(shù)，存入數(shù)組B，尋找數(shù)組B中的邊介數(shù)最大值。將A中邊介數(shù)最大值所對(duì)應(yīng)節(jié)點(diǎn)位置變?yōu)?，更新鄰接矩陣A。判斷更新后的鄰接矩陣A是否連通。如果連通，則找出連通量存入數(shù)組C，并重新計(jì)算移除一條邊后的新網(wǎng)絡(luò)的邊介數(shù)；

步驟3終止。重復(fù)步驟2，直至每個(gè)節(jié)點(diǎn)成為一個(gè)社團(tuán)。在此過(guò)程中，社團(tuán)每分裂一次，計(jì)算一次模塊度值。

1.3 Newman算法

Newman算法是一種凝聚算法， Newman算法[12-14]基本思想如下：

(1)初始化網(wǎng)絡(luò)為n個(gè)社團(tuán)，即每個(gè)節(jié)點(diǎn)就是一個(gè)獨(dú)立社團(tuán)。初始網(wǎng)絡(luò)的eij和a初始化為

(1)

a=ki/2m

(2)

其中,eij表示網(wǎng)絡(luò)中連接兩個(gè)不同社團(tuán)節(jié)點(diǎn)的邊在所有邊中所占的比例；m為網(wǎng)絡(luò)總邊數(shù)；ki為節(jié)點(diǎn)i的度；

(2)依次合并有邊相連的社團(tuán)對(duì)，并計(jì)算合并后的模塊度增量

ΔQ=eij+eji-2aiaj=2(eij-aiaj)

(3)

每次合并應(yīng)沿著使Q增大最多的方向進(jìn)行；

(3)重復(fù)執(zhí)行步驟(2)，不斷合并社團(tuán),直到整個(gè)網(wǎng)絡(luò)都合并成為一個(gè)社團(tuán)。

基于上述Newman算法的基礎(chǔ)思想，該實(shí)驗(yàn)軟件實(shí)現(xiàn)Newman算法的流程為：

步驟1初始化。初始化為n個(gè)社團(tuán)，將n個(gè)節(jié)點(diǎn)分別放入n個(gè)數(shù)組。模塊度值Q=0，按照式(1)和式(2)進(jìn)行初始網(wǎng)絡(luò) 和 值的設(shè)定；

步驟2合并。構(gòu)建一維零數(shù)組B，根據(jù)式(3)計(jì)算模塊度增量，將計(jì)算結(jié)果存入數(shù)組B中。求取數(shù)組B中最大值所對(duì)應(yīng)的節(jié)點(diǎn)，然后將與該節(jié)點(diǎn)有邊相連的社團(tuán)進(jìn)行合并。即將兩個(gè)數(shù)組合并為一個(gè)數(shù)組，生成新的數(shù)組(新的社團(tuán))；

步驟3終止。重復(fù)執(zhí)行步驟2，不斷合并數(shù)組，直到所有的數(shù)組都合并成為一個(gè)數(shù)組(即整個(gè)網(wǎng)絡(luò)都合并成為一個(gè)社團(tuán))。

2 設(shè)計(jì)方案

根據(jù)上述3種社團(tuán)結(jié)構(gòu)識(shí)別算法，本文將進(jìn)行社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件的方案設(shè)計(jì)。

2.1 設(shè)計(jì)思想

本文將LabVIEW與Matlab進(jìn)行混合編程，利用LabVIEW軟件提供可視化界面,并在LabVIEW中使用Matlab的數(shù)值運(yùn)算功能，提高編程效率。

社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件的設(shè)計(jì)思想如下所述：

(1)利用LabVIEW構(gòu)建輸入模塊和顯示模塊。輸入模塊包含網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣和社團(tuán)結(jié)構(gòu)參數(shù)設(shè)置模塊；顯示模塊包含網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖、社團(tuán)構(gòu)識(shí)別數(shù)據(jù)顯示模塊和模塊度值顯示模塊；

(2)利用Matlab進(jìn)行譜平分法、Newman算法和GN算法的仿真；

(3)在LabVIEW中調(diào)用Matlab的ActiveX對(duì)象[15]，與Matlab中的社團(tuán)結(jié)構(gòu)識(shí)別算法模型進(jìn)行通信，實(shí)現(xiàn)LabVIEW與Matlab的混合編程。

2.2 社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件的設(shè)計(jì)

社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件設(shè)計(jì)的前面板包括5個(gè)部分，分別是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣設(shè)置區(qū)、社團(tuán)結(jié)構(gòu)參數(shù)設(shè)置區(qū)、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖顯示區(qū)、社團(tuán)結(jié)構(gòu)識(shí)別數(shù)據(jù)顯示區(qū)和模塊度值顯示區(qū)，如圖1所示。

圖1 前面板以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖生成

社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件的程序設(shè)計(jì)將實(shí)現(xiàn)下述功能：軟件運(yùn)行時(shí)進(jìn)入初始化狀態(tài)，參數(shù)設(shè)置完畢后進(jìn)入網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖生成狀態(tài)；網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖生成后，進(jìn)入社團(tuán)結(jié)構(gòu)識(shí)別狀態(tài)；社團(tuán)結(jié)構(gòu)識(shí)別完成后，自動(dòng)進(jìn)入社團(tuán)識(shí)別效果顯示狀態(tài)，并可以重新進(jìn)行參數(shù)設(shè)置；實(shí)驗(yàn)結(jié)束后，前面板將呈現(xiàn)初始化界面。為實(shí)現(xiàn)上述功能的實(shí)現(xiàn)，本文采用LabVIEW軟件自帶的設(shè)計(jì)模式-狀態(tài)機(jī)實(shí)現(xiàn)，圖2所示為軟件運(yùn)行狀態(tài)圖。

圖2 軟件運(yùn)行狀態(tài)圖

圖2中所示的狀態(tài)階段，每一狀態(tài)階段的功能和設(shè)計(jì)方法如下：

(1)初始化和參數(shù)設(shè)置階段。主要進(jìn)行網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的構(gòu)建和參數(shù)設(shè)置功能。利用LabVIEW繪制出以16個(gè)黑色圓點(diǎn)表示節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，如圖1中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖顯示區(qū)所示。同時(shí)進(jìn)行社團(tuán)結(jié)構(gòu)參數(shù)的設(shè)定，設(shè)置的兩個(gè)參數(shù)分別為：社團(tuán)結(jié)構(gòu)識(shí)別算法和社團(tuán)個(gè)數(shù)，如圖1中的社團(tuán)結(jié)構(gòu)參數(shù)設(shè)置區(qū)所示；

(2)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖生成階段。主要實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的生成。利用LabVIEW構(gòu)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣，將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣設(shè)置為16×16維的布爾型數(shù)組。數(shù)組中圓形指示燈亮則表示節(jié)點(diǎn)間有邊連接，圓形指示燈暗則表示節(jié)點(diǎn)間無(wú)邊連接，如圖1中的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣所示。將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣作為輸入，在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖中顯示網(wǎng)絡(luò)的連接關(guān)系，如圖1中的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖所示；

(3)社團(tuán)結(jié)構(gòu)識(shí)別階段。實(shí)現(xiàn)在LabVIEW中直接調(diào)用Matlab的ActiveX對(duì)象，與Matlab中的社團(tuán)結(jié)構(gòu)識(shí)別算法模型進(jìn)行通信。本階段利用LabVIEW中的Case Structure進(jìn)行社團(tuán)結(jié)構(gòu)識(shí)別算法的選擇，Case Structure中包含3個(gè)分支，3個(gè)分支分別對(duì)應(yīng)于3種社團(tuán)結(jié)構(gòu)識(shí)別算法。根據(jù)前面板選擇的社團(tuán)結(jié)構(gòu)識(shí)別算法，程序跳轉(zhuǎn)至Case Structure中相應(yīng)的分支進(jìn)行運(yùn)轉(zhuǎn)。再根據(jù)前面板社團(tuán)個(gè)數(shù)的設(shè)定，運(yùn)行社團(tuán)結(jié)構(gòu)識(shí)別程序，如圖3所示。

圖3 社團(tuán)結(jié)構(gòu)識(shí)別程序圖

圖3中，將Matlab計(jì)算的社團(tuán)識(shí)別結(jié)果和模塊度值傳遞給LabVIEW，實(shí)現(xiàn)社團(tuán)識(shí)別數(shù)據(jù)、模塊度值和模塊度值以圖的形式在實(shí)驗(yàn)軟件前面板的顯示。社團(tuán)結(jié)構(gòu)識(shí)別階段之后就直接轉(zhuǎn)至社團(tuán)識(shí)別結(jié)果顯示階；

(4)社團(tuán)識(shí)別效果顯示階段。實(shí)現(xiàn)將同社團(tuán)的節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖中以相同的節(jié)點(diǎn)顏色進(jìn)行顯示。利用LabVIEW程序?qū)⑸鐖F(tuán)結(jié)構(gòu)識(shí)別結(jié)果作為輸入，通過(guò)節(jié)點(diǎn)索引確定節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖中的位置。然后將該節(jié)點(diǎn)的顏色由黑色變?yōu)橹付伾⒃诰W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖中顯示，如圖4所示。

圖4 社團(tuán)識(shí)別效果顯示程序圖

實(shí)驗(yàn)軟件最終實(shí)現(xiàn)將一個(gè)網(wǎng)絡(luò)中同社團(tuán)的節(jié)點(diǎn)以相同的節(jié)點(diǎn)顏色進(jìn)行演示的社團(tuán)識(shí)別效果，如圖5所示。

3 社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件運(yùn)行示例

為形象展示該軟件社團(tuán)結(jié)構(gòu)識(shí)別的過(guò)程，因此設(shè)置了具有明顯社團(tuán)結(jié)構(gòu)特征的網(wǎng)絡(luò)，利用該網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)識(shí)別過(guò)程的演示，如圖1的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣所示。同時(shí)本文采用不同的社團(tuán)結(jié)構(gòu)識(shí)別算法和社團(tuán)個(gè)數(shù)，對(duì)社團(tuán)結(jié)構(gòu)識(shí)別過(guò)程進(jìn)行演示，如圖5所示。

圖5 實(shí)驗(yàn)軟件生成的社團(tuán)結(jié)構(gòu)識(shí)別效果圖

圖6 模塊度值

如圖1所示，按照設(shè)置好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣，單擊“網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖生成”按鈕，即可形成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，直觀地展示網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接關(guān)系。如圖5所示，為按照設(shè)置好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣、社團(tuán)結(jié)構(gòu)識(shí)別算法以及社團(tuán)個(gè)數(shù)，單擊“社團(tuán)識(shí)別”按鈕，顯示出的社團(tuán)結(jié)構(gòu)識(shí)別效果圖。圖5(a)、圖5(b)和圖5(c)，分別為選擇譜平分法、GN算法和Newman算法時(shí)，識(shí)別2個(gè)社團(tuán)、3個(gè)社團(tuán)和4個(gè)社團(tuán)的社團(tuán)結(jié)構(gòu)識(shí)別效果圖，網(wǎng)絡(luò)中同社團(tuán)的節(jié)點(diǎn)均以相同的節(jié)點(diǎn)顏色進(jìn)行演示。將設(shè)置好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)矩陣分別與圖5(a)、圖5(b)和圖5(c)對(duì)比可知，3種社團(tuán)結(jié)構(gòu)識(shí)別算法均是在識(shí)別3個(gè)社團(tuán)時(shí)，得到最佳社團(tuán)結(jié)構(gòu)識(shí)別效果。利用圖6模塊度值的顯示進(jìn)行驗(yàn)證，從圖6(a)、圖6(b)和圖6(c)中，發(fā)現(xiàn)3種社團(tuán)結(jié)構(gòu)識(shí)別算法均在識(shí)別3個(gè)社團(tuán)時(shí)，模塊度值最大，因此可知社團(tuán)結(jié)構(gòu)識(shí)別正確。若要結(jié)束圖5的運(yùn)行狀態(tài)，點(diǎn)擊“實(shí)驗(yàn)結(jié)束”按鈕，回到圖1所示狀態(tài)，社團(tuán)結(jié)構(gòu)識(shí)別算法以及社團(tuán)個(gè)數(shù)恢復(fù)到默認(rèn)值。

4 結(jié)束語(yǔ)

社團(tuán)結(jié)構(gòu)識(shí)別過(guò)程的可視化，能使社團(tuán)結(jié)構(gòu)的理論知識(shí)變得直觀易懂，便于學(xué)習(xí)和理解。本文首先利用Matlab進(jìn)行社團(tuán)結(jié)構(gòu)識(shí)別算法的仿真，其次通過(guò)LabVIEW搭建社團(tuán)結(jié)構(gòu)識(shí)別的可視化界面，最后將LabVIEW與Matlab混合編程，設(shè)計(jì)一套基于LabVIEW的社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件。該實(shí)驗(yàn)軟件不但能動(dòng)態(tài)演示社團(tuán)結(jié)構(gòu)識(shí)別的過(guò)程和顯示社團(tuán)結(jié)構(gòu)識(shí)別數(shù)據(jù)和模塊度值的變化，還可以靈活地改變社團(tuán)結(jié)構(gòu)識(shí)別算法，展示社團(tuán)結(jié)構(gòu)參數(shù)變化對(duì)社團(tuán)結(jié)構(gòu)識(shí)別過(guò)程的影響。因此基于LabVIEW的社團(tuán)結(jié)構(gòu)識(shí)別實(shí)驗(yàn)軟件可運(yùn)用于復(fù)雜網(wǎng)絡(luò)的實(shí)驗(yàn)教學(xué)中，幫助學(xué)習(xí)者更好的學(xué)習(xí)和理解社團(tuán)結(jié)構(gòu)的理論知識(shí)。

[1] 汪小帆,李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京:清華大學(xué)出版社,2006.

[2] 鄧智龍,淦文燕.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法[J].計(jì)算機(jī)科學(xué),2012,39(6A):103-107.

[3] Newman M E J.Detecting community structure in networks[J].The European Physical Journal B-Condensed Matter and Complex Systems,2004,38(2):321-330．

[4] 狄增如.系統(tǒng)科學(xué)視角下的復(fù)雜網(wǎng)絡(luò)研究[J].上海理工大學(xué)報(bào),2011,33(2):111-116.

[5] Wang Anjing.Network virtualization: Technologies, perspectivesand frontiers[J]. Journal of Light Wave Technology,2013,31(4):523-537.

[6] 郭世澤,陸哲明.復(fù)雜網(wǎng)絡(luò)理論基礎(chǔ)[M].北京:科學(xué)出版社,2012.

[7] Pothen A, Simon H,Liou K P.Partitioning sparse matrices with eigenvectors of graphs[J]. SLAM Journal on Matrix Analysis and Applications,1990,11(3): 430-452.

[9] 李曉佳,張鵬,狄增如.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2008,5(3):19-42.

[10] Newman M E J,Girvan M. Finding and evaluating community structure in networks[J]. Physical Review Letters,2004,69:026133-026142.

[11] Newman M E J,Girvan M.Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America，2002,99 (12):7821-7826.

[12] Newman M E J.Fast algorithm for detecting community structure in networks[J]. Physical Review Letters,2004,69(5):133-142.

[13] 王豐雪,陳家琪.一種結(jié)合模擬退火和貪心策略的社團(tuán)識(shí)別算法[J].電子科技,2016,29(2):8-11.

[14] 宣照國(guó),苗靜,黨延忠,等.科研領(lǐng)域關(guān)聯(lián)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分析[J].上海理工大學(xué)學(xué)報(bào),2008,30(2):249-252.

[15] 王水魚(yú),王小娟.在虛擬儀器中實(shí)現(xiàn)LabVIEW與Matlab的無(wú)縫鏈接[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2012,21(11):123-126.

Experimental Software Developed with LabVIEW for Community Structure Detection

ZHOU Qian, LIU Haiyang, ZHOU Yunan, CHEN Qiying, LIU Gequn

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

Community structure detection is fundamental in the network structure analysis. The community structure detection software plays an important role in the popularization of network science and the algorithms validation. In view of the lack of visualized community structure detection software, we develop a software package with LabVIEW to detect the community structure and demonstrate the result. We apply LabVIEW to organize the experimental data, to construct the human-machine interface, to show the detection result, and to control the operation process. Matlab is utilized to run the community structure detection algorithms. In the software, we adopted the property node to show the detection result, employed the finite-state machine to control the operating process, and used the mixed programming of LabVIEW and Matlab to execute the community structure detection. Three typical algorithms, i.e., the spectral bisection method, GN algorithm and Newman algorithm, have been successfully embedded in the software. The paper includes the detection result diagrams and their comparison of the three algorithms.

LabVIEW; community structure; spectral bisection method; GN algorithm; Newman algorithm

2016- 11- 07

滬江基金資助項(xiàng)目(C14002)；上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院教師創(chuàng)新能力建設(shè)基金資助項(xiàng)目(GDCX-Y-1212)；上海理工大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃資助項(xiàng)目(XJ2016029)

周茜(1992-)，女，碩士研究生。研究方向：復(fù)雜網(wǎng)絡(luò)。劉歌群(1974-),男，博士后，講師，碩士生導(dǎo)師。研究方向：復(fù)雜網(wǎng)絡(luò)與計(jì)算機(jī)控制。

10.16180/j.cnki.issn1007-7820.2017.02.030

TP391.41

A

1007-7820(2017)02-114-05