在线社交网络分析及可视化系统研究与设计
摘要
近年来，随着Web2.0等互联网新概念的日益付诸实践，社交网络作为其中一种新兴的，实用的交友模式，依赖其真实性，稳定性等特点得到了用户的青睐，在网络活动中发挥着越来越重要的作用。我们可以看到，很多社交网站在最近几年取得了巨大的成就，例如Myspace 己经成为全美最受欢迎的网站之一，统计表明其流量相当于Internet 总流量的4.46%； Yahoo 的图片分享及社交网络结合体Flickr ，己经拥有超过400万用户和2亿上传图片；而作为全美第二大的社交网站Facebook ，在创立的短短三年之内，市值就已达到了惊人的150亿美元; 在国内方面，“校内网”作为大学生最主要的交流平台，也已经拥有超过2200万真实注册用户。
社交网络是指建立在真实人际关系基础上的网络平台，是作为现实中的社会团体在互联网上交流的辅助工具而存在。社交网络是现实活动的在线拓展，与传统的虚拟网络有很大的不同。传统虚拟网络脱离社会现实，结构相对无序、混乱，而社交网络作为现实人际网络的子集，同样具有人际网络的一些特征，正是基于如此我们认为对社交网络进行一定的研究是可行的，这对于促进社交网络的进一步发展具有重要的理论意义。
本文以社交网络为平台，以计算机图论知识为基础，对人际关系做了深入的研究和分析。在此基础上提出了对于在线社交网络的可视化中图的表示和制图算法。
关键字：在线社交网络 可视化系统 用户影响力 社区挖掘
1. 绪论
1.1 课题的背景和意义
在互联网发展初期，以电子邮件，QQ ，MSN 以及雅虎通为代表的即时通讯工具在网络社交中扮演了非常重要的角色。电子邮件作为社交网络的起点，解决了远程传输邮件的问题。为当时的人们提供除了打电话和写信之外，另外一种便捷、低成本的交流方式。
这类通讯工具作为第一代交友模式的平台，满足了人们无线通讯，网络交友等需求。第一代社交网络主要是建立在虚拟性、隐蔽性的交友模式基础上，具有很大的弊端。首先，第一代交友模式的使用者是以好奇心强、精神世界具有青春期特有矛盾、是非辨别能力尚未完善、社会经验较少的青少年为主力军，很多不法分子利用交友模式的虚拟性与隐蔽性来伪装个人真实身份、年龄等信息进行欺骗活动。另外，随着互联网的发展，大量信息蜂拥而至，如何迅速快捷获得有效信息，成为互联网使用者越来越尖锐的需求。虚拟网络交友模式，由于其使用者的交友圈的低信任度，充斥着大量的无用信息和欺骗信息，极大地妨碍了现代社会要求的快速、轻松、便捷地获取信息的需求。因此，第一代网络交友模式的发展渐渐出现疲乏。但是其开启了以互联网为平台的网络交友和即时通讯的先河，为第二代网络交友模式的创建提供了宝贵的经验与借鉴，同时也为第二代网络交友模式的兴起奠定了基础。 随着网络社交的迅猛发展，一个节点在网络上的“画像”更加趋于“形象”，这也代表着SNS ( Social Network Service)的悄然出现。网络化进程的快速发展，使得人们更愿意把很多日常生活也搬到网络上来。社交网络正是为方便人们的日常交友需要而诞生和发展起来的，是新兴的第二代网络交友模式，建立在使用者现实生活中的社交圈子的基础上，为其的交友需求提供了纯净、高信任度的网络平台。
第二代网络交友模式弥补了第一代网络交友模式中虚拟交友的弊端，并充分地利用了网络即时通讯的便捷，可以将现实中的交友圈子搬上网络，志于为使用者提供透明纯净、通讯快捷的交友平台，可以为使用者提供较为真实的信息，极大地满足了人们以学习、工作为目的商务交友需求。
从现在的网络发展形势来看，我们可以发现网络上的服务越来越贴近人们的生活，朝着便捷化人们生活的方向发展。21世纪兴起的社交网络，作为一个新的网络服务，也紧跟着网络发展的大潮流，为人们日常的在线交友需要提供了非常便捷有效的服务。
正是基于上述背景，我们选取了社交网络作为研究对象，对XXXXXX 进行了深入的研究和分析，本项目关注的问题其一是在线社交网络的特性，主要分析了其中社区挖掘和用户影响力研究的现状并作出总结 ，然后是对于这些信息的可视化，提示了以图为核心的可视化算法。
公认的互联网三大应用是电子邮件，即时消息和信息搜索。社交网络，从前面讨论中可以看到，由于满足了人们商务交友的新需求，近几年得到迅速发展，逐渐成为互联网的第四大应用，在Web2.0的浪潮中起着举足轻重的作用。因此，对社交网络进行研究，对于我们深入了解其发展方向具有非常重要的指导意义，也必将对社交网络的进一步发展起着积极的推动作用。
用户与社区作为社交网络的核心，是社交网络发展的根本推动力所在，对社区进行有效的挖掘，能更好的理解网络结构，协调好各个社区内的关系。因此，对用户的影响力进行有效的评估，具有非常重要的指导意义。而用户的影响力是指用户对周围的人所能产生的影响及带动作用，是用户在社交网络中的重要性的衡量。用户的影响力作为用户的重要指标，是社交网络中各种关系的基础，用户的影响力越大，所受到的关注程度也越高，对网络的反馈作用也就越大。对用户的影响力进行衡量，能为网络中的用户进行合理的排序，为社交网络
的拓展应用及进一步发展提供理论基础，同时通过社区识别技术可以优化基于用户影响力排序的结果。例如，当我们想寻找网络中满足一定条件的用户，比如有相同兴趣或者一样的出游计划的用户时，满足条件的用户可能会很多，那么如何在最短时间内从中选取最合适的结果，用户的影响力就是一个非常重要的指标；再比如，随着社交网络的发展，我们有理由相信，未来更多的商业化活动将被移植到网络上来。当我们想在社交网络上推广某种商品或者服务时，如何选取首批推荐使用产品的人群会直接影响到推广活动的效果及代价。这时候，影响力比较大的用户往往成为活动的首选人群。通过他们的介绍和宣传，能将商家的商品更快、更有效的传播给网络中的其余用户。
同样，对社区识别技术进行研究也具有非常重要的理论意义。社区反映了网络中的用户的分布情况及活动范围，对其深入研究可以帮助我们更好地了解网络结构，协调好各个社区间的关系，掌握网络中的信息组织，流动及发展状况，同时也有助于商家进行有针对性的商业活动，能对网络中的信息资源进行进一步合理的整合，为信息的查询，搜索提供更为方便快捷的途径。
总之，用户与社区作为社交网络的核心，是社交网络发展的根本推动力所在。用户影响力评估系统和社区识别算法对于优化社交网络中的信息整合，促进社交网络的发展具有非常重要的理论意义。
1.2 国内外研究现状
对于社区挖掘方面：社交网络[1]是真实的人际关系网络，可以用顶点和边来展示社交网络。基于图理论，运用多种方法对社交网络展开分析，可以帮助人们发现社交网络中的有价值信息，例如发现网络中的重要顶点、找出与某顶点最为相似的顶点等。在多种社交网络分析方法中，挖掘出网络中的社区结构[2]是研究的热点问题。社区结构不仅存在于社交网络中，也存在于生物化学网络[3]、万维网[4]等其他复杂网络中，因此社区挖掘问题研究具有重要现实意义。
在理论研究方面，Hastie[5]等人在2001年提出的基于相似度的层次聚类算法能够在无需任何先验知识的情况下，挖掘网络中存在的社区结构。该算法通过计算所有顶点对之间相似度，得出相似度矩阵，然后进行层次聚类过程，可以用树状图表示该过程，树状图揭示了网络的层次结构特征，树状图的分割位置不同得出不同的社区划分结果。后人针对该算法的改进主要集中在两个方面，一方面，定义新的相似度计算方法，提高效率；另一方面，更准确的揭示网络中存在的层次结构。例如，Sales-Pardo[6]等人在2007年提出一种基于模块度的顶点附着力概念，用来衡量顶点间相似度。Clauset[7][8]等人在2004, 2008年发表的论文引入层次随机图的概念，试图更精准的描述网络层次结构特征。Santo Fortunato[9]对社区挖掘问题以及现有的算法进行了详尽的分类总结。
在实际应用方面，存在多种社交网络分析工具，可以大致将这些工具分为三大类。第一类，主要用于科学研究，例如Pajek[10]、 UCINET[11]、 NodeXL[12]等都是较著名的用于网络分析的软件，这类软件主要面向科研工作者，可以运用多种复杂的分析手段对较大规模的网络进行分析。第二类是面向普通用户的网络分析工具，较有代表性的有在线应用TouchGraph[13]、桌面应用Vizster[14]以及由IBM 研究院和IBM Cognos 软件组织推出的ManyEyes[15]在线应用，这类工具区别于科研工具，具有操作简单、展示方式有趣等特征。最后一类是面向开发者的软件开发包，开发者可以利用开发包开发个性化的社交网络分析工具，较著名的有JUNG[15]、Prefuse[17]、GraphViz[18]等。
在用户影响力方面：对社交网络中用户间的影响力量化的研究由来已久，其中最主要的方法是将影响力以概率的形式表现，对于不同类型的社交网络，用户间的影响力有不同的定义，相应的，对应的影响力量化模型也有可能随着影响力定义的不同而不同。
Singla 等[19]提出了用户间也考虑了进去，提出了量化动态社交影响力的时间依影响力的存在并作出了定性的分析。Anagnos-topoulos 等[20]和Crandall 等[21]都将用户间的影响力定义为用户间的相似性或者相关性。但他们只是提供了关于社交影响的定性的发现，而没有提出具体的影响力的量化方法。
Goyal 等[22]也将用户间的影响力定义为用户间的相似性，但他们的工作主要针对的是在线电子商务网站，比如亚马逊等，他们将这类社交网站中用户间的相似性定义为有着相似购买行为的现象。在这类网站中，没有显式的社交信息存在，只有用户的活动历史日志是可以得到的。因此，他们提出了从用户的行为日志中学习用户间影响力的模型。同时，由于在线电子商务网站本身不存在显式的社交关系，M.G.Rodrigue 等[23]提出了从用户日志中学习社交网络结构的算法。
Tang 等[24]的研究主要关注合作网和引用网等社交网络，在这些社交网络中，用户通过合作和引用的方式被其他用户影响。他们提出了主题亲密度传播模型TAP (Topical Affinity Propagation) 来对用户间的主题明确的影响概率进行量化。通过给定的社交网络和每个用户的主题分布，找到主题明确的社交网络子网和子网成员间的主题明确的影响力权值。Wang 等[24]进一步拓展了TAP 模型，将时间因素赖因子图模型( time-dependent factor graph) 。
对于在线社交网络中用户间影响力量化的研究，可以分为两大类，分别基于在线社交网络中用户的两种不同的信息:关系信息与转发信息。最简单的基于关系信息的方法是使用一个均匀分布来评估用户和他的所有朋友间的影响力，此时仅仅涉及用户间的朋友关系信息。用户的所有朋友对用户的影响力都是相同的，都等于用户的朋友数的倒数。因此，该模型被称为均匀模型，模型背后的隐含的假设是用户的朋友间存在着十分高的同质性，因此，用户被任何两个不同的朋友影响的概率是相同的。Kwak 等[26]使用了均匀模型来量化用户间的影响力并对量化得到的结果应用pagerank 算法来找到最有影响力的用户。
Weng 等[27]同样基于关系信息提出了主题敏感的用户间影响力量化模型，仍然使用pagerank 算法来找到最有影响力的用户。他们的量化模型基于他们从数据中观察到的现象:用户间存在着较高的互粉率，他们将这归因于同质性。然而其他的研究表明在线社交网络中的互粉率并不高，甚至偏低，这与他们的观察结果相矛盾。
Tang 等[28]提出了一个不同的方法，它不但利用了在线社交网络的关系信息，还使用了用户的标签信息。对于每一条关系，都会有一个对应的标签，指代关系的类型，例如亲戚、师生等。他们提出了一个算法，当标签不存在时，可以使用现有的关系信息和标签信息来预测它。在每条关系都有了标签后，给予每个标签一个固定的影响概率。最终，他们将量化的结果应用到了影响力最大化问题中。
在基于转发信息的方法中，通常将用户间的影响力定义为用户间的转发概率，这也是目前最普遍的定义方式，表示用户的一条转发信息来自于其中的某一个朋友的概率。一般使用用户的转发频率统计量来量化用户间的转发概率，转发概率是与用户来源于他的朋友的转发信息的频率成正比的。由于转发概率的这种量化方式是通过极大似然估计法推导而得出的，因此该模型被称为极大似然模型。
Welch 等[29]同时研究了朋友关系与转发关系的语义。他们通过对关系信息与转发信息同时应用pagerank 算法获得地用户排名结果进行分析并得出结论:转发关系更好地保留了用户间的传递性，因此转发关系是比朋友关系更强的影响力指示器。
Pal 等[30]使用了主题敏感的转发信息和极大似然模型来量化用户间的影响力并从Twitte 中找到了主题相关的权威用户。同样的，Meng Zhang 等[31]也拓展了极大似然模型，提出了一个动态模型来量化用户的影响力。
1.3 本文主要工作
第一分析了在线社交网络的构成和性质。对于其中的重点问题例如：数据挖掘、用户影响力等做出了概括
其次，提出了对于在线社交网络可视化的方式，即用图来表示在线社交网络并给出了初步的方式。
2. 在线社交网络的初步讨论
2.1 社交网络的定义
社交网络即社交网络服务(SNS)，英文全称为Social Network Service，是指人和人之间通过朋友、血缘、交易、网络链接、疾病传播、理想、兴趣爱好等等关系建立起来的社会网络结构。在网络中，人与人之间通过点评、群组等功能，来为网络的用户进行“画像”，当这种“画像”越贴近显示中人的社会性，网络的社会化程度就越高。
社交网络起源于网络社交，随着网络交友的迅速发展，社交网络也在其中慢慢形成、演化、发展，为人们的生活提供更便捷的信息交流。社交网络一直朝着“节约社交时间和物质成本，获取高速、有效的信息”这一方向发展。社交网络通过网络这一平台，把不同的人联系起来，形成具有某一特点的团体。
研究表明，社交网络覆盖了社会的各个层次，上次国家外交，下至家庭关系，并且对于问题的解决，组织的运营，以及个体的成功都起到了非常关键的决定性作用。
2.2 在线社交网络的组成
社交网络包括节点，关系，用户群，社区等基本概念。
2.2.1 节点
节点，即网络中的个体，也称参与者(Actor )，指的是社交网络的参与者，即在一个网络中与他人(行动者) 相联结的具体的个人、组织、事件或其他集体性质的社会实体。
2.2.2 关系
关系，指的是指节点和节点之间的连接。在个体层次上，人和人之间如果相互认识，或者有共同的兴趣和属性，称之为他们之间具有某种关系。在社交网络上，关系指的是基于朋友关系而建立起来的网络连接，体现的是两个网络用户之间的相互信赖。一般而言，他们之间拥有比其他人更多的权利，例如，可以查看到对方一些其他用户不可获得的个人信息等。节点之间的好友关系也是各不相同的，有些人相互之间比较熟悉和了解，那么他们的关系自然也更近些，所以应该给关系引入不同的权重值来区分这类情况，但是为简单计算，我们仅仅采用了二元关系，即两个人之间要么是朋友，要么不是朋友。所有朋友关系都是同等对待的，不用不同的权重来衡量。
2.2.3 群
群，指的是仅由一部分节点为了某些共同的目的组成的小团体，是关系的一种部分聚合体。一个群里面的成员聚集在一起，可能是因为来自同一个城市，或者毕业于同一所大学，高中等等，也有可能是因为彼此之间有着某些共同的兴趣，例如音乐，体育，书籍等等。群的作用在于能让你找到更多有共同兴趣爱好的朋友，有利于彼此之间对于共同感兴趣的主题的交流。
2.2.4 社区
社区，也是某一部分节点的集合，社区和群的不同之处在于群是成员之间为了某种目的而组建起来的，是“后天”形成的，而社区是社交网络的自然存在，反应了网络成员的分布情况、来源信息以及其他一些网络的固有属性。例如在网络中，所有来自于北京工业大学的成员，构成了一个北京工业大学社区，这个社区不是社区成员自己建立的，而是在显示的人际网络中就固有存在的，用户是否属于该社区是由网络中用户所在的学校情况决定的。由于该社区内的成员都来自于北工大，成员之间的联系、交往更密切，所以朋友关系也会更密集，反映到网络图上就是该子网络内部边的密度比较大，与网络外的其余节点之间形成一个比较明显的划分。
2.2.5 自我中心网络
自我中心网络(Egocentric Network )，指环绕在自我节点周围的社会网络，既包括节点本身与他人的直接连接，也包括这些与节点有连接的其他节点之间的连接。比如，A 的自我中心友谊网络就包括A 与她的朋友之间的连接，以及A 的朋友们相互之间的连接。
2.3 在线社交网络理论基础
社会网络的理论基础源于著名的六度分隔理论和150法则。正是基于这两个
主要理论，社交网络得到了飞速的发展。
2.3.1 六度分隔理论
六度分隔理论((Six Degrees of Separation)，是由美国著名社会心理学家米尔格伦(Stanley Milgram) 于20世纪60年代提出。指的是“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人”。
“六度分隔理论”说明了社会中普遍存在的”弱纽带”，但是却发挥着非常强大的作用。有很多人在找工作时就会体会到这种弱纽带的效果。通过弱纽带人与人之间的距离变得非常“相近”。Jon Kleinberg 把这个问题变成了一个可以评估的数学模型，我们经常在与新朋友碰面的时候说“世界真小”，因为往往可能大家有共同认识的人。Jon 的研究实证了这个观点。
“六度分隔理论”的发展，使得构建于信息技术与互联网络之上的应用软件越来越人性化、社会化。软件的社会化，即在功能上能够反映和促进真实的社会关系的发展和交往活动的形成，使得人的活动与软件的功能融为一体。“六度分隔理论”的发现和社会性软件的发展向人们表明:社会性软件所构建的“弱链接”，正在人们的生活中扮演越来越重要的作用。
2.3.2 150法则
150法则(Rule of 150) ，是指公认的我们可以与之保持社交关系的人数的最大值是150。无论你曾经认识多少人，或者通过一种社会性网络服务与多少人建立了弱链接，但是那些强链接仍然符合150法则。这也符合“二八”法则，即80%的社会活动可能被150个强链接所占有。
150法则在现实生活中的应用很广泛。比如中国移动的“动感地带”sim 卡只能保存150个手机号，微软推出的聊天工具“MSN ”也只能是一个MSN 对应150个联系人。
2.4 在线社交网络主要研究方向
目前在线社交网络的主要研究方向包括基础结构研究，社交网络挖掘技术，基于社交网络的搜索技术以及社区识别技术等等，下面对这些研究方向做简单的介绍。
2.4.1 基础结构研究
社交网络不同于普通的基础网络，是建立在真实人际关系基础上的，因此对网络的结构特点进行研究对于进一步推动网络的发展具有非常重要的意义，结构研究既包括简单的基础构造研究，例如网络规模，节点可达性，节点之间距离的衡量等等，也包括异常复杂的特殊结构研究，主要包括度数中心性(DegreeCentrality)，亲近中心性(Closeness Centrality) 和中介中心性(BetweennessCentrality)等等。另外，还有不少学者关注于网络中节点所处位置的重要性，以及节点的聚集性，互惠作用等相关方面的研究。
对社交网络如上方面进行的基础研究，有利于我们揭示网络中节点与节点之间是如何相互作用的，以便进一步了解社交网络将来的发展特点和方向。
2.4.2 网络挖掘技术
在社交网络的理论研究中，另外一个重要的课题是挖掘技术的研究，挖掘技术的研究在语义网的研究中扮演了越来越重要的角色。例如知识管理、信息抽取、普氏计算等等。
这个领域的研究大部分是利用搜索引擎来挖掘人际网络关系，最新的代表性技术是一种叫作POLYPHONET 的社交网络抽取分析算法，该算法引入了一序列关于人际关系的识别，社区的挖掘，以及个人关键词挖掘等先进技术。采用Google 搜索引擎来进行信息相关度的衡量并获取相关文档。
目前，该领域的研究者主要关注如下两方面的问题，一是如何简化现有信息相关度的算法以使得整个衡量系统更易于整合，二是如何改进节点间的关系衡量算法，来加强对一些特定关系的衡量，例如个人和关键词相关度的计算，不同人际关系的分类等等。
2.4.3 用户影响力
另一个比较重要的课题就是用户影响力的量化，社交网络作为一个传播信息、思想、影响的媒体正起到一个越来越重要的角色。而社交影响的分析也已经吸引了大量研究者的注意。对社交影响的一个广泛的定义是：社交影响是一种现象，指一个用户的一个行为，可以影响其他用户做出类似的行为。对社交影响的度量便是社交影响力，它衡量了一个用户触发这种现象发生的能力。但对于具体的社交影响力的度量问题，学术界还没有一个统一的定义。研究者们提出了大量的社交影响力的定义，而他们对影响力的量化方式也随着定义的不同而不同。
总体上对社交网络用户的影响力的量化方式可以分为两种：一种是基于一些静态统计量的对用户影响力进行量化的直接方式。早期的大量影响力量化方法都属于这一类。第二种方法将对用户的影响力量化分解成两个阶段，在第一阶段中，使用模型对用户间的影响力进行量化，在第二阶段，基于第一阶段得到的用户间影响力使用模型或算法对用户的影响力进行量化。当前主流的用户影响力量化方法都是基于这个框架的。本章将具体地介绍这些影响力的定义与量化方式。
2.4.4 基于社交网络的搜索技术
基于社交网络的搜索技术也是目前的一个研究热点，传统的搜索技术并没有区分不同的个体，搜索结果对于所有人都是一致的，事实上，不同人关注的方面是不同的，单一的搜索结果并不能满足某些人的特定要求。
而基于社交网络的搜索技术尝试利用庞大的人际网络以提供更精确的搜索结果，并实现个人的定制搜索。该技术的基本思想在于将不同的人根据不同的兴趣划分成不同的社区，对于某个特定的社区，认为他们所关注的东西是类似的因此可以根绝社区对搜索结果进行定制。例如，一个汽车爱好者的社区对汽车相关的内容肯定更感兴趣，关注程度也会更高，因此这些内容的优先级会更高。另外，同一个社区的成员之间会相互影响，所以对于某个搜索结果，
该搜索记录了社区内成员的具体选择，当有同个社区的成员进行类似的搜索时，该技术就能给出更加精确的结果。
2.4.5 大规模网络的社区识别
普通网络的社区识别己经有了相对比较成熟的技术，例如由Clauset, Newman,和Moore 提出的，称之为CNM 的代表性算法。但是CNM 算法的不足之处在于其不适用于大规模网络，当网络节点多余500000个时，CNM 算法的计算速度就非常慢了。随着社交网络的发展，网络节点数己达到千万甚至上亿级别，CNM 算法的局限性就越发明显，所以最近几年，有不少学者关注于大规模网络的社区挖掘技术，具有代表性算法如日本学者Ken Wakita 和Toshiyuki Tsurumi所提出的K 丁识别技术。
3. 对于可视化的分析
3.1 图的表示
3.1.1 NetDraw软件图格式
利用图来展示社交网络，揭示社交网络包含的有价值信息，在图中进行相关分析，然后将可视化的结果呈现给用户，这种所见即所得方式很有趣且更容易被人理解和接受。要实现社交网络的可视分析则需要借助软件，这类软件设计过程中主要考虑以下几个问题：图的存储格式、制图算法、社交网络分析方法。
图的存储格式考虑以什么样的方式存储图，一方面软件以这种规定格式读取并展示图，另一方面这种格式应该方便生成和维护。制图算法主要解决软件以何种方式展示网络的问题，包括：网络中的顶点和边的分布排列规律；和用户交互时如何更新视图；在一些特殊情况下，例如图规模很大时，如何帮助用户发现图中的有价值信息。
NetDraw 是著名社交网络分析工具UCINET 的子功能模块，主要用于社交网络可视化。NetDraw 软件读取图的格式主要有两种：VNA 数据格式和DL 数据格式。VNA 数据格式不仅能存储图数据，而且可以存储顶点的属性数据以及顶点和边的展示方法信息，例如可以规定顶点的大小、形状、颜色等，边的箭头方向、粗细、说明等。DL 协议是一种灵活的图数据描述语言，它本身又包含多种不同格式，较典型的有顶点列表格式、边列表格式和全矩阵格式。
VNA 数据格式，完整的VNA 格式文档由三部分组成:顶点数据部分、顶点属性部分和连接数据部分。顶点数据部分包含了图中顶点角色的属性和属性值，例如角色ID ，性别等。顶点属性部分与顶点数据部分类似，主要区别在于这部分数据描述了顶点在显示时的特征，例如顶点的坐标、大小、形状、颜色、标签等。连接数据部分对顶点对之间存在的边以及边属性进行描述。下面是完整的VNA 数据格式示
例:
*Node data
ID, gender, role, betweenness
HOLLY female participant 78.33333588
BRAZEY female participant 0
CAROL female participant 1.333333373
PAM female participant 32.5
*Node properties
ID x y color shape size shortlabel
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
这里就是用图的邻接矩阵来描述整幅图。
3.1.2 GraphML
GraphML 是一种很容易使用的描述网络图的文档格式。GraphML 基于XML 技术，XML 即可扩展标记语言(EXtensible Markup Language)，区别于HTML ，XML 被设计为结构化、传输和存储数据。一份XML 文件必须包含根元素，根元素是所有其他元素的父元素。XML 文件中的元素形成了一棵文档树，具有良好的结构和可读性。所有元素均可拥有子元素。父、子以及同胞等术语用于描述元素之间的关系。父元素拥有子元素。相同层级上的子元素成为同胞(兄弟或姐妹) 。
由于GraphML 具备良好的通用性、可读性、可扩展性并且容易实现其解析程序，在诸多项目中都采用GraphML 作为网络图的存储方式。本文在系统实现部分就采用了GraphML 技术。下面是GraphML 文档的简单示例:
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi: schemaLocation="http://graphml.graphdrawing.org/xmlns
http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
mode id="n0"/>
mode id="nl"/>
mode id="n2"/>
mode id="n3 "/>
mode id="n4"/>
mode id="n5"/>
mode id="n6"/>
mode id="n7"/>
mode id="n8"/>
mode id="n9"/>
mode id="n10"/>
文档中表示这是一幅代号为G 的无向图，mode id="n8"/>标记了身份为n8的顶点，则定义了顶点n0和n2
之间的边。
以上文档图的可视化结果：
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 分别表示图中顶点和边的数量。该算法通常只适用于可视化中小规模的网络图。算法可视化结果示例如下:
3.2.3 Tree Layout
Tree Layout的基本思想是以树形结构展示图，选择一个顶点为根顶点，其他与根顶点直接连接的顶点则成为儿子顶点，而与儿子顶点直接相连的所有顶点又称为儿子顶点的儿子顶点，如此下去。Tree Layout通常有水平、垂直和放射状三种排列顶点的方法，其中放射状树是社交网络可视化中常使用的方法。Tree Layout示例如下：
参考文献：
[1]Hanneman, R. A. and M. Riddle.Introduction to Social Network Methods[M].Riverside, CA: University of California, Riverside,2005.
[2]才华. 社区挖掘算法研究「D].长春:吉林大学计算机科学与技术学院，2008.
[3] Wang Z, Zhang J. In serach of the biological significance of modular structures inprotein networks[J]. PLOS Computational Biology, 2007,3(6):e107.
[4] Ino H, Kudo M, Nakamura A. Partitioning of Web graphs by communitytopology[C].In: Ellis A, Hagino T, eds. Proc. of the 14th Int'1 Conf. on World WideWeb. New York: ACM Press, 2005: 661-669.
[5]Hastie, T.R.Tibshirani, and J.H.Friedman. The Elements of StatisticalLearning[M].Berlin, Germany:Springer, 2001.
[6]Sales-Pardo, M., R. Guimera, A. A. Moreira, and L. A. N. Amaral.Extracting thehierarchical organization of complex systems[C].Proc. Natl. Acad. Sci. USA,2007:104,15224-15229.
[7]Clauset, A., C. Moore, and M. E. J. Newman.Finding community structure in verylarge networks[J].Phys. Rev. E 70, 2004.
[8]Clauset, C. Moore and M. E. J. Newman.Hierarchical structure and the prediction ofmissing links in networks[J]. Nature, 2008:98-101.
[9]S.Fortunato, Community detection in graphs[J]. Physics Reports, 2010,486(3):75一174.
[10] de Nooy, Wouter, Andrej Mrvar, and Vladimir Batagelj.Exploratory SocialNetworkAnalysis with Pajek[M]. New York: Cambridge University Press, 2005.
[11〕Borgatti, S.P.M. G. Everett, L. C. Freeman. Ucinet for Windows: Software forsocial network analysis[J/OL]. Harvard, Analytic Technologies, 2002.http://www.analytictech.com
[12]D. L. Hansen, B. Shneiderman, and M. A. Smith. Analyzing Social MediaNetworks with NodeXL: Insights from a Connected World[M].Morgan Kaufmann,2010.
[ 13 ] http://www.touchgraph. com/navigator
[14]J.Heer and D.Boyd.Vizster: Visualizing Online SocialNetworks[C].In Proceedings of the 2005 IEEE Symposium on InformationVisualization, IEEE Computer Society, 2005:32-39.
[ 15 ]http://www-95 8.ibm. com/software/data/cognos/manyeyes/
[16] O'Madadhain, J., D. Fisher, P . Smyth, S. White and Y.-B. Boey. Analysis andVisualization of Network Data using JUNG[J]. Journal of Statistical Software, 2005,55(2):6-40.
[17]J.Heer, S.K.Card, and J.A.Landay.Prefuse:A toolkit for interactive informationvisualization[C].In ACM Human Factors in Computing Systems(CHI), 2005:421-430.
[18]J.Epson, ER Gansner, E. Koutsofios, SC North, and G. Woodhull. Graphviz andDynagraph-Static and Dynamic Graph Drawing Tools[J]. Graph Drawing Software,Springer-Verlag, 2004:127一148.
[19] SINGLA P , RICHARDSON M.Yes, there is a correlation:-from social networks to personal behavior on the web[C]//Proceedings of the 17th international confer- ence on World Wide Web, 2008:655-664.
[20] ANAGNOSTOPOULOS A, KUMAR R, MAHDIAN M. Influence and correlation in social networks[C]//Proceeding of the 14th ACM SIGKDD international confer-ence on Knowledge discovery and data mining, 2008:7-15.
[21]CRANDALL D, COSLEY D, HUTTENLOCHER D, et al. Feedback effects between similarity and social influence in online communities[C]//Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data min- ing, 2008:160-168.
[22]GOYAL A, BONCHI F, LAKSHMANAN L. Learning influence probabilities in so-cial networks[C]//Proceedings of the third ACM international conference on Web search and data mining, 2010:241-250.
[23]GOMEZ-RODRIGUEZ M, LESKOVEC J, KRAUSE A. Inferring netWOrkS Of dlffuSlOn and influence[J]. ACM Transactions on Knowledge Discovery from Data (TKD- D), 2012, 5(4):21.
[24]TANG J, SuN J, WANG C, et al. Social influence analysis in large-scale net- works[C]//Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009:807-816.
[25]WANG C, TANG J, SuN J, et al. Dynamic social influence analysis through time- dependent factor graphs[C]//Advances in Social Networks Analysis and Mining(ASONAM), 2011 International Conference on, 2011:239-246.
[26]KWAK H, LEE C, PARK H, et al. What is Twitter, a social network or a
newsmedia?[C]//Proceedings of the 19th international conference on World wide web, 2010:591-600.
[27]WENG J, LIM E, JIANG J, et al 厂Twitterrank: finding topic-sensitive influential twit-terers[C]//Proceedings of the third ACM international conference on Web searchand data mining, 2010:261-270.
[28]TANG S, YUAN J, MAO X, et al. Relationship classification in large scale online social networks and its impact on information propagation[C]//INFOCOM, 2011Proceedings IEEE, 2011:2291-2299.
[29] WELCH M,SCHONFELD U,HED, et Topical semantics of twitterinternational conference On Web search
[30] PaL A, COUNTS S. Identifying topical authorities in microblogs[C]//Proceedings of the fourth ACM international conference on Web search and data mining,2011:45-54.
[31]ZHaNG M, Surr C, Lm W. Identifying Influential Users Of Micro-Blogging Ser-vices: A Dynamic Action-Based Network Approach[J].PACIS Proceedings,2011.
在线社交网络分析及可视化系统研究与设计
摘要
近年来，随着Web2.0等互联网新概念的日益付诸实践，社交网络作为其中一种新兴的，实用的交友模式，依赖其真实性，稳定性等特点得到了用户的青睐，在网络活动中发挥着越来越重要的作用。我们可以看到，很多社交网站在最近几年取得了巨大的成就，例如Myspace 己经成为全美最受欢迎的网站之一，统计表明其流量相当于Internet 总流量的4.46%； Yahoo 的图片分享及社交网络结合体Flickr ，己经拥有超过400万用户和2亿上传图片；而作为全美第二大的社交网站Facebook ，在创立的短短三年之内，市值就已达到了惊人的150亿美元; 在国内方面，“校内网”作为大学生最主要的交流平台，也已经拥有超过2200万真实注册用户。
社交网络是指建立在真实人际关系基础上的网络平台，是作为现实中的社会团体在互联网上交流的辅助工具而存在。社交网络是现实活动的在线拓展，与传统的虚拟网络有很大的不同。传统虚拟网络脱离社会现实，结构相对无序、混乱，而社交网络作为现实人际网络的子集，同样具有人际网络的一些特征，正是基于如此我们认为对社交网络进行一定的研究是可行的，这对于促进社交网络的进一步发展具有重要的理论意义。
本文以社交网络为平台，以计算机图论知识为基础，对人际关系做了深入的研究和分析。在此基础上提出了对于在线社交网络的可视化中图的表示和制图算法。
关键字：在线社交网络 可视化系统 用户影响力 社区挖掘
1. 绪论
1.1 课题的背景和意义
在互联网发展初期，以电子邮件，QQ ，MSN 以及雅虎通为代表的即时通讯工具在网络社交中扮演了非常重要的角色。电子邮件作为社交网络的起点，解决了远程传输邮件的问题。为当时的人们提供除了打电话和写信之外，另外一种便捷、低成本的交流方式。
这类通讯工具作为第一代交友模式的平台，满足了人们无线通讯，网络交友等需求。第一代社交网络主要是建立在虚拟性、隐蔽性的交友模式基础上，具有很大的弊端。首先，第一代交友模式的使用者是以好奇心强、精神世界具有青春期特有矛盾、是非辨别能力尚未完善、社会经验较少的青少年为主力军，很多不法分子利用交友模式的虚拟性与隐蔽性来伪装个人真实身份、年龄等信息进行欺骗活动。另外，随着互联网的发展，大量信息蜂拥而至，如何迅速快捷获得有效信息，成为互联网使用者越来越尖锐的需求。虚拟网络交友模式，由于其使用者的交友圈的低信任度，充斥着大量的无用信息和欺骗信息，极大地妨碍了现代社会要求的快速、轻松、便捷地获取信息的需求。因此，第一代网络交友模式的发展渐渐出现疲乏。但是其开启了以互联网为平台的网络交友和即时通讯的先河，为第二代网络交友模式的创建提供了宝贵的经验与借鉴，同时也为第二代网络交友模式的兴起奠定了基础。 随着网络社交的迅猛发展，一个节点在网络上的“画像”更加趋于“形象”，这也代表着SNS ( Social Network Service)的悄然出现。网络化进程的快速发展，使得人们更愿意把很多日常生活也搬到网络上来。社交网络正是为方便人们的日常交友需要而诞生和发展起来的，是新兴的第二代网络交友模式，建立在使用者现实生活中的社交圈子的基础上，为其的交友需求提供了纯净、高信任度的网络平台。
第二代网络交友模式弥补了第一代网络交友模式中虚拟交友的弊端，并充分地利用了网络即时通讯的便捷，可以将现实中的交友圈子搬上网络，志于为使用者提供透明纯净、通讯快捷的交友平台，可以为使用者提供较为真实的信息，极大地满足了人们以学习、工作为目的商务交友需求。
从现在的网络发展形势来看，我们可以发现网络上的服务越来越贴近人们的生活，朝着便捷化人们生活的方向发展。21世纪兴起的社交网络，作为一个新的网络服务，也紧跟着网络发展的大潮流，为人们日常的在线交友需要提供了非常便捷有效的服务。
正是基于上述背景，我们选取了社交网络作为研究对象，对XXXXXX 进行了深入的研究和分析，本项目关注的问题其一是在线社交网络的特性，主要分析了其中社区挖掘和用户影响力研究的现状并作出总结 ，然后是对于这些信息的可视化，提示了以图为核心的可视化算法。
公认的互联网三大应用是电子邮件，即时消息和信息搜索。社交网络，从前面讨论中可以看到，由于满足了人们商务交友的新需求，近几年得到迅速发展，逐渐成为互联网的第四大应用，在Web2.0的浪潮中起着举足轻重的作用。因此，对社交网络进行研究，对于我们深入了解其发展方向具有非常重要的指导意义，也必将对社交网络的进一步发展起着积极的推动作用。
用户与社区作为社交网络的核心，是社交网络发展的根本推动力所在，对社区进行有效的挖掘，能更好的理解网络结构，协调好各个社区内的关系。因此，对用户的影响力进行有效的评估，具有非常重要的指导意义。而用户的影响力是指用户对周围的人所能产生的影响及带动作用，是用户在社交网络中的重要性的衡量。用户的影响力作为用户的重要指标，是社交网络中各种关系的基础，用户的影响力越大，所受到的关注程度也越高，对网络的反馈作用也就越大。对用户的影响力进行衡量，能为网络中的用户进行合理的排序，为社交网络
的拓展应用及进一步发展提供理论基础，同时通过社区识别技术可以优化基于用户影响力排序的结果。例如，当我们想寻找网络中满足一定条件的用户，比如有相同兴趣或者一样的出游计划的用户时，满足条件的用户可能会很多，那么如何在最短时间内从中选取最合适的结果，用户的影响力就是一个非常重要的指标；再比如，随着社交网络的发展，我们有理由相信，未来更多的商业化活动将被移植到网络上来。当我们想在社交网络上推广某种商品或者服务时，如何选取首批推荐使用产品的人群会直接影响到推广活动的效果及代价。这时候，影响力比较大的用户往往成为活动的首选人群。通过他们的介绍和宣传，能将商家的商品更快、更有效的传播给网络中的其余用户。
同样，对社区识别技术进行研究也具有非常重要的理论意义。社区反映了网络中的用户的分布情况及活动范围，对其深入研究可以帮助我们更好地了解网络结构，协调好各个社区间的关系，掌握网络中的信息组织，流动及发展状况，同时也有助于商家进行有针对性的商业活动，能对网络中的信息资源进行进一步合理的整合，为信息的查询，搜索提供更为方便快捷的途径。
总之，用户与社区作为社交网络的核心，是社交网络发展的根本推动力所在。用户影响力评估系统和社区识别算法对于优化社交网络中的信息整合，促进社交网络的发展具有非常重要的理论意义。
1.2 国内外研究现状
对于社区挖掘方面：社交网络[1]是真实的人际关系网络，可以用顶点和边来展示社交网络。基于图理论，运用多种方法对社交网络展开分析，可以帮助人们发现社交网络中的有价值信息，例如发现网络中的重要顶点、找出与某顶点最为相似的顶点等。在多种社交网络分析方法中，挖掘出网络中的社区结构[2]是研究的热点问题。社区结构不仅存在于社交网络中，也存在于生物化学网络[3]、万维网[4]等其他复杂网络中，因此社区挖掘问题研究具有重要现实意义。
在理论研究方面，Hastie[5]等人在2001年提出的基于相似度的层次聚类算法能够在无需任何先验知识的情况下，挖掘网络中存在的社区结构。该算法通过计算所有顶点对之间相似度，得出相似度矩阵，然后进行层次聚类过程，可以用树状图表示该过程，树状图揭示了网络的层次结构特征，树状图的分割位置不同得出不同的社区划分结果。后人针对该算法的改进主要集中在两个方面，一方面，定义新的相似度计算方法，提高效率；另一方面，更准确的揭示网络中存在的层次结构。例如，Sales-Pardo[6]等人在2007年提出一种基于模块度的顶点附着力概念，用来衡量顶点间相似度。Clauset[7][8]等人在2004, 2008年发表的论文引入层次随机图的概念，试图更精准的描述网络层次结构特征。Santo Fortunato[9]对社区挖掘问题以及现有的算法进行了详尽的分类总结。
在实际应用方面，存在多种社交网络分析工具，可以大致将这些工具分为三大类。第一类，主要用于科学研究，例如Pajek[10]、 UCINET[11]、 NodeXL[12]等都是较著名的用于网络分析的软件，这类软件主要面向科研工作者，可以运用多种复杂的分析手段对较大规模的网络进行分析。第二类是面向普通用户的网络分析工具，较有代表性的有在线应用TouchGraph[13]、桌面应用Vizster[14]以及由IBM 研究院和IBM Cognos 软件组织推出的ManyEyes[15]在线应用，这类工具区别于科研工具，具有操作简单、展示方式有趣等特征。最后一类是面向开发者的软件开发包，开发者可以利用开发包开发个性化的社交网络分析工具，较著名的有JUNG[15]、Prefuse[17]、GraphViz[18]等。
在用户影响力方面：对社交网络中用户间的影响力量化的研究由来已久，其中最主要的方法是将影响力以概率的形式表现，对于不同类型的社交网络，用户间的影响力有不同的定义，相应的，对应的影响力量化模型也有可能随着影响力定义的不同而不同。
Singla 等[19]提出了用户间也考虑了进去，提出了量化动态社交影响力的时间依影响力的存在并作出了定性的分析。Anagnos-topoulos 等[20]和Crandall 等[21]都将用户间的影响力定义为用户间的相似性或者相关性。但他们只是提供了关于社交影响的定性的发现，而没有提出具体的影响力的量化方法。
Goyal 等[22]也将用户间的影响力定义为用户间的相似性，但他们的工作主要针对的是在线电子商务网站，比如亚马逊等，他们将这类社交网站中用户间的相似性定义为有着相似购买行为的现象。在这类网站中，没有显式的社交信息存在，只有用户的活动历史日志是可以得到的。因此，他们提出了从用户的行为日志中学习用户间影响力的模型。同时，由于在线电子商务网站本身不存在显式的社交关系，M.G.Rodrigue 等[23]提出了从用户日志中学习社交网络结构的算法。
Tang 等[24]的研究主要关注合作网和引用网等社交网络，在这些社交网络中，用户通过合作和引用的方式被其他用户影响。他们提出了主题亲密度传播模型TAP (Topical Affinity Propagation) 来对用户间的主题明确的影响概率进行量化。通过给定的社交网络和每个用户的主题分布，找到主题明确的社交网络子网和子网成员间的主题明确的影响力权值。Wang 等[24]进一步拓展了TAP 模型，将时间因素赖因子图模型( time-dependent factor graph) 。
对于在线社交网络中用户间影响力量化的研究，可以分为两大类，分别基于在线社交网络中用户的两种不同的信息:关系信息与转发信息。最简单的基于关系信息的方法是使用一个均匀分布来评估用户和他的所有朋友间的影响力，此时仅仅涉及用户间的朋友关系信息。用户的所有朋友对用户的影响力都是相同的，都等于用户的朋友数的倒数。因此，该模型被称为均匀模型，模型背后的隐含的假设是用户的朋友间存在着十分高的同质性，因此，用户被任何两个不同的朋友影响的概率是相同的。Kwak 等[26]使用了均匀模型来量化用户间的影响力并对量化得到的结果应用pagerank 算法来找到最有影响力的用户。
Weng 等[27]同样基于关系信息提出了主题敏感的用户间影响力量化模型，仍然使用pagerank 算法来找到最有影响力的用户。他们的量化模型基于他们从数据中观察到的现象:用户间存在着较高的互粉率，他们将这归因于同质性。然而其他的研究表明在线社交网络中的互粉率并不高，甚至偏低，这与他们的观察结果相矛盾。
Tang 等[28]提出了一个不同的方法，它不但利用了在线社交网络的关系信息，还使用了用户的标签信息。对于每一条关系，都会有一个对应的标签，指代关系的类型，例如亲戚、师生等。他们提出了一个算法，当标签不存在时，可以使用现有的关系信息和标签信息来预测它。在每条关系都有了标签后，给予每个标签一个固定的影响概率。最终，他们将量化的结果应用到了影响力最大化问题中。
在基于转发信息的方法中，通常将用户间的影响力定义为用户间的转发概率，这也是目前最普遍的定义方式，表示用户的一条转发信息来自于其中的某一个朋友的概率。一般使用用户的转发频率统计量来量化用户间的转发概率，转发概率是与用户来源于他的朋友的转发信息的频率成正比的。由于转发概率的这种量化方式是通过极大似然估计法推导而得出的，因此该模型被称为极大似然模型。
Welch 等[29]同时研究了朋友关系与转发关系的语义。他们通过对关系信息与转发信息同时应用pagerank 算法获得地用户排名结果进行分析并得出结论:转发关系更好地保留了用户间的传递性，因此转发关系是比朋友关系更强的影响力指示器。
Pal 等[30]使用了主题敏感的转发信息和极大似然模型来量化用户间的影响力并从Twitte 中找到了主题相关的权威用户。同样的，Meng Zhang 等[31]也拓展了极大似然模型，提出了一个动态模型来量化用户的影响力。
1.3 本文主要工作
第一分析了在线社交网络的构成和性质。对于其中的重点问题例如：数据挖掘、用户影响力等做出了概括
其次，提出了对于在线社交网络可视化的方式，即用图来表示在线社交网络并给出了初步的方式。
2. 在线社交网络的初步讨论
2.1 社交网络的定义
社交网络即社交网络服务(SNS)，英文全称为Social Network Service，是指人和人之间通过朋友、血缘、交易、网络链接、疾病传播、理想、兴趣爱好等等关系建立起来的社会网络结构。在网络中，人与人之间通过点评、群组等功能，来为网络的用户进行“画像”，当这种“画像”越贴近显示中人的社会性，网络的社会化程度就越高。
社交网络起源于网络社交，随着网络交友的迅速发展，社交网络也在其中慢慢形成、演化、发展，为人们的生活提供更便捷的信息交流。社交网络一直朝着“节约社交时间和物质成本，获取高速、有效的信息”这一方向发展。社交网络通过网络这一平台，把不同的人联系起来，形成具有某一特点的团体。
研究表明，社交网络覆盖了社会的各个层次，上次国家外交，下至家庭关系，并且对于问题的解决，组织的运营，以及个体的成功都起到了非常关键的决定性作用。
2.2 在线社交网络的组成
社交网络包括节点，关系，用户群，社区等基本概念。
2.2.1 节点
节点，即网络中的个体，也称参与者(Actor )，指的是社交网络的参与者，即在一个网络中与他人(行动者) 相联结的具体的个人、组织、事件或其他集体性质的社会实体。
2.2.2 关系
关系，指的是指节点和节点之间的连接。在个体层次上，人和人之间如果相互认识，或者有共同的兴趣和属性，称之为他们之间具有某种关系。在社交网络上，关系指的是基于朋友关系而建立起来的网络连接，体现的是两个网络用户之间的相互信赖。一般而言，他们之间拥有比其他人更多的权利，例如，可以查看到对方一些其他用户不可获得的个人信息等。节点之间的好友关系也是各不相同的，有些人相互之间比较熟悉和了解，那么他们的关系自然也更近些，所以应该给关系引入不同的权重值来区分这类情况，但是为简单计算，我们仅仅采用了二元关系，即两个人之间要么是朋友，要么不是朋友。所有朋友关系都是同等对待的，不用不同的权重来衡量。
2.2.3 群
群，指的是仅由一部分节点为了某些共同的目的组成的小团体，是关系的一种部分聚合体。一个群里面的成员聚集在一起，可能是因为来自同一个城市，或者毕业于同一所大学，高中等等，也有可能是因为彼此之间有着某些共同的兴趣，例如音乐，体育，书籍等等。群的作用在于能让你找到更多有共同兴趣爱好的朋友，有利于彼此之间对于共同感兴趣的主题的交流。
2.2.4 社区
社区，也是某一部分节点的集合，社区和群的不同之处在于群是成员之间为了某种目的而组建起来的，是“后天”形成的，而社区是社交网络的自然存在，反应了网络成员的分布情况、来源信息以及其他一些网络的固有属性。例如在网络中，所有来自于北京工业大学的成员，构成了一个北京工业大学社区，这个社区不是社区成员自己建立的，而是在显示的人际网络中就固有存在的，用户是否属于该社区是由网络中用户所在的学校情况决定的。由于该社区内的成员都来自于北工大，成员之间的联系、交往更密切，所以朋友关系也会更密集，反映到网络图上就是该子网络内部边的密度比较大，与网络外的其余节点之间形成一个比较明显的划分。
2.2.5 自我中心网络
自我中心网络(Egocentric Network )，指环绕在自我节点周围的社会网络，既包括节点本身与他人的直接连接，也包括这些与节点有连接的其他节点之间的连接。比如，A 的自我中心友谊网络就包括A 与她的朋友之间的连接，以及A 的朋友们相互之间的连接。
2.3 在线社交网络理论基础
社会网络的理论基础源于著名的六度分隔理论和150法则。正是基于这两个
主要理论，社交网络得到了飞速的发展。
2.3.1 六度分隔理论
六度分隔理论((Six Degrees of Separation)，是由美国著名社会心理学家米尔格伦(Stanley Milgram) 于20世纪60年代提出。指的是“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人”。
“六度分隔理论”说明了社会中普遍存在的”弱纽带”，但是却发挥着非常强大的作用。有很多人在找工作时就会体会到这种弱纽带的效果。通过弱纽带人与人之间的距离变得非常“相近”。Jon Kleinberg 把这个问题变成了一个可以评估的数学模型，我们经常在与新朋友碰面的时候说“世界真小”，因为往往可能大家有共同认识的人。Jon 的研究实证了这个观点。
“六度分隔理论”的发展，使得构建于信息技术与互联网络之上的应用软件越来越人性化、社会化。软件的社会化，即在功能上能够反映和促进真实的社会关系的发展和交往活动的形成，使得人的活动与软件的功能融为一体。“六度分隔理论”的发现和社会性软件的发展向人们表明:社会性软件所构建的“弱链接”，正在人们的生活中扮演越来越重要的作用。
2.3.2 150法则
150法则(Rule of 150) ，是指公认的我们可以与之保持社交关系的人数的最大值是150。无论你曾经认识多少人，或者通过一种社会性网络服务与多少人建立了弱链接，但是那些强链接仍然符合150法则。这也符合“二八”法则，即80%的社会活动可能被150个强链接所占有。
150法则在现实生活中的应用很广泛。比如中国移动的“动感地带”sim 卡只能保存150个手机号，微软推出的聊天工具“MSN ”也只能是一个MSN 对应150个联系人。
2.4 在线社交网络主要研究方向
目前在线社交网络的主要研究方向包括基础结构研究，社交网络挖掘技术，基于社交网络的搜索技术以及社区识别技术等等，下面对这些研究方向做简单的介绍。
2.4.1 基础结构研究
社交网络不同于普通的基础网络，是建立在真实人际关系基础上的，因此对网络的结构特点进行研究对于进一步推动网络的发展具有非常重要的意义，结构研究既包括简单的基础构造研究，例如网络规模，节点可达性，节点之间距离的衡量等等，也包括异常复杂的特殊结构研究，主要包括度数中心性(DegreeCentrality)，亲近中心性(Closeness Centrality) 和中介中心性(BetweennessCentrality)等等。另外，还有不少学者关注于网络中节点所处位置的重要性，以及节点的聚集性，互惠作用等相关方面的研究。
对社交网络如上方面进行的基础研究，有利于我们揭示网络中节点与节点之间是如何相互作用的，以便进一步了解社交网络将来的发展特点和方向。
2.4.2 网络挖掘技术
在社交网络的理论研究中，另外一个重要的课题是挖掘技术的研究，挖掘技术的研究在语义网的研究中扮演了越来越重要的角色。例如知识管理、信息抽取、普氏计算等等。
这个领域的研究大部分是利用搜索引擎来挖掘人际网络关系，最新的代表性技术是一种叫作POLYPHONET 的社交网络抽取分析算法，该算法引入了一序列关于人际关系的识别，社区的挖掘，以及个人关键词挖掘等先进技术。采用Google 搜索引擎来进行信息相关度的衡量并获取相关文档。
目前，该领域的研究者主要关注如下两方面的问题，一是如何简化现有信息相关度的算法以使得整个衡量系统更易于整合，二是如何改进节点间的关系衡量算法，来加强对一些特定关系的衡量，例如个人和关键词相关度的计算，不同人际关系的分类等等。
2.4.3 用户影响力
另一个比较重要的课题就是用户影响力的量化，社交网络作为一个传播信息、思想、影响的媒体正起到一个越来越重要的角色。而社交影响的分析也已经吸引了大量研究者的注意。对社交影响的一个广泛的定义是：社交影响是一种现象，指一个用户的一个行为，可以影响其他用户做出类似的行为。对社交影响的度量便是社交影响力，它衡量了一个用户触发这种现象发生的能力。但对于具体的社交影响力的度量问题，学术界还没有一个统一的定义。研究者们提出了大量的社交影响力的定义，而他们对影响力的量化方式也随着定义的不同而不同。
总体上对社交网络用户的影响力的量化方式可以分为两种：一种是基于一些静态统计量的对用户影响力进行量化的直接方式。早期的大量影响力量化方法都属于这一类。第二种方法将对用户的影响力量化分解成两个阶段，在第一阶段中，使用模型对用户间的影响力进行量化，在第二阶段，基于第一阶段得到的用户间影响力使用模型或算法对用户的影响力进行量化。当前主流的用户影响力量化方法都是基于这个框架的。本章将具体地介绍这些影响力的定义与量化方式。
2.4.4 基于社交网络的搜索技术
基于社交网络的搜索技术也是目前的一个研究热点，传统的搜索技术并没有区分不同的个体，搜索结果对于所有人都是一致的，事实上，不同人关注的方面是不同的，单一的搜索结果并不能满足某些人的特定要求。
而基于社交网络的搜索技术尝试利用庞大的人际网络以提供更精确的搜索结果，并实现个人的定制搜索。该技术的基本思想在于将不同的人根据不同的兴趣划分成不同的社区，对于某个特定的社区，认为他们所关注的东西是类似的因此可以根绝社区对搜索结果进行定制。例如，一个汽车爱好者的社区对汽车相关的内容肯定更感兴趣，关注程度也会更高，因此这些内容的优先级会更高。另外，同一个社区的成员之间会相互影响，所以对于某个搜索结果，
该搜索记录了社区内成员的具体选择，当有同个社区的成员进行类似的搜索时，该技术就能给出更加精确的结果。
2.4.5 大规模网络的社区识别
普通网络的社区识别己经有了相对比较成熟的技术，例如由Clauset, Newman,和Moore 提出的，称之为CNM 的代表性算法。但是CNM 算法的不足之处在于其不适用于大规模网络，当网络节点多余500000个时，CNM 算法的计算速度就非常慢了。随着社交网络的发展，网络节点数己达到千万甚至上亿级别，CNM 算法的局限性就越发明显，所以最近几年，有不少学者关注于大规模网络的社区挖掘技术，具有代表性算法如日本学者Ken Wakita 和Toshiyuki Tsurumi所提出的K 丁识别技术。
3. 对于可视化的分析
3.1 图的表示
3.1.1 NetDraw软件图格式
利用图来展示社交网络，揭示社交网络包含的有价值信息，在图中进行相关分析，然后将可视化的结果呈现给用户，这种所见即所得方式很有趣且更容易被人理解和接受。要实现社交网络的可视分析则需要借助软件，这类软件设计过程中主要考虑以下几个问题：图的存储格式、制图算法、社交网络分析方法。
图的存储格式考虑以什么样的方式存储图，一方面软件以这种规定格式读取并展示图，另一方面这种格式应该方便生成和维护。制图算法主要解决软件以何种方式展示网络的问题，包括：网络中的顶点和边的分布排列规律；和用户交互时如何更新视图；在一些特殊情况下，例如图规模很大时，如何帮助用户发现图中的有价值信息。
NetDraw 是著名社交网络分析工具UCINET 的子功能模块，主要用于社交网络可视化。NetDraw 软件读取图的格式主要有两种：VNA 数据格式和DL 数据格式。VNA 数据格式不仅能存储图数据，而且可以存储顶点的属性数据以及顶点和边的展示方法信息，例如可以规定顶点的大小、形状、颜色等，边的箭头方向、粗细、说明等。DL 协议是一种灵活的图数据描述语言，它本身又包含多种不同格式，较典型的有顶点列表格式、边列表格式和全矩阵格式。
VNA 数据格式，完整的VNA 格式文档由三部分组成:顶点数据部分、顶点属性部分和连接数据部分。顶点数据部分包含了图中顶点角色的属性和属性值，例如角色ID ，性别等。顶点属性部分与顶点数据部分类似，主要区别在于这部分数据描述了顶点在显示时的特征，例如顶点的坐标、大小、形状、颜色、标签等。连接数据部分对顶点对之间存在的边以及边属性进行描述。下面是完整的VNA 数据格式示
例:
*Node data
ID, gender, role, betweenness
HOLLY female participant 78.33333588
BRAZEY female participant 0
CAROL female participant 1.333333373
PAM female participant 32.5
*Node properties
ID x y color shape size shortlabel
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
这里就是用图的邻接矩阵来描述整幅图。
3.1.2 GraphML
GraphML 是一种很容易使用的描述网络图的文档格式。GraphML 基于XML 技术，XML 即可扩展标记语言(EXtensible Markup Language)，区别于HTML ，XML 被设计为结构化、传输和存储数据。一份XML 文件必须包含根元素，根元素是所有其他元素的父元素。XML 文件中的元素形成了一棵文档树，具有良好的结构和可读性。所有元素均可拥有子元素。父、子以及同胞等术语用于描述元素之间的关系。父元素拥有子元素。相同层级上的子元素成为同胞(兄弟或姐妹) 。
由于GraphML 具备良好的通用性、可读性、可扩展性并且容易实现其解析程序，在诸多项目中都采用GraphML 作为网络图的存储方式。本文在系统实现部分就采用了GraphML 技术。下面是GraphML 文档的简单示例:
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi: schemaLocation="http://graphml.graphdrawing.org/xmlns
http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
mode id="n0"/>
mode id="nl"/>
mode id="n2"/>
mode id="n3 "/>
mode id="n4"/>
mode id="n5"/>
mode id="n6"/>
mode id="n7"/>
mode id="n8"/>
mode id="n9"/>
mode id="n10"/>
文档中表示这是一幅代号为G 的无向图，mode id="n8"/>标记了身份为n8的顶点，则定义了顶点n0和n2
之间的边。
以上文档图的可视化结果：
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 分别表示图中顶点和边的数量。该算法通常只适用于可视化中小规模的网络图。算法可视化结果示例如下:
3.2.3 Tree Layout
Tree Layout的基本思想是以树形结构展示图，选择一个顶点为根顶点，其他与根顶点直接连接的顶点则成为儿子顶点，而与儿子顶点直接相连的所有顶点又称为儿子顶点的儿子顶点，如此下去。Tree Layout通常有水平、垂直和放射状三种排列顶点的方法，其中放射状树是社交网络可视化中常使用的方法。Tree Layout示例如下：
参考文献：
[1]Hanneman, R. A. and M. Riddle.Introduction to Social Network Methods[M].Riverside, CA: University of California, Riverside,2005.
[2]才华. 社区挖掘算法研究「D].长春:吉林大学计算机科学与技术学院，2008.
[3] Wang Z, Zhang J. In serach of the biological significance of modular structures inprotein networks[J]. PLOS Computational Biology, 2007,3(6):e107.
[4] Ino H, Kudo M, Nakamura A. Partitioning of Web graphs by communitytopology[C].In: Ellis A, Hagino T, eds. Proc. of the 14th Int'1 Conf. on World WideWeb. New York: ACM Press, 2005: 661-669.
[5]Hastie, T.R.Tibshirani, and J.H.Friedman. The Elements of StatisticalLearning[M].Berlin, Germany:Springer, 2001.
[6]Sales-Pardo, M., R. Guimera, A. A. Moreira, and L. A. N. Amaral.Extracting thehierarchical organization of complex systems[C].Proc. Natl. Acad. Sci. USA,2007:104,15224-15229.
[7]Clauset, A., C. Moore, and M. E. J. Newman.Finding community structure in verylarge networks[J].Phys. Rev. E 70, 2004.
[8]Clauset, C. Moore and M. E. J. Newman.Hierarchical structure and the prediction ofmissing links in networks[J]. Nature, 2008:98-101.
[9]S.Fortunato, Community detection in graphs[J]. Physics Reports, 2010,486(3):75一174.
[10] de Nooy, Wouter, Andrej Mrvar, and Vladimir Batagelj.Exploratory SocialNetworkAnalysis with Pajek[M]. New York: Cambridge University Press, 2005.
[11〕Borgatti, S.P.M. G. Everett, L. C. Freeman. Ucinet for Windows: Software forsocial network analysis[J/OL]. Harvard, Analytic Technologies, 2002.http://www.analytictech.com
[12]D. L. Hansen, B. Shneiderman, and M. A. Smith. Analyzing Social MediaNetworks with NodeXL: Insights from a Connected World[M].Morgan Kaufmann,2010.
[ 13 ] http://www.touchgraph. com/navigator
[14]J.Heer and D.Boyd.Vizster: Visualizing Online SocialNetworks[C].In Proceedings of the 2005 IEEE Symposium on InformationVisualization, IEEE Computer Society, 2005:32-39.
[ 15 ]http://www-95 8.ibm. com/software/data/cognos/manyeyes/
[16] O'Madadhain, J., D. Fisher, P . Smyth, S. White and Y.-B. Boey. Analysis andVisualization of Network Data using JUNG[J]. Journal of Statistical Software, 2005,55(2):6-40.
[17]J.Heer, S.K.Card, and J.A.Landay.Prefuse:A toolkit for interactive informationvisualization[C].In ACM Human Factors in Computing Systems(CHI), 2005:421-430.
[18]J.Epson, ER Gansner, E. Koutsofios, SC North, and G. Woodhull. Graphviz andDynagraph-Static and Dynamic Graph Drawing Tools[J]. Graph Drawing Software,Springer-Verlag, 2004:127一148.
[19] SINGLA P , RICHARDSON M.Yes, there is a correlation:-from social networks to personal behavior on the web[C]//Proceedings of the 17th international confer- ence on World Wide Web, 2008:655-664.
[20] ANAGNOSTOPOULOS A, KUMAR R, MAHDIAN M. Influence and correlation in social networks[C]//Proceeding of the 14th ACM SIGKDD international confer-ence on Knowledge discovery and data mining, 2008:7-15.
[21]CRANDALL D, COSLEY D, HUTTENLOCHER D, et al. Feedback effects between similarity and social influence in online communities[C]//Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data min- ing, 2008:160-168.
[22]GOYAL A, BONCHI F, LAKSHMANAN L. Learning influence probabilities in so-cial networks[C]//Proceedings of the third ACM international conference on Web search and data mining, 2010:241-250.
[23]GOMEZ-RODRIGUEZ M, LESKOVEC J, KRAUSE A. Inferring netWOrkS Of dlffuSlOn and influence[J]. ACM Transactions on Knowledge Discovery from Data (TKD- D), 2012, 5(4):21.
[24]TANG J, SuN J, WANG C, et al. Social influence analysis in large-scale net- works[C]//Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009:807-816.
[25]WANG C, TANG J, SuN J, et al. Dynamic social influence analysis through time- dependent factor graphs[C]//Advances in Social Networks Analysis and Mining(ASONAM), 2011 International Conference on, 2011:239-246.
[26]KWAK H, LEE C, PARK H, et al. What is Twitter, a social network or a
newsmedia?[C]//Proceedings of the 19th international conference on World wide web, 2010:591-600.
[27]WENG J, LIM E, JIANG J, et al 厂Twitterrank: finding topic-sensitive influential twit-terers[C]//Proceedings of the third ACM international conference on Web searchand data mining, 2010:261-270.
[28]TANG S, YUAN J, MAO X, et al. Relationship classification in large scale online social networks and its impact on information propagation[C]//INFOCOM, 2011Proceedings IEEE, 2011:2291-2299.
[29] WELCH M,SCHONFELD U,HED, et Topical semantics of twitterinternational conference On Web search
[30] PaL A, COUNTS S. Identifying topical authorities in microblogs[C]//Proceedings of the fourth ACM international conference on Web search and data mining,2011:45-54.
[31]ZHaNG M, Surr C, Lm W. Identifying Influential Users Of Micro-Blogging Ser-vices: A Dynamic Action-Based Network Approach[J].PACIS Proceedings,2011.