Network Algorithms and Dynamics (Spring 2017)



  • Days and Times: Mondays, Wednesdays, 10:10 -11:25amnet.gif
  • Location: Mudd 825
  • Instructor: Javad Ghaderi
  • Office Hours: TBA, Mudd 1328
  • TA:

  • 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
    • Graph algorithms: minimum spanning tree, matching, network flow problems
    • 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.
  • MCMC methods