使用 Flash 描述复杂的社交网络-1 简介

look_w

社交网络简介本文主要介绍的是弹簧理论算法在社交网络分析中的应用、社交网络图作为数据源的通用格式、弹簧算法的 Flash 实现以及 Flash 结合 Java Plug-in 的实现， 因此首先需要对社交网络分析和弹簧理论的概念有一个初步了解。
社交网络分析 (SNA)简单来说，社交网络是一个由个人或社区组成的点状网络拓扑结构。其中每个点 (Node) 代表一个个体，可以是个人，也可以是一个团队或是一个社区，个体与个体之间可能存在各种相互依赖的社会关系，在拓扑网络中以点与点之间的边 (Tie) 表示。而社交网络分析关心的正是点与边之间依存的社会关系。随着个体数量的增加，以及个体间社会关系的复杂化，最后形成的整个社交网络结构可能会非常复杂。本文所讨论的复杂社交网络中节点数一般为 100 个，上限为 300 个，若超过该上限，网络形成的性能将大大下降。
社交网络分析最初是用于帮助人们理解人群中流行性疾病的传播情况并加以抑制。疾病的传播所强调的关键词即“接触”，而现在这种接触逐渐演化为人与人之间的交流和联络，在社交网络中以边的形式表现出来，一条边即表示两个个体间建立了一种关联（ties）。
一张社交网络图的形状可以直观地决定网络本身对每个个体的重要程度。一般而言，一张聚合度更高、更紧密的网络（cliques，如一个部落、家族等）对于每个成员的重要程度要远远小于一张与外网络有大量弱关联 (weak ties) 的松散网络（如一个开源社区、bbs 论坛等），如图 1 所示。
图 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 的伪代码描述了大致的迭代优化过程。
清单 1. 力导向核心算法实现伪代码

1 2 3 4 5 6 7 8 9 10 11 12

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

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

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

为了节省篇幅，省去了涉及细节的逻辑和计算，如参数的微调、斥力和引力产生的位移量公式等，如果读者有兴趣深入了解该算法可以查阅相关文献，详见 参考资源中的相关算法理论。另外，开发人员可以根据自己的偏好选择不同的编程语言来实现（后文中会提到 ActionScript 和 Java 的两种实现）。
该算法的平均时间复杂度是由两部分组成——每次迭代计算每两点间的斥力变化 O(n2) 和每条边给端点带来的引力变化 O(e)，共进行 k 次迭代计算，即 O (k * (n2+e) )。其中 n 为节点个数，e 为边数。图 2 描述了随着迭代次数的增加，力导向算法在 3D 网络图中节点相互排斥吸引的扩散过程。
图 2. 力导向算法下节点的迭代扩散趋势我们从图 2 中可以发现点和边的位移趋势：

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

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