毕业论文：在线社交网络

在国内，创建于1998 年5 月的中国同学录(5460.net)和Classmates类似，都是以同学数据为基础的校友录网站。2003 年开通的UUZone被认为是国内最早的社交网站。2005 年12 月，校内网（现改名人人网）在清华、北大、人大三所学校开通服务，这是国内首个实名制且具备一定影响力的社交网站，其主要用户集中在校园。2012年2 月，开心网成立并迅速在白领用户市场中获得认知，其页面访问量逐渐超过人人网。QQ 无疑是国内乃至全球注册用户数最多的社交网络，作为一款风行的即时聊天工具，QQ 承载着人们的各种社会关系，这使得所有使用QQ 的用户都存在于一个大的社交网络之中。

四、社交网络的主要研究问题

近几年，社交网络的研究越来越多地引起学术界的关注，研究内容包括社交网络的拓扑分析、社会化推荐(social recommendation)、网络社区发现、社交网络中的信息传播等，也取得了一些成果。 1、社交网络拓扑特性分析

当社会网络刚开始进入研究者的视线的时候，人们希望通过了解社会网络的拓扑特性，和已知的一些网络，例如WWW， Internet 的拓扑结构进行比较。这些比较主要是基于节点度分布，社交网络的网络半径、平均路径长度和聚集系数等 ，来看看社交网络的图结构和非社交

网络的图结构有什么不同。有些研究希望通过这些特性分析判断某些应用的性能。例如：有些应用只有在具有很强的局部连通的社交结构的条件才能有效的工作。这就意味着，社交图必须有大量的联系紧密的簇。 分析Facebook 的节点度分布，其分布符合幂律分布。为研究社交网络的网络半径、平均路径长度和聚集系数等特性，依据每个区域network 构建了社交网络图，所有区域network 的平均路径长度都小于6，网络半径或直径相对较低。聚集系数相对于同规模的随机图或随机幂律图具有较高的聚集性。Facebook 中所有network 的同配系数均大于0，说明度值较高的节点之间的互联的概率较大，这些度值较高的、相互连接的节点就形成了小世界网络的骨干网，这使得处于网络边缘的那些高聚集的节点与其它节点之间具有较小的平均路径长度。 2、用户行为分析

主要分析了用户访问社交网络过程中的行为，数据来源是用户访问社交网络的HTTP 会话过程数据。文中分析并比较了四种不同社交网络（Facebook, LinkedIn, Hi5,和StudiVZ）的用户访问行为特征。结果表明访问社交网站与其他网站存在不同之处：a)用户容易重复同一个行为；b)用户每次会话过程时间比较长；c）图片目录最受欢迎。除了研究用户访问社交网络的行为外，还研究了各种行为之间转移概率。为验证社交网络拓扑特性

与用户交互网络拓扑特性之间的差异，利用facebook 中的数据分别对这两种网络的拓扑特性进行统计分析，结果表明二者之间存在较大的差异，用户交互网络的网络直径显著变大。 3、社会化推荐

传统的推荐技术主要利用了user 对item 评价矩阵，但在社交网络中用户对某item 的评价往往极大影响其朋友的选择。综合了user 对item 评价以及user 之间的信任关系（构成Social Trust Ensemble）进行推荐，使得推荐结果更精确，并具有现实意义。研究基于协同过滤的社会化推荐问题，针对传统协同过滤法存在的两个问题：a）因计算复杂度而引起的特征信息融合困难；b）各种特征信息之间的依赖关系不能有效地利用，提出了多层次的连续随机场模型，用于社会化推荐。 4、社区关系挖掘

网络社区发现算法有很多种，但有些算法的可扩展性较差，适合于大规模网络的却为数不多，CNM、Wakita和Louvain是三种扩展性较好算法。然而这三种算法都存在：

当输入数据顺序不同时，得到的结果也不相同的问题。提出两个定量指标成员成对概率(pairwise membership probability)和一致性(consistency)，并依据这两个指标提出新的挖掘算法解决挖掘结果一致性

的问题。利用Filckr 中的图片和标签描述信息推测图片的拍摄位臵，并基于位臵进行新型的关系挖掘，表明时序信息和可视内容有助于推测图片呈现的位臵。结合位臵和时序信息可以还原图片的拍摄路线，启示了信息的变迁。

5、社交网络中的信息传播

目前社交网络信息传播模型大都是基于独立级联模型(Independent Cascade Model , ICM)的，但ICM 的计算量较大，用最短路径模型（Shortest-Path Model, SPM）来近似求解信息的传播范围以降低计算量，SPM 的主要思想是信息沿着从已受影响节点集合到将要受影响节点的最短路径进行传播，其速度是最快的，SPM 是ICM 的一个特例。实验结果表明最短路径模型（SPM）具有独立级联模型(ICM)的相同效果，但运行效率更高。利用因子图建模，提出三种不同的学习算法，对社会影响力进行了定量分析。从两个方面研究了信息传播最大化的问题：a）改进贪婪算法，降低运行时间；b）通过舍弃某些度值，提出新的启发式算法，以改进信息的传播速度。基于实验结果，作者认为在解决信息传播的可扩展性方面，启发式算法应优于贪婪算法。很多研究者关心，在社交网络的活动中，哪些用户行为会影响信息传播，因此，在在社会网络之上，有人又提出了interactive network，visit network 等表现用户交互行为的关系网。

6、其它基于社会网络的应用

除了针对社会网络本身特性的研究，越来越多的研究开始关注基于社会网络的其它应用问题。例如利用社会网络中朋友关系疏密程度，来防止Sybil attacks。还有利用朋友关系改善网络的流量控制以及阻断干扰消息等。

五、结论

互联网技术的发展及Web2.0 的兴起使得社交网络日益流行起来，并引起国内外人们的关注与参与，社交网络的注册人数逐年增长，其内容不断更新，这为研究大规模社交网络提供了前所未有的真实的实验平台。社交网络作为现实人际交往的扩展，其中蕴含的海量信息将会对人们的工作和生活产生影响，同时也为计算机学科相关研究带来新的机遇。