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.