一种基于网络图的计算机算法研究

敖卓缅

（阳江职业技术学院 广东省阳江市 529566）

分层结构网络图，一种基于网络图的计算机算法，它由时间差层组成，算法中运用一个名为“NeL2”的工具来处理分层结构网络图。分层结构网络图具有多个累积层，不是单一的网络图，利用这种分层结构，时间差可以包含在一幅图中。此外，各种类型的信息，例如图表在特定时间段内的总体趋势，都可以可视化显示；再如利用分层结构的网络图来表示学术文献的合著网络，使用分层结构网络图就可以看到合著网络中的变化，阅读各种信息，比如活跃研究群体的变化和其他现象。除了合著网络外，分层结构网络图还可以应用于各种数据的可视化，如思想处理器、网站变更等。

1 分层结构的网络图

网络图表示具有网络形式的数据，例如组织结构、计算机网络或学术文献的合著者。为了便于理解，经常要将这些数据可视化，这些可视化的网络图表示网络在某个时间点的状态（快照）。因此，为了确定一段时间内的“变化（差异）”，必须安排和比较几个快照，例如从去年到现在网络状态的变化，或者过去十年网络状态的变化等。此外，当使用只显示一个网络图的工具时，如果要仔细查看网络变化时，用户必须创建与快照的差异。分层结构的网络图就是把一个网络的演化看作是一系列的差异，再将差异序列表示为一个分层结构。为了处理此类图，创建开发一个名为“NeL2”的工具，它用Java（jdk5.0）显示和操作分层结构化网络图，其表达方法不是把一个网络图看作一个图形，而是把它看作几个层次的积累。举例来说，如果要参考过去一年网络的变化，所要观察的只是表示“去年数据”的图层，而要查看过去十年的变化，可以看到过去十年的变化堆积和图层。以同样的方式，堆积所有层可以让用户了解网络的当前状态。使用分层结构，可以有效地处理网络的差异。分层结构网络图算法研究如何从数学上定义分层结构网络，并解释工具“NeL2”，并以学术文献的合著网络为例，给出分层结构的网络图。此外，也假设其他类型的应用程序[1]。

2 网络图的分层表达

先引入一种分层结构来表达随时间变化的网络图。网络数据作为多个层单独管理，而不是作为一个单一的图表，每一层都取决于更新时间。网络图以灵活的方式显示数据并对其进行着色，这种方法可以帮助用户从网络图中读取大量信息[2]。

2.1 分层结构的概念

分层结构网络图算法研究处理的网络图具有分层结构的概念。这种结构类似于透明胶片（如OHP 片材），特定时间的更新保存在单个图纸（图层）上，在下一阶段完成的后续更新通过在现有图层上堆积新图层来保存。每次更新的更改都保存在每个图层上。使用分层结构可以实现以下操作：可以通过在某些点之间堆叠所有层来查看网络图，可以追踪网络的变化；当堆叠图层时，可以按时间顺序从过去追踪到未来；当按顺序移除图层时，可以按时间顺序从未来追踪到过去。可以通过单独阅读可选层，看到网络在这一层上的变化。通过多层叠加，可以看到网络在一定时期内的变化[3]。

图1：XML 中分层结构网络数据的描述实例

图2：滑块

2.2 使用分层结构的优点

使用分层结构的网络图有如下优点：

（1）当使用分层结构时，只需要一个网络图。以前，必须排列和比较多个图表，以查看网络中的差异。分层结构可以在一个网络图中表达这些变化，因为网络数据是由层与层之间信息的“差异集合”组成的，分层结构的网络可视化方法显示的是各种网络数据的差异。另一方面，“NeL2”在数据级别确定差异表达式，并通过集成这些差异来表示所有数据，该方法适用于网络演化的可视化。

（2）分层结构使网络图的操作更易于理解和直观。计算机应用通常执行与分层结构类似的操作，例如“从文档（论文）堆栈中提取第10-16 页”，在分层结构的网络图中也可以用同样的方法执行这些操作。

（3）分层结构有助于用户轻松掌握网络的特点。因为所有元素都同时显示在一个图中，用户可以在划分为层的网络图中看到随时间的变化。通过引入分层结构，用户还可以改变每一层节点和边缘的表示[4]。

2.3 网络数据格式

由于原始的XML 文档数据格式没有层的概念，如果用其来描述表示网络图的数据，就不能实现分层结构网络图要有效处理网络差异的要求。因此，要设计一种新的数据格式来表达图层信息，即具有分层结构的网络数据——层元素，其定义格式为（ID，node，edge，label，position，from，to）。我们用原始XML 文档格式描述了表示网络图的数据。与我们的技术不同，现有网络可视化技术使用的数据格式没有层的概念。因此，我们设计了一种新的数据格式来表达图层信息。具有分层结构的网络数据示例如图1所示。

因为每次添加层时网络图都会更新，所以层元素有一个ID 来表示更新日期。层元素中的节点元素（node），其表示一个节点，对应于数学定义中的v∈N。节点元素有两个属性：节点ID 和节点所属层的ID。层元素还包括边元素edge、label 元素和position 元素，其中边元素定义连接两个节点的边，它对应于数学定义中的e∈e，边元素也有两个属性：边ID 和边所属层的ID；label 元素和position 元素分别表示节点的标签和位置（x，y）坐标。层元素还有from 元素和to 元素，分别表示两端连接的节点，网络图更新时，节点或边可以根据实际情况增减。在这种情况下，将添加节点事件或边缘事件元素，而不是修改与已删除元素对应的节点或边缘元素。这些元素分别对应于数学定义中的N-和E-元素。节点和边的操作记录在这些元素上。当工具绘制图形时，这些元素会覆盖节点和边本身。使用这个数据格式的优点是，即使删除节点或边，也可以保存过去的状态。数据在操作系统加载后的状态下，无论它们属于哪一层，XML 文档、所有节点和边都是可见的。可以设计滑块来改变“NeL2”工具中的界面可见层，这样用户可以直观地操作网络图。可在设计中准备三个滑块，右边的两个滑块指定了可见层的范围，分别表示高层和低层的范围，用户可以使用左侧的滑块指定关注的层（关键层），网络图能够高亮显示指定关键层的节点和边（图2）[5]。

该工具左边滑块所示的关键层，加载数据之后自动生成，而且，所有的图层都是可见的，右边的两个滑块分别表示最新和最旧的图层数据。当要查看以某个网络演化为基础节点的网络图时，可以在顶部、右侧和底部看到相对较大的集群。但是，从网络视图中无法了解哪个集群是活动的，或者它什么时候是活动的。因此，需要操作两个右滑块，并由用户定义限制可见层。如通过操作左滑块将关键层设置为较低数值，表示不需要复杂的操作，只要简单的解释就可以自然地使用，可以看到修改指示的结果为节点连接到属于顶部集群的节点，而不是连接到底部集群的节点。当将关键层设置为很高数值时，位于左侧下方的许多节点被高亮显示，表明与最高群体对应的群体密切合作，而它与代表最低群体的群体的联系相对较远，在这一时期，与左下方的这个集群相对应的社区非常活跃[5]。

利用此工具使比较关键层和其它层变得容易。可视化合著网络的应用分层结构的网络图可以应用于此类情况，如可视化科学文献的合著网络[6]，科研合著网络的可视化，了解合著网络的这些变化有助于解释不断变化的环境、研究人员或研究领域内的趋势，以及其它状况的演化。通常合著是用数学方法定量分析的，然而，为了理解网络数据中的趋势，用直观的图表推测比用数学公式推测更为方便，有助于分析。分层结构网络图在这种情况下变得很有用[7]。

因此，分层结构的概念的引入有助于用户更容易地改变网络图的视图，并且可以假定合著网络的特征。其它应用实例分层结构化网络图也可以应用于各种数据的可视化，如网站的变化由于博客和相关工具的传播，拥有个人网站的人数正在迅速增加，这些网站每天都会被创建、修改或删除，分层结构网络图就可以在很好应用在这些场合。通过定期在图层上保存网站的更改，用户可以方便地检查任何时期的网站状态，或者如何加强或削弱网站之间的关系。利用可视化调试器的管理变更日志，将每次调试器使用数据流图保存为快照，并根据它们进行差异，使用“NeL2”工具，可以把差异指示程度通过指定特定层来实现[8]。

3 处理器

创意处理器是一类帮助重新排列思想和文档的软件。一些工具将想法标记为标签或节点，重新排列并在它们之间建立关系（用线连接它们）。当标签被视为节点，关系被视为边时，可以制作成一个层次结构网络图。将层次结构网络图用于idea 处理器的一些功能，如保存和播放，用户可以很容易地理解创意（ideas）的设计或修改。用户还可以看到创意的演变，因为它们是使用分层结构按时间顺序保存的。通过将这种过去的记录管理引入到idea 处理器中，可以很容易地遵循创意的安排和发展。

4 结束语

本文提出了网络图分层结构的概念，并给出了数学上的定义。使用层作为单位来表示网络随时间的变化，利用创建开发的“NeL2”的工具，用于处理分层结构化网络图。此外，它还提供自然操作，以便获得预期的图表。利用分层结构的网络图，可以掌握网络中的各种信息，如演化趋势和过程。采用分层结构，将合作作者网络的变化形象化，社区的形成和活动的活跃程度得到了明确的体现。