基于lda的社交网络链接预测模型研究.doc

独创性声明学位论文题目： 基于LDA的社交网络链接预测模型研究 本人提交的学位论文是在导师指导下进行的研究工作及取得的研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同仁在文中作明确说明并表示衷心感谢。学位论文作者： 签字日期： 年 月 日学位论文版权使用授权书本学位论文作者完全解西南大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权西南大学研究生院（筹）可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书，本论文：不保密，保密期限至 年 月止） 。学位论文作者签名： 导师签名：签字日期： 年 月 日 签字日期： 年 月 日目 录摘 要IABSTRACTII第1章 绪论11.1研究背景11.2研究现状21.3主要工作31.4论文结构41.5 本章小结5第2章 相关理论和技术62.1主题模型62.2复杂网络72.3社交网络82.3.1社交网络的发展82.3.2 社交网络的定义92.3.3 社交网络的数据表示102.4 社交网络分析112.5链接预测132.5.1链接预测算法142.6 本章小结16第3章 基于LDA的社交网络链接预测模型173.1 概述173.2总体框架173.3 形式化描述183.4用户兴趣信息特征提取203.4.1 兴趣主题提取203.4.2 兴趣主题相似度计算233.5社交网络结构信息特征提取233.6分类器的构造253.7模型的可行性和有效性分析253.7.1 可行性分析253.7.2 有效性分析2738 本章小结27第4章 实验294.1 实验平台294.2 数据集294.2.1 数据来源294.2.2 社交网络的构造294.2.3 数据的平衡处理314.3 实验目的314.3 评价方法314.4 实验具体方案324.5 实验结果与分析324.5.1 用户兴趣信息特征324.2.2 网络拓扑结构特征344.2.3 结果分析与比较344.6 本章小结36第5章 总结和展望37参考文献39致 谢43攻读硕士学位期间公开发表的论文44I西南大学硕士学位论文 摘要基于LDA的社交网络链接预测模型研究计算机软件与理论专业硕士研究生 补嘉指导教师 唐 雁 教授 摘 要随着Web2.0技术的不断发展，基于社区的服务，如Wikipedia、 Flickr和Facebook等越来越流行。在社区中，人们可以寻找和上传自己喜爱的图片，可以与社区中的其他用户进行链接，成为朋友。社交网络是依靠人与人之间的朋友关系组织在一起的系统，是现实人际网络的子集。社交网络用户数量的急剧增加，给网络中用户关系、用户信息等数据的挖掘带来了巨大挑战。利用用户节点的属性信息、社交网络的拓扑结构特征等预测用户节点对之间是否存在朋友关系链接，便是其中一个研究热点。现有的社交网络链接预测算法，如CN算法1、AA算法2、katz算法3等，主要关注社交网络中用户节点对之间的拓扑结构相似特征，缺乏对其属性信息之间潜在语义关系的重视，链接预测的精度不高。此外，在社交网络中，用户的兴趣信息数量巨大，如果直接对每个用户的每个兴趣进行语义关系分析，则需耗费大量时间。针对以上问题，本文引入主题模型、潜在迪里克雷分布模型(LDA， Latent Dirichlet Allocation)，首先利用LDA模型对用户节点对之间的兴趣信息进行建模，提取社交网络用户兴趣信息的主题，比较主题之间的语义相似度，这与直接对每个用户的兴趣信息进行分析相比，能够在捕获信息的潜在语义关系的同时，有效降低计算时间复杂度。其次，把复杂网络中的网络资源分配算法RA（Resource Allocation）用来对社交网络的结构信息进行特征提取。然后，通过构造分类器，利用有监督学习框架综合语义特征和拓扑结构特征进行社交网络链接预测。通过在真实的社交网络LiveJournal数据集上进行实验，与现有的链接预测算法比较，结果证明，本文提出的基于LDA的社交网络链接预测模型与已有的工作相比，在一定程度上，能够有效地提高链接预测精度。关键词：社交网络 LDA RA 链接预测AbstractResearch on Social Network Link Prediction Model based on LDA Major: Computer Software and Theory Research Direction: Web Application Technologies Supervisor: Prof. Yan Tang Author: Jia Bu (112009321001986)ABSTRACTWith the fast development of Web2.0 technology, the services based on the social community are more and more popular, for example, Wikipedia, Flickr and Facebook. In the community, people can find and upload their favorite photos, link to other users. Social Networks are the systems that relying on the friendships between people, they are a subset of interpersonal networks. The number of social network users has increased dramatically and it has brought great challenges to mining the relationship of the users, the information of the users in the network. One data mining problem of interest for social networks and the characteristics of the structure for social networks is the friendship link prediction problem.However,many social network link prediction algorithms focus on the topology structure similarity between nodes in the networks, for example,CN algorithm1,AA algorithm2 ,katz3 algorithm and so on.But these algorithms dont focus on the semantic relations between users interests.It results that the accuracy of link prediction is not high.At the same time, the user interests in the social network are huge, if we analysis the semantic relationship of them directly, we will spend a lot of time.To solve the above problems,we introduce the topic model ,the Latent Dirichlet model.First,we use LDA to model the interests between the user nodes and extract the topics of users interests in the social network,analyze the semantic similarity between these topics. Compared with the direct analysis of interests for each user,it not only can capture the latent semantic relations,but also can reduce the computation time complexity effectively.Then for the first time,we use the Rescource Allocation algorithm in the complex network into the social network to grasp the structure feature accurately.At last,by constructing the classifiers,we use of supervised learning framework integrate semantic feature and the toplogical structural characteristics to predict the friendship links in the social network. We apply the Social Network Link Prediction Model based on LDA to a real social network called LiveJournal, compare with the other methods to verify its viability and effectiveness. Experimental results on the subset of LiveJournal show the usefulness of the LDA features and structure features for predicting friendships.Key words: LDA, RA, social network, friendship link predictionIII第1章 绪论16 西南大学硕士学位论文 第1章 绪论第1章 绪论随着计算机信息科学技术的不断发展和互联网的普及，社交网络得到了越来越多的人的参与和关注，它已经逐渐成为人们日常生活的一部分，甚至已经影响到人们的工作、学习以及社会的进步。因此，社交网络分析正在逐渐成为社会学、计算机研究领域的热点。1.1研究背景复杂网络是由规模巨大的节点、节点间错综复杂的边而构成的网络。4复杂网络具有三个特性：“小世界”效应，集群及集聚程度，幂律分布。虽然复杂网络的规模很大，但网络中的任意两个节点间却存在一条非常短的路径，网络里的大多数节点仅有少量连边，少数节点拥有大量连边。一个小型微博社区的用户关系网络、一个城市的交通网络、科学家合著网络、社交网络等等都可以被看作是复杂网络。复杂网络中的节点可以代表任何事物，如人际关系的网络节点代表单独个体，万维网组成的网络节点表示不同的网页。社交网络作为复杂网络的应用领域之一，出现于90年代中期，随着近年来web2.0技术的不断发展5，互联网中信息的产生和传播的成本在大大地下降，互联网中的数据量呈现几何倍数的增长。数据可以描述成相互联系的实体的集合，这些实体的集合就构成了一个巨型的网络。在这样的背景下，社交网络变得越来越流行，它得到了越来越多人的参与和研究学者的关注。社交网络是基于社区服务的，在社区中，人们可以寻找和上传自己喜爱的图片，可以与社区中的其他用户进行链接，成为朋友。社交网络是依靠人与人之间的朋友关系组织在一起的系统，是现实人际网络的子集。由于人际关系与人们生活息息相关，且对人们的工作和学习、生活有显著影响，因此，研究和分析社交网络有重要的意义。近年来，社交网络的研究内容主要包括社交网络的拓扑结构分析、网络社区的发现、网络中信息的传播、社会化推荐（social recommendation）等等，它们取得了一定的研究成果。Lise Getoor在文献6中认为，社交网络中的链接是无处不在的，这些链接能够展现出数据的重要性。但在实际情况下，社交网络里并不是所有链接关系都是可见的，因此预测网络中个体或者组织之间是否存在链接关系就逐渐成为研究者感兴趣的问题。并且网络中的某些链接是在不断动态变化的，这个时候，研究者关注的问题可能是基于过去及目前的观察来预测未来某个时刻的链接关系。总的来说，社交网络链接预测（Social Network Link Prediction）7是根据已知的网络中的用户，网络结构等信息，预测网络中“尚未结交”用户成为朋友的可能性，这个链接可以是空间上的，也可以是时间上的。随着网络科学的快速发展，它在理论上所取得的成果为链接预测搭建了一个很好的研究平台，继而使得链接预测的研究与社交网络的结构与演化紧密联系起来7。通过链接预测的研究，我们可以分析演化网络89，也可以作为准确分析网络结构的有力辅助工具10。目前，大多数研究者提出的模型都提供了一些可能的网络演化机制。由于刻画社交网络结构特征的统计量比较多，我们很难比较不同的机制孰优孰劣，而链接预测有望为网络的演化提供一个简单统一且公平的比较平台，从而大大推动社交网络演化模型的理论研究。同时，社交网络链接预测可以预测网络中“尚未结交”的用户“应该可以成为朋友”，并将此结果发回给用户，进行个性化推荐。如果“朋友关系链接”预测准确度比较高，则有助于提高社交网络在用户心中的地位，从而提高用户对该网站的忠诚度。综合而言，社交网络链接预测有重要的理论和实际意义，具有较高的研究价值。1.2研究现状在早期的社交网络研究中，大多数是心理学家和社会科学家，但随着信息技术的快速发展，社交网络分析也在逐渐成为计算机领域的研究学者的关注热点。链接预测作为社交网络分析的一个重要领域，它是近几年产生的一个全新的研究领域，与传统的数据挖掘相比，数据挖掘处理的对象通常是单独的数据实例，这些数据实例往往可以用一个包含有多个属性值的向量来表示，并且这些数据实例之间在统计上是假设独立的。但在社交网络中，用户与用户之间不是独立的采样节点，他们之间是存在某些关联的。为了能够将用户之间的关系考虑进来，有研究学者提出了用图结构来刻画网络的社会结构。一个社交网络是由很多个节点（node）和这些节点之间的链接（Link）组成的。节点可以表示网络中的个体，也可以表示组织，链接表示节点之间的关系，如朋友关系、亲戚关系等等。社交网络的链接预测是比较困难的，因为网络中，大部分的数据集都是稀疏的。为链接预测建立统计模型的难点在于先验的知识太少，为链接存在提供的证据太少，导致准确度较低。在早期的链接预测研究中，大部分的工作都是集中于研究如何通过分析网络图的结构特征来预测链接，这些方法取得了一定的研究成果11 12。R.R.Sarukkai13利用马尔科夫链进行网络的链接预测和路径分析；J.Hong14等研究学者在对自适应性网络进行链接预测时也加入了基于马尔科夫链的方法。2008年，Clauset,Moore15等人在自然上的论文提出了一种利用网络层次结构进行链接预测，但该算法只在具有明显层次结构的网络中表现最好。OMadadhain等16利用网络的拓扑结构信息，从而建立起一个局部的条件概率模型来预测节点对之间是否存在链接。Liben-Nowell17等提出了基于网络结构的相似性定义，并将相似性计算分为基于节点和基于路径两个类型。Tang和Liu201018将图挖掘方法用于社区发现，证明了社区结构特征在网络分析中的重要性。Lu和Zhou201019在含权网络中，估计节点对之间存在链接的概率，预测节点对是否存在连边。但这些方法都忽略了网络中用户属性信息之间的潜在语义关系，链接预测的准确度有提高的空间。Patil20指出，在社交网络中，用同构原则能够有效提高预测用户之间的朋友关系的准确度。有相似文化、语言、爱好和地理位置的更容易成为朋友。Aljandal22用社交网络中的用户的兴趣信息，建立本体，通过本体之间的语义关系来对兴趣信息建模，提高了社交网络链接预测的准确度。Bahirwani 等人23利用现有的网络目录的层次结构提取概念及概念之间的关系建立本体，对文档进行分析，证明了本体的建立和使用，可以有效捕获网络中节点属性之间的语义关系，可以提高链接预测的准确度。但不管是直接分析用户节点的属性之间的相似度，还是建立用户的属性信息本体，都需要耗费大量的时间，链接预测的效率有待提高。Hsu24等提出了在社交网络中，用已知的网络结构特征及用户属性信息，对用户之间的朋友关系进行预测、分类、标记的难点。用实验证明了在社交网络中，将已知的网络结构特征与用户属性特征融合，可以在一定程度上提高链接预测的准确度。Haridas25在Hsu等人的研究基础上，使用网络中具有层次结构的Wikipedia Category Graph(WCG)，得到用户属性信息的定义，捕获这些信息之间的语义关系。Parimi201126使用迪里克雷分布 ( LDA, Latent Dirichlet Allocation（以下简称为LDA）)对社交网络中用户属性信息进行主题提取，证明了LDA可以减少链接预测的计算时间复杂度。但这些算法对用户属性语义相似度的计算比较粗糙，缺乏对网络结构特征的重视。尽管近几年来，链接预测的研究已经取得了一定的进步，但由于社交网络结构的复杂性，网络中节点属性信息的巨大性，如何在减小计算复杂度的同时，有效提取网络的拓扑结构特征，捕获网络中用户节点的属性信息之间的潜在语义关系，最终达到提高预测朋友关系的准确度的目的，是当前社交网络分析的难点之一，也是需要解决的重要问题。1.3主要工作 研究目标：针对链接预测算法RA缺乏对节点之间属性信息之间语义关系的关注的问题，本文的研究重点在于使用LDA模型对用户的属性信息建模，重视网络的结构信息，综合利用节点的属性特征和网络的拓扑结构特征进行链接预测，提高链接预测准确度。通过在真实社交网络数据集上的实验证明本文提出模型的可行性和有效性。研究意义：在理论方面，本文提出的方法利用LDA模型对网络中用户节点的兴趣信息主题特征建模，并重视社交网络的拓扑结构特征，进一步发掘了节点的属性信息对“朋友关系”链接预测的潜能，从一个新的角度揭示了网络的结构和节点属性信息与链接生成之间的关联。在应用方面，本文提出的模型可以提高链接预测准确度，可以提高社交网络的信息系统的服务质量，加强用户对社交网站的忠诚度。研究内容：(1)通过分析现有的加入语义的链接预测算法，针对其计算复杂度高、对用户属性语义相似度的计算比较粗糙两个问题，引入主题模型(Topic Model)、LDA模型，利用LDA模型提取用户兴趣信息主题，对主题进行语义相似度分析，准确捕获兴趣信息之间的潜在语义关系。(2)探讨复杂网络中基于网络拓扑结构特征的链接预测算法，通过研究将复杂网络的链接预测算法网络资源分配算法RA（Resource Allocation）运用到社交网络中，有效提取社交网络拓扑结构特征，分析社交网络中用户节点之间的拓扑结构相似度。(3)抽取社交网络的语义特征和拓扑结构特征，通过有监督学习框架组合这两种特征，使两种特征同时流入分类器，综合两种特征进行社交网络链接预测，得到链接预测的准确度。通过将模型应用到真实的社交网络LiveJournal数据集中，与现有的链接预测算法进行比较，结果表明，本文提出的模型，在一定程度上，能够有效地提高社交网络链接预测的准确度。1.4论文结构本论文共五章，结构安排如下：第一章：论文的绪论部分。简要概述了论文研究内容的背景、发展现状以及研究所做工作的内容和意义，并对全文的结构安排进行简介。第二章：相关理论和技术。主要介绍论文研究所采用的一系列相关理论，介绍了研究工作中所涉及的相关理论，包括主题模型、LDA模型，社交网络链接预测概念等。第三章：基于LDA的社交网络链接预测模型。本章首先介绍社交网络“朋友关系”链接的总体框架、总体步骤，并对相关概念进行形式化定义。接着详细叙述研究的具体内容，对本文提出的模型，分别就提取网络中用户的兴趣信息特征、结构特征、通过有监督学习的框架组合两种特征进行了深入详细的阐述。第四章：实验设计与结果分析。详细说明实验所采用的数据集的特性、预处理实验数据的方法、实验的设计、实验的平台等内容，另有实验方案及详细的结果分析。第五章：总结与未来工作展望。总结全文工作，分析了现有研究工作的不足，并对今后的工作提出了进一步的设想。1.5 本章小结本章主要讨论了论文研究的背景、国内外当前的研究现状，指出在当前社交网络链接预测研究中存在的一些问题，接着概要说明了本文研究的具体内容和意义，最后对文章余下部分的内容安排进行了阐述。西南大学硕士学位论文 第2章 相关理论和技术第2章 相关理论和技术2.1主题模型主题模型（Topic Model） 27是当前研究文档表示的主要范式，它是一个能够对大规模文档集进行有效分析的模型。如图2-1所示，主题模型认为，每篇文档（顶部大圆）是需要讨论若干个主题（底部小圆）的，这些主题的拓扑结构是线性的。为文档主题建模就是把主题看作是词汇的概率分布，文档为主题的随机结合。它通过将文档和词汇的维度转化成文档与主题，主题与词汇的维度，将文档映射到主题空间，从而使文档信息转换成易于建模的数字信息，利用对主题空间的分析从而捕获各个文档之间潜在的语义关系。运用统计的方法分析文本的主题模型有很多，它的生成模型，如LSA模型、PLSA模型、LDA模型等。有研究学者指出28,传统的生成模型， PLSA、LSA模型，文档概率值与特定的文档相关，缺乏处理新的文档的自然方法。在以上模型里，待估参数的数量会随着文档数量的不断增多而线性增长，易于过度拟合。与PLSA、LSA模型相比，LDA模型作为一种非监督机器学习的技术，如图2-2所示，它的建模过程是逆向文档集合建立生成模型，将文档主题混合权重视为维参数的潜在随机变量，而不是与训练数据直接联系的个体参数集合，推理上采用Laplace近似，期望-扩散（expectation-propagation）、变分近似等方法获取待估参数的值，克服了LSA、PLSA模型的不足。LDA是全概率生成模型，具有非常清晰的内在结构，更适合处理大规模的语料库。近年来，LDA模型、LDA的扩展模型在智能信息处理、自然语言处理中的应用得到了研究学者的重视和深入的研究，其应用涉及到词义消歧29、信息抽取30、词性的标注31、文本分割29等等。本文主要采用LDA模型对社交网络中用户的兴趣信息进行主题分析，捕获这些信息之间的潜在语义关系，以助于提高链接预测的准确度。LDA模型将在第3章中进行详细阐述。图2-1 LDA的隐含主题的拓扑结构图2-2 LDA模型的矩阵分解2.2复杂网络复杂网络是由节点和链接关系组成错综复杂的大规模网络,它之所以称为“复杂”，主要体现在32:(1)结构复杂，网络的结构可以呈现出多种不同的特征；(2)网络中不断有新的节点出现，也不断有节点在消失，从而导致网络结构也在不断发生变化；(3)网络中节点与节点之间可能存在方向性；(4)网络中的节点可以代表任何事物，如：社交网络中的节点代表单独的个体，万维网组成的复杂网络节点代表不同的网页。复杂网络主要具有三个特性：“小世界”效应，集群及集聚程度，幂律分布。也就是说，在复杂网络中，任意两个节点之间都存在一条较短的路径，少数的节点拥有大量连接，大多数的节点拥有少量连接，节点的度分布是遵守幂律分布的。如图2-3所示,人们在生活和生产中所接触到的许多系统都可以被看作是某个类型的网络。复杂网络是丰富多样的，如互联网、人际关系网、万维网、公路运输网、蛋白质相互作用网、人类大脑中的神经网等都属于复杂网络。本文研究的社交网络便是复杂网络的一个子集。早期的对复杂网络的研究主要集中在只有数十，最多数百个节点的网络上。这是因为:第一，在计算机普及之前，对网络的结构和数据分析主要依靠的是手工计算，但数百个节点的网络已经是达到了手工计算的极限；第二，早期的研究中，对网络信息的收集也主要是依靠手工完成，这导致了得到的复杂网络的规模也是非常有限32。图2-3复杂网络模型图近年来，随着计算机的普及，互联网、万维网的快速发展，对网络的研究也在发生着很大的变化。我们只需要一个网络爬虫程序，就能很快收集到数以万计的网络节点。同时，各种各样的网络层出不穷，例如网络社区网、科学家合著网、电子邮件通信网等等。这些丰富多样的网络与我们的生活、学习密切相关。因此，在这些种种变化的推动之下，人们对复杂网络的研究已经由原来的几百个节点的小型网络转到了有千百万节点的大型网络上面。2.3社交网络2.3.1社交网络的发展1967年，哈佛大学的心理学教授Stanley Milgram提出了六度分割理论34,他指出（如图2-4所示），在地球上，任何一个人与陌生人之间所间隔的人不会超过六个，即：最多通过六个人，你就能认识任何一个陌生人，它也叫小世界理论。六度分割理论说明了社会中普遍存在“弱纽带”效应，但是发挥着非常强大的作用，它是社交网络的理论基础。根据六度分割理论，在社会中，每个个体的社交圈在不断地放大，最后成为一个大型的网络，这就是人们对社交网络（Social Network）的初期的理解。随着web2.0技术的不断发展，根据六度分割理论35，创立了面向社交网络的互联网服务（Social Network Service）。这张“大网”把世界紧紧地联系在了一起，我们每个人都是网络中的一个节点，节点与节点之间的联系更是突破了地域性和时间性的限制。与此同时，互联网服务也越来越人性化、社会化。在互联网服务里，人们可以创建属于自己的个性信息，可以与其他用户成为朋友，因此，社交网络便通过“朋友的朋友”来进行拓展，从而使得它在功能上能够反映和促进真实社会关系的发展和交往活动的形成，其社会化程度越来越高，例如：LiveJournal,Facebook,人人网等。图2-4 六度分割理论模型图2.3.2 社交网络的定义社交网络（Social Network），36是由许多节点构成的一种社会结构，节点通常代表个体或者组织。社交网络是由一群个体或者组织以及他们之间的关系组成的，这种关系是建立在真实人际关系基础之上的，它可以是人和人之间可能发生的任意一种社会关系，例如兴趣、理想、亲情等等。通过各种社会关系，可以将个体或者组织串联起来。由于社交网络几乎覆盖了社会的各个层次，由一个或多个特定类型的关系维系，因此，通过这些关系产生的图形结构往往非常复杂。社交网络模型图如2-5所示。在社交网络中，人们相互之间可以共享某些知识，也可以建立起自己的社交圈，这些都在一定程度上影响了我们社会的政治和经济的发展。对于社会学家或经济学家，社交网络中的链接信息可以帮助他们更好地去了解社会和经济的发展规律，可以更好地为制定出有效的社会、经济政策提供理论根据。对于生活在社会中的人们，社交网络则是可以提供更加广阔的交流空间，大大缩短人们之间的距离。对于社交网络的经营者而言，网络中包含的大量的有用信息则可以帮助他们制定出更加合理的运营方案，建立起更准确更有针对性的推荐系统，从而提高网站在用户心中的地位。目前，对于社交网络的研究热点主要集中在社交网络模型的设计，社交网络社区划分、发现以及衍化，社交网络链接预测等等。其中，社交网络模型的设计以理论为基础，它的研究成果通常会在其他的研究分支中应用。社交网络社区划分、发现以及衍化，社交网络链接预测是从实际应用出发的，其研究成果可用来实现各种各样的推荐系统，如网上交友推荐、科学家合作推荐、社区推荐等。2.3.3 社交网络的数据表示社交网络的数据表示是分析社交网络的基础，其中图论中的图(graph)则为图2-5 社交网络模型图形式化社交网络提供了一个比较直观的表示形式。2004年，Freeman37提出分析社交网络的必须要具备的四个特征:(1)社交网络分析更加注重个体或组织（Actor）之间的联系，而不是个体或组织本身所具有的性质；(2)网络中个体或组织之间联系的数据必须要通过系统化的方法进行收集；(3)社交网络的分析是建立在图的模型基础之上的；(4)可以使用数学和相关计算工具从关系中获取有意义的信息。从上述可以看出，图是社交网络的一个重要的表示方式。在社交网络图中，包括节点、链接、度数等基本概念38。节点节点，表示的是社交网络中的个体（Actor），它指网络中的参与者，也就是在一个网络里与他人相链接的个体、组织或者其他集体性质的社会实体。链接链接，指的是节点与节点之间的连边。在社交网络中，链接是基于某个特定关系而建立起来的网络连接，它体现的是用户之间的相互信赖。节点之间的关系，为了简单计算，本文采用二元关系，即两个用户之间要么是朋友，要么不是朋友，所有的朋友关系都同等对待。有向链接和无向链接有向链接是指有方向性，即从节点X到节点Y的有向链接与从节点Y到节点X的有向链接是不同的。无向链接是指没有方向性，即从节点X到节点Y的有向链接与从节点Y到节点X的有向链接是相同的。在对社交网络进行表示时，可以用有向链接，也可以用无向链接。无向网络和有向网络之间可以相互转换，只需要把每条无向链接变成方向相反的两条有向链接即可。本文研究是把社交网络表示成一个无向网络。度数 度数，指的是与节点相连接的链接的数目。在有向网络中，度数包括出度和入度两类。节点的入度数就是和它相连接的，并且指向该节点的链接的数量。节点的出度表示和它相连接的，并且向外指的链接的数量。社交网络中的个体或组织是社交网络的基本元素，他们构成了图的节点和节点之间的连边。在此基础上，也有更为复杂的模式：(1)二元组（Dyad）：由两个个体或者组织及他们之间的关系组成，这是分析网络结构的基本单位；(2)子图（Subgroup）：由网络中的一部分个体或者组织及他们之间的关系组成，可以通过观察子图来研究社交网络中的小团体所具有的某些特征；(3)图（Graph）：网络中所有的个体及其之间的关系，用来分析网络的总体的特征。在本文研究中，我们也是通过图模式、网络中节点的度数、链接情况对社交网络的结构进行分析和研究，从而得到网络的拓扑结构特征。2.4 社交网络分析社交网络分析(Social Network Analysis)是用来建立社会关系的模型，它可以发现网络中个体或者组织间的社会关系，描述社会关系的结构。通常，社交网络分析也称之为社交网络的链接挖掘3940,它是从对象和链接出发的，可以获取关于个体或组织更丰富、更准确的信息。与此同时，网络中很多链接本身也是研究学者所关心的有效信息。例如在某些情况下，并不是所有的链接都能被观测到，因此研究的重点可以集中在预测个体或组织之间的是否存在链接。在某些领域，链接随着时间不断转变，那么研究点可能是基于当前的观察来预测在未来某个时刻是否存在某个链接。更进一步，由于考虑了节点之间的链接，社交网络的结构属性，如节点的度数、连通性等在挖掘中也提供了重要信息，同时，更复杂的模式，如子图（subgraph）38随之出现，如何获取关于这些模式的信息也给链接挖掘提出了更大的挑战。社交网络分析常见的任务根据挖掘任务的侧重点（节点、链接、图）不同，可以分成7种40，如表2-1所示。在本文研究中，我们关注的是基于链接的相关任务里的链接预测。社交网络分析的各个任务之间是相互联系、相互影响的。如基于图的相关任务就是建立在基于节点、基于链接的相关任务基础之上的。通过对社交网络进行分析，我们可以得到关于网络中的个体或者组织更加丰富和准确的信息，如预测某个体所属的类别，获得某个组织在网络中的重要性等。这些结构可以帮助我们识别到团队、某个社区中的重要角色，提高团队、社区内部的沟通效率，改进策略，继而使得我们得到更多的利益。总的来说，社交网络是作为一个应用产生出来，同时它的丰富的数据为我们提供了更好的分析素材，可以帮助我们更好地认识和理解社会，从而改造社会。表2-1 常见的社交网络分析任务及分类节点相关任务基于链接的节点排序（Link-Based Object Ranking）基于链接的节点分类（Link-Based Object Classification）节点聚类（Object Clustering）链接相关任务链接预测（Link Prediction）图相关任务子图发现（Sub-graph Discovery）图分类（Graph Classification）图的产生式模型（Generative Models for Graphs）社交网络分析一般包括以下步骤38：(1)准备数据，建立关系矩阵社交网络的数据来源一般采用问卷或者其他调查方法，也可以直接从网络的后台数据库获取。经过对数据的预处理，可以按照预定的格式建立起关系矩阵。这是社交网络分析的非常重要的基础性的工作。社交网络分析中，通常有三种关系矩阵：邻接矩阵(Adjacency Matrix),隶属关系矩阵（Affiliation Matrix）,发生矩阵(Incidence Matrix)。在本文研究中，则主要考虑邻接矩阵。在邻接矩阵中，行和列表示社交网络中的注册用户，矩阵的值为二值矩阵，如果为“0”，表示两个用户之间没有朋友关系，如果为“1”，表示两个用户之间存在朋友关系。(2)数据处理得到分析的数据后，我们便可以在此基础上进行数据处理，从而进行社交网络分析。通过网络分析软件，可以计算出社交网络