Tópicos Especiais em Redes Complexas II: Identidade Estrutural UFRJ/COPPE/PESC CPS767 - 2014/1

Six Degrees of Francis Bacon

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

• Sala H-304B -- CT, Bloco H, terceiro andar
• Dia/horário: terças e quintas, das 15h às 17h

Identidade é um conceito fundamental na definição e caracterização de objetos. No contexto de redes, identidade pode ser atribuída em função unicamente da estrutura da rede. Por exemplo, a identidade de um vértice como sendo seu grau na rede. Identidade estrutural aparece em diversas áreas do conhecimento que lidam com fenômenos em redes, tais como Biologia, Física, Sociologia, e Computação. Isto ocorre pois muitos problemas práticos estão relacionados ao problema de atribuir identidade aos vértices da rede. Nesta disciplina iremos estudar como o conceito de identidade estrutural é utilizado em diferentes contextos para resolver diferentes problemas, visando um entendimento unificado do conceito e sua aplicação.

Revisão de modelos e estrutura de redes sociais; equivalência estrutural; similaridade de vértices; anonimidade e privacidade em redes sociais; redes de proteína e gens; emparelhamento estrutural; automorfismo, isomorfismo e homomorfismo em grafos; entropia de grafos; complexidade e algoritmos eficientes.

Esta disciplina será oferecida no formato de seminário. Isto significa que cada encontro (aula) possui um tema específico e um respectivo material didático previamente selecionado (artigos científicos, capítulo de livro, etc). Todos os alunos devem ler e preparar um resumo do material que será apresentado além de participar das discussões. Um ou mais alunos (e ocasionalmente o professor) ficam responsáveis por apresentarem o material e liderarem as discussões.

• Todos devem se inscrever na lista de email abaixo para receber avisos importantes. A lista também será usada por todos como fórum de discussão.

• Para se inscrever na lista, envie uma mensagem para ie-2014-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.

11/3 - Organização, logística e motivação

• aula_1.pdf
  Apresentador: Daniel Figueiredo

13/3 - Revisão de redes socias: características, modelos

• Mark Newman, Networks: An Introduction, 2010
  Chapter 3 - Social Networks
  aula_2.pdf
  Apresentador: Daniel Figueiredo

18/3 - Equivalência estrutural (Sociologia)

• Robert A. Hanneman and Mark Riddle, Introduction to social network methods, 2005
  Chapter 12 - Positions and roles: The idea of equivalence
  Chapter 13 - Measures of similarity and structural equivalence
  Chapter 14 - Automorphic equivalence
  Chapter 15 - Regular equivalence
  Apresentador: Vitor Borges C. da Silva - Slides

25/3 - Equivalência estrutural (Sociologia)

• François Lorrain and Harrison C. White
  Structural equivalence of individuals in social networks
  The Journal of Mathematical Sociology Volume 1, Issue 1 (1971)
  Apresentador: Jefferson E. Simões - Slides

• Lee Douglas Sailer
  Structural equivalence: Meaning and definition, computation and application
  Social Networks, Volume 1, Issue 1 (1978)
  Apresentador: Jefferson E. Simões - Slides

• Patrick Doreian and Thomas J. Fararo,
  Structural equivalence in a journal network
  Journal of the American Society for Information Science, Volume 36, Issue 1 (1985)
  Opcional

1/4 - Similaridade estrutural entre vértices

• Vincent D. Blondel, Anahí Gajardo, Maureen Heymans, Pierre Senellart, and Paul Van Dooren,
  A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
  SIAM Review, 46(4) (2004)
  Apresentador: Eduardo Hargreaves - Slides

• E. A. Leicht, Petter Holme, and M. E. J. Newman Vertex similarity in networks
  Phys. Rev. E 73, 026120 (2006)
  Apresentador: Eduardo Hargreaves - Slides

8/4 - Similaridade estrutural e Graph Matching

• Laura A. Zager and George C. Verghese,
  Graph similarity scoring and matching
  Applied Mathematics Letters, Volume 21, Issue 1 (2008)
  Apresentador: Pedro Savarese - Slides

• Marco Gori, Marco Maggini and Lorenzo Sarti
  Exact and approximate graph matching using random walks
  IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), Volume 27, Issue 7 (2005)
  Apresentador: Pedro Savarese - Slides

• D. Conte, P. Foggia, C. Sansone and M. Vento
  Thirty Years of Graph Matching in Pattern Recognition
  International Journal of Pattern Recognition and Artificial Intelligence, Vol. 18, Issue 3 (2004)
  Opcional

15/4 - Graph Matching em redes sociais

• Pedram Pedarsani, Daniel R. Figueiredo, and Matthias Grossglauser,
  A Bayesian method for matching two similar graphs without seeds
  IEEE 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2013
  Apresentador: Daniel Figueiredo - Slides

• Lyudmila Yartseva and Matthias Grossglauser,
  On the performance of percolation graph matching
  ACM Conference on Online Social Networks (COSN), 2013
  Apresentador: Daniel Figueiredo - Slides

• A. Narayanan and V. Shmatikov,
  De-anonymizing Social Networks
  IEEE Symposium on Security and Privacy, 2009
  Opcional

24/4 - Anonimidade em Redes Sociais

• Lars Backstrom, Cynthia Dwork, Jon Kleinberg,
  Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography
  Communications of the ACM, Volume 54 Issue 12 (2011)
  Artigo original apareceu na International conference on World Wide Web (WWW), 2007
  Apresentador: Eduardo Hargreaves - Slides

• M. Hay, G. Miklau, D. Jensen, D. Towsley, C. Li,
  Resisting structural re-identification in anonymized social networks
  The VLDB Journal, Volume 19, Issue 6, pp 797-823 (2010)
  Apresentador: Eduardo Hargreaves - Slides

29/4 - Apresentação e discussão de propostas de projetos

• Cada aluno deve apresentar uma proposta de projeto que gostaria de realizar no contexto de identidade estrutural em redes. Cada apresentação deve durar no máximo 15 minutos. Iremos discutir as propostas e decidir em uma ou duas que serão realizadas pela turma até o final da disciplina.
• Propostas: Daniel, Eduardo, Jefferson, Pedro, Vitor.

• Propostas escolhidas: Daniel (grupo Pedro e Vitor) e Eduardo (grupo Eduardo e Jefferson)

6/5 - Não teremos aula em função do SBRC 2014

• Aproveitar para trabalhar nos projetos, e assistir à palestra do Prof. Etienne Ghys, renomado professor e pesquisador na área do caos (ver filme), que fará a Conferência Magna da Acad. Bras. de Ciências, no dia e horário da aula (ver detalhes).

13/5 - Identificação estrutural em redes de proteínas

• Nir Atias and Roded Sharan
  Comparative Analysis of Protein Networks: Hard Problems, Practical Solutions
  Communications of the ACM, Vol. 55 No. 5 (2012)
  Apresentador: Vitor Borges C. da Silva - Slides

• Rohit Singh, Jinbo Xu, and Bonnie Berger
  Global alignment of multiple protein interaction networks with application to functional orthology detection
  Proc. Natl. Acad. Sci. U.S.A. 105, 35 (2008)
  Apresentador: Vitor Borges C. da Silva - Slides

  Leitura Opcional

• Sharan, R., Suthram, S., Kelley, R.M., Kuhn, T., McCuine, S., Uetz, P., Sittler, T., Karp, R.M., Ideker, T.
  Conserved patterns of protein interaction in multiple species.
  Proc. Natl. Acad. Sci. U.S.A. 102, 6 (Feb. 2005), 1974-1979.

• Jacob Scott, Trey Ideker, Richard M. Karp, and Roded Sharan.
  Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks
  Journal of Computational Biology. March 2006, 13(2): 133-144. doi:10.1089/cmb.2006.13.133.

• S.C. Basak and V.R. Magnuson, Determining structural similarity of chemicals using graph-theoretic indices
  Discrete Applied Mathematics, Volume 19, Issues 1-3 (1988) http://dx.doi.org/10.1016/0166-218X(88)90004-2

20/5 - Homomorfismos, isomorfismos e automorfismos em grafos

• Pavol Hell,
  Algorithmic aspects of graph homomorphisms
  Surveys in Combinatorics, 2003
  Seções 1-7
  Apresentador: Jefferson Simões - Slides

• Wenfei Fan, Jianzhong Li, Shuai Ma, Hongzhi Wang, and Yinghui Wu
  Graph homomorphism revisited for graph matching
  Proc. VLDB Endow. 3, 1-2 (2010)
  Apresentador: Jefferson Simões - Slides

  Leitura Opcional

• Graph homomorphisms: structure and symmetry G Hahn, C Tardif - Graph symmetry, 1997 - Springer

• G. Hahn and G. MacGillivray, Graph homomorphisms: computational aspects and infinite graphs, manuscript, 2002.

• Survey on Homomorphism http://www.site.uottawa.ca/~lucia/CA06/TutorialBrewster.pdf

• The graph isomorphism problem: its structural complexity
  J Köbler, U Schöning, J Torán - 1994 - dl.acm.org

27/5 - Apresentação e discussão do andamento dos projetos da disciplina; votação nos artigos

• Cada grupo deve preparar uma breve apresentação informal do progresso obtido e do trabalho que ainda será realizado.

• Votação do artigo que você mais gostou:
  • "Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography" (4 votos)
  • "A Measure of Similarity between Graph Vertices" (2 votos)
  • "Structural equivalence: Meaning and definition, computation and application" (2 votos)

• Votação do artigo que você menos gostou:
  • "Graph homomorphism revisited for graph matching" (5 votos)

3/6 - Não teremos aula em função do NetSci 2014. Professor é co-autor em três trabalhos a serem apresentados como poster.

• Aproveitar para finalizar projetos!

10/6 - Apresentação de projetos. Cada dupla deve entregar um relatório do projeto (máximo 8 páginas, template de artigos da SBC) e fazer uma apresentação oral, seguida de discussão.

• Eduardo Hargreaves e Jefferson Simões
  Seu título aqui!

• Vitor da Silva e Pedro Savarese
  Seu título aqui!

Outra dia - Identificação de grafos - (muito preliminar)

• Which graphs are determined by their spectrum?
  ER Van Dam, WH Haemers - Linear Algebra and its Applications, 2003 - Elsevier

• Can one hear the shape of a network?
  J von Below - Lecture Notes in Pure and Applied Mathematics, 2001 - newton.cam.ac.uk

• Can one hear the shape of a graph?
  B Gutkin, U Smilansky - Journal of Physics A: Mathematical, 2001 - iopscience.iop.org

• The mathematical structure of the world: The world as graph
  RR Dipert - The Journal of Philosophy, 1997 - JSTOR

• 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. Isto ajudar você a entede-las melhor e também a ter suas próprias ideias!

• Você deve instalar e se familiarizar como graph-tool que é um módulo Python (eficiente) para manipular e analisar redes. Você deve escolher ao menos três redes disponíveis nos repositórios abaixo (e não apenas as redes disponíveis no graph-tool), e caracterizá-las utilizando diferentes métricas (como grau, distância e clusterização, entre outras).
  • Stanford Large Network Dataset Collection
  • The UCI Network Data Repository
  • Gephi sample datasets
  • Mark Newman's Network data repository

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