JUNG：一种实现社会网络分析自动化分析的框架

□ 李世亮

JUNG：一种实现社会网络分析自动化分析的框架

□ 李世亮

社会网络分析在许多研究领域开始用于网络社区中人际交流的研究，但目前的研究大多是基于手工数据收集和分析，只能进行静态网络结构的分析。JUNG提供了一种公共和可扩展的框架来实现数据的建模，分析和可视化展示并能够被绘制成图形或网络，可以用于社会网络分析、Web流量分析、图论的理论推导以及关系类型数据的数据挖掘等等。文章介绍了JUNG的基本原理，以及如何利用JUNG在网络社区中实现自动化的社会网络分析和可视化。

JUNG；社会网络分析；可视化；聚类；最短路径

一、研究背景

自从人类学家Barnes（1954）首次使用“社会网络”的概念分析挪威某渔村的社会结构以来，社会网络分析就被视为是研究社会结构的最简单明了、最具有说服力的研究视角之一（丁晋，2008）。

社会网络分析来自社会计量学、群体动力学和图论三个方面的基础理论（王陆，2008）。上个世纪30年代，莫雷诺首先发明了利用社群图(Sociogram)来表达社会结构和形式特征的方法，区分领导者和孤立者，揭示出不对称性和互惠性，并用图来展示关联渠道。Lewin等人认为，社会空间的结构特征是可以用拓扑学(Topology)和集合论(SetTheory)中的数学分析技术来分析的。由此发展起来的群体动力学认为，全部社会场都是由各种力量构成的场，这些力量作用于群体的成员，并塑造着他们的行动和经验。卡特赖特(Cartwright)和数学家哈拉里 (Harary)共同开创了图论(Graph Theory)，并开展了图论在群体行为方面的系列研究，突破了认知心理学以个体认知平衡为核心的研究，而转向以社会群体中的人际关系平衡为核心的研究。社群图、小团体分析等是社会网络分析的常用方法（王陆，2009）。

近年来，很多学者运用社会网络分析方法分析基于网络的虚拟学习社区和学习共同体成员的行为关系与活动，如胡勇等(2006)对异步网络协作学习知识构建的研究、陈向东等(2008)对在线协作学习的研究、冯锐 （2009） 对摄影社群的研究以及易明（2010）对社会化标签网络的研究等。社会网络作为一个资源和知识交换的主要渠道，在虚拟学习社区中扮演了支撑的角色 (Cho，Stefanone， &Gay，2002)。社会网络改变了人们将社会看作是由离散的行动者所组成的认识，而将社会看做由行动者及其拥有的关系组成的，这一关系范式使得对关系的研究从直接陈述的方法转变为更生动的对社会互动的描述(Felmlee，2003)。社会网络分析方法可以使研究者更关注虚拟学习社区中的参与者及其关系图式，更加清晰的理解在已经完成的教育模式中发生了什么，方便地发现社区成员新的行为图式、社会应用和结构成果。社会网络分析甚至可以支持预测、计划和设计更好的虚拟学习社区社会或技术功能与环境的实现（王陆，2009）。

然而，在社会网络分析方法的应用中也发现了一些不足。由于整体网络数据收集难度很大，所以一般社会网络分析都无法采用大样本随机抽样，只能采用便利抽样 (Convenient Sampling)，从而造成社会网络分析研究具有很强的个案特征，很难推论出普遍适用的原理和原则（王陆，2009）。在实现手段上，社会网络分析常常因只进行静态网络结构的分析而受到批评。尽管有研究进行了基于时间序列的社会网络分析模型的尝试，但是仍然无法获得持续的网络变化数据。实现容易使用的动态网络结构数据的收集是社会网络分析研究的一个重要发展方向（Wesserman and Faust，1994）。

二、JUNG概述

JUNG（ Java Universal Network/Graph Framework）是一个软件包，最初由加利福尼亚大学的三位博士（Joshua O'Madahain，Danyel Fisher，Scott White）开发，它提供了一种公共和可扩展的框架来实现数据的建模，分析和可视化数据并能够将其绘制成图形或网络。JUNG是一个基于Java的开源项目，其目的在于为开发关于图（Graph）或网络结构（Network）的应用程序提供一个易用、通用的基础架构。JUNG使用BSD开放源码协议发布，使用JUNG功能调用，可以方便的构造图或网络的数据结构，应用经典算法（如聚类、最短路径等），操作、计算并可视化数据的网络图。JUNG可以用于社会网络分析、Web流量分析、图论的理论推导以及关系型数据的数据挖掘等方面。

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

1.支持多种实体以及它们之间关系的表示，如有向图、无向图、多模图（图中包含一种以上的节点或者边）、多重图（具有重边的图）以及超图（图中包含有超边，每一条超边可以包含任意多个节点）。

2.支持多种机制来标识图、实体和关系的元数据。这一特性有助于创建分析工具来研究实体之间的关系，同样也可以研究实体和关系的元数据。

3.实现了多个来自图论、探索性数据分析、社会网络分析和机器学习中的算法。这些算法包括常规的聚类、分解、优化、随机图的生成、统计分析、网络距离的计算、流量以及排名计算（如中心度、PageRank、HITS等）。

4.实现了一个可视化的框架，可以支持交互式的网络数据浏览。用户可以自行选择图的布局和渲染的算法，或者利用框架来生成自己的渲染算法。

5.JUNG过滤机制可以支持抽取网络数据集的某个子集，这一特性允许用户在整个网络数据集中呈现他们所关注的那部分数据，或者特定算法的筛选结果。

以上特性使得JUNG成为了一个理想的呈现和分析关系数据集的平台。利用JUNG可以开发独立程序或者作为嵌入在某个网络平台上的工具来操作关系图或者网络数据。它可以用简单的代码片段来测试一个想法，或者搭建一个拥有复杂图形界面的分析工具。JUNG是一个可以支持不同工具的Java库，如果要使用JUNG需要具备一定的Java编程知识。使用一个库而不是现成的软件工具的优势在于网络分析过程可以根据不同的目的来自行编程。这个优点使得JUNG适合构建基于Web的Java Applet小程序，从而可以动态的从网络中读取并分析和显示关系数据。

图1 JUNG中图的继承关系

三、JUNG的设计原则

JUNG使用Java语言来设计，利用了Java的接口、抽象类和实现类来进行图的原型定义。这样进行抽象设计有三方面优势：

1.可以将设计与实现分离，这使得JUNG成为一种处理关系数据的通用语言。例如，Archetype-Graph接口指定了所有图都具备的特性，但是不包含这些特性如何实现具体算法。

2.利用Java面向对象的特性，利用抽象类和接口来实现继承关系。例如，Graph类定义了所有图的通用接口，它包含由两个节点连接的边。Graph是ArchetypeGraph的子接口，这意味着它包含所有ArchetypeGraph的属性，并且它还具有一些自己独特的属性。

3.使用方法签名来避免用户传入错误的参数，允许用户在编译阶段就发现类似的错误，而不是等到代码运行时才发现。JUNG提供的方法避免了限定在某个内部方法上，用户可以使用自己的实现方法。

图、节点、边都有一些抽象出来的属性和它们可以进行的操作。如图1所示，JUNG定义了图的继承关系。JUNG定义的节点和边只能属于一个图，这样可以方便用户查询某个节点的邻居节点。同时意味着节点和边的属性中有图的标识符，这种属性可以被用来计算两个指定节点之间的最短路径。

接口ArchetypeGraph定义了包含节点和边的图，并且定义了若干访问和修改这些集合的方法。Hypergraph和Graph接口继承了ArchetypeGraph接口，并且相应的定义了它们的边只能包含两个节点。这两个接口中还定义了增加节点和边的方法，这些方法被定义在这里而不是ArchtypeGraph中，主要原因是为了在编译环节中检查节点和边的类型是否正确。Graph还有一些子接口，定义了只包含有向边和无向边的特殊图。SparseGraph类实现了Graph接口中定义的方法，适合于稀疏图的相关运算。

四、JUNG的算法

JUNG提供了多种关系网络的算法，下面分类进行简单的介绍。

1.排序

排序算法可以为某个节点或者边通过某种法则计算出能够反应在网络中的结构特性的一个属性值。这些法则通常用于测量某个节点或边的影响力、权威度或者中心度。这些算法将输入解释为马尔可夫网，即一个有向权重图。图中的节点表示状态，边表示可能的状态转移，边的权重表示转移的概率。

JUNG中提供的排序算法包括（O'Madahain et al.， 2005） 四类：BetweennessCentrality算法通过计算通过该节点和边的最短路径数作为排序依据；PageRank算法通过改进的马尔可夫网络方法计算节点的平稳概率；HITS算法根据节点在图中的中心性来评分；VoltageRanker算法将网络看做是电子线路，并给出每个节点在该电路中的剩余电压值。

2.聚类和区块模型

对某些对象进行聚类通常是通过这些对象的某些相似属性来进行。在社会网络中，相似性是指图的拓扑属性，例如连接性，也可能是网络中节点或边的属性。JUNG提供的聚类算法包括四类：EdgeBetweennessCluster算法通过计算边的中介性来进行聚类；WeakComponentCluster算法主要用来找出一个给定图中所有弱对象，弱对象是指某个子图中至少包含有一条无向边；VoltageCluster算法通过找出网络中拥有相近“电压”值的节点来进行聚类。

在社会网络分析领域中，如果两个节点同时与某些节点相接，那么它们被认为是结构相等的。JUNG提供了BlockModelling算法，该算法可以找出图中结构相等的节点。这些算法可用来在图中找出重复对象，或者简化图形的显示（例如可以将某个大型复杂网络进行聚类，把同类的节点显示为一个节点）。

3.拓扑算法及最短路径

此类算法主要针对图的拓扑属性进行计算。JUNG提供的BFSDistanceLabeler拓扑算法用来标识出每个节点到图中某个节点的无权重最短路径；KNeighborhoodExtractor算法返回某个节点的k阶邻居节点的集合；DijkstraShortestPath算法能够计算出图中从某个节点到其他节点的带权重的最短路径。

在社会网络分析中，最短路径算法可以方便的找出网络社区中任意两个人之间的最短认识路径，从而为网络社区的交友提供有效的工具。

五、利用JUNG来进行社会网络分析

1.关系数据的输入

JUNG框架本身提供了随机图的生成算法，包括BarabasiAlbertGenerator、EppsteinPowerLaw-Generator、 KleinbergSmallWorldGenerator， 这 些随机图可以用于某些理论的验证和推演。除此之外，JUNG还支持文本格式和数据库的关系数据，其中文本格式支持Pajek的文件格式和GraphML格式。

在实际应用中可以采用文本方式来输入关系数据，如在某个学习论坛中，采集发帖和回帖的数据后，通过一个后台的Servlet输出如下格式的关系数据：

上面的例子中包含了6个节点（参与讨论的人）和6条边（论坛回复关系）。

2.关系数据的分析与可视化

由于JUNG是用Java语言实现的，因此可以方便的利用Java语言的网络功能获得关系数据。下面是获得上述关系数据的方法示例。

图的可视化表现是JUNG最为吸引人的地方。JUNG可视化功能的基本组件是BasicVisualization-Server类，该类是Swing Jpanel的一个子类，可以放置到任何一个Swing的容器对象中。要构造一个BasicVisualizationServer类，首先需要了解JUNG中“布局（Layout）”的概念。一个Layout接口的实现，实际上就是要告诉JUNG如何来绘制图的顶点和边，即确定其在图形界面上的坐标位置(x， y)。使用预定义的Layout（例如CircleLayout）可以方便的完成这个工作而不需要繁杂的手工编码。图g的可视化表现可以分以下4个步骤完成：

//1.初始化图g

//2.使用该图创建布局对象

Layout

//3.使用布局对象创建BasicVisualizationServer对象

BasicVisualizationServer

//4.将上述对象放置在一个Swing容器中并显示之

在网络社区中可以通过嵌入Java Applet小程序的方式来呈现社会网络分析的结果。嵌入Applet的示例代码如下：

3.利用JUNG进行社会网络分析的几个例子

（1） 聚类分析。如图2所示，通过聚类分析，我们可以发现在社区中的哪些成员形成了小团体，并且可以找到在小团体中谁处于中心位置。

图2 聚类分析

（2）集中度分析。在图3中，通过集中度分析，我们可以给出某个团体成员的集中度分布情况，这对于社区管理者、研究者和参与者本身都是很有价值的工具。

图3 集中度分析

（3）最短路径分析。如图4所示，最短路径分析可以自动找到某两个用户之间的最短路径，从而可以为社区成员的交友提出了很好的建议。

图4 最短路径分析

以上社会网络分析都是内建在网络社区内部的，随着成员交互关系的演进可以持续的呈现社区的交互关系，也可以根据不同的目的设计和实现更多的关系可视化工具。通过以上分析，可以得出如下结论：利用JUNG框架可以实现网络社区内全关系集合的社会网络分析，即网络社区内的全部交互关系都可以作为JUNG的数据源，利用程序自动的实现社会网络分析。其次，JUNG框架可以通过编程来呈现社会网络关系随着时间演变的过程。第三，通过聚类分析可以发现群组和核心参与者，有利于社区管理者进行活动的组织。最后，通过最短路径分析可以帮助找到好友的最短途径，进而增强社区成员的社区感并方便地找到同伴。

[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]陈向东.基于社会网络分析的在线协作学习研究[J].中国电化教育，2006，（10）：27.

[6]丁晋.教师远程研修共同体研究——以2006年教育部“中小学教师新课程国家级远程培训”为例[D].硕士，南京：南京师范大学，2008：9.

[7]冯锐.博联社摄影社群的社会网络分析[J].中国电化教育，2006，（9）：100.

[8]胡勇，王陆.异步网络协作学习中知识建构的内容分析和社会网络分析[J].电化教育研究，2006，（11）：30-31.

[9]王陆.信息化教育研究中的新内容：互动关系研究[J].电化教育研究，2008（1）：17.

[10]王陆.虚拟学习社区的社会网络分析[J].中国电化教育，2009，（2）：5-9.

[11]易明.基于社会网络分析的社会化标签网络分析与个性化信息服务研究[J].中国图书馆学报，2010，（2）：110.

2011－02－25

李世亮，在读博士，助理研究员，北京师范大学远程教育研究中心（100875）。

责任编辑 柯 南

G434

B

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