Title :
A Method for Solving a Bipartite-Graph Clustering Problem with Sequence Optimization
Author :
Harada, Keiu ; Ishioka, Takuya ; Suzuki, Ikuo ; Furukawa, Masashi
Author_Institution :
Hokkaido Univ., Sapporo
Abstract :
In this paper, we propose the solving method of bipartite-graph clustering problem (BCP) by transforming from BCP into traveling salesman problem (TSP). The analysis of information in web is an important guide to understand how to organize the wisdom of mankind. Especially, to divide from related information into communities of a suitable number is useful to the extraction of valuable information. One of the methods for extracting the community is using bipartite graph. BCP is equal to TSP with some concentrated cities, in the point of classifying the similar vertexes into each cluster. In order to solve TSP by smaller computational cost, we adopt the local clustering organization (LCO) method from many proposed solution for TSP. LCO has been proven to be possible to perform the high-speed computation for large-scale TSP. As the result of some computational experiments, we verified that our proposed method is possible to decide an optimum threshold of cost by observing the distribution.
Keywords :
graph theory; pattern clustering; travelling salesman problems; bipartite-graph clustering problem; local clustering organization; sequence optimization; traveling salesman problem; Bipartite graph; Business continuity; Cities and towns; Computational efficiency; Data mining; High performance computing; Information analysis; Large-scale systems; Optimization methods; Traveling salesman problems;
Conference_Titel :
Computer and Information Technology, 2007. CIT 2007. 7th IEEE International Conference on
Conference_Location :
Aizu-Wakamatsu, Fukushima
Print_ISBN :
978-0-7695-2983-7
DOI :
10.1109/CIT.2007.194
