document: Partitioning of Web graphs by community topology We introduce a stricter Web community definition to overcome boundary ambiguity of a Web community defined by Flake , Lawrence and Giles ( 2 ) , and consider the problem of finding communities that satisfy our definition . We discuss how to find such communities and hardness of this problem . We also propose Web page partitioning by equivalence relation defined using the class of communities of our definition . Though the problem of efficiently finding all communities of our definition is NP-complete , we propose an efficient method of finding a subclass of communities among the sets partitioned by each of n-1 cuts represented by a Gomory-Hu tree ( 10 ) , and partitioning a Web graph by equivalence relation defined using the subclass . According to our preliminary experiments , partitioning by our method divided the pages retrieved by keyword search into several different categories to some extent .
doc_bio_tags: O O O O O O O O O O O B I O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O