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.
Social Networks
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
Sensor Networks
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 are one quiz and one final examination during this course.
1回の小テストと期末試験の点数に評価する。
教科書
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.