论文部分内容阅读
当今社会互联网日益普及,近几年来涌现出了大量社交网站,这使得人们能够更加方便的利用网络交换信息实现自己的个人发展。如何将网站服务器中存储的大量用户数据构造成一个社会网络图并将其进行信息检索和直观分析形成了近几年来的一个重要研究方向——社会化网络服务。 作为社会化网络服务研究的一个重要方向,可视化技术主要研究如何将网站服务器中存储的大量数据如内容和用户等构造社会网络图并将其界面展示给用户,便于其直观分析数据。在可视化技术研究领域中,传统的布局算法当网络图规模较大时会遇到瓶颈,并且现有的评价标准都是算法设计者直接提出来的,并没有严格的理论和实验基础。 本文首先列举了关系图的一些可视化技术,然后介绍了node-link布局的两种弹簧布局算法——传统的单级布局方法和多级布局方法。基于传统布局算法的不足,本文提出了一种新的能快速对大规模(关系图节点规模在1000到10000之间)关系图布局的算法,并通过实验证明了该算法的优越性。同时本文在根据前人实验的结果提出了两种node-link评判指标,并分别设计了两组实验证明了利用该指标可以评判出布局结果的好坏。本文的主要研究内容如下: (1)提出一种新的利用简单随机抽样来提高斥力计算效率的单级布局算法,该算法对传统的布局算法的每个点的斥力计算所涉及到的点,斥力计算公式,引力计算公式进行了调整和优化,通过实验验证能大大减少单级布局算法的达到稳定状态的运行时间。 (2)结合基于抽样的单级布局算法和压缩-细化策略,本文提出了一种快速多级布局算法。该多级布局算法提出了一种新的压缩策略,使得每层压缩的图更加符合图结构,在细化每一层布局时采用了利用简单随机抽样计算斥力的单级布局算法,大大减少了大规模社会网络图的布局时间,同时该算法增加了布局结果居中的功能。 (3)传统的布局算法指标没有经过实验推断,要满足这些美学标准布局需要耗费很多的时间。本文根据前人实验推断结果提出了两种有社区结构的网络图布局算法的评价指标,同时其中指标之一还可以作为评判网络图是否有社区结构的方法。 (4)针对微博数据,本文设计并实现了一个微博关系数据分析系统,该系统集成了信息检索,对检索结果进行多种可视化选择,以及关系图扩展,路径查找,邻居查找,图信息显示,微博、博主、评论信息显示等功能。通过该分析系统,用户可以直观查找自己感兴趣的内容,并分析隐藏在查找内容之中的特性,便于二次查找。