《最大流算法发现web社团改进》由会员分享，可在线阅读，更多相关《最大流算法发现web社团改进（11页珍藏版）》请在金锄头文库上搜索。
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 ass
2、igns 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社团是自Inter
3、net诞生以来就客观存在的一些web群体，一个web社团通常是这样的一群页面的集合： 它们在内容上一般都是围绕某一主题，具有一定的相关性，或者具有某一相似特性1。一般的一个web社团只是整个互联网web图中的一个非常小的子图。如何去发现互联网上这些潜在的web社团也是近几年来才引起众多研究者关注的研究领域。在任一个图中边和节点都是很重要的元素，同样在web图当中，代表超链接的边也往往包含有一些非常重要的信息，如果能利用图的理论知识，通过web链接图来研究web社团将会有更好的效果 ，所以很多的研究工作关注通过web的超链接结构关系来挖掘web 社团资源2。众多的研究者提出了各种各样的基于链接结
4、构分析发现web 社团的方法。Gibson和Kleinberg等人3,4提出了基于链接分析搜索算法HITS，Kumar等人5从二分有向图的角度对互联网上的社团给出了一种明确的定义描述，把web社团看作一些二分有向图的核。Yasuhito6 等人提出了通过交互站点的方法。文献78最先提出通过最大流算法来发现web社团，文献910从多方面对最大流算法进行了实验及评价。2 相关研究工作2.1 最大流算法与最小割切网络中的最大流算法具有广泛的应用，在这首先介绍一下在图论中对S-T的最大流问题的简化定义：给定一个网络流图，边的容量为，两个节点，然后找出流经源节点到沉积节点最大流量。直观理解，假设边为管道
5、，节点为开关，那么最大流问题就是如何让源节点S 到沉积节点T能流过的流量最大。Ford 和Fulkerson11 已经证明了“最大流-最小割切”理论，即网络流中最大流等于把到沉积节点分离的最小割切容量，等式如下： （1） 其中为网络流，为给切，假设 ，其中 为一个子集，给定，那么边集就叫做S-T的一个割切，包含在割切中的边叫做割边，最小割切即满足割边的容量和为所有割边中最小的一个割切。2.2 web社团这里引用文献910里定义web社团为： 设 为某些节点的集合，一个web社团是其中的一个子集 ，满足条件：对任何节点 ，与属于当中节点之间连接的边数大于它和以外节点之间连接的边数，即，如图1 所
6、示 图1web社团 3 最大流算法的特点及存在的问题最大流算法应用到web 链接结构中抽取社团的思想最先是由G.Flake等人提出的，在文献910里面G.Flake等人通过实验证明了最大流算法对于解决HITS算法在社团抽取当中存在的主题漂移问题有较好的效果。下面重点探讨该算法同时所存在的一些问题并提出自己的解决方案。3.1 社团体积与边的关系 G.Flake等人在文献910里对边的容量与社团体积之间的关系进行了深入的研究 ，如下图所示。图的横坐标表示边容量的增加，纵坐标表示随之所获得的社团体积。可以看出，随着边的容量的增加，社团的体积也显著加大，但这种变化是离散的，即分阶段上升，而且不同阶段的
7、跳跃长度并不相等。从下图来看，当边的容量从9到10，14到15，20到21这几个阶段每一次跳跃后，社团的体积都急剧变大，社团变化相应的值为9到36，36到50，50 到630。明显看出边的容量在20到21这个跳跃点社团的体积增加最迅速。 图2边的容量与社团体积的关系3.2 G.Flake 算法存在的问题及改进算法的提出如前面所说，边的容量对社团的体积会产生很大的影响，不仅仅在数量上，而且还会影响到社团成员的质量。G.Flake最先提出把最大流算法用来抽取web社团，在文献910里采用分配给各边一个相同的容量值，虽然可以较好的解HITS算法存在的主题漂移问题，但对社团的质量和数量也会带来许多不利
8、的影响，而且随着web图节点的增加，噪音页面相应也会增加，仅仅通过增加边的容量并不能很好的解决这些问题，在很多情况下边的容量提升得越大，主题漂移的问题就会越易显现出来。其主要的原因就是没有考虑到每条边的不同重要程度，把所有的边一视同仁，体现不出不同边的价值度对形成社团的影响。为了更好的解决这些问题，本文提出了一种更好的分配边的容量的方法，即不是给每条边分配一个相同的常量值，而是依据信息的重要度为不同的边分配不同的边值。4 改进的最大流算法正如上节所说，一个理想的方法就是;重要的边分配给一个更大的容量，不重要的边分配给一个较小容量。那么关键的问题是如何定义一个重要边和不重要边，以及如何给不同重要
9、程度的边分配不同边的容量，这就等于给边定义一个等级或者分值一样，所以必须把它对页面的价值分布转化到边的价值分布上来。在web 超链接分析里， PageRank算法和HITS算法是用来计算页面分值和权威性的最典型的两个算法1，HITS算法是个不断反复迭代的过程，迭代到一定次数就会很快收敛。因为HITS算法最终的计算结果是得到每个页面的权威和HUB 分值，在web图中，边所连接的两个节点所对应的web页面都有它们的权威和HUB分值，自然可以认为重要的边所连接的应该是分值比较大的节点，依据这个思想来进行边容量分配，这就是本文算法的主要思想。4.1边容量分配方法首先重新定义一个可变HUB 分值和Aut
10、hority分值变量如下： ， （2） 在HITS算法里得到的HUB和权威分值都是在这个范围，不适合作为边的容量，因为最大流算法里边容量必须是一个正整数，所以通过设定一个常量系数 来得到分值的另外一种形式，这里的取值一般是基于整个邻接图的平均连接数，在本文后面的实验里设置=100 。用来表示任一节点到子节点的距离，例如假设经过两条不重复的边可以到达子节点，那么=2，接下来我们定义边的容量为下面两种形式： （3） （4）以上公式所得到的边的容量是一个动态的变量，不同边的容量由它所连接的节点和所代表的页面分值和来决定，应用该方法的效果我们在后面再讨论。下面我们给出基于以上边容量分配方法的最大流算法
11、抽取社团的详细步骤。4.2 改进的最大流算法下面给出基于HITS算法边容量分配的最大流发现社团的详细步骤：1. Input: 子节点集合 2. Output : 3. ;( 围绕每一个子节点 ，以深度2抽取一个web子图)4. 计算HUB和权威分值向量和5. 按照前面的介绍的方法构建邻接图6. 应用前面公式（2）设置边的容量 ， 如果，那么添加 到，并设置边的容量 。7. 执行的最大流算法。8. 获得一个节点集合，其中每个节点要求和子节点连通 ，并对每一个节点都进行分值计算（在后面会介绍分值计算方法）9. 根据计算的分值排序，把前面一些分值最高的非子节点添加到子节点集合当中。反复执行步骤1到8
12、 直到中的节点趋于一个稳定的社团为止。10. 按分值大小的顺序输出 中社团的节点 从实验来看， 中的节点通常很快就会趋于稳定，因为虽然子节点集合会不断扩展，但整个邻接图却一般不会加大，即使扩展也不会扩展太大。本文采取了和文献78 里不同方法给中的成员节点计算分值。设表示从其它社团节点链接到它的入链接数，表示它的出链接数。用来表示节点的分值，那么我们计算分值的公式如下： （4）在文献7中计算分值仅仅以每个节点的链接数为依据，因为有些排在前面分值较高的节点会有相同的链接数。但它们的权威和HUB 分值也许并不相同，所以仅仅以链接数来选择最高分值的节点加入到子节点当中去是不太好的。本文把每个节点的权威
13、分值和HUB分值也考虑进去了，所以避免了这种情况。5 试验及其评价5.1 试验数据的收集与清理 数据集 ： 由于web 挖掘需要的数据集往往非常庞大，web 社团的挖掘需要更大数据资源才能体现算法的性能和优越性，为了测试算法的效果和验证它的有效性，对不同的查询主题和不同数据集分别进行了实验，数据量接近5G。种子节点集：一般每个社团都有一个明确的主题，所以在抽取社团前需要给定一个比较接近主题的URL页面作为子节点，为了更有代表性的说明问题，本文分别选择了20个互不相同的主题页面作为子节点，前十个选择了以英文为关键字的查询主题，后十个选择了中文为关键字的查询主题，每一个主题都具有明确的意义。表1中
14、列出了各个子节点及其详细的说明数据清理 ：数据清理是为了更好的进行数据挖掘以获得高质量的挖掘结果而做的准备工作。算法在实验之前对获得的粗燥数据集进行了必要的数据清理，数据清理后我们就可以得到一个比较合理的邻接web图。在数据清理过程中主要做了一下几个工：1 首先排除了那些入链接或者出链接数超过了500以上的web页面，因为这样的一些页面往往是非常出名的一些站点页面，像Yahoo,Google,等，这些站点页面根本就不需要用户使用什么挖掘策略去获得的。2 去除那些RUL里包含有关键词%，？，bbs，cgi-bin ,diary,news等的页面，因为这样的一些页面往往和用户要找的主题无关。还会产
15、生更多的主题漂移问题。3 去除镜像页面，所谓的镜像页面是指与主网站的内容相同的其它位置的网站页面就叫做镜像网站页面 ，太多的镜像页面只会重复同一个页面内容，扰乱用户的视野，所以要尽可能事先去除。5.2 实验及性能评价为了更好的说明改进方法的效果，本文对两种方法的实验结果进行了多方面的比较和分析。在下面的数据分析当中分别用C1 和C2表示两种最大流算法所获得的社团，C1表示本文改进算法的结果，C2是Flake等人方法的结果 。表1显示了针对于每个子节点所获得的web社团的大致情况，包括子节点，主题，web邻接图的节点数以及两种方法所获得的社团成员数。其中|V|, |C1| ,|C2|分别表示web邻接图的节点数，改进算法获得的社团成员数及原算法获得社团成员数。C2一竖排的第11，12，17 个主题上面都标有一个“*”表示在这种情况下所获得的社团体积都是不合理的失败情况。如表所示，改进算法所获得的社团C1在总体上要明显好于原来的算法结果，原来的算法虽然在某些情况下确实获得了比较好的结果，但在另外一些情况下却产生了非常坏的结果，比如在主题3，13，15，17这几个情况下
