Web中的社会网络分析技术，本文主要内容关键词为：社会论文,技术论文,网络论文,Web论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：TP393，G250文献标识码：A文章编号：1007－7634（2009）12－1871－05
1 前言
社会网络的定义是Wellman于1988年提出的“社会网络是由某些特定群体（人、企业和组织）间的社会关系构成的相对稳定的关系网”[1]，社会网络中的节点一般是人物、机构或地点等，而其中的边是某种特定的关系，例如朋友关系或链接关系等。随着Web规模的不断扩大和信息形式的多样化，因为Web也是一个社会性的网络，Web上的信息为社会研究学者提供了一个巨大的数据源，这就为基于Web的社会网络分析研究的发展提供了广阔的发展空间。近年来，Web社会网络分析技术的研究受到了越来越广泛的重视。与之相关的研究工作是在90年代中后期开始的利用搜索引擎的社会网络的构建与分析[2]和Web社区的社会网络分析等[3－4]。
对Web的社会网络分析技术按研究对象的不同分为以下两类：一类是以网页为研究对象的社会网络分析，另一大类是以网页内容中的实体为研究对象的社会网络分析。
2 以网页为研究对象
以网页为研究对象进行社会网络分析是以Web中的页面为节点，以页面之间的链接关系作为边来构建社会网络，通过对该网络的结构分析来确定页面重要程度。从具体的实现细节来分，大概可以分为三种不同的实现途径：基于链接分析的技术、基于二分有向图的技术和基于最大流的技术。前两种属于依据相互连接的hub和authority发现社区的算法，最后一种属于依据成员链接密度来发现社区的算法。
2.1 基于链接分析的技术
在链接分析中最重要的算法是Kleinberg的HITS算法[5]，他提出了“hub”和“authority”的概念，一个authority页面是指对一个主题信息非常有价值的页面；一个hub页面是指该页中的超级链接列表包含大量指向主题信息非常有价值的页面的链接。纯HITS算法是由Gibson等人[6]在HITS基础上进行的，该算法提出了通过连接拓扑图的分析来超链社区的概念，通过使用一个简单、清晰地数学概念定义这些社区的结构，将社区定义为一个由“hub”页面链接起来的“authority”页面构成的核。这些社区通过这种链接模式形成了一种层次化的主题概念。和HITS相同，Gibson等人的算法也是从根集合的选择开始，但是对采用了不同搜索引擎、不同语言、不同大小的根集合做了比较，对于不同主题产生根集合应用HITS算法，最后，利用web页面相邻矩阵的主特征向量表示该主题下的主要社区的页面集合，而非主特征向量可表示该主题下非主要的社区。由于该算法在运行HITS时，篡改扩展边的权重，从而改变主体扩展图的最终路径，导致主题的交叉错合（contamination）或者漂移（drift）。此外，类似的工作还有M.R.Henzinger[7]在HITS算法的基础上不仅实现了社区的发现算法，而且还考虑了社区与社区之间关系的发现算法。
在精度检索和网络评估中，对HITS算法进行的改进，HITS的幂迭代公式中的邻接矩阵的边不再是0或1，而是一定的权值。权值由链接附近的文档内容来决定，这样的文档称之为锚文档，针对具体主题词的查询，认为锚文本（anchor text）附近包含主题词文字的那些超链具有比其他边更高的权重。自动资源编辑（Automatic Resource Compilation，ARC）[8]和Clever系统[9]采用这种方法计算边的权重，查询结果精度可以获得显著提高。
基于HITS的算法的依据是将页面分为中枢页面和权威页面，根据web图的邻接矩阵的主特征向量和非主特征向量得到主要社区和一些次要的社区，实际上是根据中枢页面和权威页面的相对聚集程度来发现社区的特征。虽然特征向量对于纯文本下搜索和聚类条件下搜索提供了很好的解决方案，但是在Web的环境中，计算代价显得太大，同时，由于HITS构造的子图会包含一些和主题无关的页面，主题可能发生偏移。
2.2 基于二分有向图的技术
基于二分有向图的技术可以克服上述现象，由于HITS算法是一个“迭代－收敛”的过程，在获取了一个与查询主题相关的返回页面根集合S后，根据S中的页面的链接关系再向集合S中扩充与S中页面相链接的页面，将S扩展成一个更大的基础集合T。而一个二分有向图将集合节点分为两个不相交的集合，在同一个集合中没有两个节点是相邻的。一个完全二分有向图中在两个集合中的每一对节点是相邻的，若X和Y表示两个集合，X和Y中的节点分别为m和n，则完全二分有向图表示为K（m，n），完全二分有向图以图结构反映了HITS的本质，也就是说，若有向边是从X到Y链接，则集合中的X和Y分别为HITS中的hub和authority，如图1所示。
图1 K（3，4）完全二分有向图[10]
基于二分有向图的方法是将社区抽象为一个二分有向图，和HITS不同，其数据来源不是依据某个主题的，而采用的是一般的爬取结果。由于二分有向图是针对整个Web爬取结果进行的，因此发现的社区较为完整。Kumaret[11－12]提出的拖网（trawling）算法就属于这一类型。拖网通过一般的爬行策略扫描数据集合发现所有潜在的社区，通过重复的剪枝得到所有的核，最后采用关联规则挖掘算法聚类得到核的集合，每个核就是一个社区。
HITS和二分有向图算法均在计算前要准备数据源。HITS得到邻接矩阵，二分有向图得到图的节点的集合，然后对静态的数据源展开计算，所以计算时间主要由数据量、迭代次数、收敛速度和CPU性能等因素影响。
2.3 基于最大流的技术
基于最大流的技术则根据图形理论提出了发现社区的方法。该技术是利用爬行器检索到的页面集作为数据源，通过爬行过程得到Web图形。从一个Web页面的种子集合开始爬取，找到与种子集合存在链接的所有页面，设置一个虚拟的源节点和宿节点，找到最小割集，最后产生社区。Flake等人[13]根据图形理论，将社区识别问题看作解决网络的最大流量／最小割集问题，并将社区定义为在Web图中具有这样一些特性的页面的集合：社区内的页面之间的链接（在两个方向）的密度要大于社区之间页面链接的密度，图2是在该定义下的一个简单的Web社区例子。介绍了一种基于最大流的web采集器，通过一个基于主题的采集器沿着链接路径采集高度相关的页面，最后使采集范围能够逼近一个社区，在某种意义上这种社区发现技术是高度内聚的，社区成员比非社区成员更紧密耦合。
最大流算法的特点是基于集中爬行器得到Web图的方法，计算时间主要受网络检索页面的时间影响。所以流量算法是在线算法，数据源是动态的。
图2一个的Web社区（节点在左边）[14]
总的来说，上述这些技术基本上都是以Web链接分析为基础的，都采用了Web的结构对社区的影响来发现社区的特征。HITS算法和最大流的算法的特点是先确定某个主题，然后利用搜索引擎的返回结果作为种子集合，在种子集合的基础上构造数据集，优点是数据集较小，缺点是由于事前确定主题，所以只能发现一些明确定义的社区。二分有向图的技术是以网络爬行器爬取的页面为数据集，优点是可以发现大量潜在的社区，缺点是由于确定的数据量很大，许多链接分析方法无法直接应用。目前以网页为研究对象的分析技术仅仅是实现将页面集合分割为社区，没有考虑所得到的社会网络之间如何建立有效的联系和有价值的结构。
3 以实体为研究对象
随着互联网的发展，用户使用Web的行为从原有的单纯使用Web数据信息源转变成为和Web进行交互，网络中出现了各种自治的Web社区，由于Web社区中包含了大量的实体信息以及实体之间的相互关系，因此对Web的社会网络研究也由对Web结构的分析随之转向以Web中的内容的实体信息为研究对象。
3.1 以系统用户为实体的研究
这类研究包括论坛、BBS、电子期刊数据库等系统，系统中的实体是使用系统的用户，用户之间通过主动或被动地交流建立联系。由于像论坛这样的系统其社会网络的构建是自然的，不需要特意发现网络节点和节点关系，相对困难的是如何发现这样的系统并有效地收集数据。例如Newman在对SCI中四个数据库的研究[14]，其中的实体是论文作者，实体间的关系则定义为作者之间的共同作者（co- author）或者是作者之间的引用关系等。Adamic等人[15]以Stanford大学的Nexus论坛系统为研究平台，将论坛中的用户看做是社会网络中的节点，由于用户注册时填写了详细的个人信息，通过加入好友方式构建起了社会网络，好友关系组成了节点的边，研究的行为包括e- mail、聊天、跟帖、买卖商品、用户搜索等。由于系统的用户自动构成了社会网络，对其的研究工作主要集中在网络计量分析和网络内部结构的分析。
3.1.1 网络计量分析
网络计量学（webmetrics）是1997年由T.C.Almind和P.Ingwersen提出的[16]，它是参照和借鉴文献计量学的理论和方法，用于对网络环境中的信息资源进行定量研究。网络计量学研究的对象包括网络信息直接计量、网上文献信息及相关特征信息计量、网络结构单元的信息计量。目前网络计量分析提出了一些定量分析的指标，如中心度、弱相关结构、子群体结构、连通度等，这些分析指标大大提高了社会评估准确度。
例如Newman在对SCI中四个数据库（生物医药、高能物理、计算机科学、数学）进行了实证研究，通过分析SCI数据库作者论文数（点的度数）、论文作者数（同色边的最大完全图）、最大连通分支的大小、最大完全图的大小等特征参数，并且进一步以各学科的论文发表的特点来解释了这些不同。在对合著关系网络分析中，利用引文和著者数据库，顶点是论文的作者，用一条边表示两个作者的合著关系，网络距离为1，合著者的合著者距离递加1，生成合著网络。研究的合著网络中科学家之间的距离与网络中的总人数的对数成比例。通过著者社会网络的分析，发现作者发表文章的数量和文献合著网络的最短距离具有负相关性。此外，该分析同时也对学者学术声誉评价具有重要作用，Newman的研究表明，介数高的作者和平均距离低（平均距离是一个顶点到网络中所有其他顶点的最短路径的算术平均值，而介数是某一顶点出发的最短路径的条数，二者用于评价网络节点的核心性）的作者是网络中信息的集疏地，并能控制信息流向，是衡量学者学术影响力的比较恰当的指标。
目前这类研究的大部分工作仍然停留在社会网络参数的测量与比较，通过测量与比较分析社会网络行为，而对网络的行为进行预测的工作则相当少。
3.1.2 网络内部结构的分析
通过深入研究分析社会网络的内部结构不仅可以分析网络行为，而且还可以网络未来的行为进行预测，和使用定量分析的指标相比，根据社会网络的结构、内容，发现网络中的局部结构和其节点属性与结构的关系可以得到更深入的分析结果。例如Adamic根据用户注册信息中的丰富属性和网络结构之间的相关性，分析出用户的“个性”属性与“学院”构成的子团之间的密切相关，英语专业的学生在业余时间喜欢读书，共同兴趣爱好的人容易成为好朋友等，得出了性格与个人偏好、专业与兴趣、性别与爱好之间的关系。而L.Backstrom等人[17]则对LiveJournal和DBLP两个网络社区引入了时间因素研究了网络结构随时间的演化，根据创新扩散（diffusion of innovation）理论模型得出在社区的某个兴趣区域内某个节点k的行为会随着相邻节点p变化，同时也利用决策树来预测网络结构、节点行为的变化等，利用决策树预测LiveJournal增长的分析如图3所示。
3.2 以网页内容为实体的研究
以系统用户为实体的研究中系统的社会网络构建是自然的，而以网页内容为实体的研究没有自然形成的社会网络，因此其研究内容主要集中在社会网络的构建上，研究内容是以网页内容中的实体为核心，发现文本中的命名实体，并且定义、发现实体之间的关系，然后以命名实体为节点，关系作为边构建社会网络。
图3 二层决策树预测LiveJournal社区增长
例如McCallum等人[18]开发了一个首尾相连的系统抽取社会网络中的用户，采用文本中的共现来发现用户实体和测量实体间的关系，系统最初的版本抽取的范围为e- mail信息，个人主页等，新版本抽取范围扩大到整个Web。类似的工作还有POLYPHONET系统[19]采用基于规则的命名实体发现方法，从Web中抽取人物关系，利用Google来获取相关Web文档作为语料库，通过人工确定一组关系描述模式用来发现人物实体之间的关系并对这些关系按预定义的方式进行分类。Y.Jin等人[20]也使用了实体在文本中的共现来定义抽取社会网络中的公司和演员实体。在这类工作中实体与实体关系的发现、分类、标注量是社会网络构建发现的重要组成部分。
与以网页为研究对象分析技术相比，以实体为研究对象的分析技术是基于语义的层次来发现网络的节点和边，容易发现潜在的社会网络，分析出实体之间有效的联系，发现有价值的内部结构。但是类似科技论文数据库或各类论坛，其数据集是封闭的，而以网页内容中的实体为研究核心进行实体发现以及实体关系发现，其网络节点的发现也主要集中在封闭数据集合上提取，缺少基于开放数据集的研究方法，而社会网络中节点的位置以及节点间的连接关系是随时间的变化而变化的。
4 结语
Web中的社会网络已经成为数据挖掘领域一个新的发展方向。Web发展非常迅速，由于社会网络是持续变化的，是一个动态的网络，目前的研究工作主要以封闭的数据集作为研究对象，缺乏在动态开放数据集上构建网络分析技术和方法，因此，探讨有效的Web社会网络动态分析算法和理解实体关系是未来的研究方向，社会网络的分析除了考虑网络中的节点位置和节点之间的关系之外，还应将时间因素加入到研究模型中来，挖掘社会网络所不能够发现的节点间的关系。
收稿日期：2009－04－01
标签：有向图论文; 社会网络论文; 实体关系图论文; 网络节点论文; 用户研究论文; 社会结构论文; web技术论文; 网络结构论文; 用户分析论文; hits算法论文; 算法论文;