Redes Complexas PESC/COPPE/UFRJ COPPE CPS765 - 2018/3 ECI COS010 - 2018/2

Retirado do Visual Complexity Website (Internet Mapping project)

• Daniel R. Figueiredo

• Sala H-304A - CT, Bloco H, terceiro andar
• Dia/horário: segundas e quartas, das 15h às 17h

• Guilherme da Costa Sales - gcsales@cos.ufrj.br
• Horário de atendimento: Segundas, 13:30 às 14:30, ou por email
• Local: Sala I-246 (CT, Bloco I, segundo andar), tocar campainha (Carol)

O objetivo desta disciplina é explorar como artefatos sociais, tecnológicos e naturais estão conectados e o significado desta conectividade para os diferentes processos que operam nestas redes. Iremos estudar características estruturais de redes reais identificando algumas de suas propriedades recorrentes, como distribuições de cauda pesada nos graus. Apresentaremos modelos matemáticos para representar redes reais capazes de capturar suas propriedades. Estudaremos processos como robustez e fragilidade perante falhas estruturais, busca por informação ou por pessoas, e disseminação de informação, rumores, ou epidemias. Por fim, iremos elucidar como estrutura e funcionalidade estão atreladas na formação de redes.

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 alunos devem se inscrever na Lista de Email de Redes Complexas. A lista será utilizada para avisos e discussão em geral. Alunos também podem (e devem) contribuir para a lista, tanto com perguntas como com respostas.

Aula	Data	Comentário	Slides	Leitura/Tarefa
1	6/8	Logística, regras do jogo, programação. Motivação, redes por todos os lados, redes complexas	aula_0.pdf aula_1.pdf	Fazer resumos 1 e 2
-	8/8	Não teremos aula		Fazer resumos 1 e 2
2	13/8	Discussão das palestras, conceitos, medidas, e modelagem matemática		Entregar resumos 1 e 2
-	15/8	Não teremos aula		Fazer resumos 2 e 3
3	20/8	Discussão das palestras, conceitos, medidas, e modelagem matemática		Entregar resumos 2 e 3
-	22/8	Não teremos aula		Fazer resumo 5
4	27/8	Discussão do capítulo de livro, aplicações, características, "network science"		Entregar resumo 5
-	29/8	Não teremos aula		Fazer trabalho prático 1
5	3/9	Discussão do trabalho prático 1 (prepare-se para falar sobre seu trabalho)		Entregar trabalho prático 1
-	5/9	Não teremos aula
1	10/9	Logística, regras do jogo, programação. Motivação, redes por todos os lados, redes complexas	aula_0.pdf aula_1.pdf	Fazer resumos 1,2,3,4
2	12/9	Falando sobre redes, características estruturais, grau, distância e clusterização	aula_2.pdf	Fazer resumos 1,2,3,4
3	17/9	Características de redes reais, aspectos frequentes, medindo centralidade, betweeness, closeness	aula_3.pdf	Entregar resumos 1,2,3,4
4	19/9	Medindo centralidade recursivamente, autovetor, Katz, pagerank, passeios aleatórios (RW)	aula_4.pdf	Saiu trabalho prático 1. Saiu lista 1.
5	24/9	Padrões de mixagem, correlação entre vizinhos, similaridade entre vértices	aula_5.pdf	Fazer trabalho prático 1 e lista 1
6	26/9	Lei de potência, distribuição Zeta, propriedades, distribuição Zipf	aula_6.pdf	Fazer lista 1, entregar trabalho prático 1
7	1/10	Distribuição de Pareto, visualizando lei de potência, estimando parâmetros (MLE), exemplos. Modelos de projetos para a disciplina	aula_7.pdf modelos_projetos.pdf	Fazer lista 1
-	3/10	Não teremos aula. Pensar na proposta de trabalho para disciplina		Terminar lista 1
8	8/10	Modelos de redes, grafos aleatórios, modelo G(n,p), propriedades	aula_8.pdf	Entregar lista 1
9	10/10	Threshold functions, subgrafos, tamanho de componente conexas, distâncias, conectividade, assimetria	aula_9.pdf	Começar proposta
-	15/10	Não teremos aula. Professor atuando como avaliador externo da 17a. Jornada de Iniciação Científica da UNIRIO. Trabalhar na proposta de trabalho para disciplina		Fazer proposta
10	17/19	Aplicando o modelo G(n,p), problemas, preferential attachment, modelo BA, distribuição de grau The Barabási-Alberst Model, pelo próprio Barabási (capítulo 5 do seu livro)	aula_10.pdf	Fazer proposta
-	22/10	Não teremos aula. Professor participando do Encontro Nacional de Inteligência Artificial e Computacional - ENIAC 2018. Trabalhar na lista 2 e na proposta de trabalho para disciplina		Saiu lista 2. Fazer proposta
-	24/10	Não teremos aula. Professor participando do Encontro Nacional de Inteligência Artificial e Computacional - ENIAC 2018. Trabalhar na lista 2 e na proposta de trabalho para disciplina		Fazer lista 2. Fazer proposta
11	29/10	Entrega e apresentação de proposta de projeto para a disciplina.	Ver detalhes abaixo	Fazer lista 2
12	31/10	Experimento de Milgram, outros experimentos, modelo Small World, propriedades.	aula_12.pdf	Fazer lista 2, começar projeto
13	5/11	Modelos baseado em sequência de graus, modelo com comunidades (SBM)	aula_13.pdf	Fazer lista 2
-	7/11	Não teremos aula.		Terminar lista 2
14	12/11	Busca em redes, busca com informação, navigabilidade em redes, modelo de Kleinberg	aula_14.pdf	Entregar lista 2
15	14/11	Falhas em redes, robustez, influência da estrutura, ponto crítico	aula_15.pdf	Saiu lista 3
-	19/11	Feriado (enforcado): Dia da Consciência Negra, 20/11		Fazer projeto, lista 3
16	21/11	Partição e bisseção em grafos, ratio cut, modularidade, Algoritmos de Newman e Louvain, limitações	aula_16.pdf	Fazer projeto, lista 3
-	26/11	Não tivemos aula (professor doente)		Fazer projeto, lista 3
17	28/11	Epidemia em redes, modelos epidemiológicos, ponto crítico	aula_17.pdf	Fazer projeto, lista 3
18	3/12	Apanhado final, futuro em redes, redes dinâmicas, dúvidas.	aula_18.pdf	Fazer projeto, lista 3
19	5/12	Prova única com duas horas de duração. Rever listas, refazer leituras, rever trabalhos práticos.		Entregar lista 3
20	10/12	Workshop para apresentação dos projetos (15' cada grupo). Aula de 15h às 19h com pausa café e bolo!		Entregar relatório (projeto)

• Os resumos de palestras e artigos devem ter no máximo uma página e devem identificar as principais ideias apresentadas. Você deve também identificar se tais ideias podem ser aplicadas em outros contextos, corroboradas utilizando outros procedimentos empíricos, ou mesmo refutadas (dê sua opinião). O objetivo dos resumos é ajudar a você refletir sobre as ideias sendo transmitidas.

• Resumo 1 - Entrega 13/8 - PESC: 17/9
  • Assistir ao TED Talk The hidden influence of social networks do Nicholas Christakis. Você pode consultar o livro Connected ou ainda aos artigos científicos de co-autoria de Christakis ou Fowler que serviram como base para a palestra, como os seguintes:
  • J.H. Fowler and N.A. Christakis, "Cooperative Behavior Cascades in Human Social Networks," PNAS: Proceedings of the National Academy of Sciences 107(12): 5334-5338 (March 2010)
  • A.L. Hill, D.G. Rand, M.A. Nowak, and N.A. Christakis, "Infectious Disease Modeling of Social Contagion in Networks," PLoS Computational Biology 6(11): e1000968 (November 2010);
  • N.A. Christakis and J.H. Fowler, "The Spread of Obesity in a Large Social Network Over 32 Years," New England Journal of Medicine 357(4): 370-379 (July 2007)
• Resumo 2 - Entrega 13/8 - PESC: 17/9
  • Assistir ao TED Talk I am my connectome do Sebastian Seung. Você pode consultar o livro Connectome ou ainda os artigos científicos introdutórios de Seung que serviram como base para a palestra, como os seguintes:
  • S. Seung, Connectomics: Tracing the Wires of the Brain, Dana Foundation, 2008.
  • S. Seung, Towards functional connectomics, Nature, 2011.

• Resumo 3 - Entrega 20/8 - PESC: 17/9
  • Assistir ao TEDMED Talk Do your proteins have their own social network? do Albert Barabási. Você pode consultar o livro Linked ou ainda aos artigos científicos introdutórios de co-autoria de Barabási que serviram como base para a palestra, como os seguintes:
  • J. Loscalzo, A.-L. Barabási, Systems biology and the future of medicine, WIREs Systems Biology and Medicine 3, 619-627 (2011)
  • M. Vidal, M. E. Cusick, A.-L. Barabasi, Interactome Networks and Human Disease, Cell 144, 986-995 (2011)
• Resumo 4 - Entrega 20/8 - PESC: 17/9
  • Assistir ao TED Talk Who controls the world? do James B. Glattfelder. Você pode consultar sua tese de doutorado ou ainda artigos científicos decorrentes que serviram como base para a palestra, como os seguintes:
  • S Vitali, JB Glattfelder, S Battiston, "The network of global corporate control", PloS one 6 (10), 2011
  • J.B. Glattfelder, S. Battiston, "Backbone of complex networks of corporations: The flow of control"; Phys. Rev. E 80, 1 (2009).

• Resumo 5 - Entrega 27/8
  • Ler o primeiro capítulo do livro texto, Network Science, do Albert László Barabási, dando foco às diferentes aplicações que são apresentadas. Opcional: ler o Capítulo 0, no qual Barabási conta um pouco do início de sua própria trajetória com redes.

• Primeira Lista de Exercícios - Entrega 8/10
• Segunda Lista de Exercícios - Entrega 12/11
• Terceira Lista de Exercícios - Entrega 3/12 - adiada para 5/12

• Trabalho 1 - Caracterizando redes com o graph-tool - Entrega 3/9 - PESC: 26/09

  Nesta tarefa você deve instalar e se familiarizar como graph-tool que é um módulo Python (eficiente) para manipular e analisar redes, ou algum outro software para manipular redes, como o NetworkX ou o Gephi que é uma excelente ferramenta para desenhar redes. Você deve escolher ao menos três redes disponíveis nos repositórios abaixo ou em outros repositórios (e não apenas as redes disponíveis no graph-tool), e caracterizá-las utilizando algumas diferentes métricas (como grau, distância, clusterização, tamanho das componentes conexa, entre outras). Para cada métrica, calcule as seguintes estatísticas: máximo, mínimo, média, desvio padrão, e trace a distribuição empírica (esta última apenas para o grau).

  • Stanford Large Network Dataset Collection
  • The UCI Network Data Repository
  • Mark Newman's Network data repository
  • Datasets - Network Science Textbook by Barabási

  Você deve preparar um pequeno relatório (duas páginas) com seus resultados e uma breve discussão do observado.

• Proposta de projeto: Proposta e apresentação: 29/10 (segunda)
  Você deve entregar uma proposta de projeto com no máximo 2 páginas descrevendo precisamente o que será o seu projeto, que deve ser realizado em dupla. Você deve utilizar um dos modelos de projetos (ver aula) para ajudar a determinar exatamente o que você vai investigar. Você deve preparar uma apresentação de 10 minutos sobre sua proposta (a ser apresentada em dupla).
• Datasets que podem ser utilizados em projetos:
  • Stanford Large Network Dataset Collection
  • Public Data Sets on Amazon Web Services
  • Mark Newman's Network data repository
  • Datasets - Network Science Textbook by Barabási
  • Yahoo Webscope Program
  • The ClueWeb09 Dataset
  • Open Street Map
  • The UCI Network Data Repository
  • DBLP Computer Science Bibliography
  • Wikipedia

• Projeto finalizado: Relatório e apresentação: 10/12 (segunda), das 15h às 19h
  Você deve preparar uma apresentação de 15 minutos sobre seu projeto, relatando a motivação, o problema, o trabalho realizado e o que foi encontrado. Você deve também entregar um relatório com no máximo 8 páginas, utilizando o modelo de artigos (template) da SBC, relatando a motivação, o problema investigado, o trabalho executado e o que foi encontrado.

  Resultado da votação da turma no melhor trabalho. Parabéns ao João Bertolino e Roberto Pacheco pelo trabalho mais votado (com oito votos)!

• Prova única: 3/12 - adiada para 5/12 (quarta), 15h (pontualmente), sem consulta, 2h de duração.

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 talks in 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.

Aplicações -- Epidemia

• Romualdo Pastor-Satorras and Alessandro Vespignani, Epidemic Spreading in Scale-Free Networks, Phys. Rev. Lett. 86, 3200-3203 (2001).
• Duygu Balcana, Vittoria Colizza, Bruno Gonçalves, Hao Hu, José J. Ramasco and Alessandro Vespignani, Multiscale mobility networks and the spatial spreading of infectious diseases, Proc. Nat. Acad. Sci. (PNAS), vol. 106 no. 51 21484-21489 (2009).

• Albert-László Barabási, Network Science. Cambridge University Press, 2015.
• Mark Newman, Networks: An Introduction. Oxford University Press, 2010.
• M. E. J. Newman, A.-L. Barabási, and D. J. Watts, The Structure and Dynamics of Networks. Princeton University Press, 2006.
• 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).
• Wikipedia: "Network Science" (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.