Sumários
Graph partitioning and community finding
26 novembro 2018, 14:00 • Alexandre Francisco
Graph clustering with a priori unknown number of clusters/partitions. Soft vs hard clustering. Community finding. Pairwise and arbitrary matching based methods. Clique percolation, cFinder, computational hardness and applications where induced cliques can be used. Betweenness based methods. Hierarchical clustering. Modularity: definition and underlying null model. Modularity optimization and inherent computational complexity. Modularity greedy optimization: CNM algorithm. References for this class: Networks: An Introduction, by M. E. J. Newman (2010), Sections 11.6, 11.7, 11.0 and 11.11; http://glaros.dtc.umn.edu/gkhome/views/metis; http://www.cfinder.org/; https://web.ist.utl.pt/aplf/arXiv/10-FBO-QTQLG.pdf; http://ece-research.unm.edu/ifis/papers/community-moore.pdf; https://web.ist.utl.pt/aplf/arXiv/10-FO-FCFIND.pdf
Project support
23 novembro 2018, 15:30 • Alexandre Francisco
Support and discussion concerning the second project.
Graph partitioning: max-flow vs min-cut, K-L and local clustering
23 novembro 2018, 14:00 • Alexandre Francisco
Minimum cuts: s-t min-cut vs max-flow, Edmons-Karp algorithm, problem complexity. Fixed size partitioning, Kernighan-Lin algorithm: main ideas and complexity. Local clustering through ranking and sweeping: PageRank and Heat Kernel; Cheeger ratio aka conductance; computation on sparse graphs. References for this class: Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest (2002), Chapter 26; Networks: An Introduction, by M. E. J. Newman (2010), Section 11.4; https://doi.org/10.1073/pnas.0708838104; https://projecteuclid.org/euclid.im/1243430567.
Project support
19 novembro 2018, 15:30 • Alexandre Francisco
Support and discussion concerning the second project.
Graph partitioning: spectral clustering
19 novembro 2018, 14:00 • Alexandre Francisco
Power method, applications and limitations. Matrix representation vs power method complexity. Computation of the second largest eigenvalue, and corresponding eigenvector, for the graph Laplacian. Graph partitioning and spectral clustering. Problem complexity. Spectral clustering relaxation and algorithm. References for this class: Networks: An Introduction, by M. E. J. Newman (2010), Sections 11.1-11.3, 11.5.