最大流算法发现web社团改进

最大流算法发现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 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社团是自Internet诞生以来就客观存在的一些web群体，一个web社团通常是这样的一群页面的集合： 它们在内容上一般都是围绕某一主题，具有一定的相关性，或者具有某一相似特性1。一般的一个web社团只是整个互联网web图中的一个非常小的子图。如何去发现互联网上这些潜在的web社团也是近几年来才引起众多研究者关注的研究领域。在任一个图中边和节点都是很重要的元素，同样在web图当中，代表超链接的边也往往包含有一些非常重要的信息，如果能利用图的理论知识，通过web链接图来研究web社团将会有更好的效果 ，所以很多的研究工作关注通过web的超链接结构关系来挖掘web 社团资源2。众多的研究者提出了各种各样的基于链接结构分析发现web 社团的方法。Gibson和Kleinberg等人3,4提出了基于链接分析搜索算法HITS，Kumar等人5从二分有向图的角度对互联网上的社团给出了一种明确的定义描述，把web社团看作一些二分有向图的核。Yasuhito6 等人提出了通过交互站点的方法。文献78最先提出通过最大流算法来发现web社团，文献910从多方面对最大流算法进行了实验及评价。2 相关研究工作2.1 最大流算法与最小割切网络中的最大流算法具有广泛的应用，在这首先介绍一下在图论中对S-T的最大流问题的简化定义：给定一个网络流图，边的容量为，两个节点，然后找出流经源节点到沉积节点最大流量。直观理解，假设边为管道，节点为开关，那么最大流问题就是如何让源节点S 到沉积节点T能流过的流量最大。Ford 和Fulkerson11 已经证明了“最大流-最小割切”理论，即网络流中最大流等于把到沉积节点分离的最小割切容量，等式如下： （1） 其中为网络流，为给切，假设 ，其中 为一个子集，给定，那么边集就叫做S-T的一个割切，包含在割切中的边叫做割边，最小割切即满足割边的容量和为所有割边中最小的一个割切。2.2 web社团这里引用文献910里定义web社团为： 设 为某些节点的集合，一个web社团是其中的一个子集 ，满足条件：对任何节点 ，与属于当中节点之间连接的边数大于它和以外节点之间连接的边数，即，如图1 所示 图1web社团 3 最大流算法的特点及存在的问题最大流算法应用到web 链接结构中抽取社团的思想最先是由G.Flake等人提出的，在文献910里面G.Flake等人通过实验证明了最大流算法对于解决HITS算法在社团抽取当中存在的主题漂移问题有较好的效果。下面重点探讨该算法同时所存在的一些问题并提出自己的解决方案。3.1 社团体积与边的关系 G.Flake等人在文献910里对边的容量与社团体积之间的关系进行了深入的研究 ，如下图所示。图的横坐标表示边容量的增加，纵坐标表示随之所获得的社团体积。可以看出，随着边的容量的增加，社团的体积也显著加大，但这种变化是离散的，即分阶段上升，而且不同阶段的跳跃长度并不相等。从下图来看，当边的容量从9到10，14到15，20到21这几个阶段每一次跳跃后，社团的体积都急剧变大，社团变化相应的值为9到36，36到50，50 到630。明显看出边的容量在20到21这个跳跃点社团的体积增加最迅速。 图2边的容量与社团体积的关系3.2 G.Flake 算法存在的问题及改进算法的提出如前面所说，边的容量对社团的体积会产生很大的影响，不仅仅在数量上，而且还会影响到社团成员的质量。G.Flake最先提出把最大流算法用来抽取web社团，在文献910里采用分配给各边一个相同的容量值，虽然可以较好的解HITS算法存在的主题漂移问题，但对社团的质量和数量也会带来许多不利的影响，而且随着web图节点的增加，噪音页面相应也会增加，仅仅通过增加边的容量并不能很好的解决这些问题，在很多情况下边的容量提升得越大，主题漂移的问题就会越易显现出来。其主要的原因就是没有考虑到每条边的不同重要程度，把所有的边一视同仁，体现不出不同边的价值度对形成社团的影响。为了更好的解决这些问题，本文提出了一种更好的分配边的容量的方法，即不是给每条边分配一个相同的常量值，而是依据信息的重要度为不同的边分配不同的边值。4 改进的最大流算法正如上节所说，一个理想的方法就是;重要的边分配给一个更大的容量，不重要的边分配给一个较小容量。那么关键的问题是如何定义一个重要边和不重要边，以及如何给不同重要程度的边分配不同边的容量，这就等于给边定义一个等级或者分值一样，所以必须把它对页面的价值分布转化到边的价值分布上来。在web 超链接分析里， PageRank算法和HITS算法是用来计算页面分值和权威性的最典型的两个算法1，HITS算法是个不断反复迭代的过程，迭代到一定次数就会很快收敛。因为HITS算法最终的计算结果是得到每个页面的权威和HUB 分值，在web图中，边所连接的两个节点所对应的web页面都有它们的权威和HUB分值，自然可以认为重要的边所连接的应该是分值比较大的节点，依据这个思想来进行边容量分配，这就是本文算法的主要思想。4.1边容量分配方法首先重新定义一个可变HUB 分值和Authority分值变量如下： ， （2） 在HITS算法里得到的HUB和权威分值都是在这个范围，不适合作为边的容量，因为最大流算法里边容量必须是一个正整数，所以通过设定一个常量系数 来得到分值的另外一种形式，这里的取值一般是基于整个邻接图的平均连接数，在本文后面的实验里设置=100 。用来表示任一节点到子节点的距离，例如假设经过两条不重复的边可以到达子节点，那么=2，接下来我们定义边的容量为下面两种形式： （3） （4）以上公式所得到的边的容量是一个动态的变量，不同边的容量由它所连接的节点和所代表的页面分值和来决定，应用该方法的效果我们在后面再讨论。下面我们给出基于以上边容量分配方法的最大流算法抽取社团的详细步骤。4.2 改进的最大流算法下面给出基于HITS算法边容量分配的最大流发现社团的详细步骤：1. Input: 子节点集合 2. Output : 3. ;( 围绕每一个子节点 ，以深度2抽取一个web子图)4. 计算HUB和权威分值向量和5. 按照前面的介绍的方法构建邻接图6. 应用前面公式（2）设置边的容量 ， 如果，那么添加 到，并设置边的容量 。7. 执行的最大流算法。8. 获得一个节点集合，其中每个节点要求和子节点连通 ，并对每一个节点都进行分值计算（在后面会介绍分值计算方法）9. 根据计算的分值排序，把前面一些分值最高的非子节点添加到子节点集合当中。反复执行步骤1到8 直到中的节点趋于一个稳定的社团为止。10. 按分值大小的顺序输出 中社团的节点 从实验来看， 中的节点通常很快就会趋于稳定，因为虽然子节点集合会不断扩展，但整个邻接图却一般不会加大，即使扩展也不会扩展太大。本文采取了和文献78 里不同方法给中的成员节点计算分值。设表示从其它社团节点链接到它的入链接数，表示它的出链接数。用来表示节点的分值，那么我们计算分值的公式如下： （4）在文献7中计算分值仅仅以每个节点的链接数为依据，因为有些排在前面分值较高的节点会有相同的链接数。但它们的权威和HUB 分值也许并不相同，所以仅仅以链接数来选择最高分值的节点加入到子节点当中去是不太好的。本文把每个节点的权威分值和HUB分值也考虑进去了，所以避免了这种情况。5 试验及其评价5.1 试验数据的收集与清理 数据集 ： 由于web 挖掘需要的数据集往往非常庞大，web 社团的挖掘需要更大数据资源才能体现算法的性能和优越性，为了测试算法的效果和验证它的有效性，对不同的查询主题和不同数据集分别进行了实验，数据量接近5G。种子节点集：一般每个社团都有一个明确的主题，所以在抽取社团前需要给定一个比较接近主题的URL页面作为子节点，为了更有代表性的说明问题，本文分别选择了20个互不相同的主题页面作为子节点，前十个选择了以英文为关键字的查询主题，后十个选择了中文为关键字的查询主题，每一个主题都具有明确的意义。表1中列出了各个子节点及其详细的说明数据清理 ：数据清理是为了更好的进行数据挖掘以获得高质量的挖掘结果而做的准备工作。算法在实验之前对获得的粗燥数据集进行了必要的数据清理，数据清理后我们就可以得到一个比较合理的邻接web图。在数据清理过程中主要做了一下几个工：1 首先排除了那些入链接或者出链接数超过了500以上的web页面，因为这样的一些页面往往是非常出名的一些站点页面，像Yahoo,Google,等，这些站点页面根本就不需要用户使用什么挖掘策略去获得的。2 去除那些RUL里包含有关键词%，？，bbs，cgi-bin ,diary,news等的页面，因为这样的一些页面往往和用户要找的主题无关。还会产生更多的主题漂移问题。3 去除镜像页面，所谓的镜像页面是指与主网站的内容相同的其它位置的网站页面就叫做镜像网站页面 ，太多的镜像页面只会重复同一个页面内容，扰乱用户的视野，所以要尽可能事先去除。5.2 实验及性能评价为了更好的说明改进方法的效果，本文对两种方法的实验结果进行了多方面的比较和分析。在下面的数据分析当中分别用C1 和C2表示两种最大流算法所获得的社团，C1表示本文改进算法的结果，C2是Flake等人方法的结果 。表1显示了针对于每个子节点所获得的web社团的大致情况，包括子节点，主题，web邻接图的节点数以及两种方法所获得的社团成员数。其中|V|, |C1| ,|C2|分别表示web邻接图的节点数，改进算法获得的社团成员数及原算法获得社团成员数。C2一竖排的第11，12，17 个主题上面都标有一个“*”表示在这种情况下所获得的社团体积都是不合理的失败情况。如表所示，改进算法所获得的社团C1在总体上要明显好于原来的算法结果，原来的算法虽然在某些情况下确实获得了比较好的结果，但在另外一些情况下却产生了非常坏的结果，比如在主题3，13，15，17这几个情况下，虽然我们使用了多种固定边容量进行了实验，但所获得的结果还是不那么理想。 对两种方法我们分别观察了前10个和主题相关的最权威页面情况，在下图3示意了结果大致情况，由图所示可以看出C1 和C2中平均的相关页面数分别大约为6.25（范围分布大约从3到10）和4.30（范围分布大约从1到7），C1的效果明显好于C2。同时可以看出，在所选的20个主题中有14个情况C1 比C2要好，4 个情况是相同的水平，只有2个情况是C1 比 C2 差的。而且大多数包括在C2 中的相关页面也都包括在C1中了。表2详细列举了关于主题1社团的前10 个成员URL的具体情况，右边的“+”和“-”分别用来表示该页面和主题的相关与不相关性。种子页面1是关于JAVA方面的内容，表C1中所有的URL页面都是和主题“JAVA”要求非常接近的一些页面，而在C2中除了种子页面以外和主题接近的页面数一共只有3个，虽然它们有些也是关于JAVA的讨论内容，但往往不是和用户最关心的JAVA开发，JAVA软件，JAVA技术等方面内容，比如“http:/archive.apache.org/dist/java/ ”这个成员，而且仔细观察就会发现：C1中的成员页面的HUB分值都高于C2 中的HUB分值，也即它们之间的相互链接数大于C2中成员之间的相互链接数 。表3详细列举了关于主题11的前10 成员URL的具体情况，这是一个关于“健康”主题的社团情况，如表所示，C1中虽然出现了一个不太理想的成员，且C2中和主体相关的成员 数也明显增加了，但总体上来看，C1比C2 中的效果还是要好 。图 3 每一主题分值最前的10个页面中和主题相关的社团成员分布情况。其中下面横排对应的是20个主题，C1，C2 所对应的两种方法的平均社团成员页面数分别为6.05和4.20表1。种子节点、社团主题、邻接图体积及两种方法发现的社团相关情况结点编号种子节点URL主题|V|C|C2|1JAVA 88219182http:/www.w3.org/XML/XML89815103Data ming 727194*4Computer667514125Coffe45317136Wedding 102347207Walking 104358138Foods 297814189http:/library.thinkquest.org/C005462/Starsand astronomy3727341710http:/www.koreananimals.org/Animalprotection1125311111健康1420281212医疗2546421513旅游857186*14汽车3542421915英语学习795178*16世界军事2456331417中国经济1045112*18中国政治2046251719考研1256191520教育20342411表2关于主题“”：C1C21+2http:/www.java-+3+http:/www.apl.jhu.edu/hall/java/-4+http:/www.javalobby.org/+5+http:/archive.apache.org/dist/java/-6+http:/www.ibiblio.org/javafaq/javatutorial.html-7+-8+-9+http:/micro.magnet.fsu.edu/primer/java/scienceopticsu/powersof10/-10http:/www.blackdown.org/+表3第11个主题：健康C1C21+.tw/+2+-3+-4+-5+6-+7+-8+9+10+-6 小结Web社团是一种很自然的网络群体，也是一种很重要的网络资源，目前所有发现web社团的方法都是基于链接结构和web图模型的思想，其中Fake等人提出的最大流算法是一种比较好的方法，相对于HITS算法中存在的严重主题漂移问题有很大的改善，但由于采取的是固定边容量的分配方法，对社团的数量和质量还是会产生诸多问题。在这里，本文为发现网络社团的最大流算法提出了一种改进方法。 特别，提出了一个比较好的动态分配边容量的改进最大流算法。为了验证改进算法的效果，对算法进行了实验对比，并列举了实验结果里每个网络社团排名最前的10个节点，通过大量的试验数据对比，显示了改进算法取得了较好的效果。当然对web社团发现研究还只是初步的开始，更多的工作需进一步努力和改进 ，我们下一步的工作就是期望能开发一个在线标准系统，能够根据参数的设置自动发现更多更好的web社团。 参考文献 1 王晓宇，周傲英 .万维网的链接结构分析及应用综述 J.软件学报，2003:14（10）2 Kumar R, Raghavan P, Rajagopalan S, Sivakumar D, Tomkins A, Upfal E. The Web as a graph. In: Serge A, ed. Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Pennsylvania: ACM Press, 1999. 109118. 3 Kleinberg J. Authoritative sources in a hyperlinked environment. In: Tarjan RE, et al., eds. Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. New Orleans: ACM Press, 1997. 668677. 4 Gibson D, Kleinberg J, Raghavan P. Inferring Web communities from link topology. In: Proceedings of the 9th ACM Conference on Hypertext and Hypermedia. Pittsburgh: ACM Press, 1998. 225234. 5 P.Krishna Reddy, Masaru Kitsuregawa .Building a community hierarchy for the Web based on bipartite graphs. 2002.36 Yasuhito Asano, Hiroshi Imai, Masashi Toyoda, and Masaru Kitsuregawa . Finding Neighbor Communities in the Web using an Inter-site Graph. Proceedings of the 14th International Conference on Database and Expert Systems Applications (DEXA 2003), 2003.9 7 G. Flake, S. Lawrence, and C. L. Giles. Efficient identificationof web communities. In 6th ACM SIGKDD InternationalConference on Knowledge Discovery and DataMining, pages 150160, 2000.8 G. W. Flake, S. Lawrence, C. L. Giles, and F. Coetzee. Selforganization of the web and identification of communities.IEEE Computer, 35(3):6671, 2002.9 N. Imafuji and M. Kitsuregawa. Effects of maximum flowalgorithm on identifying web community. In 4th International Workshop on Web Information and Data Management,pages 4348, 2002.10 N. Imafuji and M. Kitsuregawa. Finding a web community by maximum flow algorithm with hits score based capacity. In 8th International Conference on Database Systems for Advanced Applications, pages 101106, 2003.11 L. Jr. and D.R.Fulkerson. Maximal flow through a network.Canadian Journal of Mathematics, 8:399404, 1956. 作者简介： 何拥军 男( 1976- )硕士研究生 2005年毕业于湖南大学，主要研究方向: 数据挖掘，数据库。 读研期间曾在计算机科学，计算机工程与应用等核心期刊上发表多篇论文，现任教于广东科学技术职业学院计算机工程技术学院。 地址： 广东省珠海市金湾区红旗镇广东科学技术职业学院计算机工程技术学院 （519090） Tel： 0756-7858291；Email：heyj76 龚发根：男（ 1970- ），江西永丰人，硕士，主要研究方向：网络信息安全