The aim of this course is to offer a detailed overview of the theory of complex networks, a relatively new field, the study of



Baixar 29,43 Kb.
Encontro09.07.2018
Tamanho29,43 Kb.

Reds Complexas: aplicações em computação: “social networking”, modelos de arquitetura Web, caching, “crawlers” e algoritmos de busca

DCC/UFMG - PÓS e Graduação - 2o Semestre de 2007

Virgílio A. F. Almeida


  1. Descrição:

O objetivo do curso é oferecer uma visão detalhada da teoria das redes complexas, com suas aplicações em ciência da computação, como Internet, Web, recuperação de informação, caching e algoritmos. A teoria de redes complexas se aplica a outras áreas também, como redes sociais, economia, biologia e física. O curso focaliza principalmente na análise estática das estruturas de topologia das redes complexas. Alguns aspectos de evolução dinâmica (ex.: temporal) serão abordados.

B) Objetivos Específicos

Em particular, no curso serão abordados cinco tópicos em torno das redes complexas. Primeiro, vamos estudar de maneira geral as redes e suas propriedades. Depois, vamos tópicos especificos e algumas apliações. Começamos com as redes conhecidas como “small world”, que existem entre os grafos randômicos e “lattices” regulares. Vamos estudar as redes complexas com características como “scale-free” e leis de potência (“power laws”) que descrevem as distribuições de vários atributos dessas redes. Esses tópicos serão estudados em detalhe. Ao entender essas características e propriedades das redes complexas, vamos estudar trabalhos recentes que fazem uso dessas propriedades para projetar algoritmos e mecanismos de arquitetura de redes (ex.: protocolos, caching, etc). O último tópico sera um conjunto de artigos que aplicam redes complexas em diversos problemas em computação.



C) Tópicos e Bibliografia Associada

1) Introdução às Redes

    1. Duncan J. Watts, A twenty-first century science, Nature, 2007 Feb; 445(7127):489. www.nature.com/nature/journal/v445/n7127/full/445489a.htm
    2. The structure and function of complex networks, M. E. J. Newman, http://arxiv.org/abs/cond-mat/0303516 (versão reduzida do mesmo artigo: SIAM Review, Volume 45 Issue 2).


2) Redes do Tipo “Small World”

    1. Duncan J. Watts, "Small Worlds," Chapter 3 of D.J. Watts, Six Degrees: The Science of a Connected Age (New York & London: W.W. Norton & Company, 2002). (*)

    2. Watts, D.J., & Strogatz, S.H. (1998). Collective dynamics of 'small-world' networks, Nature, vol. 393, pp. 440-442. (*) Adamic, L.A. (1999). The small world web. In Lecture Notes in Computer Science, Proceedings of the European Conference in Digital Libraries (ECDL) '99 Conference, pp. 443-454 (Berlin: Springer, 1999). (*)

    3. Watts, D.J. (1999). Networks, dynamics and the small-world phenomenon. American Journal of Sociology, vol. 105, no. 2, pp. 493-527.

Aplicacão 2

  1. R. Albert, H. Jeong, and A.-L. Barabási, Diameter of the World Wide Web, Nature 401, 130-131 (1999).

  2. Barabasi, A. (2001). The physics of the Web, Physics World, vol. 14, no. 7, art. 9. (*)

  3. Newman, M.E.J. (2001). The structure of scientific collaboration networks, Proceedings of the National Academy of Sciences, vol. 98, no. 2, pp. 404-409.

  4. On Six Degrees of Separation in DBLP-DB and More, Ergin Elmacioglu, Dongwon Lee ACM SIGMOD Record, Vol. 34, No. 2, p.33-40, June 2005.

3) Leis de Potência na Web e Internet

  1. Duncan J. Watts, "Beyond the Small World," Chapter 4 of D.J. Watts, Six Degrees: The Science of a Connected Age (New York & London: W.W. Norton & Company, 2002). (*)

  2. Barabasi, A., & Albert, R. (1999). Emergence of scaling in random networks. Science, vol. 286, pp. 509-512. (*)

  3. Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000). Graph structure in the web. In the Proceedings of the 9th World Wide Web Conference. (*)

  4. Adamic, L.A., & Huberman, B.A. (2000). Power-law distribution of the World Wide Web. Science, vol. 287, p. 2115a. (*)

  5. Barabasi, A.L., Albert, R., Jeong, H., & Bianconi, G. (2000). Power-law distribution of the World Wide Web. Science, vol. 287, p. 2115b. (*)

  6. Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999). On power-law relationships of the Internet topology. Computer Communication Review, vol. 29, pp. 251-262.
Aplicacão 3

  1. R. Albert, H. Jeong, and A.-L. Barabási, Error and attack tolerance in complex networks, Nature 406 , 378 (2000).

  1. Ebel, H., Mielsch, L.I., & Bornholdt, S. (2002). Scale-free topology of e-mail networks. Physical Review E, vol. 66, 035103.

  2. "Anaylsis of topological characteristics of huge online social networking services," Yong-Yeol Ahn, Seungyeop Han, Haewoon Kwak, Sue Moon, Hawoong Jeong, 16th World-Wide Web(WWW) Conference, May

  3. Structure and tie strengths in mobile communication networks
    Barabási J.-P. Onnela, J. Saramäki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, and A.-L., PNAS published online Apr 24, 2007;

4) Crawlers e Buscas em Redes

  1. “Random Web Crawls”, Toufik Bennouas , Fabien de Montgolfier, 16th International World Wide Web Conference (WWW2007), Banff, Canada 2007.

  2. J. Leskove, C. Faloutsos, “Sampling from Large Graphs”, KDD’06, Augusr 2006.

  3. Eda Baykan, Sebastian de Castelberg, Monika Henzinger, "A Comparison of Techniques for Sampling Web Pages", Workshop on Information Integration on the Web, WWW 2006

  4. Duncan J. Watts, "Search in Networks," Chapter 5 of D.J. Watts, Six Degrees: The Science of a Connected Age (New York & London: W.W. Norton & Company, 2002). (*)

  5. Kleinberg, J. (2000). Navigation in a small world. Nature, vol. 406, p. 845. (*)

  6. Watts, D.J., Dodds, P.S., & Newman, M.E.J. (2002). Identity and search in social networks. Science, vol. 296, pp. 1302-1305.

  7. Adamic, L.A., Lukose, R.M., Puniyani, A.R., & Huberman, B.A. (2001). Search in power-law networks. Physical Review E, vol. 64, no. 046135. (*)

  8. Menczer, F. (2002). Growing and navigating the small world Web by local content, Proceedings of the National Academy of Sciences, vol. 99, no. 22, pp. 14014-14019.


5) Aplicações Diversas

  1. Exploiting Social Interactions in Mobile Systems, Andrew G. Miklas, Kiran K. Gollu, Kelvin K. W. Chan, Stefan Saroiu, Krishna P. Gummadi, and Eyal de Lara, Proceedings of the Ninth International Conference on Ubiquitous Computing (Ubicomp), Innsbruck, Austria, September 2007.

  2. Exploiting Social Networks for Internet Search, by Alan Mislove, Krishna P. Gummadi, and Peter Druschel. Proceedings of the 5th ACM Workshop on Hot Topics in Networks (HotNets), Irvine, CA, November 2006.

  3. Gueorgi Kossinets1* and Duncan J. Watts, Empirical Analysis of an Evolving Social Network, Science 6 January 2006, Vol. 311. no. 5757, pp. 88 – 93

  4. SIMPS: Using Sociology for Personal Mobility. Authors:, Borrel, Vincent; Legendre, Franck; Dias de Amorim, Marcelo; Fdida, Serge. eprint arXiv:cs/0612045, http://arxiv.org/abs/cs/0612045

  5. Rodrigo Almeida and Virgílio Almeida, A Community-Aware Search Engine, Proceedings of the 13th International Conference on World Wide Web, WWW 2004, New York. (*)

  6. A Crawler-based Study of Spyware on the Web, by Alexander Moshchuk, Tanya Bragin, Steven D. Gribble, and Henry M. Levy. Proceedings of the 13th Annual Network and Distributed System Security Symposium (NDSS 2006), San Diego, CA, February 2006.

D) Programa do Curso, Calendário de Aulas e Leituras de Artigos




Agosto

      • Dia 6 - apresentação do curso

      • Dia 8 – tópico 1, artigos [1, 2]

      • Dia 13 – tópico 1, artigos [2]

      • Dia 15 – Feriado

      • Dia 20 – tópico 2, artigos [4]

      • Dia 22 – tópico 2, artigos [5]

      • Dia 27– tópico 2, artigos [6]

      • Dia 29– tópico 2, artigos [8]


Setembro

  • Dia 3 – tópico 2, artigos [9]

  • Dia 5 – tópico 3, artigos [12]

  • Dia 10 – não haverá aula – estudo de artigos e preparação de propostas

  • Dia 12 – Entrega e apresentações da proposta do projeto (não haverá prorrogação)

  • Dia 17 – Apresentações das propostas

  • Dia 19 – tópico 3 artigos [13]

  • Dia 24 - tópico 3, artigos [14]

  • Dia 26- tópico 3, artigos [16]



Outubro

  • Dia 1 – tópico 3, artigos [18]

  • Dia 3 – tópico 3 artigos [19]

  • Dia 8 – topico 4 artigos [22]

  • Dia 10 - tópico 4 artigos [23]

  • Dia 15 – Prova #1

  • Dia 17 – topico 4 artigos [24]

  • Dia 22 - tópico 4 artigos [25]

  • Dia 24 – topico 4 artigos [28]

  • Dia 29 – não haverá aula – estudo da referencia

  • Dia 31 – não haverá aula – estudo da referencia



Novembro

  • Dia 5 – entrega e apresentação dos relatórios de progresso do projeto

  • Dia 7 – tópico 5, artigos [29]

  • Dia 12 - tópico 5, artigos [30]

  • Dia 14 – tópico 5, artigos [32]

  • Dia 19 – tópico 5 (reserva tecnica)

  • Dia 21 - tópico 5, (reserva técnica)

  • Dia 26 – tópico 5, (reserva tecnica)

  • Dia 28 - Prova #2


Dezembro

  • Dia 3 – apresentação de projetos

  • Dia 5 – apresentação de projetos

E) Pré-Requisitos


Curso de Estatística/Probabilidades e Matemática Discreta, equivalentes aos oferecidos na graduação do DCC.

F) Livros



Gerais:

  • Albert-László Barabási, Linked: How Everything Is Connected to Everything Else and What It Means, Plume Publishing, 2003.

  • Duncan Watts, Six Degrees: The Science of a Connected Age, W. W. Norton & Company, Feb. 2004



Específicos:


  • Romualdo Pastor-Satorras and Alessandro Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, February 2004.

  • Stefan Bornholdt (Editor), Heinz Georg Schuster (Editor), Handbook of Graphs and Networks : From the Genome to the Internet, Wiley February 2003.


5) Notas e Exercicios


  • Provas (2): 20 + 25%

  • Participação em Aulas: 15%

  • Projeto: 40%




    • Proposta

Escrever uma proposta de 2-3 páginas que descreva:




  • O problema que voce planeja estudar

    • Seja especifico, concreto e direto!

  • Por que voce pensa que o problema e importante

    • voce deseja desenvolver o topico por isso…

  • Trabalhos relacionados que voce já leu...

  • Qual o seu plano de trabalhi

    • pontos especificos que deseja alcançar; sua referência pela qual sera avaliado

    • pontos específicos que irá alcançar

    • pontos que você poderia alcançar se for incrivelmente bem!

Seu projeto tera a seguinte composição de nota




  • 10% proposta

  • 10% relatório intermediario

  • 10% apresentacao em classe

  • 70% o relatrio final:

  • 10% motivação e originalidade

  • 20% clareza do texto

  • 20% completude

  • 20% análise trabalhos relacionados




©livred.info 2017
enviar mensagem

    Página principal