英语原文共 137 页，剩余内容已隐藏，支付完成后下载完整资料
第一章 社交媒体与社交运算
1.1社交网络
过去的十年间，网络和互联网的快速发展和变化。许多参与性web应用程序和社交网站纷纷出现，吸引将人们聚集在一起，并赋予他们新的协作和沟通模式。大量的在线志愿者以过往无法企及的深度与广度，合作撰写百科全书式的文章；网络市场通过用户购物和评论互动，利用大众智慧推荐产品；政治运动因为新的参与形式和集体行动而受益。
表1.1列出了各种社交媒体，包括博客、论坛、媒体共享平台、微博、社交网络、社交新闻、社交书签和维基百科。在社交媒体不同的特征下隐含着有别于传统媒体、网页的共性，即媒体信息的消费者同时也是媒体信息的生产者。
在电视、广播、电影和报纸等传统媒体中，只有少数“权威”或“专家”决定应该制作哪些信息以及如何发布这些信息。大多数用户是与信息生产过程分离的消费者。传统媒体的传播模式是单向的，从集中的生产者到广泛的消费者。
然而，社交媒体的用户既可以是消费者，也可以是生产者。随着数以亿计的用户活跃在各种社交媒体网站上，每个人都可以成为媒体的出口。这种新型的大众传播，使及时的新闻和草根信息得以产生，用户生成的内容大量生产，形成了群体的智慧。一个例子是2005年的伦敦恐怖袭击(Thelwall, 2006)，一些目击者将他们的经历写进博客，提供事件的第一手报告。另一个例子是2009年伊朗总统大选后的血腥冲突，许多人在社交平台Twitter上提供实时更新。社交媒体还允许合作写作产生高质量的作品。例如，“自2001年创建以来，维基百科已迅速成长为最大的参考网站之一，截至2009年，每月吸引约6500万访客。”有超过85000名活跃的贡献者，用260多种语言撰写了超过1400万篇文章。”
社交媒体的另一个显著特点是丰富的用户互动。成功社交媒体的发展依赖于用户的参与。更多的用户交互鼓励更多的用户参与，反之亦然。例如，Facebook声称截至2010年8月，其活跃用户已超过5亿。用户参与是社交媒体成功的一个关键因素，它帮助推动8个社交媒体网站进入前20名，如表1.2所示(Alexa在2010年8月3日发布的互联网流量)。用户是通过他们之间的交互联系在一起的，用户网络就是从这些交互中产生的。新的机会出现了，我们研究人类的互动和集体行为在一个前所未有的规模和许多计算的挑战随之而来，促使先进的计算技术和算法的发展。
本文主要介绍与社区侦测相关的社会网络分析的基本概念并使用简单的例子来说明目前的算法如何使用及分析社会媒体数据。本文涵盖了社会媒体中关于社区检测的重要主题。我们从贯穿本书的概念和定义开始。
1.2概念与定义
网络数据不同于属性值数据，具有自己独特的属性。
1.2.1网络和表征
社会网络是由节点(个人或组织)和关系组成的社会结构，其中关系以友谊或者是亲属关系等形式，将各节点连接起来。刻画一个网络有两种常用的方式。一个是以便于可视化的图形表示。图1.1显示了一个由9个角色组成的社交网络的玩具示例。社交网络也可以用矩阵来描述(称为sociomatrix (Wasserman和Faust,1994)，或邻接矩阵)，如表1.3所示。需要注意的是，社交网络通常是非常稀疏的，如表中许多0所示。这种稀疏性可用于执行有效的网络分析。在邻接矩阵中，我们不指定对角元素。根据定义，对角条目表示自链接，即
，从一个节点到自身的连接。通常，对于网络分析，对角线条目设置为0。然而，在某些情况下，对角元素应该固定为1。此后,除非我们显式指定，对角线上的元素默认为零。网络可以加权、签名和定向。在加权网络中，边与数值相关。在有符号网络中，一些边与正相关，有些可能是负面的。有向网络具有与边相关的方向。在我们的图1.1中的例子，网络是无向的。相应的，邻接矩阵也是对称的。然而，在一些社交媒体网站上，互动是有方向性的。例如，在Twitter中，一个用户x跟随另一个用户y，但用户y不一定跟随用户x。在本例中，跟随者-跟踪网络是定向的、不对称的。这一讲的重点是，除非明确指定，a最简单的网络形式。，带布尔边权值的无向网络，就像这个例子在表1.3。这一讲中讨论的许多技术可以扩展到处理加权的，还有签名和定向网络。
我们分别用V和E来表示网络中的节点集和边集。
网络节点数为n，边数为m。矩阵Aisin;{0,1}ntimes;n表示网络的邻接矩阵。条目A ijisin;{0,1}表示是否存在链接在节点v i和v j之间，两个节点v i和v j之间的边记为e(vi,v j)。两个节点如果A ij = 1, vi和vj是相邻的。N i表示所有与v i相邻的节点，即节点v i的邻域，与节点v i相邻的节点数称为其度，记为d i) .E.g。在网络图1.1中，d 1 = 3,d 4 = 4。如果节点是，则一条边与该节点相边的终端节点。例如，e(1,4)边与节点1和节点4相邻。两个节点之间的最短路径(比如，vi和vj)称为测地线。测地线中的跳数是两个节点之间的测地线距离(记为g(v i,v j))。
1.2.2 大规模网络的性质
社交媒体的网络通常非常庞大，有数百万的行动者和关系。这些大规模网络具有一些在小型网络中很少被注意到的常见模式。其中最显著的是:无标度分布、小世界效应和强大的社区结构。具有非平凡拓扑特征的网络被称为复杂网络，以区别于简单网络，如格图或随机图。
大型网络中的节点度通常服从幂律分布。让我们来看看图1.2两个YouTube网络具有特定节点度的节点数量和Flickr。从图中可以看出，大多数节点的度都很低，只有少数节点的度非常高(例如，度gt; 10 4)。在一个对数-对数的范围内，这两个网络都表现出相似的模式(近似线性，或直线的节点数量)。这种模式称为幂律分布，或无标度分布，因为分布的形状不随比例的变化而变化。有趣的是，如果我们放大到尾部(例如，检查那些具有gt; 100度的节点)，我们仍然会看到幂律分布。这种自相似性与尺度无关。具有节点度幂律分布的网络称为无标度网络。
社交网络的另一个显著特征是所谓的小世界效应。特拉弗斯和米尔格拉姆(1969)进行了一项实验，研究美国人社交网络的平均路径长度。在实验中，被选择的对象被要求从内布拉斯加州奥马哈市或堪萨斯州威奇托市的个人开始，向他的熟人发送一封连锁信(然后是偏远地区)到目标个人在波士顿，马萨诸塞州。最后收到了64封信，平均路径长度在5.5左右，或大约6，因此，著名的“六度分离”。这一结果最近在一个超过1.8亿人的行星级即时消息网络中也得到了证实，其中任意两个人的平均路径长度为6.6(Leskovec和Horvitz,2008)。
为了校准这个小世界效应，定义了一些额外的测量方法。网络中最长的测地线的长度是它的直径(Wasserman and Faust, 1994)。图1.1中网络的直径为5(对应于节点2与节点9之间的测地线距离)。在现实世界中，大多数大型网络的直径都很小。
社交网络也表现出强大的社区结构。也就是说，一个群体中的人彼此之间的互动比群体外的人要多。由于朋友的朋友也可能是朋友，所以这种传递性可以通过聚类系数来衡量，然后用朋友之间的连接数除以他们之间可能的连接总数。
聚类系数衡量一个人的朋友之间的联系密度。一个网络群体的平均聚类系数往往比随机网络高得多实例，在图1.1中，节点6有4个邻居，分别是4、5、7和8。其中，我们有四个连接e(4,5) e(5,7) e(5,8) e(7,8)。因此，节点6的聚类系数为4/(4times;3/2)= 2/3。网络的平均聚类系数为0.61。然而，对于一个随机图来说，节点和连接数相同，期望聚类系数为14/(9times;8/2)= 0.19。
1.3 现存挑战
数百万用户在网上玩、工作和社交。这种数据洪流允许前所未有的大规模社会网络分析-数百万行动者甚至更多在一个网上工作。例如电子邮件通信网络(Diesner et al.， 2005)，即时消息网络(Leskovec和Horvitz, 2008)，移动电话网络(Nanavati等，2006)，友谊
网络(Mislove et al.， 2007)。其他形式的复杂网络，如合著或引用网络，生物网络，代谢途径，基因调控网络和食物网络也检验和证明了类似的模式(Newman等人，2006)。社会媒体使一个新的研究人际关系的实验室。
这些大规模的网络结合了社交媒体的独特特性，为挖掘社交媒体提出了新的挑战。
以下是一些例子:
bull; 可伸缩性。社交媒体中呈现的网络可以是巨大的，通常涉及数百万行动者和数亿个连接，而传统的社交网络分析通常涉及数百个或更少的主题。现有的网络分析技术如果直接应用于这种大规模的网络，可能会失败。
bull;异质性。在现实中，个体之间可能存在多种关系。两个人可以同时成为朋友和同事。
因此，网络中同一组参与者之间存在各种各样的交互。一个网络中还可以包含多种类型的实体。对于许多社会书签和媒体共享站点来说，用户、标记和内容相互交织在一起，导致在一个网络中存在异构实体。对这些涉及异构实体或交互的异构网络的分析需要新的理论和工具。
bull;进化。社交媒体强调时效性。例如，在内容共享网站和博客圈中，人们很快就对大多数共享内容和博客帖子失去了兴趣。这与传统的web挖掘不同。新用户加入现有成员之间建立的新连接，而资深用户则成为休眠用户。我们如何在网络中捕捉个体的动态?我们能找到作为社区中坚力量的顽固分子吗?他们能决定自己社区的兴衰吗?
bull;集体智慧。在社交媒体上，人们倾向于分享他们的联系。群体的智慧，以标签、评论、评论和评级的形式，经常是可以获得的。元信息与用户交互一起可能对许多应用程序都很有用。如何有效地利用社会连接信息和集体智能来构建社会计算应用程序仍然是一个挑战。
bull;评估。关于挖掘社交媒体的一个研究障碍是评价。在传统的数据挖掘，我们习惯于训练-测试模型的评价。它在社交媒体上有所不同。由于许多社交媒体网站都需要保护用户隐私信息，所以可用的基准数据有限。另一个经常遇到的问题是缺乏社会计算任务的数据，这进一步阻碍了一些比较研究不同的工作。没有事实依据，如何进行公平的比较和评价?
1.4 社会计算任务
与这些挑战相关的是一些相关的研究任务。我们用例子来说明它们。
1.4.1 网络建模
自从瓦茨和斯特罗加茨(1998)和巴拉巴斯和阿尔伯特(1999)的开创性工作以来，网络
建模已经获得了一些重要的动力(Chakrabarti和Faloutsos, 2006)。研究人员研究发现跨领域的大型网络建模遵循一定的模式，例如，无标度分布，小世界效应和强大的社区结构。鉴于这些模式，用一些简单的机制来建立重复模式的网络动态模型是很有趣的。例子包括瓦特和斯特罗加茨模型(瓦特和斯特罗加茨，1998)解释小世界效应和优先依附过程(Barabasi和Albert,1999)解释幂律分布。网络建模(Chakrabarti和Faloutsos, 2006)提供了对独立于网络域的网络动态的深入理解。网络模型可用于模拟研究网络的各种特性，如网络受攻击时的鲁棒性、给定网络结构内的信息扩散等。
当网络扩展到数百万个以上的节点时，计算就成为一个挑战。一些网络统计数据，如直径和平均聚类系数。解决这个问题的一种方法是抽样(Leskovec和Faloutsos, 2006)。它通过调查原始庞大网络的一小部分，提供了对不同统计数据的近似估计。其他人探索I/O高效计算(Becchetti et al.，2008;Desikan and Srivastava,2008)。最近，利用分布式计算能力的技术(例如，Hadoop平台中的MapReduce机制)正引起越来越多的注意。
1.4.2中心性分析与影响建模
中心性分析是关于识别网络中最“重要”的节点(Wasserman和Faust, 1994)。传统的社会网络分析依赖于链接结构来识别具有高中心性的节点。常用的标准包括度中心性、中介中心性、亲密中心性和特征向量中心性(相当于Pagerank得分(Page et al.， 1999)。在社交媒体中，可以获得附加信息，比如评论和标签。这一变化为融合各种信息源以研究中心性提供了机会(Agarwal et al.， 2008)。
一个相关的任务是影响建模，旨在了解影响或信息的过程扩散部位。研究人员研究信息是如何传播的(Kempe et al.，2003)以及如何找到信息。在群体中影响最大的节点的子集。它的同级任务包括通过在线放置有限数量的传感器来阻止谣言传播或检测级联行为(Leskovec et al.2007b)。在市场营销领域，它也被称为病毒式营销(理查森和多明戈斯，2002年)或口碑营销。它的目的是识别有影响力的客户，以便营销，这样可以有效地影响他们的朋友，以实现最大的回报。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239850]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
