在线社交网络分析及可视化系统研究与设计

HOLLY 1160 271 255 1 10 HOLLY BRAZEY 1214 577 255 1 10 BRAZEY CAROL 671 612 255 1 10 CAROL PAM 985 127 255 1 10 PAM *Tie data

from to friends strength HOLLY PAM 1 1 CAROL HOLLY 1 2 BRAZEY CAROL 1 2 PAM BRAZEY 1 3

DL数据格式

顶点列表格式示例: dl n=50

format=nodelist data: 1 7 8 2

3 19 21 49 6 2 6

dl标记了该文档的类型是DL数据。n的值表示图这幅图包含的顶点数量的上限。“format = nodelist”指示文档具体类型是顶点列表格式，以此区别于边列表、全矩阵格式。data则是上面图元数据和下面图的具体描述数据的分界。第一行表示id为1的顶点连接到id为7, 8, 2的三个顶点，其他行含义相同。 边列表格式示例: dl n=50

format=edgelist data: 1 7 1 8 1 2 3 19

“17”表示id是1和7的顶点之间有边连接。其他行含义相同。 全矩阵格式示例:

dl n=5

format=fullmatrix data: 00100 00011 10010 01100 01000

这里就是用图的邻接矩阵来描述整幅图。

9

3.1.2 GraphML

GraphML是一种很容易使用的描述网络图的文档格式。GraphML基于XML技术，XML即可扩展标记语言(EXtensible Markup Language)，区别于HTML，XML被设计为结构化、传输和存储数据。一份XML文件必须包含根元素，根元素是所有其他元素的父元素。XML文件中的元素形成了一棵文档树，具有良好的结构和可读性。所有元素均可拥有子元素。父、子以及同胞等术语用于描述元素之间的关系。父元素拥有子元素。相同层级上的子元素成为同胞(兄弟或姐妹)。

由于GraphML具备良好的通用性、可读性、可扩展性并且容易实现其解析程序，在诸多项目中都采用GraphML作为网络图的存储方式。本文在系统实现部分就采用了GraphML技术。下面是GraphML文档的简单示例:

文档中

10

之间的边。 以上文档图的可视化结果：

3.2 制图算法

3.2.1 Random Layout

制图算法决定了整幅图中所有顶点和边的展示方式，目的在于帮助用户能够以一种更优的和自己想要的方式观察网络结构。由于某些制图算法的计算复杂度较高，所以用户必须在图的呈现方式和展示效率中作出权衡，也就是说，需要依据网络规模的具体需求，选择恰当的制图算法。例如Spring Embedding Layout算法虽然可以得到清晰的可视化结果，但因为计算复杂度高，一般只适合可视化包含数百个顶点的中等规模的网络。

Random Layout随机化顶点在图中的位置。这种制图方法生成的可视化结果难以观察，但优势是计算复杂度与网络规模线性相关，一般适用于大规模网络的可视化。

3.2.2 Spring Embedding Layout

Spring Embedding Layout ( Force-Based Layout)模拟物理力系统，顶点之间存在相互排斥力，边相当于连接顶点对的弹簧。算法运行时，排斥力分离顶点集合，边则将顶点有序组织成图。算法过程通过数次迭代，图不断趋于平衡，顶点在一次迭代过程中确定的位置，在下一次迭代过程中保持不变。算法的可视化结果可以清晰的展示图结构，图中一般没有或很少出现边交叉，不会存在顶点重叠的情形。算法计算复杂度为O(nlog n)或O(e) ，n和e分别表示图中顶点和边的数量。该算法通常只适用于可视化中小规模的网络图。算法可视化结果示例如下:

11

3.2.3 Tree Layout

Tree Layout的基本思想是以树形结构展示图，选择一个顶点为根顶点，其他与根顶点直接连接的顶点则成为儿子顶点，而与儿子顶点直接相连的所有顶点又称为儿子顶点的儿子顶点，如此下去。Tree Layout通常有水平、垂直和放射状三种排列顶点的方法，其中放射状树是社交网络可视化中常使用的方法。Tree Layout示例如下：

12