Redes Complexas:
Aplicações em computação: Web, RI, redes, redes sociais e algoritmos
DCC/UFMG - PÓS e Graduação - 2o Semestre de 2008
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 e algoritmos. A teoria de redes complexas se aplica a várias áreas, como
física, economia, biologia e física. O curso apresenta métricas e modelos para analisar
a estrutura estática das redes complexas. Apresenta ainda modelos de evolução
dinâmica (ex.: temporal). Um dos objetivos do curso é aplicar os fundamentos de
redes complexos para modelar redes sociais, de tal forma a usar esses resultados no
projeto de algoritmos e sistemas em várias áreas da computação.
2) Objetivos Específicos
Em particular, no curso serão abordados seis tópicos em torno das redes complexas.
Primeiro, vamos analisar as propriedades das redes conhecidas como “small world”,
que existem entre os grafos randômicos e “lattices” regulares. Redes complexas
apresentam 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, pode-se projetar algoritmos para busca e recuperação em tais redes. Podese ainda estudar mecanismos de difusão e deteçcão de informação (ex.: inovação,
virus, edpidemias, spam, etc) em tais redes. Esses tópicos e seus algoritmos serão
estudados no curso.
3) Tópicos e Bibliografia Associada
• 1) Redes Complexas: estrutura e funcionalidade
o
o
o
o
M. E. J. Newman , The structure and function of complex networks, , SIAM Review 45,
167–256 (2003).
Duncan J. Watts, A twenty-first century science, Nature, 2007 Feb; 445(7127):489
Aaron Clauset, Cosma Rohilla Shalizi, and M. E. J. Newman,Power-law distributions in
empirical data, submitted to SIAM Review. http://wwwpersonal.umich.edu/~mejn/pubs.html
A.-L. Barabási, The architecture of complexity IEEE Control Systems Magazine 27:4,
33-42 (2007). http://www.barabasilab.com/pubs.php
• 2) Redes do Tipo “Small Worlds”
1
o
o
o
o
o
o
o
o
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). (*)
Watts, D.J., & Strogatz, S.H. (1998). Collective dynamics of 'small-world' networks,
Nature, vol. 393, pp. 440-442. (*)
Newman, M.E.J. (2000). Models of the small-world, Journal of Statistical Physics, vol.
101, pp. 819-841.
R. Albert, H. Jeong, and A.-L. Barabási, Diameter of the World Wide Web, Nature 401,
130-131 (1999).
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). (*)
Barabasi, A. (2001). The physics of the Web, Physics World, vol. 14, no. 7, art. 9. (*)
Watts, D.J. (1999). Networks, dynamics and the small-world phenomenon. American
Journal of Sociology, vol. 105, no. 2, pp. 493-527.
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.
• 3) Redes do Tipo “Scale-Free”: leis de Potência na WWW e Internet
o
o
o
o
o
o
o
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. (*)
Adamic, L.A., & Huberman, B.A. (2000). Power-law distribution of the World Wide
Web. Science, vol. 287, p. 2115a. (*)
Barabasi, A.L., Albert, R., Jeong, H., & Bianconi, G. (2000). Power-law distribution of
the World Wide Web. Science, vol. 287, p. 2115b. (*)
Barabasi, A., & Albert, R. (1999). Emergence of scaling in random networks. Science,
vol. 286, pp. 509-512. (*)
Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999). On power-law relationships of the
Internet topology. Computer Communication Review, vol. 29, pp. 251-262.
R. Albert, H. Jeong, and A.-L. Barabási, Error and attack tolerance in complex networks,
Nature 406 , 378 (2000).
Ebel, H., Mielsch, L.I., & Bornholdt, S. (2002). Scale-free topology of e-mail networks.
Physical Review E, vol. 66, 035103.
• 4) Aplicações A: gerais
o
o
o
o
o
o
o
R. Albert, H. Jeong, A.-L. Barabási, Error and attack tolerance of complex networks ,
Nature 406, (2000). http://www.barabasilab.com/pubs.php
Duncan J. Watts, "Epidemics and Failures," Chapter 6 of D.J. Watts, Six Degrees: The
Science of a Connected Age (New York & London: W.W. Norton & Company, 2002). (*)
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). (*)
Kleinberg, J. (2000). Navigation in a small world. Nature, vol. 406, p. 845. (*)
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. (*)
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.
.M. C. González, C. A. Hidalgo, A.-L. Barabási, Understanding individual human
mobility patterns , Nature 453, 779-782 (2008).
• 5) Aplicações B: redes sociais
2
o
o
o
o
o
o
o
o
Watts, D.J., Dodds, P.S., & Newman, M.E.J. (2002). Identity and search in social
networks. Science, vol. 296, pp. 1302-1305.
Gueorgi Kossinets1* and Duncan J. Watts, Empirical Analysis of an Evolving Social
Network, Science 6 January 2006, Vol. 311. no. 5757, pp. 88 – 90
Jun Zhang, Mark Ackerman and Lada Adamic, Expertise Networks in Online
Communities: Structure and Algorithms, WWW2007, Banff, Canada
D. Crandall, D. Cosley, D. Huttenlocher, J. Kleinberg, S. Suri. Feedback Effects between
Similarity and Social Influence in Online Communities. Proc. 14th ACM SIGKDD Intl.
Conf. on Knowledge Discovery and Data Mining, 2008.
P. Vaz de Melo, V. Almeida, A. Loureiro, Can Complex Network Metrics Predict the
Behavior of NBA Teams?.Proc. 14th ACM SIGKDD Intl. Conf. on Knowledge Discovery
and Data Mining, 2008.
, J. Leskovec, L. Backstrom, R. Kumar, A. Tomkins., Microscopic Evolution of Social
Networks , Proc. 14th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data
Mining, 2008.
M. Seshadri, S. Machiraju, A. Sridharan, J. Bolot, C. Faloutsos, J. Leskovec., Mobile
Call Graphs: Beyond Power-Law and Lognormal DistributionsProc. 14th ACM
SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2008.
L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social
Networks: Membership, Growth, and Evolution. Proc. 12th ACM SIGKDD Intl. Conf. on
Knowledge Discovery and Data Mining, 2006.
4) 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) Organização do Curso
•
•
•
3
Provas: duas provas em sala de aula, cada uma valendo 25% do conceito final.
“Midterm Paper” (10%), individual ou grupos de 2 alunos. O “paper” de no 5
páginas (coluna dupla) deverá fazer um “survey” completo sobre um tema
escolhido e propor novas idéias, se possível apresentar resultados.
Projeto (35%) – individual ou grupos de 2 alunos. O trabalho deverá desenvolver
um projeto experimental, de maneira sistemática, de acordo com o método
científico. O projeto poderá usar temas de pesquisas de outras disciplinas, como
•
•
redes, recuperação de informação, redes de sensores, robótica, sistemas
operacionais, etc. Entretanto, tem de ser um novo projeto e não algo já
apresentado em outra disciplina. Pode aproveitar trabalhos iniciados em outras
disciplinas, mas tem de apresentar os conhecimentos deste curso.
Os alunos deverão ler antes das aulas os artigos que serão discutidos e alguns
selecionados farão apresentações e haverá arguições sobre os artigos assinalados
para cada aula. Os alunos deverão participar ativamente das discussões de artigos
em sala de aula.
Nota Final: leituras (5%), exercícios (10%), projeto (35%) e provas (50%)
6) Programa do Curso e Calendário de Aulas e Leituras de Artigos
Agosto
Dia 11 - apresentação do curso
Dia 13 – tópico 1,
Dia 18 – tópico 1,
Dia 20 – tópico 1
Dia 25 – KDD – estudo individual e leitura de artigos
Dia 27 – KDD – estudo individual e leitura de artigos
Dia 1 – tópico 2
Dia 3 – tópico 2
Dia 8 – tópico 2
Dia 10 – tópico 3
Dia 15 – India – estudo individual artigos [3]
Dia 17 – India – estudo individual artigos [3]
Dia 22 - tópico 3
Dia 24 - tópico 3
Dia 29 - Prova #1
Dia 5 – tópico 4
Dia 7 – tópico 4
Dia 13 – tópico 4
Dia 15 - tópico 4
Dia 20 – tópico 5
Dia 22 – tópico 5
Dia 27 - tópico 5
Dia 29 – não haverá aula
Dia 3 – tópico 5
Dia 5 – tópico 5
Setembro
Outubro
Novembro
4
Dia 10 - CNPq - estudo individual
Dia 12 – CNPq - estudo individual
Dia 17 – tópico 5
Dia 19 - reserva Técnica
Dia 24 – reserva Técnica
Dia 26 - Prova #2
Dia 1 – apresentação de projetos
Dia 3 – apresentação de projetos
Dia 8 – apresentação projetos
Dezembro
5