面向社会网络分析的数据挖掘方法研究数据挖掘课程论文.doc

1、面向社会网络分析的数据挖掘方法研究摘 要随着信息技术的发展，越来越多的社会关系数据被收集。如果能够有效地对它们进行分析，必将加深人们对社会学的理解，促进社会学的发展。但是数据量的增大同时对分析技术提出了巨大的挑战。如今社会网络的规模早已超出了原有分析手段的处理能力，必须借助更为有效的工具才能完成分析任务。数据挖掘作为一种帮助人们从海量数据中发现潜在有用的知识的工具，在很多领域发挥了重要的作用。社会网络分析又称为链接挖掘，是指用数据挖掘的方法处理社会网络中的关系数据。本文对数据挖掘和社会网络分析中的一些方法进行了介绍并对数据挖掘算法在社会网络分析的应用进行了概括。关键词：设会网络分析；数据挖掘；

2、链接挖掘RESEARCH ON SOCIAL NETWORK ANALYSIS-ORIENTED DATA MINING METHODABSTRACTWith the development of information technology, more and more social relation data have been collected. Effectively analyzing these data will help the human understand the properties of society, and promote the development of

3、 sociology. However, the growth of data presented a huge challenge to the analysis method. Now the scale of social network has already gone beyond the scope of the handling capacity of the original analytical methods. Some more effective tool should be utilized to complete the analysis tasks. Data M

4、ining helps people find a potentially useful knowledge from Massive Data, and play an important role in many fields. Social network analysis is also called linking mining. It use methods of data mining to deal with relational data in social network. This paper briefly introduces some methods in the

5、areas of data mining and social network analysis, and generalizes the application of data mining using in social network analysis.KEY WORDS： social network analysis; data mining; link mining目 录1.引言12.社会网络和数据挖掘方法介绍32.1社会网络分析方法32.1.1用户用户网络模型32.1.2用户事件网络模型42.2数据挖掘方法52.2.1关联规则分析62.2.2聚类分析83.数据挖掘在社会网络分析中

6、的应用93.1基于相似度度量方法103.2基于统计的方法123.3基于频繁模式挖掘的方法144.总结151.引言传统的机器学习处理的社会学中的对象是单独的数据实例，这些数据实例往往可以用一个包含多个属性值的向量来表示，同时这些数据实例之间假设是统计上独立的。例如要训练一个疾病诊断系统，它的任务是诊断一个被试者是否患有某种传染病。传统的学习算法用一个向量来表示一个被试者，同时假设两个被试者之间的患病情况是相互独立的，即知道一个确诊病人对于诊断其他被试者是否患病不能提供任何帮助。直观经验告诉我们这种假设是不合理的。直到二十世纪 30 年代，Jacob Moreno 和哈佛大学的一组研究人员分别提出

7、了社会网络模型来分析社会学中的现象和问题。现代社会学主要研究现代社会的发展和社会中的组织性或者团体性行为。社会学家发现社会实体之间存在着相互的依赖和联系，并且这种联系对于每个社会实体有着重要的影响。基于这样的观察，他们通过网络模型来刻画社会实体之间的关系，并进一步用来分析社会关系之间的模式和隐含规律。为了更好的研究这个问题，他们试图用图结构来刻画这种社会网络结构。一个社会网络由很多节点（node）和连接这些节点的一种或多种特定的链接（link）所组成。节点往往表示了个人或团体，也即传统数据挖掘中的数据实例，链接则表示了他们之间存在的各种关系（relation），如朋友关系、亲属关系、贸易关系、

8、性关系等。由于数据收集方式的限制，早期的社会网络局限于一个小的团体之内，往往仅包含几十个结点。借助于图论和概率统计的知识，人工处理可以从中分析出一些简单的性质和模式。但是，随着现代的通信技术的发展，越来越多的数据被收集和整合在一起，建立一个大的社会网络成为可能。例如，可以通过电子邮件的日志来建立使用者之间的联系网络，或者通过网络日志及网络通讯录等方式将用户提交的联系人信息建立社会网络。所以，现在的社会网络规模比早期网络庞大，通常包含几千或者几万的结点，甚至有多达百万个结点的网络。面对这样庞大复杂的网络，简单的数学知识和原始的人工处理已经不可能进行有效的分析。数据挖掘是从巨量数据中发现有效的、新

9、颖的、潜在有用的并且最终可理解的模式的非平凡过程。数据挖掘就是为了解决当今拥有大量数据，但缺乏有效分析手段的困境而出现的研究领域。目前，已经在包括生物信息学，自然语言处理等许多方面发挥了巨大的作用。与传统的数据挖掘只关注数据实例不同，社会网络分析对链接同样关注。从数据挖掘角度，社会网络分析又称为链接挖掘（link mining）。通过对链接的挖掘我们可以获得关于实例更丰富（如某个实例在整个网络中的重要性）、更准确（如预测某个实例所属的类别）的关系数据（relational data）。社会网络分析是关系数据挖掘的主要应用。关系数据挖掘的发展为社会网络分析提供了更有力的工具，促进了社会网络分析的

10、发展。本文分析了社会网络分析数据的方法以及任务和需求，介绍了几类适于社会网络分析的数据挖掘算法。2.社会网络和数据挖掘方法介绍2.1社会网络分析方法社会网络分析是一套用来分析多个个体通过相互联系构成的网络的结构，性质以及其他用于描述这个网络的属性的分析方法的集合。如社会网络分析方法提供了根据网络中节点的联系紧密情况将网络分层的方法，网络中节点相互作用模式识别，将网络分块，给用户评级，信息扩散，对社会网络提供图形描述，中心度的分布等。下面我们介绍社会网络分析最重要的两个模型，用户用户网络模型和用户事件网络模型2.1.1用户用户网络模型在网络模型中，我们把用户作为节点，用户之间的联系作为节点之间的

11、连线，构成一个社会网络。用户之间产生联系，一个用户对另一个用户的连接可以是一次也可以是多次，并且是带有方向的，因此这是一个带有数值的有向网络。如果用户 A 指向用户 B，则产生弧 AB，这条弧由 A 指向 B，连接的次数就是这条弧的值。整个网络中节点的数量用 l 表示。每个结点用i表示。图2.1 用户用户网络示意图图 2.1 给出了一个由 6 个用户构成的简单的“用户用户网络”示意图。图2.1 中，结点 1到2有1条弧，值为3，表示用户1与用户2有3次连接。结点2与3之间是双向弧，值为 1 和 3，表示用户2与用户3有1次连接，表示用户3与用户2有3次连接，以此类推。威望度计算：在一个有向带值

12、得网络中，一个结点的威望度是指这个结点的入度与所有节点的入度和的比值 6。 (式2.1)式2.1是威望度的计算公式，其中xi-表示节点i的入度。入度是指所有指向该结点的弧上的值的和。如图 2.1中，节点3的入度为 2+3=5，威望度为 5/14=0.385；节点6的入度为 1，威望度为 1/14=0.077；结点1的入度为 0，威望度为 0/13=0。一个结点的威望度越高，该结点所代表的用户被其他用户连接的次数就越多，该用户在网络模型所处的位置就越重要。计算表明在节点数量巨大的网络中所有的节点符合幂律分布而不是随机网络中的正态分布钟形曲线。我们将其记作，根据公式，其中参数就是幂次数。例如，在计

13、算过的万维网文档上的外指链接后，其链接符合公式，其中=2.57。中心度计算：在一个有向带值的网络中，一个结点的中心度是指这个结点的出度与所有结点的出度和的比值6。 (式2.2)式2.2是中心度的计算公式，其中xi+表示节点i的出度。出度是指所有该节点指向其他结点的所有弧上的值的和。如图2.1中结点1的出度为 2+3+2=7，中心度为7/14=0.538，结点3的出度为 1+1+1=3，中心度为3/14=0.154。一个结点的中心度越高，表示该结点连接别人的次数就越多，说明该用户在网络模型中越活跃。2.1.2用户事件网络模型在网络模型中，用户之间除了连接这种联系以外，用户还因为同时参与一个事件而

14、联系，而事件也因有相同的用户参与而联系。在模型中，通过用户与事件之间的联系构建网络拓扑图，假如用户参与了事件 e，则在v和e之间连线，因为我们这里主要研究事件传播的广度，因此我们不考虑用户对同一事件的多次参与，又因为这种联系只在两种不同类型的对象（用户和事件）之间存在，所以方向已经没有意义，因此这是一个不带值的无向图4。图 2.2 用户事件网络示意图图 2.2 给出了一个由6个用户和5个事件构成的简单的“用户事件网络”示意图。图中，左边的6个圆球表示6个用户，由i标出，i从1到6；右边的5个圆球表示5个事件，由ei标出，i从1到5。图中的线连接用户与事件，如1到e1有一条连线，表示用户1参与了

15、事件e1，以此类推。事件的中心度计算：事件的中心度是指参与该事件的人数与总人数个数的比值。 (式2.3)式(2.3)为事件中心度计算公式，其中 xi表示参与ei事件的用户，n表示该图中总的用户个数。如图2.2 中e2事件的参与人数为3，事件中心度为3/6=0.5。事件之间的联系。在图2.2中，事件之间没有直接联系，但是却存在间接联系，我们认为拥有相同的用户参与的两个事件之间存在联系，拥有相同用户的数量越多则两个事件联系越紧密。如，事件e1和e2拥有一个相同的用户（1），则它们的联系强度为1；事件e2和e3拥有 2 个相同的用户（3,4），则它们的联系强度为2。通过这种方式建立只有事件之间的联系

16、而把用户从网络中剥离出来得到新的“事件事件网络”模型，可以很方便的找出联系最紧密的事件。2.2数据挖掘方法数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。与数据挖掘相近的同义词有数据库中的知识发现(KDD Knowledge Discovery in Database)、数据分析、数据融合以及决策支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，仅支持特定的发现问

17、题。即所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。数据挖掘的任务是从数据中发现模式。模式有很多种，按功能可分为两大类：预测型模式和描述型模式。第一种是预测型模式，即可以根据数据项的值精确确定某种结果的模式。挖掘预测型模式所使用的数据也都是可以明确知道结果的。第二种是描述型模式，即对数据中存在的规则做一种描述，或者根据数据的相似性把数据分组。描述型模式不能直接用于预测。数据挖掘涉及多学科技术的集成，包括数据库技术、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、信息检索、图像于信息处理和空间数据分析

18、1。这里主要介绍关联规则分析和聚类分析。2.2.1关联规则分析在Jiawei Han的数据挖掘概念与技术中将关联规则的定义如下：设I=I1,I2,Im 是项的集合。设任务相关的数据D是数据库事务的集合，其中每个事物T是项的集合，使得TI。每一个事务有一个标识符，称作TID。设A是一个项集，事务T包含A当且仅当AT。关联规则是形如AB的蕴涵式，其中AI，BI，并且AB=。规则AB在事务D中成立，具有支持度s，其中s是D中事务包含AB（即集合A与B的并或A和B二者）的百分比。它是概率P(AB)。规则AB在事务D中具有置信度c，其中c是D中包含A的事务同时包含B的百分比这是条件概率P(BA)5。即

19、Support(AB)=P(AB)Confidence(AB)= P(BA)同时满足最小支持度阈值和最小置信度阈值的规则称为强关联规则。也说这样的关联规则是有趣的。一般来说关联规则的挖掘可以看成两步的过程：找出所有的频繁项集：根据定义，这些项集的每一个出现的频繁性至少与预定义的最小支持计数一样。由频繁项集产生的强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。关联规则的主要算法有Apriori算法Apriori算法是一种以概率为基础的具有影响的挖掘布尔型关联规则频繁项集的算法。其利用循序渐进的方式，找出数据库中项目的关系,以形成规则。其过程分为两步:一为连接(类矩阵运算)，二为剪枝

20、(去掉那些没必要的中间结果)。在此算法中常出现项集的概念。项集 (itemset)简单地说就是项的集合。包含K个项的集合为k项集。项集的出现频率是包含项集的事务数，称为项集的频率。如果项集满足最小支持度，则称它为频繁项集。频繁k项集的集合计作LK.步骤说明(1)制定最小支持度及最小置信度。(2)Apriori算法使用了候选项集的概念,首先产生出物项集合,称为候选项集,若候选项集的支持度大于或等于最小支持度,则该候选物项集合为频繁项集合(Large Itemset).(3)在Apriori算法的过程中,首先由数据库读入所有的数据,得出候选1项集合C1(Candidate 1-itemset)的支

21、持度,再找出频繁1项集合L1(Large 1-itemset),并利用这些频繁1项集合的结合,产生候选2项集合C2(Candidate 2-itemset).(4)再扫描数据库,得出候选2项集合C2的支持度以后,再找出频繁2项集合L2,并利用这些频繁2项集合L2的结合,产生候选3项集合C3。(5)重复扫描数据库、与最小支持度比较,产生更高层次的频繁项集合,再结合产生下一级候选项集,直到不再结合产生出新的候选项集为止。在此算法中要不断地重复两个步骤,连接步和剪枝步。其具体内容如下。连接步为找Lk,通过Lk-1与自己连接产生候选k项目集的集合。该候选项的集合记做Ck。为方便起见，Apriori假定

22、事务或项集中的项按字典次序排序。对于(k-1)项集li，意味着将项排序，使得li1 li2 lik-1。设l1和l2是Lk-1中的项集。记号lij表示li的第j项。执行连接Lk-1Lk-1,其中Lk-1的元素l1和l2是可以连接的,如果(l11 =l21)(l12 =l22)(l1k-2 =l2k-2)(l1k-1l2k-1)连接产生的结果项集是l11l12l1k- 1l2k- 1。剪枝步Ck的成员可以是也可以不是频繁的,但所有的频繁k项目集都包含在Ck中。扫描数据库,确定Ck中每个候选集计数(设置一个标志位Flag)。从而确定Lk（即根据定义，计算值不小于最小支持度计数的所有候选是频繁的，从

23、而属于Lk）。2.2.2聚类分析聚类分析将数据划分成有意义或有用的组。聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的(相关的)，而不同组中的对象是不同的(不相关的)。组内的相似性越大，组间差别越大，聚类就越好。聚类的方法通常有 K 均值算法，凝聚层次聚类，DBSCAN。K 均值是基于原型的，划分的聚类技术。它试图发现用户指定个数(K)的簇。基本 K 均值的算法为：1）选择 K 个点作为初始质心。2）repeat3）将每个点指派到最近的质心，形成 K 个簇。4）重新计算每个簇的质心。5）until 质心不发生变化。凝聚层次聚类：首先将每一

24、个点作为单点簇；然后重复的合并两个最近的簇，直到产生单个的，包含所有点的簇。具体算法如下：1）将每一个点分为一个簇。2）计算邻近度矩阵。3）repeat4）合并最接近的两个簇。5）更新邻近度矩阵，以反映新的簇与原来簇之间的邻近性。6）until 剩下需要个数的簇。步骤 2 中计算两个点的邻近度的方法很多，最常用的是计算欧几米德距离，平方欧几米德距离，夹角余弦，皮尔逊相关系数等。步骤 4 中合并最接近的两个簇可以有多种选择方案：组间连接，合并两类的结果使所有原本属于两类的两两点对之间的平均距离最小。组内连接，两类合并为一类后，类中所有点与点之间的平均距离最小。最短距离法，两类之间的最近点代表两类

25、的距离。最远距离法，两类之间的最远点代表两类的距离。图 2.3 组间距离基于图的定义在图 2.3 中，如果用 a, b 之间的距离代表组 A，B 之间的距离，则是最短距离法，如果用 c, d 之间的距离代表组 A，B 之间的距离，则是最远距离法。除了这 4 种常用方法以外还有重心法，中位数法，ward 法.DBSCAN 是一种产生划分聚类的基于密度的聚类算法，簇的个数由算法自动地确定。低密度区域中的点被视为噪音而忽略。因此 DBSCAN 不产生完全聚类。3.数据挖掘在社会网络分析中的应用在2.2中已经说过，数据挖掘任务可分为描述型(descriptive)任务和预测型(predictive)任

26、务两类：描述型数据挖掘任务试图刻画和归纳数据库中数据的总体特性；而预测型数据挖掘任务则试图根据以往数据中包含的经验，预测新的条件下发生的事件。社会网络分析的任务也不过这两种，一类从社会网络中发现社会的特性，另一类利用已经建好的网络模型，对某些情况进行预测。对于这两类任务，传统的数据挖掘算法已经有许多方法，关系数据挖掘的方法中既有从 ILP 中发展而来的算法，也有通过将原有算法改进后形成的算法。特别是关于连接挖掘(Link Mining)的算法能够很好地解决社会网络分析的任务。下面简单介绍几类适用于社会网络分析的数据挖掘算法：3.1基于相似度度量方法数据挖掘中的许多方法基于相似度度量，例如 k-

27、近邻算法和一些聚类算法，以及在一些排序任务之中给出一个评价准则。相似度的定义是这类算法中的核心步骤。相似度的定义是和问题相关的，同一个的数据集在不同的任务下最佳的相似度的定义很有可能是不同的。很多的时候很难选取一个适合的相似度度量，尤其当属性数目多，并且和目标任务的关系不明确的时候。但是，如果能够给出合适的相似度度量，这类算法具有很好的直观解释。相似性度量在联系预测中应用联系预测是判断两个行动者之间是否存在某种联系。在社会网络 G 中，相似度度量函数对于每个结点对给出一个存在联系的可能性 score(x, y)。在有些应用中，该函数可以看作是根据网络 G 的拓扑结构，对每个结点 x 和 y 计

28、算了他们之间的相似程度。而在有些社会网络分析任务中，这个权重并非是计算结点间的相似程度，而是为了特别的目标进行适当的修改。这些权重有的基于结点的临近结点(node neighborhoods)，有的基于所有路径的集成(Ensemble of all paths)。基于临近结点如果两个作者的共事者有很大的交集，他们将来进行合作的可能性将大于两个基本没有相同共事者的作者。两个有着交叠的社交圈的人也比其他人更有可能成为朋友。从这样的直觉观察出发，结点x和结点y在未来发生联系的可能性与他们的临近结点有关。对于结点x，用 (x)表示x在图G中的近邻。有一些方法通过度量 (x)和 (y)的相交程度作为结点

29、x和结点y之间出现联系的可能性。公共近邻（common neighbors）用近邻交集包含元素的数目作为衡量交叠程度的标准是最为直接的想法，即定义：Jaccard 系数(Jaccard coefficient) Jaccard 系数是借鉴了信息检索中常使用的相似性度量，Adamic/Adar 方法(Adamic/Adar Method) 以上两种方法都是简单的计数，将所有的近邻同等对待，而 Adamic/Adar 方法则考虑了近邻的性质，进行了加权偏好联结(Preferential attachment) 非常适用于网络的增长模型。它基于网络中从结点 x 增加一条边的概率正比于结点 x 当前的

30、近邻数目。即当前近邻多的结点，更可能产生新的连接。该公式也同时说明了在无尺度网络中已经获得连接的节点有更大的能力去获取更多的连接，正是这种结构产生了无尺度网络中的一些特殊的中心节点。基于集成所有路径在某些应用中，两个结点间最短路径距离往往不能准确地刻画两个结点的相似度。因而，有一系列的方法考虑通过集成两个结点间所有的路径的方式来定义它们的相似度。Katz 方法(Katz method) 给短路径更高的权重，然后将所有的路径加起来其中， 是G中结点x到结点y所有长度为l的路径。如果选取得很小，这个度量和公共近邻产生的结果比较相似，因为长度大的路径对于和的贡献非常小。命中时间（Hitting ti

31、me）在 G 上随机游动（Random walk）是指从图 G 中结点 x 开始，反复地移动到 x 的近邻中均一地随机选出的一个近邻。从结点 x 到结点 y 的命中时间就是指从结点x开始通过随机游动到结点y的期望移动次数。通勤时间（Commute time）由于命中时间通常不具有对称性，有时采用通勤时间作为距离度量，其定义为SimRank 是下面递归定义的不动点：两个结点相似的程度取决于他们联结到相似的近邻。数值上，定义 score ( x , x ) 1其中。这里只列出上面几种定义，其实根据不同的应用，还有很多不同的变种。并不存在某一种度量优于其它各种度量。必须结合不同的应用来进行适当的选取

32、，这个是基于度量方法的一个不足。3.2基于统计的方法现阶段统计关系学习方面的主要针对于在关系数据中的学习概率模型带来的挑战的研究。特别地，我们经常要进行研究究竟关系数据特征如何影响由精确学习所带来的统计推断，研究者们我们提出集中连接度（concentrated linkage），程度差异（degree disparity）,关系自相关（relational autocorrelation）三方面的特征，并且从这三方面来探讨他们如何在学习算法中产生的病态行为1。为了更加充分解释这一研究，关系数据特征如下：集中连接度（concentrated linkage）真正的关系数据集能够表示连接度在不同类

33、型的对象中的显著非一致性。在不同的情形下在关系数据集中有着不同的集中连接度，比如在电影中就会有许多电影连接许多的演员，如图3.1左。但是在上市公司中每个上市公司只可能连接到极少数的会计事务所，如3.1右。低连接度 高连接度图3.1集中连接度程度差异（degree disparity） 另一个关系数据集的特性便是程度差异。这一特性的产生往往是不同类的对象有交大的差异程度。图3.2直观的显示了程度差异。在不同的数据集中均发现了相似的程度差异。例如在不同行业中贸易公司的法人数量差异和大学网站中不同类型网页中的超连接数量的不同。无程度差异 高程度差异图3.2 程度差异关系自相关（relational

34、autocorrelation） 自相关是在不同关联对象中相同属性的价值相关性。例如，在时间t+1的属性值对于在时间t的该属性值就具有很高的相关性。类似，我们定义了关系自相关来描述在邻近表中的变量值的相关性。例如票房收入与导演关系紧密（关联系数为0.65），但与演员关系较小（关联系数为0.17）。图3.3直观的显示了关系相关性。低相关性 高相关性图3.3 关系相关性关系数据的这三个特征使得建立出优秀的统计模型需要考虑更多的方面。统计关系学习（Statistical Relational Learning）是将统计的方法和数据的关系表示结合起来的一类算法，它关注数据的联合概率分布。统计关系学习发

35、展很快，很多模型被提出，主要有 PRM(Probabilistic Relational Models), RMN(Relational Markov Networks）, SLR(Structural Logic Regression), RDM(Relational Dependency Networks), MLN(Markov Logic Networks)。这些统计关系学习的模型就是针对关系数据建立的，因而可以很好地描述社会网络，进而完成所需的分析任务。基于统计的算法往往因为需要优化的参数较多，计算开销相对较大。MLN(Markov Logic Networks)3Richardso

36、n 和 Domingos 希望通过 MLN 将概率和以及逻辑整合在同一个表示之中。因为概率模型能够很好处理不确定性，而逻辑表示能够简洁地表示知识。MLN 将马尔可夫网和一阶逻辑结合起来。马尔可夫网描述了一组随机变量的联合概率分布。通常，采用log-linear 模型表示为：其中，Z 是规范化项，是状态x的特征属性，（即定义域为的函数）。马尔可夫逻辑中的一个公式由一个一阶逻辑公式及相应的权重组成。一组马尔可夫逻辑公式所做成的集合就被称为马尔可夫逻辑网络，它定义了所有可能的变元取值组合的概率分布。下面给出它的形式化定义：一个马尔可夫逻辑网络 L 是一组二元组，其中是一个一阶逻辑公式，是一个实数值。

37、它同一个有限的常量集合通过下面的两条准则共同定义了一个马尔可夫网：1. L 中出现的所有谓词的每个可能的取值对应于中的一个二值结点。结点值为 1 表示其对应的谓词取真。2. L 中的每一个公式 的每一种取值对应应于中的一个特征属性。该特征属性取 1 表示其对应的公式值为真。该特征属性的权重就是 L中所对应的。有些社会网络模型可以看作是一个马尔可夫网络，而且可以简单地用类似的语句来表示，其中 x，y 表示行动者，R（x, y）表示它们之间的关系，A（x, v）表示 x 的一个属性，语句的权重表示了结点间的关系和该属性相似性之间的关联程度。例如，一个表达朋友之间倾向于有相同的吸烟习惯就可以简单地表

38、达为3.3基于频繁模式挖掘的方法频繁项集，即在数据集中出现频率超过每个预定的值的模式，能够在一定程度上反应数据集的特性。挖掘频繁项集是关联规则挖掘中的重要步骤，找到社会网络中的频繁子图也是社会网络分析中的重要任务。Apriori是频繁项集挖掘中一种非常有影响的算法。它得名于算法使用了关于频繁项集性质的先验知识。Apriori 采用了层次式搜索的迭代方法，利用频繁 k-项集来生成频繁(k+1)-项集。首先，从数据库中找到频繁 1-项集，记作 L1，以此类推见2.2.1介绍。AGM（Apriori-based Graph Mining）算法就是使用邻接矩阵作为图的表示，先生成候选项，然后剪除其中非

39、频繁子图的方法来有效地在图结构的数据中挖掘出频繁出现的子结构2。4.总结社会网络分析由于不满足数据的独立同分布假设，因而给数据挖掘的研究提出了新的挑战，并产生了一个新的方向：链接挖掘。近来在数据挖掘和机器学习领域针对关系数据模型的准确性研究取得了很大进步。但是这些研究对于其他学科应用并不广泛。致力于针对交叉学科的有效算法和数据表示依然有待发展。Han随着现代的通信技术的发展越来越多的社会网络数据的被整理到一起，这样既给该领域带了前所未有的机会，也同时对数据分析技术提出了巨大的挑战。数据挖掘作为一种帮助人们从大量数据中发现有用的知识的工具，经过不断地发展，已经能够处理像社会网络这种结构化的网络数

40、据，并在社会网络构建过程中发挥越来越重要的作用。同时，社会网络分析也可以有助于完成一些其它数据挖掘应用。加强在不同领域之间应用的交流，对数据挖掘和各个领域的发展都十分有利。参考文献1D.Jensen, J.Neville, Data mining in social networks, In the National Academy of Sciences Workshop on Dynamic Social Network Modeling and Analysis, 2003. 2Inokuchi A, Washio T., Motoda H., An apriori-based algo

41、rithm for mining frequent substructures from graph data. In Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, Lyon, France, 2000, 13-23.3 眭俊明, 数据挖掘在社会网络分析中的应用概述J, Assignment of Data Mining Course.4 张引, 社会网络分析中的数据挖掘综述J.5 JW.Han, M.Kamber, 数据挖掘概念与技术M,机械工业出版社 范明 孟小峰 译.6 林聚任， 社会网络分析：理论，方法与应用M,北京师范大学出版集团.7 艾伯特拉斯洛巴拉巴西，链接网络新科学M,湖南科学技术出版社.