Prerequisites: Probability, Elementary Stochastic Processes, Elementary Graph Theory, but more importantly, mathematical maturity and a level of comfort with reading and writing proofs.

Description:This is the first offering of this course (as an special topics course). The course studies models, algorithms, and dynamics with focus on networked systems. It covers various topics in network science, graph algorithms, random walks, epidemics, load balancing, etc. The topics will be selected from the list below:

Mathematical models of networks: random graphs, the small-world phenomenon, power-law distribution, preferential attachment, etc

Dynamics: random walks, Markov chains, characterization of convergence rate to steady state, MCMC methods, spread of epidemics and opinions in social networks,

Other topics: server scheduling, load balancing, join the shortest queue, power of two choice, etc.

Textbook: Most of the topics are selected from the following textbooks:

Epidemics and Rumours in Complex Networks, by M. Draief and L. Massoulie (Cambridge, 2009). (available in the library as ebook)

Markov Chains, Gibbs Fields, Monte Carlo Simulation, and Queues, by Pierre Bremaud (Springer, 1999). (available in the library)

Grades: Based on homework assignments (30%), a midterm during the semester (March 27, 2017) (20%), and a course project (50%)

Figure on the right:The spreading of information, ideas or diseases in complex networks. The most efficient spreaders are not always necessarily the most connected agents in a network (Nature Physics Cover, November 2010 Volume 6 No 11) Announcements:
A few project suggestions

Galton-Watson Process:

Applications of the Galton-Watson process to human DNA evolution and demography, Neves, A G M, Moreira C H C, 2005

A branching process approximation to cascading load-dependent system failure, Dobson, Ian, Benjamin A. Carreras, and David E. Newman, 2004.

Branching process models for surveillance of infectious diseases controlled by mass vaccination. Farrington, C. P., M. N. Kanaan, and N. J. Gay. 2003

Epidemics:

A. Ganesh, L. Massoulie, and D. Towsley. The effect of network topology on the spread of epidemics. IEEE INFOCOM, 2005.

R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading, Symposium on Foundations of Computer Science, pages 565-574, 2000

D. Shah and T. Zaman. Rumors in a network: Who's the culprit? IEEE Transactions on Information Theory, 2011

K. Zhu and Lei Ying. Information Source Detection in the SIR Model: A Sample Path Based Approach. To appear in IEEE/ACM Transactions on Networking.

F. Chierichetti, S. Lattanzi, and A. Panconesi. Rumour spreading and graph conductance. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Consensus networks, Multi-agent Systems

D. Mosk-Aoyama and D. Shah. Fast distributed algorithms for computing separable functions, IEEE Transactions on Information Theory, 2008.

A. Jadbabaie, J. Lin, and A. S.Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Transactions on Automatic Control, 2003.

R. Olfati-Saber and R. M. Murray. Consensus problems in networks of agents with switching topology and time-delays, IEEE Transactions on Automatic Control, 2004

Javad Ghaderi and R. Srikant, Opinion Dynamics in Social Networks with Stubborn Agents: Equilibrium and Convergence Rate, Automatica, vol. 50, no. 12, 2014.

Load balancing and data centers

Mitzenmacher, Michael. "The power of two choices in randomized load balancing." Parallel and Distributed Systems, IEEE Transactions on, 12.10 (2001): 1094-1104.

Gupta, V., Balter, M. H., Sigman, K., & Whitt, W. (2007). Analysis of join-the-shortest-queue routing for web server farms. Performance Evaluation, 64(9), 1062-1081.

Harchol-Balter, Mor, Mark E. Crovella, and Cristina D. Murta. "On choosing a task assignment policy for a distributed server system." Journal of Parallel and Distributed Computing 59.2 (1999): 204-228.

Singla, A., Hong, C. Y., Popa, L., & Godfrey, P. B. (2012, April). Jellyfish: Networking Data Centers Randomly. In NSDI (Vol. 12, pp. 17-17).

Influence maximization:

Chen, Wei, Yajun Wang, and Siyu Yang. "Efficient influence maximization in social networks." Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009.

Chen, Wei, Chi Wang, and Yajun Wang. "Scalable influence maximization for prevalent viral marketing in large-scale social networks." Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2010.

Goyal, Amit, Francesco Bonchi, and Laks VS Lakshmanan. "A data-based approach to social influence maximization." Proceedings of the VLDB Endowment 5.1 (2011): 73-84.

Days and Times:Mondays, Wednesdays, 10:10 -11:25amLocation: Mudd 825Instructor: Javad GhaderiOffice Hours:TBA, Mudd 1328TA:Prerequisites:Probability, Elementary Stochastic Processes, Elementary Graph Theory, but more importantly, mathematical maturity and a level of comfort with reading and writing proofs.Description:This is the first offering of this course (as an special topics course). The course studies models, algorithms, and dynamics with focus on networked systems. It covers various topics in network science, graph algorithms, random walks, epidemics, load balancing, etc. The topics will be selected from the list below:Textbook:Most of the topics are selected from the following textbooks:Grades: Based on homework assignments (30%), a midterm during the semester (March 27, 2017) (20%), and a course project (50%)Figure on the right:The spreading of information, ideas or diseases in complex networks. The most efficient spreaders are not always necessarily the most connected agents in a network (Nature Physics Cover, November 2010 Volume 6 No 11)Announcements:A few project suggestions

2004.Parallel and Distributed Systems, IEEE Transactions on,12.10 (2001): 1094-1104.Performance Evaluation,64(9), 1062-1081.Journal of Parallel and Distributed Computing59.2 (1999): 204-228.NSDI(Vol. 12, pp. 17-17).Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2009.Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2010.Proceedings of the VLDB Endowment5.1 (2011): 73-84.