Universidade de Lisboa Repositório da Universidade de Lisboa

Repositório da Universidade de Lisboa >
Faculdade de Ciências (FC) >
FC - Teses de Doutoramento >

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

Título: Optimização em grafos num contexto de redes sociais, tecnológicas e no ensino da matemática: estudo do problema de balanceamento de uma comunidade na world wide web
Autor: Colaço, Susana Isabel Gueifão
Orientador: Pato, Margarida Vaz, 1955-
Cativo, Maria Eugénia, 1954-
Palavras-chave: Estatística
Teses de doutoramento
Issue Date: 2007
Resumo: Operations Research (OR) has been widely applied in several traditional contexts (e.g. route optimisation, partitioning problems, scheduling problems, etc.). More recently, new applications include the design of telecommunication networks and data mining among others. Within this context of new application domains, the exploration of OR to Mathematics teaching is also briefly discussed within this thesis in a chapter dedicated to conceptual framework and bibliographic revisions. However, the main investigation focus on the application of graph optimisation to socio-technical networks and the World Wide Web (Web). Web topologies are commonly characterised by hierarchical structures and highly unbalanced compositions, as illustrated by the centrality and connectivity of their elements. Web communities are one among many examples of Web structures. The major interest of the problem addressed in this thesis lies in reconfiguring such communities to reduce their initial disequilibria. The Web Balancing Problem is addressed, along with a network model and integer programming formulations. GRASP and tabu search heuristics were developed to find feasible solutions to the problem. Computational results are also reported, based on several web communities, involving comparison and combination of these meta-heuristics. Some of these Web communities were obtained by crawling the web and using epistemic boundaries. Other communities were randomly generated by network analysis tools. The results confirmed more balanced structures for the Web communities investigated.
A Investigação Operacional (IO) tem sido tradicionalmente aplicada em diversos contextos como o desenho de rotas, problemas de partição e de escalonamento, etc.. Mais recentemente, começou a ser utilizada em novas áreas como o desenho de redes de telecomunicações e data-mining. Neste âmbito e num capítulo inicial de enquadramento e revisão bibliográfica, discute-se de forma sucinta, o modo como problemas de IO podem vir a ser utilizados no ensino da Matemática. Esta investigação tem enfoque particular na utilização de optimização em grafos para a modelação de redes sócio-tecnológicas, como a World Wide Web (Web). As topologias da Web são normalmente caracterizadas por estruturas hierárquicas e composições bastante desequilibradas, como é demonstrado pela centralidade e conectividade dos seus elementos. As comunidades Web são apenas um dos muitos exemplos destas estruturas na Web. O contributo proposto nesta tese tem como objectivo principal a reconfiguração destas comunidades Web, de modo a reduzir o seu desequilíbrio estrutural inicial. O trabalho de investigação caracterizou o Problema de Balanceamento de uma Comunidade na Web, apresentando um modelo de grafo bem como formulações em programação inteira. Foram desenvolvidas heurísticas de pesquisa GRASP e Tabu para encontrar soluções admissíveis para o problema. São também apresentados resultados computacionais baseados em diversas comunidades Web e envolvendo a comparação e combinação das referidas metaheurísticas. Algumas destas comunidades Web foram obtidas por crawling da Web e utilizando fronteiras epistémicas ou conceptuais. Outras comunidades foram geradas aleatoriamente com software de análise de redes. Os resultados confirmam a reconfiguração e obtenção de estruturas mais balanceadas para as comunidades Web em análise.
Descrição: Tese de doutoramento em Estatística e Investigação Operacional (Optimização), apresentada à Universidade de Lisboa através da Faculdade de Ciências, 2008
URI: http://hdl.handle.net/10451/1674
Appears in Collections:FC - Teses de Doutoramento

Files in This Item:

File Description SizeFormat
3651_TeseDoutoramentoSColaco2007.pdf2,36 MBAdobe 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.

 

  © Universidade de Lisboa / SIBUL
Alameda da Universidade | Cidade Universitária | 1649-004 Lisboa | Portugal
Tel. +351 217967624 | Fax +351 217933624 | repositorio@reitoria.ul.pt - Feedback - Statistics
DeGóis
  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