During this class, we discuss fundamental and state-of-the-art research results on network optimization. The class covers results on sensor networks and social networks. Network design algorithms and efficient algorithms for networks with several million nodes are also discussed during the class.
Class 1: Basic Graph Theory
Class 2: Betweenness Centrality
Class 3: Graph Partitioning, Pagerank Centrality
Class 4: Tree Decomposition
Class 5: Submodular Function Optimization (I)
Class 6: Influence Maximization, LP Duality
Class 7: Exercises on Social Networks
Class 8: Guest Lecture
Class 9: Submodular Function Optimization (II), Target Coverage Problem
Class 10: Garg-Konemann Framework (I)
Class 11: Garg-Konemann Framework (II)
Class 12: Primal-Dual Optimization Framework
Class 13: Semi-Definite Programming
Class 14: Network Localization Problem
Class 15: Exercises on Sensor Networks
The lecture is given in English using a projector and a blackboard.
There is a final examination and four optional assignments during this course.
Lecture notes given in classes.
Ding-Zhu Du and Peng-Jun Wan. Connected Dominating Set: Theory and Applications. Springer, 2012.
Jure Leskovec, Anand Rajaraman, and Jeffrey D. Ullman. Mining of Massive Datasets. Cambridge University Press, 2014.
Students should be familiar with mathematical expression before joining this course.