- 1 -
基于相似度的社区发现最大流算法
桂挡平
大连理工大学软件工程系，辽宁大连（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)网页展现出来，尽管这
些中心性网页和权威性网页之间并不知道相互的存在，但是可以将这一组中心性网页和权威
性网页理解为一个web社区。由于这种web社区的定义是完全基于结构的，因此可以在不知
道特定主题的情况下发现它们。Kleinberg等人认为需要用一小部分高权威性的相关网页来表
示社区的主题。利用HITS算法除了依赖于主题的广泛性之外，同时还依赖于web知识结构，
那些在web上存在更多甚至更合理链接的主题，利用HITS具有较好的结果。针对那些在web
中体现较少链接的主题，HITS的效果便不令人满意。所以此方法缺乏对web社区的一种清晰
描述，使得在没有给出特定主题描述时，无法从web中有效地抽取潜在的社区。针对HITS
算法的不足，又提出了HITS算法的各种改进算法。IBM Almaden研究中心的Clever工程组提
- 2 -
出了ARC(Automatic Resource Compilation)算法，结合链接的锚文本，以适应不同的链接具
有不同的权值的情况。和提出了SALSA(Stochastic Approach for
Link-Structure Aanlysis)算法,结合PageRank的随机漫游和HITS中把网页分为Authoritive和
Hub的思想，减少了HITS算法中的主题漂移现象，具有更高的健壮性。
等人[6]最先提出通过最大流算法来抽取 web社团，将社区定义为在 web图上具
有这样一些特性的页面的集合，社区内的页面之间的链接（在两个方向上）的密度要大于社
区之间页面链接的密度。采用分配给各边一个相同的容量值的办法来解决 HITS算法存在的
主题漂移问题，但对社区的质量和数量也会带来许多不利的影响，而且随着 web图的增加，
噪音页面也会增加。
利用二分图算法可以发现大量的社区的核心，却无法确定社区的边界。最大流算法相对
于HITS算法中严重的主题漂移问题有很大的改善[8]，原始的最大流算法采用固定边容量的分
配方法，发现的社区包含大量与主题无关的页面。
针对原始的最大流算法存在的问题，通过对最大流算法的分析，并结合web社区的特点，
提出了一种改进的最大流发现社区的方法。本文将边的容量大小设为页面之间的相似性，发
现的社区与主题具有很高的相关性，改进了社区的质量。
本文的组织结构如下：第2节回顾了网络流理论及原始最大流算法的缺点，第3节介绍了
基于相似度的最大流社区发现算法，第4节介绍了实验结果和结果分析，第5节是结论和未来
可做的工作。
2．基于最大流的社区发现算法及缺点
网络流理论回顾
图 G=(V,E),它的结点集为 V={v1,v2,…,vm},边集为 E={eij}，用 eij表示结点 vi指向 vj，
每条边 eij都有一个非负的容量 cij，从任意点 s到点 t的最大流 Fst是由满足下列条件的边 eij
的容量 fij组成的：
j i k i
st i
ij ki st i
v O(v ) v I(v )
F if v =s
f f F if v =t (1)
0 otherwise∈ ∈
⎧ ⎫⎪ ⎪− = −⎨ ⎬⎪ ⎪⎩ ⎭
∑ ∑
在（1）中对于所有 eij∈E，满足 0≤fij≤cij。Fst 表示从 s 到 t 的网络流的大小，
O(vi)={vj|eij∈E},I(vi)={vk|eki∈E}。
定理 1(Ford-Fulkerson 定理)从 s到 t的最大流 Fst等于分割 s，t的最小割 i( )mmV V→ 的
大小。
割 i 00( )V V→ 是 E中始点位于 0V 中终点位于 i 0V 中的边的一个集合，其中 0V ， i 0V 是结
点集合且 s∈ 0V ，t∈ i 0V ， 0V ∪ i 0V =V 。割 i 00( )V V→ 的大小定义如下：
i
i00
00
( )
( )
ij
ij
e V V
F V V c
∈ →
→ = ∑ （2）
从结点 s到结点 t的最小割 i( )mmV V→ 就是使该值达到最小的割。理论证明见[9，]。
Ford和 Fulkerson[9]提出了解决最大流问题的方法，即通过寻找划分 s和 t的最小割。根据定
理(1)，为了找到社区之间的最小相似性，即最小割的大小，等价于求 web图上的最大流。
- 3 -
原始最大流的社区发现算法缺点
我们把与社区主题无关的页面称为噪音页面。原始的最大流发现社区的方法中，边的容
量大小都相等，是个常量，不能体现结点与主题的相关性，发现的社区含有很多噪音页面，
原始的算法可以把有很多链接却与主题无关的页面包含进来。
Noriko等[10]提出了一种基于HITS的最大流算法，为不同的边赋不同值，认为重要的边
连接重要的页面。文中利用HITS算法计算出来的hub值和authority值，来量化边的重要性。
用c(v,u)表示结点v和u之间的边容量。av’表示结点v的authority值，hv’表示结点v的hub值。那
么边容量
' '
( , ) 1
2
v uh ac v u += + 。这种基于HITS的最大流算法比原始的最大流算法发现的社区
质量好，但是仍然存在一些噪音页面。由于HITS算法存在主题漂移的问题，计算出来的hub
值和authority值在反映页面重要程度时也会出现漂移，导致与主题无关的页面被包含进来。
本文利用链接相似性和主题相异性来计算页面之间的相似性，根据最大流算法理论，若
页面的相似性很高，那么属于同一个社区的概率也高。利用本文的计算边容量大小的方法，
若页面的主题与种子集的主题相关，得出它们之间的边容量的值也越大，表示它们属于同一
个社区的概率也大。改进后的算法可以发现高质量的社区，可以把那些链接数目虽小却与主
题很相关的页面包含进来。
3．基于相似度的最大流社区发现算法
基于相似度的边的容量计算
页面之间相似度的衡量可以从页面内容，链接这两方面来考虑。页面内容一般都非常大，
需要获取并存储整个页面，还要对文本内容进行处理，这些都增加了算法的额外负担。不同
于文本内容，链接结构简单，是统一的没有区别，并且是个独立于语言的信息资源，可以有
效的防止垃圾信息[11]。
本文提出的计算页面相似度的方法仅考虑页面之间的链接关系。我们用 p→q表示从页
面 p到页面 q的超链接关系，即从页面 p可到达页面 q。若 p→q则说明页面 p的作者认为
页面 q是有用的，链接常常连接着相关的页面。利用链接关系来考察相似度的理论依据是，
那些共同指向同一页面或被同一页面所指的页面在语义上存在一定的相关性。
为了准确衡量两个页面的相似度，本文提出三种页面相似性，具体定义如下。
定义 1共引用相似性 若页面 p和 q所指向的页面集存在交集，则 p和 q存在共引用相
似性，共引用相似性是一种直接链接相似性。如图 1所示。
定义 2共被引用相似性 若指向页面 p和 q的页面集存在交集，则 p和 q存在共被引用
相似性，共被引用相似性是一种直接链接相似性。如图 2所示。
p q
p q
图 1 页面之间的共引用关系 图 2 页面之间的共被引用关系
- 4 -
定义 3传递相似性 若页面 p和 q存在直接链接相似性，页面 q和 r存在直接链接相似
性，则 p和 r存在间接链接相似性，本文称之为传递相似性。如图 3，4所示。
图 3 页面之间的传递引用关系 图 4 页面之间的传递被引用关系
定义 4链接相似度函数 是一个邻居函数，用来测量页面 p和 q的局部相似关系，它的
值由共引用、共被引用相似性和传递相似性决定。该值越大，页面 p和 q属于同一个社区的
可能性越大。用公式表示为：
( ) pq pq pqsim co ci st= × + + × （3）
copq表示 p和 q的共引用相似度，cipq表示 p和 q的共被引用相似度，stpq表示 p和 q的
传递相似度。我们用黄金分割比例系数来体现页面 p和 q之间的直接链接相似度和间接链接
相似度对相似度函数的影响。在这里，直接链接相似度包括共引用和共被引用相似度，由于
它们对相似度函数的作用大，比例系数也应该大，在此，分配为 。间接链接相似度是
指传递相似度，给它分配的影响因子取小值，大小为 。
下面我们说明 copq，cipq和 stpq的计算方法。
页面 p和 q的共引用关系如图 1所示。页面 p和 q存在共引用相似性，共同指向的页面
数目越多它们的相似性就越高。共引用相似度的大小表示为：
p q
pq
p q p q
O O
co
O O I I
= ∩∪ ∪ ∪ （4）
其中，Op表示结点 p 的出度，Ip表示结点 p 的入度。在两个页面共同指向的页面数目
一定的情况下，他们的边的总和越小，相似性越高。
页面 p,q的共被引用关系如图 2。页面 p和 q存在共被引用相似性，若同时指向页面 p
和 q的页面数目越多，它们的相似性越高。共被引用相似度的大小表示为：
p q
pq
p q p q
I I
ci
O O I I
= ∩∪ ∪ ∪ （5）
从权威性（authority）页面和中心性（hub）页面的角度来分析，页面之间的共引用值
可以看成它们作为中心性(hub)页面时相似度的大小。共被引用值可以看成它们作为权威性
(authority)页面时相似度的大小。
在图 3和图 4中，页面 p和页面 q有相似性，页面 q和页面 r有相似性，则页面 p和页
面 r 也具有一定的相似性。为了计算它们之间的相似度，本文引入广义 Jaccard 系数。将共
引用的 Jaccard值与共被引用的 Jaccard值之和作为传递相似度的值。大小表示为：
- 5 -
( )
( )
( )
( )
1 1
2 2 2 2
1 1 1 1 1 1
( ) ( ) ( ) ( )
m m
kp kq kp kq
k k
pq m m m m m m
kp kq kp kq kp kq kp kq
k k k k k k
co co ci ci
st
co co co co ci ci ci ci
= =
= = = = = =
× ×
= +
+ − × + − ×
∑ ∑
∑ ∑ ∑ ∑ ∑ ∑
（6）
为了更进一步提高社区质量，本文考虑了页面之间主题的相异性。位于页面内容的 title
标签之间的字符串反映了页面的主题。比较主题的相异性，等价于比较字符串的相异性。现
有的计算字符串相似度的方法按照计算所依据的特征不同，可以分为三种方法：基于字面相
似性的方法、基于统计关联的方法、基于语义相似性的方法。其中，基于字面相似的计算方
法主要有基于编辑距离的计算方法[12]和基于相同字或词的方法。基于统计关联的方法主要
有基于词汇共现、向量空间模型、基于部分语法分析等。基于语义的方法主要是利用释义词
典或者一些大规模的本体对词汇进行语义上的相似度计算。本文利用基于字面相似性的编辑
距离的方法来计算主题的相异性，得到页面 p和 q的主题相异度 difpq。
页面之间的相似度受链接相似度和主题相异度的共同影响。若页面 p和 q的链接相似度
大，说明它们之间的相似性大，边的容量值大。若页面 p和页面 q的主题相异度小，说明它
们的主题相似性大，边的容量值大。为了体现这种关系，我们定义如下几种模型来求解页面
p和 q的相似度大小 cpq。我们提出的几种待分析的模型如下：
线性模型公式为： ( )pq pq pqc sim 1-dif= λ× × （7）
一次指数模型公式为： dif pqpq pqc sim e
−= λ × × （8）
二次指数模型公式为： ( )2dif pqpq pqc sim e−= λ× × （9）
三次指数模型公式为： ( )
3
dif pq
pq pqc sim e
−= λ × × （10）
其中，参数 λ的作用是为了使容量的大小为整数，本文设定 λ=100。这五种模型的对应
的曲面如图 5-图 8所示。
图 5线性模型 图 6一次指数模型
- 6 -
图 7二次指数模型 图 8三次指数模型
图中坐标轴 sim、dif和 c分别表示链接相似度、主题相异度和容量大小。图 5显示线性
模型中主题相异性对容量的影响过大；而由图 8看出，在三次指数模型中，主题相异性对容
量的影响过小。图 7中在链接相似度相等的情况下主题相异性对容量 c的影响较合理。并且
要求当链接相似度（即坐标轴 sim）越大，容量 c也越大。因此本文选择二次指数模型，即
公式（9）来计算页面的相似性。
改进的最大流发现社区算法
本文给出的社区发现算法如下：
Input：S={vs1,vs2,...,vsk}；种子集，k为种子集的数目，设置迭代次数
m
Output：O={vo1,vo2,…,von}；一个社区
Step1：从种子集出发，对每个种子进行深度为 2的的扩展
Step2：得到原始的 web 图 G’(V’,E’)，利用公式（9）对该图进行容
量计算，得到容量矩阵 C
Step3：构造新图 G(V,E)，结点集 V 是原始图中的结点集 V’，对所
有的 cij∈C，且 cij≠0，添加边 eij到 E中。
Step4：添加虚拟源点 s和下沉点 t到 V中
Step5：对所有的点 vsi∈S，添加边(s, vsi)到 E中，并且设边的容量 c(s,
vsi)=∞
Step6：对所有的边(u,v)∈E，设置边的容量c(u,v)=cuv
Step7：对点v∈V ，且v∉ S，添加边(v,t)到E中，并且设边的容量c(v,t)=
λ（即上文中的参数λ）
Step8：对G执行s-t算法
Step9：O={ v∈V，且与s相连}
- 7 -
4．实验和评价
数据集的建立
本文选择如下 24个主题进行实验。对于每个主题，并根据文本搜索引擎 Altavista 返回
的前 15个结果作为种子集。在扩展页面的过程中，去掉出度或入度非常大的页面，因为这
种页面形成的密集链接对社区的发现会造成不利的影响。
构建 web图
图 9 计算边的容量大小（一）
对图 9，两个页面链接相似且页面主题内容都是“The Automobile of the 21st Century”利
用本文的计算方法，它们的边容量大小为 61。
图 10 计算边的容量大小（二）
对图 10，两个页面有相似的链接，但是页面的主题内容不同，计算得到它们的边容量
大小为 6。
最大流最小割算法的选择
本文利用的最大流最小割算法是改进了 Ford-Fulkerson的算法[13]，每次找一条从源点到
汇点的“最短”路径，“最短”路径满足，距离最短，路径上的容量总和最大。这个算法的时间
复杂度为 O(FM)，其中，F是最大流，M是边的数目，该算法每次尽可能大的提升流。
图 11 流网络
对于图 11 这种流网络，原始的 Ford-Fulkerson 算法总共要执行 2×106次加法运算。利
用这种改进的算法，只要执行 4次加法运算。
- 8 -
实验结果分析
本文对实验结果的评价，是比较社区中前十个页面与主题的关系。表一中前三列分别是
主题编号，种子集的 url和种子的主题。|V|代表图中结点数目，|a1|，|a2|，|a3|分别是原始最
大流，基于 HITS的最大流算法和本文改进的最大流算法发现的社区中排名前十的页面中，
与主题相关的页面数目。
表 1 实验结果
No Seed URLs Topics |V| |a1| |a2| |a3|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
abortion
affirmative_action
amusement_parks
architecture
armstrong
automobile_industries
blues
cheese
classical_guitar
computational_complexity
computational_geometry
genetic
geometry
globalization
gun_control
jordan
moon_landing
movies
net_censorship
recipes
roswell
shakespeare
table_tennis
vintage_cars
1376
689
1168
2350
704
473
901
1148
874
503
495
2163
1621
1850
957
2160
237
3289
823
1023
731
1342
389
864
6
5
7
3
4
6
5
3
5
4
6
5
8
7
6
4
5
7
5
4
6
4
5
7
7
5
8
6
5
7
6
5
9
6
10
6
7
8
7
8
6
7
6
5
7
5
6
6
8
9
10
6
7
8
9
8
8
7
10
9
8
8
7
9
7
9
8
6
8
8
7
9
Average precision(%)
通过上表可以看出，改进后的算法发现的社区比原始的最大流算法，基于 HITS的最大
流算法质量高，平均精确度（Average precision）比原始最大流提高了 27%,比基于 HITS的
最大流算法提高了 14%。表明发现的社区与主题的相关性有了很大的提高。实验结果的图
形表示如图 12。
- 9 -
图 12 24个主题的实验结果比较
5．结论和未来工作
本文改进了原始最大流发现社区的算法，把页面的相似度作为边的容量。通过实验，
可以看出，改进的算法，大大提高了原始最大流发现社区的结果的精度。证明了这种方法是
可行，但是发现还是会有少量的页面与主题不相关，需要更进一步改进。未来可以深入研究
的工作有：（1）若把页面的链接关系用树来描述，则本文全方位地考虑了位于同一层的页
面之间的相似度，却没有考虑与页面的父亲之间的相似度。（2）本文仅考虑距离为 1的页
面之间的相似度，若两个页面通过大于 1的走步交汇于同一点，可以确定这两个页面也有相
似性[14]。
- 10 -
参考文献
[1] Chakrabarti S,etal. Hypersearching the WEB. Scientific American,June1999
[2] Kleinberg. Hubs, authorities, and communities on the www. ACM Computing Surveys, 1999.
[3] Gibson. D, Kleinberg. J, and Raghavan. P. Inferring Web Communities from Link Topology, Proceedings of
the 9 ACM Conference on Hypertext and Hypermedia (1998), 225-234
[4] Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins: Trawling the web for
emerging cyber-communities. Proceedings of the 8th World Wide Web Conference, 1999.
[5] P. Reddy and M. Kitsuregawa. Inferring web communities through relaxed cocitation and dense bipartite
graphs. In Proc. of Data Base Engineering Workshop, 2001.
[6] G. Flake, S. Lawrence, and C. L. Giles. Efficient identification of web communities. In Sixth ACM SIGKDD
Conference, pages 150--160, Boston, MA, August 2000.
[7] J. Kleinberg. Authoritative sources in a hyperlinked environment. Proceeding of 9th ACM-SIAM Symposium
on Discrete Algorithms, 1998.
[8] N Imafuji,M Kitsuregawa. Finding Web Communities by Maximum Flow Algorithm using Well-Assigned
Edge Capacities. IEICE TRANSACTIONS on Information and Systems ,2004
[9] L. R. Ford, Sr. and E. Fulkerson, Flows in Networks. Princeton NJ:Princeton Univ. Press, 1962.
[10] N Imafuji, M Kitsuregawa. Finding a Web Community by Maximum Flow Algorithm with HITS Score Based
Capacity. Database Systems for Advanced
[11] ,, Similarity Search to Fight Web Spam. Informatics Laboratory
Computer and Automation Research Institute Hungarian Academy of Sciences,2006.
[12] Monge AE , Elkan CP. The field-matching problem: algorithm and applications. In : Proceedings of the
Second Internet Conference on Knowledge Discovery and Data Mining ,Oregon , Portland , 1996 , 8. 267～270
[13] L. Jr. and . Maximal flow through a Journal of Mathematics, 8:399–404,
1956.
[14] Daniel Fogaras, Balazs Link-Based Similarity Search. International World Wide Web
Conference Committee (IW3C2),2005.
A Maximum Flow Algorithm Based on Similarity for Web
Communities Identification
Gui Dangping
Academy of Software Engineering, Dalian University of Technology, Dalian, Liaoning (116621)
Abstract
Web communities are composed of web pages about similarity topics,Maximum algorithm is one of
approaches for web communities paper improves maximum flow algorithm on the
basis of similarity of linkage and difference of topic between experiment’s result shows that
the quality of the communities are identified by our maximum flow algorithm are better than original
maximum flow algorithm and maximum flow algorithm based on HITS.
Keywords: discovering community; web linkage; similarity; maximum flow algorithm
作者简介：桂挡平，1983 年生，大连理工大学软件工程系，硕士研究生，研究兴趣：web
社区发现，数据挖掘。
