Sumários

Topic 03: Topics of algorithms and data structures for large-scale networks (part )

25 setembro 2017, 14:00 Francisco Correia dos Santos

Topic 03: Topics of algorithms and data structures for large-scale networks (2 or 3 classes)

  • List of topics discussed:
    • Efficient and compact data structures for large graphs (Compact Sparse Rows/Columns, CSR and CSC, Webgraph, K2 Trees, etc.)
    • Finding connected components (without loading the graph in memory?)
    • APSP and betweenness.
    • Transitive closure and reachability. CCs and SCCs. Topological sorting.
    • Neighborhoods and their properties.
    • Approximating neighborhoods.
    • MSTs. MST and betweenness. Counting MSTs.
    • Counting triangles (with heavy hitters)
    • Counting subgraphs and motifs. Hardness. Subgraph isomorphism. G-trie.
    • Random walks vs eigenvalue-based centrality. Power method.
    • Laplacian and the heat kernel.


Lab01

22 setembro 2017, 15:30 Francisco Correia dos Santos

Problem set 1. Basic network concepts and properties. Vertex centrality. 



Network representations and measures.

22 setembro 2017, 14:00 Francisco Correia dos Santos

Topic 02: Network representations and measures. See Slides online.

Computational complexity, big-O notation, network representation, graph data structures, and basic algorithms on graphs [check any conventional algorithms book, or Newmann 2010, Sections 9.1., 9.2, 9.3, 9.4., 10.1., 10.2, 10.3 ]Simple network global measures: Degree distributions, Clustering Coefficient and Average Path Length.Centrality measures: degree centrality, eigenvector centrality, Katz centrality, PageRank, closeness centrality, betweenness centrality) [check, for instance, Newmann 2010: Sections 7.1, 7.2, 7.3., 7.4., 7.6, 7.7.]. 


Not Taught.

18 setembro 2017, 15:30 Francisco Correia dos Santos

Não houve aula laboratorial.


Not Taught.

18 setembro 2017, 15:30 Francisco Correia dos Santos

Não houve aula laboratorial.