NeSVA是北京邮电大学通信软件工程中心研究开发的一款基于链接分析的可视化分析框架,该框架是本中心原有的网络可视化框架JSNVA^{[ 4]}的升级版本。框架不但可以作为网络可视化的前端展示软件开发包,同时还提供了大量的网络分析统计功能可用作网络分析的计算后台。NeSVA的设计目标是实现一个简洁的分析评估复杂网络的性质、特点、变化以及决定性因素的可视化分析框架。NeSVA可以评估目前各种类型的用点边关系表示的网络。这些网络种类可以包括社会网络、活动网络、工作网络、知识网络、供应链以及通信网络等。NeSVA核心部分主要由以下几个模块组成:图结构模块、算法模块、布局算法模块、网络展示模块、IO模块,如图1所示:

图1

	Figure Option ViewDownloadNew Window
	图1 NeSVA框架核心部分的体系结构

(1)图结构模块:图模块实现了底层存储网络的数据结构,该框架的所有算法几乎都基于这些底层数据结构。该模块将图的结构实现为点集合与边集合,同时提供了对于图结构的大量基本操作,从而支持各类网络分析与可视化算法。

(2)算法模块:该模块使用图结构模块提供的数据结构,实现各类网络分析算法。模块中有两类重要的子模块分别是社团发现模块与中心性模块。同时为了对比不同网络结构的生成机制与了解不同网络生成模型的结构特征, NeSVA中实现了大量的网络生成算法,如图2所示:

图2

	Figure Option ViewDownloadNew Window
	图2 不同网络模型产生的网络

(3)布局算法模块:该模块主要实现各类网络可视化中的布局算法,如Spring力导引算法^{[ 5]},FR力导引算法^{[ 6]}, 辐射布局算法^{[ 7]}。

(4)网络展示模块:通过使用图结构模块中的图数据与布局算法模块中的各类布局算法将网络动态展示。

(5)IO模块:NeSVA实现了多种文件格式(如GML、Net、CSV等)数据的导入和导出功能,这样可以很好地与现有的网络分析软件融合。

(1)大规模网络的存储结构

图数据结构提供了大量的存储节点与边属性的操作,通过使用Java JDK中的HashMap类存储不同的属性名与相应的属性的映射关系,从而实现常数时间的属性存储与获取功能。为了存储大规模的实际网络,主要利用邻接表来实现具体的网络数据的存储,从而提高空间复杂度。图模块与算法模块的设计是松耦合的,可以“独立”实现对大规模网络的后台计算功能而脱离前段的可视化展示方式。如在2GB内存的普通PC上,可以基于图模块与算法模块计算实际电话网络(150万节点,1 000万条边)中节点的重要性、最大团分布、网络中社团结构的划分等。

(2)社团发现算法的实现

社团发现模块实现了大量的社团发现算法,如最大完全图发现算法,各类非重叠社团发现算法GN^{[ 8]}、CNM^{[ 9]}、MCL^{[ 10]}、LPA^{[ 11]}、BGLL^{[ 12]}等与重叠社团发现算法CPM^{[ 13]},极大团发现算法^{[ 14]}等。中心性模块主要是使用不同的打分算法分析网络中节点与边的重要性。这些算法包括节点与边的中介度(Betweenness Centrality)、Closeness Centrality、节点度、节点聚集系数、PageRank值等。这些算法的实现适用于高效的大规模网络社团发现,如发现Google-Web网络(875 713个节点,4 322 051条边)中的社团结构,使用LPA算法仅需要113秒,而BGLL算法需要约738秒。为了评估这些算法的有效性,NeSVA中实现了不同的社团相似性评估算法,如互信息相似性^{[ 15]}、Rand 系数相似性^{[ 16]}、Mirkin系数相似性^{[ 16]}、Jaccard系数相似性^{[ 16]}等算法。通过与社团网络模型生成的标准网络进行对比,这些评估算法可以定量地评价各类社团发现算法的效果。

(3)可视化算法与网络展示

由于力导引算法在网络可视化领域有广泛的适用性与很好的美学效果,对于大图的展示主要依赖于各类力导引算法。为了提高力导引算法对于大规模网络的可视化能力与提高展示算法的交互性,使用了 N-body算法^{[ 17]}来计算点对间的斥力,从而使原有的O(n²)的计算复杂度降低为O(nlog(n)),n为网络中的节点数。当前JUNG 和Pajek中最好的可视化算法每次布局的复杂度为O(n²)。

图展示模块中的GraphCanvas类是Swing中JPanel的子类,对网络展示主要是绘制在该面板上。GraphCanvas可以应用于任意Swing的应用,以支撑缩放等动画效果。在每步动画中,GraphCanvas类调用LayoutEngine类的Scheduler模式^{[ 18]}实现对网络的动态展示。同时,LayoutEngine类中通过Template Method模式定义网络布局算法的基本步骤,从而使各个布局算法通过相同的接口被灵活调换。图3展示了DBLP数据库从1959年至2009年的合作者网络数据集中合作次数超过4次的作者对,在该网络中共有21 762个节点与21 029 条边,通过使用基于N-body算法的Spring力导引布局算法,可以交互地实时展示该网络的结构。对比当前其他网络可视化框架,NeSVA具有较强的大规模网络展示能力与优势。

图3

	Figure Option ViewDownloadNew Window
	图3 DBLP作者合作网络

IVis是一款基于NeSVA开发的网络分析工具。该工具主要包含三种图数据结构:原始网络、子网络与社团网络。社团网络是一个抽象网络,在该网络中每个节点是一个社团,每条边表示社团间的联系。IVis主要分为以下几个操作步骤:数据预处理、统计分析、社团发现与可视化分析,如图4所示:

图4

	Figure Option ViewDownloadNew Window
	图4 IVis的用户界面

在数据预处理步骤中,用户可以导入基本的网络数据,同时还可以导入边的权重与时间信息。在统计分析步骤,用户可以使用不同的网络分析算法分析网络的拓扑特征,如度分布、连通分量分布、聚类系数、最大团分布等。同时用户还可使用不同的中心性算法计算网络中节点的重要性,如度、中介性、PageRank值、Closeness值等。在社团发现步骤中,可以运用各种社团划分算法从原始网络中得到密集子图和社团网络。在可视化分析步骤中,用户还可以可视化地观察原始网络、子网络与社团网络的拓扑特征,并可以通过基本的鼠标操作选择相应的社团,使这些社团自动展开,从而查看该社团子网络的链接情况。

本实验分析了万方数据数字化期刊群及会议群中2004年至2008年北京邮电大学论文关键词关系网络。实验在该关系网络中选取了万方数据5年记录中的7 673篇论文构建一个可供展示关键词关系的网络,并设定了一个同被引次数阈值将该网络进行过滤,从而确保该网络中的边均为较稳定的关联关系。本文最终选取了关键词联系在三次以上的关系对,采取LPA发现算法识别出网络中的社团,如图5所示:

图5

	Figure Option ViewDownloadNew Window
	图5 关键词网络的研究领域

图5可以较为清晰地识别出计算机学科中的不同研究领域,如:QoS研究相关领域、服务质量研究相关领域、网络管理研究相关领域、Web服务研究相关领域、下一代网络研究相关领域、3G移动通信研究相关领域、4G通信研究相关领域、电磁波研究相关领域、无线传感器研究相关领域、信息安全研究相关领域、无线通信研究相关领域、路由交换研究相关领域、IPv6研究相关领域等。这些领域很好地与当前北京邮电大学学科设置和研究方向相对应,由此看出,IVis的分析结果良好,基本符合真实情况。

本文收集了北京邮电大学1998年到2004年的合作者网络,在该网络中共有1 663个节点和4 775条边。通过GN算法,可以得到网络的社团划分。由于模块度的取值在-1到1之间,当模块度取值大于0.3时,网络中有明显的社群存在^{[ 8]}。该网络的模块度Q为0.83,社会网络中的模块表明该网络中有很强的社团结构,并得到了一个基于社团的网络,如图6所示:

图6

	Figure Option ViewDownloadNew Window
	图6 北京邮电大学作者社团网络

在图6的社团网络中,节点为社团,如果两个社团中有合作的链接,则在两个社团节点中连接一条边。通过对该社团网络中节点的中介性打分,得到中介性最大的社团是图6中标注的社团,该社团的主要作者来自电信学院、部分来自物理学院,他们的研究方向都基本集中于光通信领域。结果验证了北京邮电大学在光通信领域学术上的地位及学校资源的优势所在。

社会网络中的结构变化往往代表着其基于的社会个体关系的改变,同时这种结构的变化也对预测、描述重要事件与个体的行为提供了新的有效手段。随着时间的推移,网络中的关键人物或者关键点可能会发生变化。本文使用NeSVA预测对于特点节点从网络中删除后,网络结构与功能的变化和节点作用的变化,以及人员的离开对组织结构的影响。计算光通信社团子网络各个节点的中介度值。光通信社团子网络删除JinTong Lin节点前后的前10名作者中介度如表1所示:

表1

表1

表1 光通信社团删除JinTong Lin节点前后的前10名作者中介度 排名 作者 中介度 (删点前) 作者 中介度 (删点后) 1 JinTong Lin 9543.1 PeiDa Ye 9995.8 2 PeiDa Ye 7945.0 YueFeng Ji 6559.7 3 YueFeng Ji 5825.5 Jian Wu 6184 4 BoJun Yang 3459.6 BoJun Yang 3591.1 5 XiaoGuang Zhang 3321.0 XiaoGuang Zhang 3226.3 6 KeJian Guan 2202.5 GuangTao Zhou 3134.3 7 ShuQiang Chen 1923.7 KeJian Guan 2925.6 8 Min Zhang 1873.0 ShuQiang Chen 1832.4 9 Li Yu 1421.7 Kun Xu 1808.1 10 Jian Wu 1375.2 JianJun Yu 1599.7

表1 光通信社团删除JinTong Lin节点前后的前10名作者中介度

由表1可知,JinTong Lin节点原为该社团中介度最高的节点,同时可以发现他的一个合作者Jian Wu的中介度排名仅为10。如图7所示,当从该社团子网络中删除JinTong Lin节点后,JinTong Lin的合作者Jian Wu的中介性排名有了很大的跃升:从原来的第10名提升为第3名,成为相对较重要的学者。同时还可以发现:删除JinTong Lin节点后该社团网络的连通性并没有受到很大影响,该子网络中的绝大多数节点还是保持连通,表明社团发展态势良好,并不会由于一个重要作者的离开而引起该社团结构的巨大变化。

图7

	Figure Option ViewDownloadNew Window
	图7 光通信社团删除JinTong Lin节点前后的网络

在进行合作者网络分析时,由于合作者数据会出现重名现象,实施过程中可能存在误差,影响实际效果。数据处理中需要加入重名处理功能进行判断。在特定的领域内,对应于相同实体(Entity)的表象(Reference)往往具有相似的属性特征,如对于已经在某期刊上发表的一篇文章,其属性有文章题目、作者、作者的信息、文章的来源、所在期刊的卷期和页码等。实际中可以根据表象的属性进行相似度的判断,解决重名问题给数据统计和分析带来的很多错误和不确定。