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

Retirado do Visual Complexity Website (Internet Mapping project)

• Daniel Ratton Figueiredo

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

• Igor de Oliveira Nunes - ionunes@cos.ufrj.br
• Horário de atendimento: terça das 9h às 11h
• Local: Sala I-246 (CT, Bloco I, segundo andar), tocar no "LAND"

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.

Todos devem se inscrever no Moodle da discilina. Iremos utilizar esta plataforma para troca de mensagens e avisos, e entrega de tarefas (listas e trabalhos). Alunos também podem (e devem) contribuir para a lista, tanto com perguntas como com respostas. O código de acesso para inscrição na disciplina no Moodle é rc2019.

Aula	Data	Comentário	Slides	Leitura/Tarefa
1	5/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
2	7/8	Aula apenas para os alunos que perderam a primeira aula		Fazer resumos 1 e 2
3	12/8	Discussão das palestras, conceitos, medidas de homofilia, modelagem matemática de redes		Entregar resumos 1 e 2
-	14/8	Não teremos aula		Fazer resumos 3 e 4
4	19/8	Discussão das palestras, conceitos, medidas, e modelagem matemática		Entregar resumos 3 e 4
-	21/8	Não teremos aula		Fazer resumo 5 e 6
5	26/8	Discussão das palestras, conceitos, medidas, e modelagem matemática		Entregar resumos 5 e 6
-	28/8	Não teremos aula		Fazer resumo 7
6	2/9	Discussão do capítulo de livro, aplicações, características, "network science"		Entregar resumo 7
-	4/9	Não teremos aula		Fazer resumo 8, e trabalho prático 1
7	9/9	Discussão do capítulo de livro, aplicações, características, "network science"		Entregar resumo 8
-	11/9	Não teremos aula		Fazer trabalho prático 1
8	16/9	Apresentação do trabalho prático (15 minutos cada aluno)		Entregar trabalho prático 1
-	18/9	Não teremos aula
-	23/9	Não teremos aula: Professor participando do Day of Networking Workshop e trabalhando com seus colaboradores Vishal Misra e Dan Rubenstein na Columbia University
-	25/9	Não teremos aula: Professor participando do Day of Networking Workshop e trabalhando com seus colaboradores Vishal Misra e Dan Rubenstein na Columbia University
1	30/9	[Início Pós-Graduação] 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
2	2/10	Falando sobre redes, características estruturais: grau, distância, e clusterização, características frequentes de redes reais	aula_2.pdf	Fazer resumos 1, 2, 3
3	7/10	Medindo centralidade, betweeness, closeness, autovetor, Katz, pagerank, personalized pagerank	aula_3.pdf	Entregar resumos 1, 2, 3. Saiu trabalho prático 1
4	9/10	Padrões de mixagem, homofilia, correlação entre vizinhos, similaridade entre vértices	aula_4.pdf	Fazer trabalho prático 1
5	14/10	Lei de potência, distribuição Zeta, propriedades, distribuição Zipf	aula_5.pdf	Saiu lista 1
6	16/10	Distribuição de Pareto, visualizando lei de potência, estimando parâmetros (MLE), exemplos, Lognormal Modelos de projeto para a disciplina	aula_6.pdf modelos_projetos.pdf	Terminar trabalho prático 1
7	21/10	Discussão sobre passeios aleatórios, cadeias de Markov, distribuição estacionária, e convergência. Discussão das propostas de projeto para disciplina.	aula_7.pdf	Entregar trabalho prático 1
-	23/10	Não teremos aula. Preparar proposta de projeto para disciplina		Fazer lista 1
-	28/10	Não teremos aula. Feriado em função do Dia do Servidor Público		Finalizar proposta
8	30/10	Entrega e apresentação de proposta de projeto para a disciplina		Entregar proposta, fazer lista 1
9	4/11	Modelos de redes, grafos aleatórios, modelo G(n,p), propriedades	aula_9.pdf	Terminar lista 1
10	6/11	Threshold functions, subgrafos, tamanho de componente conexas, distâncias, conectividade, assimetria	aula_10.pdf	Entregar lista 1, saiu lista 2
11	11/11	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_11.pdf	Fazer lista 2
12	13/11	Experimento de Milgram, outros experimentos, modelo Small World, propriedades.	aula_12.pdf	Fazer lista 2
13	18/11	Modelos baseado em sequência de graus, modelo com comunidades (SBM)	aula_13.pdf	Fazer lista 2
-	20/11	Não teremos aula. Feriado em função do Dia da Consciência Negra		Terminar lista 2
14	25/11	Falhas em redes, robustez, influência da estrutura, ponto crítico	aula_14.pdf	Saiu lista 3
15	27/11	Partição e bisseção em grafos, ratio cut, modularidade, Algoritmos de Newman e Louvain, limitações	aula_15.pdf	Entregar lista 2, começar lista 3
16	2/12	Epidemia em redes, modelos epidemiológicos, ponto crítico	aula_16.pdf	Fazer projeto, lista 3
17	4/12	Apanhado final, futuro em redes, redes dinâmicas, dúvidas, avaliação	aula_17.pdf	Fazer projeto, lista 3
-	9/12	Não teremos aula		Terminar lista 3
18	11/12	Prova única com duas horas de duração. Rever listas, refazer leituras, rever trabalhos práticos.		Entregar lista 3
19	16/12	Workshop para apresentação dos projetos (10' cada grupo). Aula das 8:30h às 12:30h na sala H-304A com pausa café e panetone!		Terminar projeto
-	18/12	Não teremos aula. Finalizar relatório do projeto		Entregar relatório dia 20/12

• 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.

  Os resumos devem ser entregue no Moodle da disciplina até às 13h do dia de entrega (antes da aula). Resumos entregues com atraso serão penalizadas em 20% ao dia.

• Resumo 1 - Entrega 11/8 - Pós-Graduação: 07/10
  • 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 11/8 - Pós-Graduação: 07/10
  • 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 18/8 - Pós-Graduação: 07/10
  • 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 18/8
  • 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 25/8
  • Assistir ao TED Talk A Visual History of Human Knowledge do Manuel Lima. Você pode consultar o livro The Book of Trees: Visualizing Branches of Knowledge ou ainda material disponível no website do autor.
• Resumo 6 - Entrega 25/8
  • Assistir ao TED Talk Your social media "likes" expose more than you think da Jennifer Golbeck. Você pode consultar o livro Analyzing the Social Web ou ainda artigos científicos relacionados ao tema da palestra, tais como:
  • Golbeck, J., Robles, C., Turner, K., "Predicting personality with social media", Human Factors in Computing Systems (CHI), 2011
  • DuBois, T., Golbeck, J., Srinivasan, A., "Predicting trust and distrust in social networks. IEEE International Conference on Social Computing, 2011

• Resumo 7 - Entrega 02/9
  • Ler Capítulo 1 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.

• Resumo 8 - Entrega 09/9
  • Ler os seguintes artigos de divulgação científica sobre Redes Complexas, mais recentemente chamada por Ciência das Redes (os artigos podem ser obtidos estando na rede da UFRJ ou através do Porta Periódico CAPES, via intranet da UFRJ):
  • Scale-Free Networks: A Decade and Beyond, por Albert-László Barabási, Science, Jul/2009.
  • Twenty years of network science, por Alessandro Vespignani, Nature, Jun/2018.

• Primeira Lista de Exercícios - Entrega 4/11 - adiada para 6/11
• Segunda Lista de Exercícios - Entrega 25/11 - adiada para 27/11
• Terceira Lista de Exercícios - Entrega 9/12 - adiada para 11/12

• Trabalho 1 - Caracterizando redes com o graph-tool - Entrega e apresentação: 16/9 - Pós-Graduação (apenas entrega): 21/10

  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 quatro 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 diferentes métricas, como grau, distância, tamanho das componentes conexas, e outras (você pode escolher outras). Para cada métrica analisada, calcule as seguintes estatísticas: máximo, mínimo, média, mediana, desvio padrão, e distribuição empírica (faça um gráfico).

  • 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 (quatro páginas) com seus resultados e uma breve discussão do que foi observado, assim como uma apresentação de 15 minutos.

• Proposta de projeto: Proposta e apresentação: 30/10 (quarta)
  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 individualmente ou emn 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 8 minutos sobre sua proposta (a ser apresentada em dupla). Seja conciso e preciso na descrição e apresentação de sua proposta.
• 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:
  Apresentação: 16/12 (quarta) das 8:30h às 12:30
  Relatório: 20/12 (sexta)
  

  Você deve preparar uma apresentação de no máximo 10 minutos sobre seu projeto, relatando a motivação, o problema, o trabalho realizado, e o que foi encontrado (resultados). Você deve também entregar um relatório com no máximo 7 páginas, utilizando o modelo de artigos (template) da SBC, e de preferência usar o Latex (use o Overleaf, que é muito bom).

  Seu relatório deve ter uma introdução, onde você apresenta uma motivação e discute o problema que será investigado; uma seção onde você define mais preisamente o problema e a metodologia que você está utilizando, assim como os dados usados nos experimentos; uma breve discussão de trabalhos relacionados; uma apresentação e discussão dos resultados (o que você encontrou).

  Resultado da votação da turma no melhor trabalho, que teve uma disputa acirrada. Parabéns ao Raul Barbosa pelo trabalho mais votado!

• Prova única: 9/12 (segunda) - adiada para 11/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. 2nd Edition, Oxford University Press, 2018.
• 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.