基于LabVIEW的社团结构识别实验软件

周 茜，刘海洋, 周煜南，陈祺盈, 刘歌群

(上海理工大学 光电信息与计算机工程学院，上海 200093)

基于LabVIEW的社团结构识别实验软件

周 茜，刘海洋, 周煜南，陈祺盈, 刘歌群

(上海理工大学 光电信息与计算机工程学院，上海 200093)

社团结构识别是网络结构分析的基本环节，文中基于LabVIEW开发了一种具有识别结果演示功能的社团结构识别实验软件。该软件利用LabVIEW组织实验数据、规划人机界面、显示识别结果并管理操作流程，利用Matlab进行社团结构识别算法的计算。在软件的开发过程中，识别结果的显示采用属性节点技术，操作流程的管理采用有限状态机技术，社团结构识别算法的计算采用LabVIEW与Matlab混合编程技术。该软件实现了谱平分法、GN算法和Newman算法共3种典型算法的计算与结果显示，给出了软件的运行效果和算法之间的对比图。

LabVIEW；社团结构；谱平分法；GN算法；Newman算法

随着对网络科学研究的深入，研究者发现许多实际网络都具有一个相同的性质，即社团结构，也就是说整个网络是由若干个“群(Group)”或“团(Cluster)”构成[1]。每一个群内部的节点之间连接相对紧密，但各个群之间的连接相对稀疏。由于网络规模的庞大和系统连接的多样性使得研究其结构和功能变得复杂，因此揭示网络中的社团结构，是了解网络系统结构和功能之间的对应关系，降低对复杂系统认识难度的方法[2-4]。目前，社团结构分析已广泛应用于生物学、计算机科学和社会学等多个领域中。

目前针对网络社团结构的分析，多借助Pajek、NetworkX、CFinder和Igraph等仿真软件。然而这些仿真软件并不能动态地演示社团结构识别的过程，因此提供一种面向社团结构识别过程可视化的展示工具已成为一种需要[5]。

本文设计开发了基于LabVIEW的社团结构识别实验软件，不仅能直观展示社团结构识别的动态过程，而且还能体现社团结构参数对社团结构识别的影响，为社团结构识别过程可视化提供了一种较好的展示工具。

1 社团结构识别算法

社团结构的研究已有较长的历史，研究者提出了一系列算法来寻找复杂网络中的社团结构。其中经典的社团结构识别算法[6]有：Kernighan-Lin算法、谱平分法、GN算法、Newman算法和派系过滤算法等。本文着重分析了谱平分法、GN算法和Newman算法。

1.1 谱平分法

谱平分法是Pothen等人基于图的Laplace矩阵的谱特征提出的一种将网络划分为两个社区的二分算法[7]。谱平分法基础理论是[8-9]：假设G是一个具有n个节点的无向图，则G的Laplace矩阵是一个n×n维的对称矩阵L。矩阵L表示成L=K-A，其中K是一个对角矩阵，其对角线上的元素就对应各个节点的度，而A则为该网络的连接矩阵。Laplace矩阵L是实对称矩阵，其非退化的特征值对应的特征向量总是正交的。因此除去最小特征值，矩阵L的其他特征值对应的特征向量总是包含正负两种元素。当网络只有两个社团时，根据第二小特征值对应的特征向量中的元素对网络中的节点进行分类。其中，正元素对应的节点属于一个社团，负元素对应的节点则属于另一个社团。

基于上述谱平分法的基础理论，该实验软件实现谱平分法的基本流程是：

步骤1构建图G的 Laplace矩阵L；

步骤2计算矩阵L的特征值和特征向量，求取除0外的最小特征值对应的特征向量l；

步骤3将特征向量l中正元素对应的节点放入一个数组，负元素对应的节点放入另一个数组，生成两个社团；

步骤4根据模块度公式[10]，计算两个社团的模块度。公式中 表示模块度； 表示矩阵L对角线元素； 表示与第 个社团中的节点相连的边在所有边中所占的比例；

步骤5对Q值较大的社团进行平分，重复步骤1～步骤4，直至完成要求的社团结构识别个数。

1.2 GN算法

GN算法是一种分裂算法，不断从网络中移除边，直至将所有的边都删除。GN算法的基本思想[10-11]是：

(1)计算网络中所有边的介数；

(2)找到介数最大的边并将它从网络中移除；

(3)重复步骤(2)，直至网络中所有的边均被移除。

基于上述GN算法的基础思想，该实验软件实现GN算法的基本流程为：

步骤1初始化。初始化网络为一个社团，构建网络的邻接矩阵A和n×n维的零数组B；

步骤2移除边。计算网络中所有边的介数，存入数组B，寻找数组B中的边介数最大值。将A中边介数最大值所对应节点位置变为0，更新邻接矩阵A。判断更新后的邻接矩阵A是否连通。如果连通，则找出连通量存入数组C，并重新计算移除一条边后的新网络的边介数；

步骤3终止。重复步骤2，直至每个节点成为一个社团。在此过程中，社团每分裂一次，计算一次模块度值。

1.3 Newman算法

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

(1)初始化网络为n个社团，即每个节点就是一个独立社团。初始网络的eij和a初始化为

(1)

a=ki/2m

(2)

其中,eij表示网络中连接两个不同社团节点的边在所有边中所占的比例；m为网络总边数；ki为节点i的度；

(2)依次合并有边相连的社团对，并计算合并后的模块度增量

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

(3)

每次合并应沿着使Q增大最多的方向进行；

(3)重复执行步骤(2)，不断合并社团,直到整个网络都合并成为一个社团。

基于上述Newman算法的基础思想，该实验软件实现Newman算法的流程为：

步骤1初始化。初始化为n个社团，将n个节点分别放入n个数组。模块度值Q=0，按照式(1)和式(2)进行初始网络 和 值的设定；

步骤2合并。构建一维零数组B，根据式(3)计算模块度增量，将计算结果存入数组B中。求取数组B中最大值所对应的节点，然后将与该节点有边相连的社团进行合并。即将两个数组合并为一个数组，生成新的数组(新的社团)；

步骤3终止。重复执行步骤2，不断合并数组，直到所有的数组都合并成为一个数组(即整个网络都合并成为一个社团)。

2 设计方案

根据上述3种社团结构识别算法，本文将进行社团结构识别实验软件的方案设计。

2.1 设计思想

本文将LabVIEW与Matlab进行混合编程，利用LabVIEW软件提供可视化界面,并在LabVIEW中使用Matlab的数值运算功能，提高编程效率。

社团结构识别实验软件的设计思想如下所述：

(1)利用LabVIEW构建输入模块和显示模块。输入模块包含网络拓扑结构矩阵和社团结构参数设置模块；显示模块包含网络拓扑结构图、社团构识别数据显示模块和模块度值显示模块；

(2)利用Matlab进行谱平分法、Newman算法和GN算法的仿真；

(3)在LabVIEW中调用Matlab的ActiveX对象[15]，与Matlab中的社团结构识别算法模型进行通信，实现LabVIEW与Matlab的混合编程。

2.2 社团结构识别实验软件的设计

社团结构识别实验软件设计的前面板包括5个部分，分别是网络拓扑结构矩阵设置区、社团结构参数设置区、网络拓扑结构图显示区、社团结构识别数据显示区和模块度值显示区，如图1所示。

图1 前面板以及网络拓扑结构图生成

社团结构识别实验软件的程序设计将实现下述功能：软件运行时进入初始化状态，参数设置完毕后进入网络拓扑结构图生成状态；网络拓扑结构图生成后，进入社团结构识别状态；社团结构识别完成后，自动进入社团识别效果显示状态，并可以重新进行参数设置；实验结束后，前面板将呈现初始化界面。为实现上述功能的实现，本文采用LabVIEW软件自带的设计模式-状态机实现，图2所示为软件运行状态图。

图2 软件运行状态图

图2中所示的状态阶段，每一状态阶段的功能和设计方法如下：

(1)初始化和参数设置阶段。主要进行网络拓扑结构图的构建和参数设置功能。利用LabVIEW绘制出以16个黑色圆点表示节点的网络拓扑结构图，如图1中网络拓扑结构图显示区所示。同时进行社团结构参数的设定，设置的两个参数分别为：社团结构识别算法和社团个数，如图1中的社团结构参数设置区所示；

(2)网络拓扑结构图生成阶段。主要实现网络拓扑结构图的生成。利用LabVIEW构建网络拓扑结构矩阵，将网络拓扑结构矩阵设置为16×16维的布尔型数组。数组中圆形指示灯亮则表示节点间有边连接，圆形指示灯暗则表示节点间无边连接，如图1中的网络拓扑结构矩阵所示。将网络拓扑结构矩阵作为输入，在网络拓扑结构图中显示网络的连接关系，如图1中的网络拓扑结构图所示；

(3)社团结构识别阶段。实现在LabVIEW中直接调用Matlab的ActiveX对象，与Matlab中的社团结构识别算法模型进行通信。本阶段利用LabVIEW中的Case Structure进行社团结构识别算法的选择，Case Structure中包含3个分支，3个分支分别对应于3种社团结构识别算法。根据前面板选择的社团结构识别算法，程序跳转至Case Structure中相应的分支进行运转。再根据前面板社团个数的设定，运行社团结构识别程序，如图3所示。

图3 社团结构识别程序图

图3中，将Matlab计算的社团识别结果和模块度值传递给LabVIEW，实现社团识别数据、模块度值和模块度值以图的形式在实验软件前面板的显示。社团结构识别阶段之后就直接转至社团识别结果显示阶；

(4)社团识别效果显示阶段。实现将同社团的节点在网络拓扑结构图中以相同的节点颜色进行显示。利用LabVIEW程序将社团结构识别结果作为输入，通过节点索引确定节点在网络拓扑结构图中的位置。然后将该节点的颜色由黑色变为指定颜色，并在网络拓扑结构图中显示，如图4所示。

图4 社团识别效果显示程序图

实验软件最终实现将一个网络中同社团的节点以相同的节点颜色进行演示的社团识别效果，如图5所示。

3 社团结构识别实验软件运行示例

为形象展示该软件社团结构识别的过程，因此设置了具有明显社团结构特征的网络，利用该网络进行社团结构识别过程的演示，如图1的网络拓扑结构矩阵所示。同时本文采用不同的社团结构识别算法和社团个数，对社团结构识别过程进行演示，如图5所示。

图5 实验软件生成的社团结构识别效果图

图6 模块度值

如图1所示，按照设置好的网络拓扑结构矩阵，单击“网络拓扑结构图生成”按钮，即可形成网络拓扑结构图，直观地展示网络节点之间的连接关系。如图5所示，为按照设置好的网络拓扑结构矩阵、社团结构识别算法以及社团个数，单击“社团识别”按钮，显示出的社团结构识别效果图。图5(a)、图5(b)和图5(c)，分别为选择谱平分法、GN算法和Newman算法时，识别2个社团、3个社团和4个社团的社团结构识别效果图，网络中同社团的节点均以相同的节点颜色进行演示。将设置好的网络拓扑结构矩阵分别与图5(a)、图5(b)和图5(c)对比可知，3种社团结构识别算法均是在识别3个社团时，得到最佳社团结构识别效果。利用图6模块度值的显示进行验证，从图6(a)、图6(b)和图6(c)中，发现3种社团结构识别算法均在识别3个社团时，模块度值最大，因此可知社团结构识别正确。若要结束图5的运行状态，点击“实验结束”按钮，回到图1所示状态，社团结构识别算法以及社团个数恢复到默认值。

4 结束语

社团结构识别过程的可视化，能使社团结构的理论知识变得直观易懂，便于学习和理解。本文首先利用Matlab进行社团结构识别算法的仿真，其次通过LabVIEW搭建社团结构识别的可视化界面，最后将LabVIEW与Matlab混合编程，设计一套基于LabVIEW的社团结构识别实验软件。该实验软件不但能动态演示社团结构识别的过程和显示社团结构识别数据和模块度值的变化，还可以灵活地改变社团结构识别算法，展示社团结构参数变化对社团结构识别过程的影响。因此基于LabVIEW的社团结构识别实验软件可运用于复杂网络的实验教学中，帮助学习者更好的学习和理解社团结构的理论知识。

[1] 汪小帆,李翔，陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.

[2] 邓智龙,淦文燕.复杂网络中的社团结构发现算法[J].计算机科学,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] 狄增如.系统科学视角下的复杂网络研究[J].上海理工大学报,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] 郭世泽,陆哲明.复杂网络理论基础[M].北京:科学出版社,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] 李晓佳,张鹏,狄增如.复杂网络中的社团结构[J].复杂系统与复杂性科学, 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] 王丰雪,陈家琪.一种结合模拟退火和贪心策略的社团识别算法[J].电子科技,2016,29(2):8-11.

[14] 宣照国,苗静,党延忠,等.科研领域关联网络的社团结构分析[J].上海理工大学学报,2008,30(2):249-252.

[15] 王水鱼,王小娟.在虚拟仪器中实现LabVIEW与Matlab的无缝链接[J].计算机系统应用,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

沪江基金资助项目(C14002)；上海理工大学光电信息与计算机工程学院教师创新能力建设基金资助项目(GDCX-Y-1212)；上海理工大学大学生创新创业训练计划资助项目(XJ2016029)

周茜(1992-)，女，硕士研究生。研究方向：复杂网络。刘歌群(1974-),男，博士后，讲师，硕士生导师。研究方向：复杂网络与计算机控制。

10.16180/j.cnki.issn1007-7820.2017.02.030

TP391.41

A

1007-7820(2017)02-114-05