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

Retirado do Visual Complexity Website (Genetic Interaction Network)

• Daniel Ratton Figueiredo

• Dia/horário: segundas e quartas, das 15h às 17h
• Sala H-304B

• Rodrigo Luna - rluna [AT] cos.ufrj.br
• Horário de atendimento: sob demanda (grupo no telegram ou email)

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.

• Se inscrever no Moodle da discilina. O código de acesso para inscrição é codigo765
• Iremos utilizar o Moodle para avisos e entrega de listas e trabalhos.

Aula	Data	Comentário	Slides	Vídeo	Tarefa
-	26/09	Não teremos aula: Reitoria suspende aulas desta manhã			Fazer resumos 1 e 2
1	28/09	Logística, regras do jogo, programação das aulas. Redes, redes por todos os lados, do que se trata redes complexas Falando sobre redes, características estruturais (densidade, graus, distâncias, e clusterização)	aula_0.pdf aula_1.pdf aula_2.pdf	Aula 0 Aula 1 Aula 2	Fazer resumos 1 e 2
2	03/10	Características frequentes de redes reais Medindo centralidade, betweeness, closeness, autovetor, Katz, pagerank, personalized pagerank	aula_2.pdf aula_3.pdf	Aula 2 Aula 3	Entregar resumos 1 e 2. Saiu lista 1 e trabalho prático 1
3	05/10	Padrões de mixagem, assortatividade, correlação de grau, similaridade entre vértices (jaccard, adamic/adar, coseno)	aula_4.pdf	Aula 4	Fazer resumos 3 e 4.
4	10/10	Lei de potência, distribuição Zeta, propriedades, distribuição Zipf, exemplos	aula_5.pdf	Aula 5	Entregar resumos 3 e 4.
-	12/10	Não teremos aula: Feriado nacional do Dia de Nossa Senhora Aparecida (Padroeira do Brasil)			Fazer lista 1
5	17/10	Distribuição de Pareto, visualizando leis de potência, estimando o expoente (MLE), estimando x0, Lognormal, exemplos	aula_6.pdf	Aula 6	Entregar Lista 1
6	19/10	Modelos de redes, grafos aleatórios, modelo G(n,p), propriedades simples	aula_7.pdf	Aula 7	Saiu Lista 2
7	24/10	Modelo G(n,p), funções de threshold, surgimento de subgrafos, componentes conexas, distâncias, automorfismos	aula_8.pdf	Aula 8	Entregar resumos 5 e 6
8	26/10	Aplicando o modelo G(n,p), avaliando o modelo, 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 Projeto	Entregar Trabalho Prático 1
9	31/10	Mundo pequeno, experimento de Milgram, experimentos mais recentes, modelo Small World, propriedades. Modelos de projeto para a disciplina	aula_10.pdf	Aula 10 modelos_projetos.pdf	Fazer lista 2
-	2/11	Feriado Nacional: Dia de Finados			Fazer lista 2
10	07/11	Modelos baseado em sequência de graus, modelo com comunidades (SBM), propriedades, aplicações	aula_11.pdf	Aula 11	Fazer lista 2
11	09/11	Busca em redes, busca com informação, navigabilidade em redes, modelo de Kleinberg, exemplo real	aula_12.pdf	Aula 12	Fazer lista 2
-	14/11	Enforcado pelo Feriado Nacional: Dia da Proclamação da República			Entregar lista 2
12	16/11	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_13.pdf	Aula 13	Saiu lista 3
13	21/11	Partição e bisseção em grafos, ratio cut, modularidade, Algoritmos de Newman e Louvain, limitações	aula_14.pdf	Aula 14	Fazer proposta
14	23/11	Entrega e apresentação da proposta de projeto para a disciplina		Discussão	Entregar proposta
-	28/11	Não teremos aula (ponto facultativo): Jogo do Brasil na Copa do Qatar			Iniciar projeto
15	30/11	Epidemias, modelos epidemiológicos, epidemia em redes, criticalidade em função da estrutura	aula_15.pdf	Aula 15	Fazer projeto, lista 3
-	5/12	Não teremos aula (ponto facultativo): Jogo do Brasil na Copa do Qatar			Iniciar projeto
16	07/12	Apanhado final, caminho trilhado, redes dinâmicas, futuro promissor, avaliação da disciplina. Dúvidas em preparação para a prova	aula_16.pdf	Aula 16	Fazer projeto, lista 3
17	12/12	Prova única com duas horas de duração. Rever listas, resumos, e trabalho prático.			Entregar lista 3
18	21/12	Workshop de apresentação dos projetos (12' cada grupo). Aula às 13h, e votação do melhor trabalho			Relatório dia 23/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é o final do dia de entrega. Resumos entregues com atraso serão penalizadas em 10% ao dia.

• Resumo 1 - Entrega: 03/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: 03/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: 10/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: 10/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: 24/10
  • Assistir ao TED Talk A Visual History of Human Knowledge e ao RSA ANIMATE The Power of Networks ambos 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: 24/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: 17/10 - adiado para 21/10
• Segunda Lista de Exercícios - Entrega: 14/11
• Terceira Lista de Exercícios - Entrega: 12/12

• Trabalho 1 - Caracterizando redes - Entrega: 26/10 - adiado para 28/10

  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 clusterização (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 e apresentação:23/11

  Você deve entregar uma proposta de projeto para a disciplina com no máximo 1 página descrevendo precisamente o que será o seu projeto, que deve ser realizado individualmente. Você deve preparar uma apresentação de 5 minutos sobre sua proposta. Seja conciso e preciso na descrição e apresentação de sua proposta.

• Projeto finalizado: Apresentação: 21/12 às 13h - Relatório: 23/12

  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!

• Prova única: 12/12, 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 -- Robustez

• 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).
• Callaway, D. S., Newman, M. E., Strogatz, S. H., & Watts, D. J. Network robustness and fragility: Percolation on random graphs, Phys. Rev. Lett., 85(25), 5468 (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.

• Remco van der Hofstad, Random Graphs and Complex Networks
• Sebastien Roch, Modern Discrete Probability: An Essential Toolkit

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