Extracting web communities as a dense subgraph of web graph

摘要

In this paper, we describe the properties of the web communities derived as two distinct types of dense subgraphs in web graph. Web graph consists of nodes and edges, which represent web pages and hyperlinks respectively. A web community is a set of web pages having a common topic and so far various graph theoretical approaches have been proposed to extract web communities from web graph. Although all these approaches regard a web community as the dense part of web graph, the graph structures are different from each other. We analyze the effects of structural difference in the dense subgraph on the characteristic of web comn1uI1ities obtained by methods based on complete bipartite graphs and maximum flow algorithm.