Sumários

Não houve aula

14 Dezembro 2011, 09:30 Alexandre Francisco

Não houve aula.


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.