一种改进的社区发现最大流算法

web community is a set of web pages having more links in the communities than the outside, using the maximum flow algorithm,we will extract a sense subgraph which can be recognized as a web community[1]. The previously proposed approach has a problem that a certain graph structure containing noises is always extracted, this problem is mainly caused by edge capacities assigned a constant value. When applying maxflow algorithm to web community identification, how to assign the edge capacity will decide the quality of the community. Basing on the characteristics of probability distribution, and utilizing powerlaw distribution of web page’s in-degree and outdegree, this paper proposes a maximum flow algorithm MBP（Maxflow-Based-Powerlow Algorithm）which assign edge capacities variably based on powerlaw distribution, this method not only considers the differences of edges’ importance which link from the same node , but also considers that from different nodes, so that it mends traditional maximum flow algorithm ,and improves the quality of web communities.