基于Matlab平台社会网络-毕业论文.doc

1、毕业设计（论文）报告纸共 IV 页 第 I 页装订线摘 要社会网络是指人们根据相识关系所形成的网络形态。随着万维网的迅速发展，其中蕴含的社会网络迅速膨胀，其结构异常复杂，导致人们很难通过数字、表格或文字的方式对其进行表示、分析和管理，并使其中所包含的丰富信息资源难于被发现和有效利用。可视化方法可以将复杂的社会网络结构转换成美观的图形，辅助人们直观地理解社会网络结构并从中挖掘有用的信息，是社会网络分析的一个重要途径。在前人研究的基础上，本论文针对从照片共享网站 Flickr 中采集的社会网络数据，通过在 SqlServer 数据库管理平台上的 SQL 编程对社会网络数据集进行了压缩，并基于 Ma

2、tlab 平台设计和实现了布点算法对提取的关键网络结构进行了可视化展示。论文的详细研究工作包括：（1）通过考察 Flickr 网站，以 E-R 图的方式总结了 “用户” 、 “图片” 、 “标签”等数据的总体组织结构，对选取的 Flickr 数据集进行了简单说明，并从数据压缩方法和作图算法两个方面对目前社会网络可视化技术的研究现状进行了总结；（2）为了提高数据压缩的效率，提出了使用 SqlServer 平台上 SQL 编程的社会网络数据集压缩方案；按照方案，以给定用户作为中心节点提取了周边的局部社会网络，根据局部社会网络中用户节点度数选取了关键的网络节点，通过查找最短路径将中心节点与关键节点关

3、联起来，最终得到了三个矩阵形式表示的关键社会网络；（3）鉴于 Matlab 平台对向量操作和图形化操作的良好支撑，提出了利用Matlab 平台实现可视化算法和绘制关键社会网络图的方案；按照方案，首先设计和实现了相关算法按照“同心圆”的模式围绕中心节点对关键社会网络进行了初始布点，然后实现了力引导布点算法对关键社会网络进行了节点位置调节和可视化作图，最后设计和实现了相关算法引入辅助节点对作图结果进行了完善，得到了较为美观、清晰的关键社会网络图。关键词复杂网络，社会网络，可视化，可视化算法，压缩算法，布点算法毕业设计（论文）报告纸共 IV 页 第 II 页装订线ABSTRACTSocial net

4、work is formed by people with acquaintance relationships. With the rapid grow of the World Wide Web, the social network in cyberworld expands fastly, and its structure is so complex that the traditional methods like figures, tables or text are useless to show, analysis and manage the social network,

5、 making a wealth of information resources contained hard to be discovered and used effectively. Visualization, an important way to analysis social network nowadays, can convert complex social network structure into beautiful graph, therefore help people intuitively understand social network structur

6、e and dig more useful information in it. Based on previous research efforts, this thesis mainly focuses on a social network dataset retrieved from the photo-sharing website Flickr, by extracting key network for the dataset through SQL programs on SqlServer platform, designing and implementing algori

7、thms to layout and display the key network on Matlab platform. In detail, the research work in the thesis includes: (1) By study the Flickr website, the overall organizational structure of data containing “user“, “image“ and “tag“ is summed up and illustrated in an E-R diagram, the selected data set

8、 of social network in Flickr is introduced, and the current art of state of social network visualization technology is explained in two aspects of data compression methods and layout algorithms;(2) In order to improve the efficiency of data compression, a new scheme is proposed which bases on SQL pr

9、ogramming on SqlServer platform; according to this scheme, the local social network surrounding a given user (noted as the central node in the local network) is extracted, some key nodes with big degrees in local social network are selected, the nodes locating on the shortest path of the central nod

10、es and key nodes are selected, and eventually three key social networks are retrieved and represented in matrix forms.(3) Because that the Matlab platform can well support vector operations and graphics operations, a visualization scheme is proposed which uses Matlab to implement visualization algor

11、ithms and draw the key social network diagrams; according to this scheme, an algorithm is designed and implemented to initially layout nodes in the key social networks in a “concentric circles“ pattern, a traditional force-directed layout algorithm is implemented to automatically adjust the position

12、s of nodes in the key social networks and to draw the diagrams of key social networks, another algorithm is designed and implemented to import auxiliary nodes into the diagrams of key social networks to make these diagrams more beautiful and more intuitionistic.KEYWORDSComplex network , Social Netwo

13、rk , Visualization , Visual algorithm , Compression algorithm , Layout algorithm毕业设计（论文）报告纸共 IV 页 第 III 页装订线目 录摘 要 .IABSTRACT .II1.1 研究背景 .11.2 国内外研究现状 .11.2.1 国外研究现状 .11.2.2 国内研究现状 .21.3 研究内容、方法、手段及预期成果 .21.3.1 研究内容 .21.3.2 研究方法及手段 .21.3.3 预期成果 .31.4 章节安排 .3第二章 Flickr 网站及可视化技术简介 .42.1 Flickr 网站 .42

14、.1.1 网站简介 .42.1.2 网站总体结构 .52.1.3 数据集 .62.2 数据压缩技术概述 .62.2.1 压缩与可视化的关系 .62.2.2 压缩算法的概述 .72.3 可视化作图技术概述 .82.3.1 作图算法的要求 .82.3.2 作图算法的思想 .82.4 小结 .10第三章 社会网络数据压缩 .113.1 总体数据压缩思路及方案 .113.1.1 压缩思路 .113.1.2 压缩方案 .113.2 提取给定用户周边局部网络 .123.2.1 关键表设计 .123.2.2 提取周边好友节点 .123.2.3 提取好友的出入度数 .153.2.4 结果数据分析 .163.3

15、 选取关键节点 .163.4 生成关键网络 .173.4.1 最短路径算法的概述 .173.4.2 实现最短路径算法 .183.4.3 生成关键网络节点的关系矩阵 .203.4.4 关系矩阵的结果展示 .213.5 小结 .22第四章 社会网络可视化展示 .23毕业设计（论文）报告纸共 IV 页 第 IV 页装订线4.1 总体思路 .234.2 初始布点 .234.3 可视化布点算法 .254.3.1 布点算法的思路 .254.3.2 布点算法的伪代码 .264.3.3 Matlab 实现及结果 .274.4 基于 Matlab 的辅助点展示 .304.4.1 扩展研究的意义及算法概述 .30

16、4.4.2 MATLAB 实现示例及结果 .334.5 小结 .35第五章 总结与展望 .365.1 课题研究总结 .365.2 不足与展望 .365.2.1 不足之处 .365.2.2 未来发展趋势的展望 .37致谢语 .39参考文献 .40毕业设计（论文）报告纸共 41 页 第 1 页装订线第一章 绪论1.1 研究背景近年来，信息系统如万维网、电信网、移动通讯网络迅猛发展，可获得社会关系网络数据的规模逐渐增大，以致人们无法通过传统的技术和方法来管理和运作这些复杂网络。人们通过对 Web 网络、社会关系网络、生物网络等的研究，发现了这些网络都具有某些共同的性质，这些性质包括：(1)整体稀疏，

17、局部密集；(2)顶点度数服从幂率分布，也被引申为无尺度特性；(3)整体分布具有高聚集度、低平均最短路径( 平均最短路径=O(loglog N)，具有小世界特性。具有以上性质的网络被称为复杂网络。如果仅用数据表格或文字的形式来表示复杂的网络，理解起来非常困难，导致网络所包含的信息无从体现。将复杂网络方便、直观地表示出来的最好方法是将其进行可视化。科学计算可视化的思想是上个世纪 80 年代美国科学基金会(NSF)提出的。当时在科学计算中产生了大量数据，人们很难清楚知道这些数据所表示的含义以及数据之间的关系，于是提出了将它们以图形化的方式显示出来的可视化思想。复杂网络研究的兴起进一步促进了网络可视化

18、技术的发展，同时对可视化技术提出了更高的要求。复杂社会网络可视化一方面可以通过精确的结构展示帮助人们认识网络的内部结构，另一方面可以帮助挖掘隐藏在网络内部的有价值的信息1。其中受关注度最多的一个问题是可视化技术，包括布点算法和可视化压缩算法。布点算法中最重要的一个分支是 P.Eades 提出的力导引 (FDA，Force-Directed Algorithm)算法2，而可视化压缩算法的提出和发展则使得可视化技术用于复杂网络成为可能。社交网络是互联网用户根据相识关系所形成的一个虚拟网络结构，可以充分发挥“草根网民 ”的集体智慧，代表着互联网的未来发展方向，其典型应用如博客、播客、交友网站、即时通

19、讯工具等。从拓扑结构上看，社交网络是一种特殊的复杂网络（其它的复杂网络例子如交通网络、基因网络、网页超链接网络等） ，具有“六度空间”理论所描述的“小世界”特性。目前已有大量的社交网络建图算法，国外也有一些现成的建图工具。通过可视化建图来展示社交网络的拓扑结构，具有数字和图表所无可比拟的优势，是社交网络研究的重要手段。1.2 国内外研究现状1.2.1 国外研究现状国外研究现状伴随着网络技术的突破性进步和互联网的应用，国外研究人员于毕业设计（论文）报告纸共 41 页 第 2 页装订线20世纪90年代中期开始了复杂网络可视化的研究。近年，随着网络和计算机用户队伍的壮大，人们对复杂网络可视化的研究十

20、分地关注。其中，寻找可视化算法是关键，先后出现了由P.Eades提出的力导引(FDA，Force-Directed Algorithm)算法2以及发展出的各种改进算法T. Kamada和S. Kawai提出的KK算法3和T. M. J. Fruchterman和E. M. Reingold提出的基于再次改进的弹性模型的FR算法4；这些都属于布点算法。在将复杂社会网络中海量的数据量进行压缩和实现将复杂的大规模图形转化为较为美观的小规模图形的过程中，可能会使原始图形失去连接性；为了保留原始图形的连接性，使社会网络关系图不失真，Feder和Motwani、Adler和Mitzenmacher等人、A

21、T &T Research的Gilbert和Levchenko 、AT &T Research的由Koren等人组成的团队都先后提出了相似的压缩算法。1.2.2 国内研究现状国内互联网技术的引进和推广晚于国外发达国家，但是，近几年来随着互联网技术在国内地不断发展壮大，为在该领域的理论研究和学术探讨创造了条件，国内研究专家也开始了对可视化技术的学术研究工作。主要的研究人员有王柏，吴巍，徐超群，吴斌和刘军等人，他们都取得了一定成果。但至今，国内的技术还不够成熟，无法广泛地进行复杂网络可视化研究的普及和资源共享。1.3 研究内容、方法、手段及预期成果1.3.1 研究内容（1）从现有的 Flickr

22、社交网站中提取数据集 Flickr Links 和 Flickr Wall Posts，将其导入到 SQL Server 数据库中，然后基于 Matlab 技术实现社会网络的建图。（2）选择并实现布点算法，实现均匀布点和绘出美观而清晰的社会网络图。（3）选择并实现压缩算法，实现压缩一部分次要的数据，使图不会过于复杂和混乱。（4）采用基于 Matalb 开发工具来建图，结合布点算法和可视化压缩算法来开发出相应的应用程序，实现社会网络可视化建图。1.3.2 研究方法及手段（1）把每一个用户看做图像中的一个顶点，把用户之间存在的关系用图形中的一条连线表示。（2）从美学的角度来看，要求布点算法应尽量满

23、足这几个要求：整体布局对称性；避免边的交叉和弯曲；保持边长统一；节点分布尽量均匀。经过前人的不断地研究和实验，从中选择合适的布点算法并将其实现。毕业设计（论文）报告纸共 41 页 第 3 页装订线（3）随着网络规模的不断增大，单纯地应用以往经典的布点算法来作图，已经无法满足实际应用中可视化展现复杂网络的需要。其遇到的困难主要体现在性能和可阅读性两方面：一方面，大数据量的节点位置调整耗费过多的计算资源；另一方面，将所有节点展现在结果图上，使人根本无法从中获得任何有效的信息。为了更好地帮助人们理解复杂网络的整体拓扑结构，使用可视化压缩算法可以压缩一部分数据，从复杂的网络数据中选取关键的数据并将其可

24、视化，这样绘出的社会网络可视化图就更有信息含量，基本上都包含了用户所需要的信息。压缩数据的核心是选取网络中那些拥有较多好友的用户为关键数据。（4）利用 SQL 编程语言实现社会网络数据的压缩，利用 Matlab 实现布点算法来绘制社会网络可视化图。1.3.3 预期成果（1）将从 Flickr 网站获得数据集导入到 SQL Server 数据库中，在 SQL Server中生成数据库 db_flickr_Data.mdf；同时生成 dtUser 表和 dtLink 表。（2）实现合适的布点算法和压缩算法，产生相应的应用程序。（3）绘出基于 Matlab 的社会网络建图。（4）完成毕业论文。1.4

25、 章节安排本文详细地阐述了复杂网络可视化算法，以及这些算法是如何优化从而达到美学标准和尽可能展现清晰的结果。本文其他部分组织如下：第 2 章将介绍 Flickr 网站及社会网络数据集即研究数据的来源，并从数据压缩方法和作图算法两个方面对目前社会网络可视化技术的研究现状进行了总结。第 3 章将介绍基于 SQL 编程的社会网络数据集的压缩方案，并按照方案最终得到了矩阵形式表示的关键社会网络。第 4 章将介绍利用 Matlab 平台实现可视化算法和绘制关键社会网络图的方案；并按照方案扩展和实现了力引导布点算法对关键社会网络地可视化作图，最后还设计和实现了相关算法引入辅助节点对作图结果进行了完善，得到

26、了较为美观、清晰的关键社会网络图。第 5 章将总结社会网络可视化的相关问题并对其未来发展方向进行展望。最后，发出由衷地致谢并列出参考文献。毕业设计（论文）报告纸共 41 页 第 4 页装订线第二章 Flickr 网站及可视化技术简介本章在介绍 Flickr 社交网站的基础上，对网站中社会网络数据的组织方式进行了分析，对选取的 Flickr 数据集进行了简单说明，并从数据压缩方法和作图算法两个方面对目前社会网络可视化技术的研究现状进行了总结。2.1 Flickr 网站2.1.1 网站简介Flickr 是一家既提供免费又提供付费的数位照片储存和分享方案，也提供网络社群服务的平台。一般认为 Flic

27、kr 是 Web2.0 应用方式的绝佳例子。许多使用者除了可以在 Flickr 上分享他们的私人照片，也可以把该服务作为网志图片的存放空间，因而，该网站受到许多网志作者地喜爱。Flickr 受欢迎的原因是它是一款创新的在线社交工具，能够将照片标上标签（Tag）并且以此方式浏览。Flickr 集合了通过使用者间的关系而相互连接，依其连接内容彼此产生关联。图片上传者可自己定义该相片的关键字，也就是“标签（Tags） ”，这样搜寻者可很快地找到想要的相片，例如可以把指定拍摄地点或照片的主题作为标签，而创作者也能很快地了解相同标签（Tags）下有哪些由其他人所分享的照片。Flickr 也会挑选出最受欢

28、迎的标签名单，缩短搜寻相片的时间。Flickr 也让使用者能够将照片编入“照片集（Sets） ”，或是将有相同标题开头的照片结成群组（Group） 。然而，照片集比传统的资料夹分类模式更有弹性，因为一张照片可被归类到多个照片集中，或是仅分到一个照片集中，或是完全不属于任何的照片集。使用者除了可透过 Tags 分享照片外， Flickr 也提供连络人机制（Contacts ） ，通过 Contacts 机制，使用者可看到对方最新的照片，以及快速浏览该连络人的公开相片。使用者也可通过将私人照片加入其他公开 Group，供群组内的所有会员浏览，有些 Group 更提倡会员之间互相交流，如著名的“1-

29、2-3”Group，即提倡“ 在群组内贴出 1 张相片后，至少看 3 张群组内的其他照片，并至少帮其中 2 张照片留言”，这样可以提高相片曝光率。另外 Flickr 也会参照浏览数和被加入最爱的次数，选出当日风格照片于站内刊登。总之，Flickr 网站是一个绝佳的图片交流网站。Flickr 网站的界面介绍图如图 2.1 所示：毕业设计（论文）报告纸共 41 页 第 5 页装订线图 2.1 Flickr 网站界面图总之，Flickr 不仅仅可以帮助用户在线存储及分享相片，还为用户提供了很多的服务功能：1、用户拥有自己的主页，用来发布照片或图片。2、浏览者可以对照片发表个人评论。3、支持各种规格的

30、图片，从大头贴到大幅写真，都能上传。4、可以对图片进行编辑，比如放大、缩小或旋转。5、用户可以对上传照片的访问权限进行设置，对浏览照片和评论的人进行限定。6、用户可以直接通过电子邮件或照相机上传照片。7、可以将照片发布到大部分博客网站(LiveJournal， Blogger，Moveable Type，Typepad， Manila，等等)。2.1.2 网站总体结构通过对 Flickr 网站的初步分析，基本上把握了该网站的总体结构，同时用 E-R图来描述该网站的总体结构，如下图 2. 2 所示：发布评论用户好友 I D标签图片登录密码最爱图片性别年龄u s e I d姓名所在地相册好 友发布者发布时间评论者 评论内容B e l o n g sT i t t l e拍摄时间附加咨询P H O T O I DI D添加*图 2.2 Flickr 网站的 E-R 图毕业设计（论文）报告纸共 41 页 第 6 页