UTL Repository >
ISEG - Instituto Superior de Economia e Gestão / ISEG - School of Economics & Management Lisbon >
Departamento de Matemática / Mathematics Department >
DM - Documentos de trabalho / Working Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10400.5/1428

Title: A bi-objective hub-and-spoke approach for reconfiguring Web communities
Authors: Colaço, Susana
Pato, Margarida Vaz
Keywords: multi-objective
heuristics
Web communities
Web communities
Issue Date: 2008
Publisher: Centro de Investigação Operacional - Universidade de Lisboa
Citation: Colaço, Susana e Margarida Vaz Pato. 2008. "A bi-objective hub-and-spoke approach for reconfiguring Web communities". Universidade de Lisboa - Centro de Investigação Operacional – CIO - Working paper nº 4/2008
Series/Report no.: CIO - Working paper;4/2008
Abstract: Web communities in general grow naturally, thus creating unbalanced network structures where a few domains centralise most of the linkups. When one of them breaks down, a significant part of the community might be unable to communicate with the remaining domains. Such a situation is highly inconvenient, as in the case of wishing to pursue distribution policies within the community, or for marketing purposes. In order to reduce the damages of such an occurrence, the Web community should be reconfigured, in such a way that a complete sub-network of main domains -the hubs - is identified and that each of the other domains of the community - the spokes - is doubly linked at least with a hub. This problem can be modellised through a bi-objective optimisation problem, the Web Community Reconfiguring Problem, which will be presented in this paper. A bi-objective mixed binary formulation will also be shown, along with a brief description of GRASP, tabu search and hybrid heuristics which were developed to find feasible solutions to the problem, possibly efficient solutions to the bi-objective problem. A computational experiment is reported, involving comparison of these metaheuristics when applied to several Web communities, obtained by crawling the Web and using epistemic boundaries and to other randomly generated ones. The heuristics revealed excellent quality for the small dimension cases whose efficient solutions were roughly all determined. As for the other medium and higher dimension instances, the heuristics were successful in building a wide variety of feasible solutions that are candidate efficient solutions. The best behaviour was attained with the GRASP and the GRASP and tabu hybrid search. Comparison of some metrics before and after reconfiguration confirmed that the final structures are more balanced in terms of degree distribution reinforcing the connecting effect imposed by the reconfiguration process.
URI: http://hdl.handle.net/10400.5/1428
Appears in Collections:DM - Documentos de trabalho / Working Papers

Files in This Item:

File Description SizeFormat
MVP-4.2008.pdf296.66 kBAdobe PDFView/Open
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpaceOrkut
Formato BibTex mendeley Endnote Logotipo do DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 
Estamos no RCAAP Governo Português separator Ministério da Educação e Ciência   Fundação para a Ciência e a Tecnologia

Financiado por:

POS_C UE