基于相似度的社区发现最大流算法.pdf

基于相似度的社区发现最大流算法
桂挡平
大连理工大学软件工程系，辽宁大连（116621）

摘 要：web 社区是具有相似主题的网页集合，最大流算法是发现 web 社区的方法之一。
本文在给出了页面之间的链接相似性与主题相异性定义的基础上，对最大流算法进行改进。
实验结果表明本文改进的最大流算法发现社区的质量要高于传统最大流算法和基于 HITS 的
最大流算法发现的社区。
关键词：社区发现；web 链接；相似度；最大流算法
中图分类号：TP393

1．引言
随着全球网络化、信息化的发展，网络资源变得丰富而全面，每天增加约1百万的文档
[1]，不到9个月的时间文档总数就会翻一番。面对如此庞大的web信息海洋，有调查表明：99%
的web信息对于99%的用户是无用的，因此如何改进搜索引擎技术，从而准确高效地返回给
不同用户群体所需要的web页面变得十分重要。搜索引擎是在整个web上进行搜索，如果能
够将搜索范围缩小到与查询主题相关的社区，将社区的页面按重要程度排序返回给用户，那
么将极大的提高搜索精度和准确度。
Web社区是一种很自然的网络群体，也是一种很重要的网络资源。它们的内容一般都是
围绕某一主题具有一定的相似性。如何发现这些潜在的web社区是近几年来引起众多研究者
关注的研究领域。目前发现web社区的方法大都是基于web图形的链接分析，分为基于主题
的社区发现和无主题的社区发现。具体的实现技术有三种：基于最大流的技术[6]，基 于 HITS
的技术[2，3，7]和基于二分有向图的技术[4，5]。
Kumar等人从二分有向图的角度对web社区给出了一种明确的定义描述，提出了拖网
(trawling）算法[4]。根据随机二分图的理论，一个足够大而稠密的随机二分图将以很高的概
率包含一个完全二分有向图。如果将某个社区的链接结构看作一个大而稠密的二分有向图，
则社区的核就可以用一个完全二分有向图来表示。即如果在web上存在一个某种主题的社
区，那么这种二分的核必包含在其中，指出web的创建过程虽然是分布的、无计划的过程，
但不是随机的过程，新创建的超链接与web中已存在的超链接具有某种依赖关系。但对于如
何确定核的参数，以及采用怎样的方法从整个web结构图中枚举出所有社区的核，Kumar等
人并没有说明。
美国康奈尔大学教授Kleinberg和Gibson等人提出的HITS算法模型提供了一种很自然的
方式[2，3，7]，将链接的结构用一组中心性(hub)网页和权威性(authority)网页展现出来，尽管这
些中心性网页和权威性网页之间并不知道相互的存在