Redes Complexas PESC/COPPE/UFRJ CPS765 - 2020/2

Retirado do Visual Complexity Website (Genetic Interaction Network)

• Daniel Ratton Figueiredo

• Dia/horário: terças e quintas, das 15h às 17h
• Sala virtual: https://meet.google.com/cww-nswv-kqg

• Ronald Chiesse de Souza - rcsouza [AT] cos ufrj br
• Horário de atendimento: sob demanda (enviar mensagem)

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.

• Todos precisam se inscrever no Moodle da discilina. O código de acesso para inscrição é codigo765

• Iremos utilizar o Moodle para troca de mensagens e avisos, e entrega de listas e trabalhos.

Aula	Data	Comentário	Slides	Vídeos (D = Discussão)	Tarefa
1	13/10	Logística, regras do jogo, programação das aulas. Motivação, redes por todos os lados, o que é redes complexas	aula_0.pdf aula_1.pdf	Aula 0 - Aula 0D Aula 1 - Aula 1D	Fazer resumos 1, 2, 3
2	15/10	Falando sobre redes, características estruturais: grau, distância, e clusterização, características frequentes de redes reais	aula_2.pdf	Aula 2_1 - Aula 2_1D Aula 2_2 - Aula 2_2D	Fazer resumos 1, 2, 3
3	20/10	Medindo centralidade, betweeness, closeness, autovetor, Katz, pagerank, personalized pagerank	aula_3.pdf	Aula 3_1 - Aula 3_1D Aula 3_2 - Aula 3_2D	Entregar resumos 1, 2, 3. Saiu lista 1
4	22/10	Padrões de mixagem, homofilia, correlação entre vizinhos, similaridade entre vértices	aula_4.pdf	Aula 4_1 - Aula 4_1D Aula 4_2 - Aula 4_2D	Fazer resumos 4, 5, 6. Saiu trabalho prático 1
5	27/10	Lei de potência, distribuição Zeta, propriedades, distribuição Zipf	aula_5.pdf	Aula 5_1 - Aula 5_1D Aula 5_2 - Aula 5_2D	Fazer lista 1, trabalho prático 1
6	29/10	Distribuição de Pareto, visualizando lei de potência, estimando parâmetros (MLE), exemplos, Lognormal	aula_6.pdf	Aula 6_1 - Aula 6_1D Aula 6_2 - Aula 6_2D	Entregar resumos 4, 5, 6
7	3/11	Modelos de redes, grafos aleatórios, modelo G(n,p), propriedades	aula_7.pdf	Aula 7_1 - Aula 7_1D Aula 7_2 - Aula 7_2D	Entrega TP 1
8	5/11	Threshold functions, subgrafos, tamanho de componente conexas, distâncias, conectividade, assimetria Modelos de projeto para a disciplina	aula_8.pdf modelos_projetos.pdf	Aula 8_1 - Aula 8_1D Aula 8_2 - Aula 8_2D Aula 8_3	Saiu lista 2
9	10/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) Animação do modelo BA em ação	aula_9.pdf	Aula 9_1 - Aula 9_1D Aula 9_2 - Aula 9_2D	Entregar lista 1
10	12/11	Experimento de Milgram, outros experimentos, modelo Small World, propriedades.	aula_10.pdf	Aula 10_1 - Aula 10_1D Aula 10_2 - Aula 10_2D	Fazer lista 2
11	17/11	Modelos baseado em sequência de graus, modelo com comunidades (SBM)	aula_11.pdf	Aula 11_1 - Aula 11_1D Aula 11_2 - Aula 11_2D	Fazer lista 2
-	19/11	Monitoria com o Ronald no horário da aula (ver link)			Fazer lista 2
12	24/11	Entrega e apresentação da proposta de projeto para a disciplina		Aula 12_1 Chat 12_1	Entregar proposta
-	26/11	Monitoria com o Ronald no horário da aula (ver link)			Fazer lista 2
13	1/12	Busca em redes, busca com informação, navigabilidade em redes, modelo de Kleinberg	aula_13.pdf	Aula 13_1 - Aula 13_1D Aula 13_2 - Aula 13_2D	Entregar lista 2
14	3/12	Falhas em redes, robustez, influência da estrutura, ponto crítico Animação de falhas aleatórias e ataques direcionados, e muitos outros detalhes!	aula_14.pdf	Aula 14_1 - Aula 14_1D Aula 14_2 - Aula 14_2D	Fazer projeto
15	8/12	Partição e bisseção em grafos, ratio cut, modularidade, Algoritmos de Newman e Louvain, limitações	aula_15.pdf	Aula 15_1 - Aula 15_1D Aula 15_2 - Aula 15_2D	Saiu lista 3
-	10/12	Possível monitoria com o Ronald no horário da aula (ver link)			Fazer lista 3
16	15/12	Epidemias, modelos epidemiológicos, epidemia em redes, criticalidade em função da estrutura	aula_16.pdf	Aula 16_1 - Aula 16_1D Aula 16_2 - Aula 16_2D	Fazer projeto, lista 3
17	17/12	Iniciando uma epidemia, identificando a origem de uma epidemia, efeitos da proteção local na epidemia	aula_17.pdf	Aula 17_1 - Aula 17_1D Aula 17_2 - Aula 17_2D	Fazer projeto, lista 3
18	22/12	Apanhado final, futuro em redes, redes dinâmicas, dúvidas, avaliação	aula_18.pdf	Aula 18_1 - Aula 18_1D	Fazer projeto, lista 3
-	24/12	Início do recesso de final de ano			Fazer lista 3
-	5/01	Monitoria com o Ronald no horário da aula (ver link)			Fazer lista 2
19	7/01	Prova única com duas horas de duração. Rever listas, resumos, e trabalho prático.		Aula 19	Entregar lista 3
-	12/01	Não teremos aula. Terminar projeto (relatório e apresentação)			Fazer lista 2
20	14/01	Workshop de apresentação dos projetos (15' cada grupo). Aula de 15h às 19h e votação do melhor trabalho (ver abaixo o resultado)		Aula 20	Entregar relatório (projeto), dia 19

• 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é o final do dia de entrega. Resumos entregues com atraso serão penalizadas em 10% ao dia.

• Resumo 1 - Entrega: 20/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: 20/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: 20/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: 27/10
  • 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/10
  • 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: 27/10
  • 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

• Primeira Lista de Exercícios - Entrega: 5/11 - adiada para 10/11
• Segunda Lista de Exercícios - Entrega: 24/11 - adiada para 1/12
• Terceira Lista de Exercícios - Entrega: 07/01

• Trabalho 1 - Caracterizando redes - Entrega: 3/11

  Nesta tarefa você deve instalar e se familiarizar com alguma biblioteca de análise de redes, como graph-tool, NetworkX, igraph. Você deve escolher ao menos quatro redes disponíveis nos repositórios abaixo (ou outros repositórios), e caracterizá-las utilizando diferentes métricas, como grau, distância, tamanho das componentes conexas, e outras (você pode escolher as 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 com as diferentes redes).

  • The Colorado Index of Complex Networks (ICON) (muitas redes)
  • "Awesome public datasets" (apenas alguns são redes)
  • Stanford Large Network Dataset Collection
  • The UCI Network Data Repository
  • Mark Newman's Network data repository
  • Datasets - Network Science Textbook by Barabási

  Prepare um pequeno relatório (quatro páginas, no máximo) com seus resultados (tabelas e gráficos), e uma breve discussão do que foi observado.

• Proposta de projeto: Entrega: 19/11 - adiada para 24/11
  

• Projeto finalizado: Apresentação: 14/01 (quinta), das 15h às 19h - Relatório : 19/01 (terça)

  Você deve preparar uma apresentação de no máximo 12 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 de 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.

  Iremos votar no melhor trabalho (juri popular) no dia da apresentação!

  Parabéns à Nathalie Deziderio e Vinícius da Costa pelo trabalho mais votado!
  1- Daniel e Amanda (classificação da inclinação política de senadores)
  2- Fábio (ranqueamento de agências financeiras baseado em compra/venda)
  3- Diego (simulação do espalhamento de notícia em redes sociais)
  4- Cleiton e Santoro (caracterização da rede de municípios relacionados por covid)
  5- Nathalie e Vinicius (datação, expressão e sinônimos em obras literárias)
  6- Caio (caracterização das redes de instrumentistas)
  7- Luis Armando e Vitor (caracterização da rede de aeroportos nos EUA)
  8- Luiz Cláudio (classificação do tipo de rede a partir da estrutura via redes neurais)
  9- Rodrigo (rede de empresas em licitação e detecção de comunidades)
  10- Renan e Ary (caracterização da rede de fundos de investimento)
  11- Felipe (caracterização da rede de diretores de empresas, assortatividade)
  12- Bruno e Pedro (caracterização de rede de músicas baseadas em acordes)
  

• Prova única: 7/01 (quinta), 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.