Grasp and tabu search for redesigning web communities

• Author(s): Colaço, Susana ; Pato, Margarida Vaz
• Date: 2006
• Persistent ID: http://hdl.handle.net/10400.5/1430
• Origin: Repositório da UTL
• Subject(s): heuristics; GRASP; tabu search; web communities; hub-and-spoke networks
• Document Type: Other
• Language: English

Description

Web topologies are commonly characterised by hierarchical structures and highly unbalanced compositions, as illustrated by the difference of centrality and connectivity as to their elements. The major interest of the problem addressed in this paper lies in restructuring web communities to reduce these initial disequilibria so as to democratise information access or even for the purpose of preserving contents distributed on the Internet. Discussion of this issue thus leads to a hub location problem, formalised by network and integer programming models. Due to its highly complex nature, a GRASP and a tabu search heuristics were developed to find good quality feasible solutions to the problem. The set of test instances includes web communities obtained by crawling the web and using epistemic boundaries, as well as other randomly generated communities, built with specific network analysis software. The experiment demonstrated that the metaheuristics produced low costs and balanced structures, at least for the lower dimension web communities considered. All the redesigned web communities are more closely connected than before and the average distance among their elements reduced.