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