《最大流算法发现web社团改进》由会员分享,可在线阅读,更多相关《最大流算法发现web社团改进(10页珍藏版)》请在金锄头文库上搜索。
1、 最大流算法发现 web 社团改进何拥军 龚发根摘要:提出了一种更好的分配边容量的方法,即不是给每条边分配一个相同的常量值,而是为不同的边依据信息的重要度来动态的分配不同的边值,较好的解决最大流算法发现 web 社团中的主题漂移问题。关键词:web 社团; 超链接; 最大流The maximal-flow discovers the web mass organization algorithm improvementAbstract: Proposed side one kind of better assignment the capacity method, namely is not
2、assigns a same constant value for each, but is comes the dynamic assignment different on the other hand value for different on the one hand based on the information importance, the good solution maximal-flow algorithm discovers in the web mass organization the subject drifting question.1 引言Web 社团是自
3、Internet 诞生以来就客观存在的一些 web 群体,一个 web 社团通常是这样的一群页面的集合: 它们在内容上一般都是围绕某一主题,具有一定的相关性,或者具有某一相似特性 1。一般的一个 web 社团只是整个互联网 web 图中的一个非常小的子图。如何去发现互联网上这些潜在的 web 社团也是近几年来才引起众多研究者关注的研究领域。在任一个图中边和节点都是很重要的元素,同样在 web 图当中,代表超链接的边也往往包含有一些非常重要的信息,如果能利用图的理论知识,通过 web 链接图来研究 web 社团将会有更好的效果 ,所以很多的研究工作关注通过 web 的超链接结构关系来挖掘 web
4、 社团资源 2。众多的研究者提出了各种各样的基于链接结构分析发现 web 社团的方法。Gibson 和Kleinberg 等人 3,4提出了基于链接分析搜索算法 HITS,Kumar 等人 5从二分有向图的角度对互联网上的社团给出了一种明确的定义描述,把 web 社团看作一些二分有向图的核。Yasuhito6 等人提出了通过交互站点的方法。文献 78最先提出通过最大流算法来发现 web社团,文献 910从多方面对最大流算法进行了实验及评价。2 相关研究工作2.1 最大流算法与最小割切网络中的最大流算法具有广泛的应用,在这首先介绍一下在图论中对 S-T 的最大流问题的简化定义:给定一个网络流图
5、,边的容量为 ,两个节点 ,然后找出),(EVG),(vucVts,流经源节点 到沉积节点 最大流量。直观理解,假设边为管道,节点为开关,那么最大流问s t题就是如何让源节点 S 到沉积节点 T 能流过的流量最大。Ford 和 Fulkerson11 已经证明了 “最大流- 最小割切”理论,即网络流中最大流等于把到沉积节点 分离的最小割切容量,等式如下:st ),(SminCaxw(1) 其中 w为网络流, S)(,为给切,假设 VT,其中 S为一个子集, VS,给定TtS,s,那么边集 v,u|Ev就叫做 S-T 的一个割切,包含在割切中的边叫做割边,最小割切即满足割边的容量和为所有割边中最
6、小的一个割切。2.2 web 社团这里引用文献910里定义 web 社团为: 设 为某些节点的集合,一个 web 社团是其中V的一个子集 ,满足条件:对任何节点 , 与属于 当中节点之间连接的边VCCv 数大于它和 以外节点之间连接的边数,即 ,如图 1 所示 -图 1web 社团 3 最大流算法的特点及存在的问题最大流算法应用到 web 链接结构中抽取社团的思想最先是由 G.Flake 等人提出的,在文献910里面 G.Flake 等人通过实验证明了最大流算法对于解决 HITS 算法在社团抽取当中存在的主题漂移问题有较好的效果。下面重点探讨该算法同时所存在的一些问题并提出自己的解决方案。3.
7、1 社团体积与边的关系 G.Flake 等人在文献910里对边的容量与社团体积之间的关系进行了深入的研究 ,如下图所示。图的横坐标表示边容量的增加,纵坐标表示随之所获得的社团体积。可以看出,随着边的容量的增加,社团的体积也显著加大,但这种变化是离散的,即分阶段上升,而且不同阶段的跳跃长度并不相等。从下图来看,当边的容量从 9 到 10,14 到 15,20 到 21 这几个阶段每一次跳跃后,社团的体积都急剧变大,社团变化相应的值为 9 到 36,36 到 50,50 到 630。明显看出边的容量在 20 到 21 这个跳跃点社团的体积增加最迅速。图 2 边的容量与社团体积的关系3.2 G.Fl
8、ake 算法存在的问题及改进算法的提出如前面所说,边的容量对社团的体积会产生很大的影响,不仅仅在数量上,而且还会影响到社团成员的质量。G.Flake 最先提出把最大流算法用来抽取 web 社团,在文献910里采用分配给各边一个相同的容量值,虽然可以较好的解 HITS 算法存在的主题漂移问题,但对社团的质量和数量也会带来许多不利的影响,而且随着 web 图节点的增加,噪音页面相应也会增加,仅仅通过增加边的容量并不能很好的解决这些问题,在很多情况下边的容量提升得越大,主题漂移的问题就会越易显现出来。其主要的原因就是没有考虑到每条边的不同重要程度,把所有的边一视同仁,体现不出不同边的价值度对形成社团
9、的影响。为了更好的解决这些问题,本文提出了一种更好的分配边的容量的方法,即不是给每条边分配一个相同的常量值,而是依据信息的重要度为不同的边分配不同的边值。4 改进的最大流算法正如上节所说,一个理想的方法就是;重要的边分配给一个更大的容量,不重要的边分配给一个较小容量。那么关键的问题是如何定义一个重要边和不重要边,以及如何给不同重要程度的边分配不同边的容量,这就等于给边定义一个等级或者分值一样,所以必须把它对页面的价值分布转化到边的价值分布上来。在 web 超链接分析里, PageRank 算法和 HITS 算法是用来计算页面分值和权威性的最典型的两个算法1 ,HITS 算法是个不断反复迭代的过
10、程,迭代到一定次数就会很快收敛。因为HITS 算法最终的计算结果是得到每个页面的权威和 HUB 分值,在 web 图中,边所连接的两个节点所对应的 web 页面都有它们的权威和 HUB 分值,自然可以认为重要的边所连接的应该是分值比较大的节点,依据这个思想来进行边容量分配,这就是本文算法的主要思想。4.1 边容量分配方法首先重新定义一个可变 HUB 分值和 Authority 分值变量如下:, (2) 2rhv,iiiv,ra在 HITS 算法里得到的 HUB 和权威分值都是在 这个范围,不适合作为边1ah0iiv,的容量,因为最大流算法里边容量必须是一个正整数,所以通过设定一个常量系数 来得
11、到r分值的另外一种形式,这里 的取值一般是基于整个邻接图的平均连接数,在本文后面的实验r里设置 =100 。用 来表示任一节点到子节点的距离,例如假设 经过两条不重复的边可r dp v以到达子节点,那么 =2,接下来我们定义边的容量 为下面两种形式:Eu)c(,(3)dpv,2ahu)c(v,ii,(4)1)(,iiu,以上公式所得到的边的容量是一个动态的变量,不同边的容量由它所连接的节点和所代表的页面分值和来决定,应用该方法的效果我们在后面再讨论。下面我们给出基于以上边容量分配方法的最大流算法抽取社团的详细步骤。4.2 改进的最大流算法下面给出基于 HITS 算法边容量分配的最大流发现社团的
12、详细步骤:1. Input: ,.l21ssvS 子节点集合 2. Output : m21ccC3. E)G(V,;( 围绕每一个子节点 Svis,以深度 2 抽取一个 web 子图)4. 计算 HUB 和权威分值向量 H和 A5. 按照前面的介绍的方法构建邻接图 E)G(V,6. 应用前面公式(2)设置边的容量 vcu, ,, 如果 Eu)(v,,那么添加 u)(v, 到 E,并设置边的容量 )(c)。7. 执行 t-s的最大流算法。8. 获得一个节点集合 ,.m21ccvC,其中每个节点要求和子节点连通 ,并对每一个节点都进行分值计算(在后面会介绍分值计算方法)9. 根据计算的分值排序,
13、把前面一些分值最高的非子节点添加到子节点集合 S当中。反复执行步骤 1 到 8 直到 中的节点趋于一个稳定的社团为止。10. 按分值大小的顺序输出 C中社团的节点 从实验来看, C 中的节点通常很快就会趋于稳定,因为虽然子节点集合会不断扩展,但整个邻接图却一般不会加大,即使扩展也不会扩展太大。本文采取了和文献78 里不同方法给 中的成员节点计算分值。设 )(Invic表示从其它社团节点链接到它的入链接数, )(Outvic表示它的出链接数。 )(icS用来表示节点 ic的分值,那么我们计算分值的公式如下:)()()( thInavSicici vc (4)在文献7中计算分值仅仅以每个节点的链接
14、数为依据,因为有些排在前面分值较高的节点会有相同的链接数。但它们的权威和 HUB 分值也许并不相同,所以仅仅以链接数来选择最高分值的节点加入到子节点当中去是不太好的。本文把每个节点的权威分值和 HUB 分值也考虑进去了,所以避免了这种情况。5 试验及其评价5.1 试验数据的收集与清理 数据集 : 由于 web 挖掘需要的数据集往往非常庞大,web 社团的挖掘需要更大数据资源才能体现算法的性能和优越性,为了测试算法的效果和验证它的有效性,对不同的查询主题和不同数据集分别进行了实验,数据量接近 5G。种子节点集:一般每个社团都有一个明确的主题,所以在抽取社团前需要给定一个比较接近主题的 URL 页
15、面作为子节点,为了更有代表性的说明问题,本文分别选择了 20 个互不相同的主题页面作为子节点,前十个选择了以英文为关键字的查询主题,后十个选择了中文为关键字的查询主题,每一个主题都具有明确的意义。表 1 中列出了各个子节点及其详细的说明数据清理 :数据清理是为了更好的进行数据挖掘以获得高质量的挖掘结果而做的准备工作。算法在实验之前对获得的粗燥数据集进行了必要的数据清理,数据清理后我们就可以得到一个比较合理的邻接 web 图。在数据清理过程中主要做了一下几个工:1 首先排除了那些入链接或者出链接数超过了 500 以上的 web 页面,因为这样的一些页面往往是非常出名的一些站点页面,像 Yahoo
16、,Google,等,这些站点页面根本就不需要用户使用什么挖掘策略去获得的。2 去除那些 RUL 里包含有关键词 %,?,bbs,cgi-bin ,diary,news 等的页面,因为这样的一些页面往往和用户要找的主题无关。还会产生更多的主题漂移问题。3 去除镜像页面,所谓的镜像页面是指与主网站的内容相同的其它位置的网站页面就叫做镜像网站页面 ,太多的镜像页面只会重复同一个页面内容,扰乱用户的视野,所以要尽可能事先去除。5.2 实验及性能评价为了更好的说明改进方法的效果,本文对两种方法的实验结果进行了多方面的比较和分析。在下面的数据分析当中分别用 C1 和 C2 表示两种最大流算法所获得的社团,C1 表示本文改进算法的结果,C2 是 Flake 等人方法的