转自：

, 软件工程师, IBM

2009 年 9 月 03 日

目前，如何以图形化的方式，向用户直观地呈现一个复杂社交网络，已逐渐成为 Web2.0 社交类网站关注的重点。弹簧理论非常适用于描述社交网络间的复杂关系，文章以弹簧理论中的经典算法力导向算法为理论基础，详细介绍了两种 Flash 实现方法。另一方面，由于 Flash Player 的内部语言 ActionScript 在计算能力上的先天劣势使得在 Flash 中实现时间复杂度较高的算法总会遇到性能瓶颈，如何在 Flash 中进行算法调优也成了客户端开发人员关注的难点。文章先会对弹簧算法的理论、特点及运用领域做一概述；随后将介绍对社交网络图数据源的最佳存储和传输规范之一的 GraphML 标准；后文将着重介绍基于 Flash 的两种实现方案；最后通过一组性能测试数据，简单分析两种实现方案的性能差异。

本文主要介绍的是弹簧理论算法在社交网络分析中的应用、社交网络图作为数据源的通用格式、弹簧算法的 Flash 实现以及 Flash 结合 Java Plug-in 的实现， 因此首先需要对社交网络分析和弹簧理论的概念有一个初步了解。

简单来说，社交网络是一个由个人或社区组成的点状网络拓扑结构。其中每个点 (Node) 代表一个个体，可以是个人，也可以是一个团队或是一个社区，个体与个体之间可能存在各种相互依赖的社会关系，在拓扑网络中以点与点之间的边 (Tie) 表示。而社交网络分析关心的正是点与边之间依存的社会关系。随着个体数量的增加，以及个体间社会关系的复杂化，最后形成的整个社交网络结构可能会非常复杂。本文所讨论的复杂社交网络中节点数一般为 100 个，上限为 300 个，若超过该上限，网络形成的性能将大大下降。

社交网络分析最初是用于帮助人们理解人群中流行性疾病的传播情况并加以抑制。疾病的传播所强调的关键词即"接触"，而现在这种接触逐渐演化为人与人之间的交流和联络，在社交网络中以边的形式表现出来，一条边即表示两个个体间建立了一种关联（ties）。

一张社交网络图的形状可以直观地决定网络本身对每个个体的重要程度。一般而言，一张聚合度更高、更紧密的网络（cliques，如一个部落、家族等）对于每个成员的重要程度要远远小于一张与外网络有大量弱关联 (weak ties) 的松散网络（如一个开源社区、bbs 论坛等），如图 1 所示。

自身网络越开放，与外界网络建立越多的弱关联，越容易开拓人的思维，分享更多知识，提供更多机遇。换句话说，社交网络分析建议，我们要避免与同一网络的个体间建立过多的冗余关联，同时要尝试与不同的外界网络建立联系。下面我们将由浅入深地介绍社交网络分析中的几个重要度量参数：

• 度（degree）-- 一个节点有 n 条边即度数为 n，如图 1 中的点 A 度数为 6；
• 接近度（closeness）-- 若一个节点与其他节点的几何距离之和（如最短路径之和）相对较小，我们认为该节点的接近度偏高，如图 1 中的点 B；
• 中间状态（betweenness）-- 在整个网络中，一个点在其他两两节点之间的最短路径上多次出现，我们说这样的点具有较高的中间状态值，如图 1 中的点 B；
• 中央性（centrality）-- 以上 3 个参数都是用于度量中央性的。简单来说，中央性指的是一个节点对于整个网络的重要程度。比如上文提到的具有弱关联（weak ties）的节点即有很高的中央性；
• 桥（bridge）-- 如果一条边删除后会增加整个网络图中的连通分支的数量，我们称这条边为桥，如图 1 中的边 CD。

本文只介绍了几个对社交网络分析的图形特性有重大影响的度量参数，至于其他的一些参数，读者可以查阅 中的维基百科。

我们还可从图 1 的网络形状中获得一些额外信息：

• 当一个集群（clique）中的一组点之间的联系相对紧密时，集群会相对收敛，如图 1 中点 B 所在黄色集群，反之亦然；
• 相对联系较少的点分布在网络的边缘区域；
• 边与边之间的相交较少；
• 每个点在集群中均匀分布，部分边的长度一致；
• 整张网络具有对称性。

我们说，具备以上特性和美感的网络结构图更直观可读，更易于社交网络分析。那么我们通过怎样的算法能够描述出图 1 中的网络模型呢？弹簧理论算法给出了答案。

基于力导向 (Force-directed) 的算法作为弹簧理论算法的一类典型，被广泛应用于描述社交网络等关系型信息图。它的原理其实非常易懂，我们可以把整张网络想象成一个虚拟的物理系统。系统中的每个节点都可以看成是一个带有一定能量的放电粒子，粒子与粒子之间存在某种库仑斥力，使它们两两相互排斥。同时，有些粒子间被一些"边"所牵连，这些边产生类似弹簧的胡克引力，又紧紧牵制着"边"两端的粒子。在粒子间斥力和引力的不断作用下，粒子们从随机无序的初态不断发生位移，逐渐趋于平衡有序的终态。同时整个物理系统的能量也在不断消耗，经过数次迭代后，粒子之间几乎不再发生相对位移，整个系统达到一种稳定平衡的状态，即能量趋于零。此刻，最终的这幅理想的社交网络图也基本绘制完成。清单 1 的伪代码描述了大致的迭代优化过程。

Set up initial node positions randomly  Loop for k     For each node u         For each node v             net-force += Coulomb_repulsion( u, v )         End For     End For     For each edge e compute         net-force += Hooke_attraction( u1, u2 ) // u1, u2 is start and end node of edge e     End For     Update x and y values with each net-force // every node has its own net-force  End Loop

伪代码的整体思想归纳如下：

1. 随机分布初始节点位置；
2. 计算每次迭代局部区域内两两节点间的斥力所产生的单位位移（一般为正值）；
3. 计算每次迭代每条边的引力对两端节点所产生的单位位移（一般为负值）；
4. 步骤 2、3 中的斥力和引力系数直接影响到最终态的理想效果，它与节点间的距离、节点在系统所在区域的平均单位区域均有关，需要开发人员在实践中不断调整；
5. 累加经过步骤 2、3 计算得到的所有节点的单位位移；
6. 迭代 n 次，直至达到理想效果。

为了节省篇幅，省去了涉及细节的逻辑和计算，如参数的微调、斥力和引力产生的位移量公式等，如果读者有兴趣深入了解该算法可以查阅相关文献，详见 中的相关算法理论。另外，开发人员可以根据自己的偏好选择不同的编程语言来实现（后文中会提到 ActionScript 和 Java 的两种实现）。

该算法的平均时间复杂度是由两部分组成--每次迭代计算每两点间的斥力变化 O(n²) 和每条边给端点带来的引力变化 O(e)，共进行 k 次迭代计算，即 O (k * (n²+e) )。其中 n 为节点个数，e 为边数。图 2 描述了随着迭代次数的增加，力导向算法在 3D 网络图中节点相互排斥吸引的扩散过程。

我们从图 2 中可以发现点和边的位移趋势：

• 伊始，节点的扩散速率相对较快；随着迭代次数的不断增加，点的运动幅度愈小（即节点所携带的能量愈少）；最终，整个网状结构趋于平衡；
• 随着迭代次数的增加，边与边的相交总数也在减少，同一顶点相关的边的长度趋于接近，使整张网络更具对称性和可读性；
• 中间状态（betweenness）较高的点逐渐收敛，导致集群（cliques）愈加收敛；
• 随着作为桥（bridge）的边逐渐被拉长，集群与集群之间的距离也被放大，集群间具备较强中央性（centrality）的节点（如拥有弱关联（weak ties）的节点）逐渐更易于识别。

而以上几点也正符合上文归纳的适用于社交网络分析的网状结构图的几大基本特性。

既然力导向算法把社交网络分析的图形特性展现得如此完美，那么它是否还有进一步优化的余地呢？有一定算法基础的读者不难发现，该算法的最大弊病在于：为了追求图形的对称美，它在每一次的迭代中，都对每两点间的斥力进行了累加计算，即每次迭代的该部分时间复杂度达到了 O(n²)。若忽略边产生引力的部分计算，且假设迭代至趋于平衡的时间复杂度是 O(n)，那么整个算法的时间复杂度为 O(n³)。这样对于大型复杂网络图，这种算法的效率将随着时间复杂度的上升而大大下降。我们该如何降低时间复杂度呢？这里文章给读者留下一个悬念，有兴趣的读者不妨思考一下。

ActionScript 是基于 Adobe Flash Player 运行环境下的编程语言，它是一种类似 JavaScript 并遵循 ECMA 规范的脚本语言。目前最新版本号是 3.0，ActionScript 3.0 使 Flash 开发更接近面向对象设计思想的 Java 语言，由于其新版本引进了面向对象设计思想，它已被广泛运用于 Flash/Flex/AIR 的开发。ActionScript （后文中提到的 ActionScript 都是指 ActionScript 3.0）被 Flash Player 内置的 ActionScript 虚拟机 (AVM) 所执行，这又有点类似于 Java 虚拟机 (JVM)。

本文并不详细讲述 ActionScript 3.0 的语法，如想了解该语言的用法，可以查看 中的相关教程。

GraphML --顾名思义（Graph+XML）是一种基于 XML 且用于描述图（Graph）的通用文件格式。为何要选择 GraphML ？由于 GraphML 并不像其他一些描述图的文件格式，采用的是自定义格式（如 GML），它是完全基于 XML，因此对于生成、存储或是处理图的服务而言，它是一个理想的标准。同时它也非常直观易用，容易被开发者理解和接受，尽管它有着所有基于 XML 文件格式所共有的通病--传输或存储时文件相对过大，不如 Json 和 AMF （Adobe 的一种二进制传输格式）那般轻量级。那么它通常用于描述怎样的图呢？以下作者列出了一些它所支持的图的类型：

• 有向图（directed graphs）、无向图（undirected graphs）及有向兼无向图；
• 超图（hypergraphs）；
• 分级图（hierarchical graphs）；
• 图形显示；
• 为外部数据提供的引用；
• 作为特定应用的属性数据；
• 轻量级语法分析器。

而在社交网络中，边（edge）是被定义成人与人之间的关系，这里我们假设甲和乙之间存在一条无向边即表示甲乙相互认识，即这是一幅无向图。因此作者用 GraphML 来描述和存储一个社交网络无向图。

下面来看一个例子：

          
           
            
            
              
          
           1.0
             
            
              
               
                 
           john@us.ibm.com     
               
                 
                
               
          
                  ...     
               
               
                 
           1.1     
               
             
           
        

清单 2 即是一段简单明了的描述无向图的 GraphML 片段，与其对应的网状图即图 3。

接下来我们来仔细分析清单 2 中整个 GraphML 的格式和规范：

• 首先，作为一个 XML，必须得有一个 header，此例中第 1 行描述了该 XML 文档遵循 XML 1.0 标准且它的编码是 UTF-8（XML 文档标准编码），当然用户也可以定义自己的编码；第 2 行包含了一个主节点 graphml 节点，它属于 http://graphml.graphdrawing.org/xmlns 名字空间。
• 接下来是 GraphML 的核心部分--申明整个图以及其包含所有的点和边。第 8 行中定义了 Graph 的标识符和边默认是否有向，这里标识符必须为空字符串，而 edgedefault="undirected"，故为无向边。之后是所有点和边的定义，包括它们的标识符（id）以及边的起始点和目标点的标识符，如第 20 行 <edge source="1" target="2"> 即定义了一条从点"1"至点"2"的无向边。
• 另外，还可以为点和边附加一些自定义的属性，如每个点所对应人的 email 信息，每条边的权重等。这些属性一般都是以子节点的形式插入相应的点节点和边节点中，如第 11 行点的 email 信息以及第 21 行边的权重值。在插入到点节点和边节点之前，我们首先要在 XML 的伊始处为这些自定义属性作必要声明，如标识符、名称、数据类型、域、甚至默认值等。第 4、5 行即分别是对前述的 email 信息和边的权重的声明，如第 5 行：
  <key id="w" for="edge" attr.name="weight" attr.type="double"><default>1</default></key>
  • 节点名 key 对应文档正文中插入的自定义属性中 data 节点的属性名称 key；
  • id 作为标识符以区分不同的的自定义属性，如 "w" 代表边权重属性；
  • for 代表属性属于的不同域，可以是 graph、node、edge 或 all，这里是 edge，表示只能作为边节点的属性；
  • attr.name 类似 id，描述该属性的名称，目的是标识该属性的文字含义，但值得注意的是它并不在文档中被使用到，替代它作为标识符的是 id；
  • attr.type 指定了该属性的数据类型，可以是 boolean, int, long, float, double, string（即 Java 语言的基本数据类型，在 ActionScript 中相对应的分别是 Boolean, int, uint, Number, Number, String），这里因为是边的权重值，故选择 double 类型；
  • default 声明了该属性的默认值，这里默认值是 1.0。该属性为可选。

上文中提到，ActionScript 是一门专门用于进行矢量计算和图形显示的语言，但由于其基于浏览器和脚本语言的局限性，使其在进行一些复杂算法的计算效率上表现并不突出。下面介绍用它如何来实现 。

首先，读入记录一张图的 GraphML （本例中的所有边都是无向边），ActionScript 将读入的 XML 格式的文件转换成 XML 对象，代码如清单 3 所示。

private var xml:XML  public function loadData():void {     var xmlLoader:URLLoader = new URLLoader()     xmlLoader.dataFormat = URLLoaderDataFormat.TEXT     xmlLoader.addEventListener(Event.COMPLETE, xmlCompleteHandler)     xmlLoader.addEventListener(IOErrorEvent.IO_ERROR, xmlIOErrorHandler)     var request:URLRequest = new URLRequest("data/graphml.xml")     xmlLoader.load(request)  }  private function xmlCompleteHandler(e:Event):void {   (e.target as URLLoader).removeEventListener(Event.COMPLETE, xmlCompleteHandler)   (e. target as URLLoader).removeEventListener(IOErrorEvent.IO_ERROR, xmlIOErrorHandler)     xml = new XML(e. target.data)  }  private function xmlIOErrorHandler(e:IOErrorEvent):void {   (e. target as URLLoader).removeEventListener(Event.COMPLETE, xmlCompleteHandler)   (e. target as URLLoader).removeEventListener(IOErrorEvent.IO_ERROR, xmlIOErrorHandler)     //TODO: graphML loaded fail  }

ActionScript 同 JavaScript 一样支持 ECMAScript for XML（E4X）标准，可以通过简单的语法迅速将 XML 文档解析成自定义的模型对象，关于 E4X 的详细介绍，读者可以查看 。清单 4 中所解析的 XML 文档，读者可以查看 。由于篇幅原因略去了自定义类的代码，包括一个 Map 类来模拟 Map 数据结构以及三个模型类 Node、Edge、Graph 来存储点、边和图对象，读者可以查看 的示例源代码。

var graph = new Graph(new Map(), new Map())     var tmpNode:Node = null     var tmpEdge:Edge = null     var nodeId:String, sourceId:String, targetId:String     var weight:Number     var edgeKey:int     for each (var node:XML in xml..node) {         tmpNode = new Node()         nodeId = node.@id         tmpNode.id = ++graph.nodeCount         graph.nodeMap.put(nodeId, tmpNode)     }     for each (var edge:XML in xml..edge) {         tmpEdge = new Edge()         sourceId = edge.@source         targetId = edge.@target         weight = parseFloat(edge.data.(@key == "weight").text().toXMLString()         tmpEdge.src = graph.nodeMap.get(sourceId)         tmpEdge.dest = graph.nodeMap.get(targetId)         tmpEdge.weight = weight         if (tmpEdge.src && tmpEdge.dest) {             edgeKey = tmpEdge.src.id * 1000 + tmpEdge.dest.id             graph.edgeMap.put(edgeKey, tmpEdge)         }         graph.edgeCount++     }

帧频即每秒钟播放的帧数，最早是电影制作中引入的术语，而 Flash 是一帧接一帧的动画，也可以看成是一部网页中播放的小电影。Flash 中默认帧频是 12 fps，而最高可达 120 fps。

XML 文档解析完成后，下面将开始进行算法的迭代过程，这里我们定义总迭代次数为 250 次。在迭代前，先要初始化点在舞台的位置，本文所有点的坐标将随机落在 Flash 舞台中央 40 × 40 像素的矩形区域内，参见清单 5 的 start() 方法。

具体迭代过程如何进行呢？首先，我们为 Flash 设置默认帧频为 50 fps，这样既能保证画面的精细度及 Graph 扩散的流畅性，同时又避免了卡壳现象及 Graph 扩散过快而不易看清。图 4 显示了在 Flex Builder 内如何设置默认帧频。接着，为 Sprite 对象添加一个 enterFrameHandler 的监听函数，根据帧频在 Flash 每次进入新帧时调度，每调度一次即执行一次迭代，直至迭代结束移除监听。

每次迭代概括成以下 6 个步骤：

1. 实时更新 Flash 舞台的矩形大小，即画布区域；
2. 实时调整参数：如每次迭代的斥力引力因子、重绘频率因子等；
3. 计算点与点间的斥力，根据斥力因子算出斥力导致的正坐标偏移量；
4. 计算边产生的引力，根据引力因子算出引力导致的负坐标偏移量；
5. 累加偏移量并根据坐标偏移量实时更新点的坐标；
6. 根据重绘频率因子决定是否重绘 Graph。

步骤 1-5 请参见清单 5 的 dynamicDraw() 方法，具体实现细节可查看 中的算法理论；步骤 6 请参见清单 5 的 repaintGraph() 方法，相关的 ActionScript 绘图函数，读者可查看 中的相关教程。

private var visLayer:GraphRender // A Sprite to render graph  private var iter:int = 0 // current iteration time  private const ITER_MAX:int = 250 // total iteration times  private var renderFreq:int = 5 // render frequency  private var region:Rectangle  private var nodes:Array  private var edges:Array  public function start(graph:Graph):void {  // random nodes init location     region = new Rectangle(0, 0, stage.stageWidth, stage.stageHeight)     var start_x:Number, start_y:Number     start_x = region.x + region.width * .5     start_y = region.y + region.height * .5     nodes = graph.nodeMap.values()     edges = graph.edgeMap.values()     for each (var tmpNode:Node in nodes)     {         tmpNode.x = start_x + 40 * (Math.random() - .5)         tmpNode.y = start_y + 40 * (Math.random() - .5)     }     visLayer = GraphRender(graph)     visLayer.addEventListener(Event.ENTER_FRAME, enterFrameHandler)  }  private function enterFrameHandler(evt:Event):void {     perform()  }  // iterate once  private function perform():void {     dynamicDraw()     repaintGraph() // repaint nodes and edges     iter++     if (iter >= ITER_MAX) { // iteration over!         visLayer.removeEventListener(Event.ENTER_FRAME, enterFrameHandler)     }  }  private function dynamicDraw():void {     ...  // (1) update flash movie stage size  // (2) adjust coefficients like offset, eject factor, render frequency  // (3) compute repulsion between nodes  // (4) compute attraction of each edge  // (5) update nodes coordinates  }  // (6) repaint graph  private function repaintGraph():void {     var v:int = 0     if (iter % renderFreq == 0) {         for each (var tmpNode:Node in nodes) {             tmpNode.repaintNode()         }         for each (var tmpEdge:Edge in edges) {             tmpEdge.repaintEdge()         }     }  }

清单 5 描述了以上算法的整个迭代过程。

图 5 显示了不同迭代阶段--迭代次数分别是 5、20、40、80、100、250 时刻的 Graph 截图。读者不难发现，两张截图间经历了 150 次迭代--从第 100 次迭代至最后一次迭代，但点的相对偏移量并不大。也就是说，在前 100 次迭代中，点迅速从原始位置向外扩张，点大部分的偏移量在这个阶段完成；而在后 150 次迭代中，点的偏移量相对较小，只做细微坐标调整。

pic5.png

我们可以将图 5 中的最终态与 进行对比，果然惊人的相似！在此，我们顺便回顾一下社交网络分析中最重要的图形度量特性：

• 集群相对收敛，特别是其中度数 / 接近度 / 中间状态较高的节点；

• 集群间的桥与弱关联相对易读。

我们知道，ActionScript 是 Adobe Flash Player 的内部语言，而 Flash Player 作为浏览器的插件，早早就支持了与浏览器的宠儿 JavaScript 语言的交互。

清单 6 与清单 7 分别列出了在 ActionScript 中如何调用一个已定义的 JavaScript 方法，以及在 JavaScript 中如何调用一个已声明为回调函数的 ActionScript 方法。

ActionScript code:     var retval:* = ExternalInterface.call("fooInJs", "a", true)  JavaScript code:     function fooInJs(arg1, arg2) {         alert(arg1 + arg2);     }

ActionScript code:  // add callback declaration as early as possible!     ExternalInterface.addCallback("fooInAS", foo)     public function foo(arg:*):void {         trace(arg)     }  JavaScript code:     var movie = document.getElementById("swfId");     movie.fooInAS("aaa");

ExternalInterface 类是外部 API，在 ActionScript 和 Flash Player 的容器之间实现直接通讯的应用程序编程接口，如本文含 JavaScript 的 HTML 页。 作者推荐对所有 JavaScript 与 ActionScript 之间的通信使用 ExternalInterface。

以下几点在开发中值得注意：

• 等待 ActionScript 调用的 JavaScript 方法定义必须在 ActionScript 调用它之前加载完毕，作者建议必要时可以将部分 JavaScript 片段放在 HTML 页的顶部，虽然这违反了提高网站性能最佳实践的原则之一--将 JavaScript 放在 HTML 页的底部。
• 等待 JavaScript 调用的 ActionScript 回调函数必须在 JavaScript 调用之前尽早地作好回调声明，否则 JavaScript 端可能报"未定义该方法"的错误！
• 不论是 ActionScript 调用 JavaScript 方法，或是 JavaScript 调用 ActionScript 方法，均可传参数和得到返回值，所传参数和返回值的类型只能是 String、Boolean 等元数据类型；
• 等待调用的 ActionScript 方法的方法名可以和它作为回调函数的声明名称，即 JavaScript 可见的方法名不一致，例如清单 7 中，foo 是 ActionScript 方法名，fooInAS 是回调函数的声明名称；
• 等待调用的 ActionScript 方法可以是 private，也可以是 public 的。

同样的，作为浏览器插件的 Java Plug-in 也可以与 JavaScript 进行通信。清单 8 和清单 9 列出了 Java 与 JavaScript 的交互代码。清单 8 列出的是 Java Plug-in 调用 JavaScript 方法的一种途径，其中引入了 JSObject 类，读者同样可以通过其他途径来实现。

Java code:     try {         Applet applet = this;         JSObject js = JSObject.getWindow(applet);         Object[] args = new Object[] { "a", "b" };         Object retval = js.call("fooInJS", args);     } catch (JSException e) {         e.printStackTrace();     }  JavaScript code:     function fooInJS(arg1, arg2) {         alert(arg1 + arg2);     }  HTML code:     
                  
             

Java code:     public String fooInJava(String arg1, String arg2) {         return arg1 + arg2;     }  JavaScript code:     var movie = document.getElementById("swfId");     movie.fooInJava("a", "b");

相对于 ActionScript 与 JavaScript 之间的交互，Java 与 JavaScript 间的交互略有不同，请查看 表 1 与表 2：

表 1. ActionScript/Java 与 JavaScript 交互的异同

比较项	ActionScript (JavaScript)	Java (JavaScript)
JS 所调用 callback 方法	需显示声明，JS 端可能因未找到声明而报错	Applet 入口类的所有 public 方法
插件内与外部 JS 可见的 callback 方法名	可以不一致	一致
JS 所调用的 callback 方法访问权限	public, internal, protected, private	public
调用 JS 时是否引入第三方类库	否，内部提供 flash.external.ExternalInterface	是，需要导入 jre\lib\plugin.jar，提供 netscape.javascript.JSObject
HTML Object	-	需设定 MAYSCRIPT 为 true
允许传参数和返回值	是	是
参数和返回值类型	基本数据类型，如 Boolean, int, uint, Number, String 等	包装了基本数据类型的 Object 类型，如 Boolean, Integer, Double, String 等

可以看出，ActionScript 定义的 callback 方法范围更广、权限更加灵活，但编程时更容易产生一些意想不到的错误。

充分了解了 Flash 及 Java Plug-in 与 JavaScript 交互的方法后，下面介绍 Flash 如何结合 Java Plug-in 实现力导向算法，从而提高运算效率。

核心思想是运用 Java 语言作为计算语言，ActionScript 作为绘图和矢量变换语言，通过 JavaScript 作为传输中介，Json 格式的 String 作为传输媒介，在浏览器端进行来回传输。

• 首先，Flash 将相关信息，如 Graph 的节点总数、所有边的始末点编号、Flash 舞台大小、迭代次数等，打包成 Json 格式的 String 通过 JavaScript 传输给 Java Plug-in；
• 随即，Java 通过迅速计算，得到每次迭代中所有点的坐标，同样以 Json 格式的 String 经由 JavaScript 返回 Flash；
• 接着，Flash 根据帧频定帧地更新坐标，重绘出整个 Graph。

图 6 显示了整个交互的流程图。

由于篇幅关系，本文不再给出 ActionScript+Java 的实现代码，读者可以在 中找到示例源代码。

从性能上分析以上两种实现，无疑是 Java Plug-in 以其语言在计算能力上的天生优势大大领先于 Flash 的 ActionScript。图 7 显示了在相同环境下，由于 Graph 中节点数的不同，对于两种实现的一组测试数据。

不难发现，随着节点数逐渐增加，当达到 300 个时，ActionScript 竟耗时 36.1 秒，整整比 Java 慢了近 10 倍！由于算法中的时间复杂度最高的部分是每次迭代时遍历所有节点并计算两两节点间斥力的过程，所以读者不妨认为这 10 倍之差是两种语言在执行迭代循环的 while 或 for 语句时的性能差距。

除了计算语言、节点数等两大主导因素，还会有哪些其他因素影响整体性能呢？我们是否必须借助 Java Plug-in 等外部插件来提升性能呢？在 Flash Player 10 中会不会引入新技术来打破 ActionScript 在计算性能上的瓶颈呢？如果将弹簧理论运用在三维空间中，是否会有新的性能问题出现呢？带着以上问题，作者会在将来的研究中给出进一步结论。

弹簧理论算法是一种呈现复杂社交网络关系图的尚佳的解决方案。本文简单介绍了在 Flash Player 中弹簧理论算法的两种实现方案，其中的后一种方案给出了解决 Flash 计算性能瓶颈的变通方案。而对于实现方案的性能所涉及的诸多因素也值得大家深究。

本文仅代表作者本人观点，不代表 IBM 公司观点。

描述	名字	大小	下载方法
文中用到的 Flash 示例程序	graph-bin.zip	96KB
文中用到的 Flash 示例程序源代码	graph-src.zip	159KB

学习

• 访问 ：获取社交网络分析的知识。
• 访问 ：获取力导向算法的核心理论。
• （SOFTWARE - PRACTICE AND EXPERIENCE，第 21 卷，1991 年 11 月）：获取更复杂详尽的力导向算法理论。
• 访问 ：获取 ActionScript 的知识。
• （developerWorks，2007 年 4 月）：ActionScript 3.0 是一种强大的面向对象编程语言，它标志着 Flash Player Runtime 演化过程中的一个重要阶段。
• ：学习运用 Flash 绘制出逼真的实时图像效果。
• 访问 ：获取 GraphML 的知识。
• （developerWorks，2008 年 9 月）：学习使用 ECMAScript for XML（E4X），挖掘 E4X 改进后的功能，它使 XML 数据的分析、计算、编辑以及相关操作更加简单明了。
• （ActionScript.org，2006 年 3 月）：了解 ActionScript 3.0 中的 E4X 新特性。
• 访问 ：了解 ActionScript 3 和 Java 如何处理 Json 对象。
• ：获取 Flash 中帧频的知识。
• ：获取 Java Plug-in 与 JavaScript 交互的知识。
• ：通过专门关于 Web 技术的文章和教程，扩展您在网站开发方面的技能。
• developerWorks 和：随时关注 developerWorks 技术活动和网络广播。

获得产品和技术

从 Json 主页下载 和 处理 Json 的第三方类库。

		傅冬雷目前在 IBM 软件开发中心的 Lotus 软件服务团队担任软件开发工程师，他致力于企业级社交网络分析网站的开发和维护，对 Flash/Flex/AIR 等富客户端技术具有浓厚兴趣。