Sumários
Cadeias de Markov, ranking e clustering local
12 dezembro 2011, 08:00 • Alexandre Francisco
Cadeias de Markov, conceitos e o teorema fundamental. Caminhos aleatórios em grafos orientados e não orientados. PageRank. Heat kernel. Métodos de cálculo e convergência (power-method). Local clustering baseado em ranking.
Referências complementares: Motwani and Raghavan: Randomized Algorithms, Cambridge University Press, 1995; Chung: The heat kernel as the pagerank of a graph, PNAS, 2007.
Motivos em redes complexas
7 dezembro 2011, 09:30 • Alexandre Francisco
Motivos em redes complexas. Contagem de subgrafos. Problemas e limitações. Estruturas de dados: G-tries. Subgrafos sobrepresetados e sobrerepresentados. Avaliação e significância estatística.
Referência complementar: Pedro Ribeiro: Efficient and Scalable Algorithms for Network Motifs Discovery, PhD Thesis, Fac of Sciences, Univ of Porto, 2011.
Métodos de partição e reordenação para grafos
5 dezembro 2011, 08:00 • Alexandre Francisco
Comunidades em grafos, clustering e reordenação de vértices (cont.). Problemas e limitações. Métodos baseados em propagação de labels. Modularidade e optimização gananciosa. Métodos multi-level, coarsening e refinamento. Cortes minimos como abordagem à partição de grafos e optimização de clusters.
Referências complementares: S. Fortunato: Community detection in graphs, Physics Reports 486:75-174, 2010; Boldi et al.: Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks, WWW'2011; Abou-rjeili and Karypis: Multilevel Algorithms for Partitioning Power-Law Graphs, TR 05-034, CSE Dept, University of Minnesota, 2005; Flake et al: Graph Clustering and Minimum Cut Trees, Internet Mathematics Vol. 1, No. 4: 385-408.
Grafos: estruturas de dados (cont.)
30 novembro 2011, 09:30 • Alexandre Francisco
Grafos: estruturas de dados eficientes e sucintas para representação de listas de adjacências. Distribuições do grau dos vértices, intervalos em listas de adjacências, etc. Codificação eficiente de inteiros dada uma distribuição. Comunidades em grafos, clustering e reordenação de vértices.
Referências complementares: CLRS, Introduction do Algorithms; Codes for the World−Wide Web, by Paolo Boldi and Sebastiano Vigna, Internet Math., 2(4):405−427, 2005.