Redes Complexas UFRJ/COPPE/PESC CPS765 - 2011/3

Retirado do Visual Complexity Website (Internet Mapping project)

• Daniel R. Figueiredo
  
• Horário de atendimento: sob demanda (enviar email)

• Sala H304B -- CT, Bloco H, terceiro andar
• Dia/horário: segundas e quartas das 13h às 15h.

• Jefferson Simões
• Horário de atendimento: Segundas das 15h às 16h
• Local: Sala I-246 (CT, Bloco I, segundo andar), tocar campainha (Carol)

O aumento significativo de informação empírica sobre os mais variados sistemas formados por entidades que de alguma forma estão relacionadas vem despertando grande interesse no meio acadêmico e empresarial. Exemplos de tais sistemas, que podem ser representados por grafos (ou seja, redes), incluem redes tecnológicas (ex. Internet), redes sociais (ex. Orkut) e redes biológicas (ex. neurônios). Ao analisarmos a estrutura destes sistemas, dois fatos podem ser observados: (i) muitos sistemas possuem propriedades topológicas não-triviais (ex. seguem uma lei de potência); (ii) há muita semelhança entre as propriedades topológicas de diferentes sistemas. Por que tais sistemas possuem propriedades topológicas que seguem leis de potência? Por que a semelhança entre sistemas tão distintos? Quais são as implicações destas propriedades no sistema em questão? Redes Complexas surge como uma área cujos objetivos são caracterizar e compreender este abrangente fenômeno.

Introdução e motivação. Redes tecnológicas, biológicas e sociais. Propriedades topológicas. Leis de potência e redes livre de escala. Processo de ramificação. Modelo G(n,p) e suas propriedades. Geração de grafos aleatórios. Modelos para redes complexas. Modelo preferencial attachment (BA). Modelo small-world (WS). Aplicações em redes tecnológicas e redes sociais. Navegabilidade em redes sociais. Modelos temporais e evolucionários.

• Todos os alunos devem se inscrever na lista de email abaixo para receber avisos importantes (dia/horário das provas, dúvidas gerais, etc). A lista deve ser usada por todos como fórum para discussão.
• Para se inscrever na lista, envie uma mensagem para rc-2011-join@land.ufrj.br sem nada no assunto ou no corpo da mensagem. Depois confirme sua inscrição através da mensagem que você irá receber do servidor da lista.

Aula	Data	Comentário	Slides	Leitura/Tarefa
E1	10/08	Logística, motivação, exemplos, TED Talk (Christakis)	aula_0.pdf	Ler artigos da Scientific American (2003) e Science (2009).
E2	22/08	Apresentação de artigos de divulgação científica. "Scale-free networks" por Rodolfo Carvalho; "Scale-free networks: A Decada em Beyond" por Gabriel Mendonça	Slides Rodolfo Slides Gabriel	Entregar resumos dos artigos (impresso).
E3	24/08	Discussão sobre importância de vértices, discussão sobre trabalho prático.	aula_E-3.pdf	Começar trabalho prático. Ler artigo sobre "Dark Networks".
E4	31/08	Apresentação dos artigos sobre "Dark Networks" por Rafael Romeiro.	Slides Rafael	Entregar resumo, começar trabalho prático.
-	7/09	Feriado nacional: Dia da Independência do Brasil		Fazer trabalho prático.
E5	14/09	Rede neurais, connectome, vídeos do Prof. Sebastian Seung e do Jeff Hawkins. Discussão dos trabalhos práticos em andamento.	Ver links para vídeos abaixo.	Terminar trabalho prático
E6	21/09	Professor visitante (virtual). Aula do Prof. Don Towsley, transmitida ao vivo via Skype, diretamente da disciplina de "Network Science" sendo oferecida na UMass (horário excepcional: 11:15 - 12:30). Tema: Centralidade em redes.	ch7.pdf	Terminar trabalho prático
E7	28/09	Apresentação dos trabalhos práticos. Estudo do processo de formação de cidades no espaço (Gabriel + Rafael); Estudo do processo de remoção de vértices na rede da Internet (Rodolfo).		Fim da esquenta!
1	03/10	Logística, organização, programação da disciplina. Introdução ao tema, redes por todos os lados, exemplos e a importância da estrutura.	aula_0.pdf aula_1.pdf	Ler o artigo da Science 2009 (ver Introdução Geral)
2	05/10	Classes de redes, falando sobre redes, matriz de adjacência, propriedades estruturais, grau, distância, clusterização.	aula_2.pdf	Ler seções 7.1, 7.2, 7.3.1-4 do capítulo do livro do JAI. Saiu lista 1
-	10/10	Não teremos aula. Professor estará participando de um Workshop internacional na área de Redes de Computadoresi. Ver aula de reposição abaixo.		Ler seções 7.1, 7.2, 7.3.1-4 do capítulo do livro do JAI. Fazer lista 1
-	12/10	Feriado nacional: Dia de Nossa Senhora Aparecida, padroeira do Brasil.		Fazer trabalho parte 2.
3	13/10	[Aula de reposição: 8h, sala H304] Características de redes reais, centralidade, betweeness, closeness	aula_3.pdf	Entregar lista 1
4	17/10	Centralidade de autovalor, Katz, PageRank, passeios aleatórios, centralidade de RW	aula_4.pdf	Saiu lista 2. Pensar no projeto. Leitura: "Eigenvector-like measures of centrality" Seções 1-4, e livro do Newman Capítulo 7.
5	19/10	Padrões de mixagem (mixing patterns), correlação entre graus, simularidade entre vértices, clusterização	aula_5.pdf	Fazer lista 2. Fazer leitura: "The structure and function of complex networks", Part III, Sections A,B,C,E,F,G
6	24/10	Lei de potência, distribuição Zeta, propriedades, distribuição Zipf, exemplos	aula_6.pdf	Fazer lista 2 e leitura: "Power laws, Pareto distributions and Zipf's law", Seções I, II e III
7	26/10	Distribuição de Pareto, medindo lei de potência, estimando parâmetros	aula_7.pdf	Fazer lista 2 e leitura: "Power laws, Pareto distributions and Zipf's law", Seções I, II e III
8	31/10	Lei de potência na prática, distribuição log-normal, introdução a processos de ramificação, modelo de projetos	aula_8.pdf	Leitura: "Power laws, Pareto distributions and Zipf's law", Seções I, II e III
-	2/11	Feriado nacional: Dia de Finados.		Definir projeto. Saiu lista 3. Fazer leitura!
9	7/11	Modelo de Galton-Watson, propriedades e extinção sumária, análise de criticalidade. Apresentação de proposta de projeto.	aula_9.pdf	Fazer lista 3
10	9/11	Modelo de Galton-Watson, análise do caso supercrítico.	aula_10.pdf	Fazer lista 3. Leitura: Capítulo do livro do JAI, seções 7.4, 7.4.1, 7.4.2
-	14/11	Enforcado pelo Feriado Nacional: Dia da Proclamação da República do Brasil		Fazer lista 3. Leitura: Capítulo do livro do JAI, seções 7.4, 7.4.1
-	16/11	Não teremos aula. Professor visitando o EPFL para trabalhar com o Prof. Matthias Grossglauser em tema relacionado a Redes Complexas.		Terminar lista 3. Trabalhar no projeto.
11	21/11	Modelos de redes, grafos aleatórios, modelo G(n,p), propriedades	aula_11.pdf	Leitura: Capítulo do livro do JAI, seções 7.4.2
12	23/11	Modelo G(n,p), threshold functions, propriedades estruturais	aula_12.pdf	Leitura: Capítulo do livro do JAI, seções 7.4.2. Leitura opcional: "Networks out of Control" por M. Grossglauser e P. Thiran, Capítulo 9.
13	28/11	Aplicando o modelo G(n,p), problemas, preferential attachment, modelo BA, distribuição de grau.	aula_13.pdf	Leitura: Capítulo do livro do JAI, seção 7.4.3, artigo "Emergence of scaling in random networks" de Barabási e Albert.
14	30/11	Experimento de Milgram, modelo small world, propriedades.	aula_14.pdf	Leitura: Capítulo do livro do JAI, seção 7.4.4, artigo "Collective dynamics of "small-world" networks" de Watts e Strogatz
15	5/12	Resilience ("robustez"), falha aleatória, falha determinística, influência da estrutura	aula_15.pdf	Saiu lista 4. Leitura: JAI: seção 7.5, 7.5.1, artigo "Error and attack tolerance of complex networks"
16	7/12	Busca com informação, navigabilidade em redes, navigabilidade em Redes Sociais.	aula_16.pdf	Leitura: JAI: seção 7.5.2, artigo "The small-world phenomenon: An algorithmic perspective", opcional "Geographic Routing in Social Networks".
17	12/12	Redes dinâmicas. Apanhado final, discussão, dúvidas, avaliação.	EPFL-DynGraphs.pdf aula_17.pdf	Leitura: JAI: seção 7.6, opcional "Characterizing continuous-time random walks on dynamic networks"
18	14/12	Prova única às 13h, pontualmente. Rever todas as listas e todas as leituras em preparação para a prova.		Entregar lista 4.
19	19/12	Entrega e apresentação dos trabalhos. Horário das 13h - 17h, com pausa para o café! Cada grupo terá 20 minutos para apresentar.

• Primeira Lista de Exercícios - Entrega 13/10
• Segunda Lista de Exercícios - Entrega 31/10
  Redes a serem utilizadas nesta lista:
  • Yeast: protein-protein interaction network in budding yeast
  • US Corporate Ownership (directed network).
  • Jazz Musicians Network.
  • Political blogs (directed network).
• Terceira Lista de Exercícios - Entrega 21/11

  Datasets a serem utilizados nos exercícios desta lista:
  Samples 1
  Samples 2
  Samples 3

• Quarta Lista de Exercícios - Entrega 14/12

• Trabalho da Esquenta (ver slides da aula E3) - Entrega e apresentação: 28/09


• Grafos a serem usados nos estudos de caso do trabalho:
  
  
  • Grafo dos Sistemas Autônomos que formam a Internet: as_graph.txt
    Veja detalhes sobre o AS graph em BGP Routing Table Analysis Reports.

• Prova única: 14/12 às 13h pontualmente

Introdução Geral
• A.-L. Barabási, E. Bonabeau, Scale-free networks. Scientific American 288, 60-69 (2003).
• Special Issue: Complex Systems and Networks Science, Vol. 325, Issue 5939, Pages 357-504 (2009).
  Em particular, o artigo "Scale-Free Networks: A Decade and Beyond".

Aspectos relacionados e gerais
• Nicholas Christakis, The hidden influence of social networks, TED Talk, 2010.
• James Hendler, Nigel Shadbolt, Wendy Hall, Tim Berners-Lee, Daniel Weitzner, Web Science: An Interdisciplinary Approach to Understanding the Web Communications of the ACM Vol. 51 No. 7, 2008.
• Jennifer Xu, Hsinchun Chen, The topology of Dark Networks. Communications of the ACM, Vol. 51, 2008.
• Valdis Krebs, Uncloaking Terrorist Networks. First Monday, Volume 7 Number 4 - 1 April 2002.
• Sebastian Seung, I am my connectome, TED Talk, 2010. Human Connectome Project.
• Jeff Hawkins, On how brain science will change computing, TED Talks, 2003. Redwood Center for Theoretical Neuroscience.
• MIT 150 Symposium: Brains, Minds and Machines, May 2011 (several interesting talksin different panels).

Surveys e Métricas
• R. Albert, A.-L. Barabási, Statistical mechanics of complex networks. Reviews of Modern Physics 74, 47-97 (2002).
• M. E. J. Newman, The structure and function of complex networks. SIAM Review 45, 167-256 (2003).
• Daniel R. Figueiredo, Introdução a Redes Complexas. Jornada de Atualização em Informática (JAI), 2011.
• Massimo Franceschet, PageRank: Standing on the Shoulders of Giants. Communications of the ACM, Vol. 54 No. 6 (2011).
• Phillip Bonacich, Paulette Lloyd, Eigenvector-like measures of centrality for asymmetric relations. Social Networks, Vol 23, Issue 3, July 2001.

Lei de potência
• M. E. J. Newman, Power laws, Pareto distributions and Zipf's law. Contemporary Physics 46, 323-351 (2005)
• M. Mitzenmacher, A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, Vol 1, No. 2, pp. 226-251, 2004.

Preferential Attachment

• A.-L. Barabási, R. Albert, Emergence of scaling in random networks, Science 286, 509-512 (1999).
• G. Bianconi, A.-L. Barabási, Competition and multiscaling in evolving networks, Europhysics Letters 54, 436-442 (2001).

Small World

• Jeffrey Travers and Stanley Milgram, An Experimental Study of the Small World Problem, Sociometry, Vol. 32, No. 4. (Dec., 1969), pp. 425-443.
• Duncan J. Watts and Steven H. Strogatz, Collective dynamics of "small-world" networks, Nature, 393:440-442 (1998).
• P. S. Dodds, R. Muhamad, and D. J. Watts, An experimental study of search in global social networks, Science, 301, 827-829 (2003).
• M. E. J. Newman and D. J. Watts, Scaling and percolation in the small-world network model, Phys. Rev. E 60, 7332-7342 (1999).

Aplicações -- Resiliência

• R. Albert, H. Jeong, A.-L. Barabási, Error and attack tolerance of complex networks, Nature 406, 378-482 (2000).
• Reuven Cohen, Keren Erez, Daniel ben-Avraham, and Shlomo Havlin, Resilience of the Internet to Random Breakdowns, Phys. Rev. Lett. 85, 4626-4628 (2000).

Aplicações -- Busca em redes

• Lada A. Adamic, Rajan M. Lukose, Bernardo Huberman and Amit R. Puniyani, Search in Power-Law Networks, Phys. Rev. E, 64 46135 (2001).
• Jon Kleinberg, The small-world phenomenon: An algorithmic perspective, Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000.
• Jon Kleinberg, Navigation in a Small World, Nature 406 (2000), 845.
• David Liben-Nowell, Jasmine Novak, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins, Geographic Routing in Social Networks, Proc. of the National Academy of Sciences (PNAS), 102(33):11623-11628, August 2005.

• M. E. J. Newman, A.-L. Barabási, and D. J. Watts, The Structure and Dynamics of Networks. Princeton University Press, 2006.
• Mark Newman, Networks: An Introduction. Oxford University Press, 2010.
• Alain Barrat, Marc Barthélemy, Alessandro Vespignani, Dynamical Processes on Complex Networks. Cambridge University Press, 2008.
• S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: From biological networks to the Internet and WWW. Oxford University Press, 2003.

• Wikipedia: "Complex Networks" (e links relacionados).
• Você pode pesquisar por livros no acervo da UFRJ.

Livros de interesse geral sobre redes complexas (não técnicos)

• Duncan J. Watts, Six Degrees: The Science of a Connected Age. W. W. Norton & Company, 2003.
• Albert-László Barabási, Linked: How Everything Is Connected to Everything Else and What It Means by. Plume, 2003.
• Nicholas A. Christakis and James H. Fowler, Connected: The Surprising Power of Our Social Networks and How They Shape Our Lives Little, Brown and Company, 2009.