COMP5313 - Large-Scale Networks

The growing connectedness of modern society translates into simplifying global communications and accelerating spreads of news, information and epidemics. The focus of this unit is on the key concepts to address the challenges induced by the recent scale shift of complex networks. In particular, the course will present how scalable solutions exploiting graph theory, sociology, game theory and probability tackle the problems of communicating (routing, diffusing, aggregating) in dynamic and social networks.

General Information

Tentative roadmap

Week Lecture Required material Optional material Important concepts Lab/Tutorial
Week 1 Administrativa + Introduction Ch.1 Linked: The New Science of Networks. A.-L. Barabasi path, cycle, connected component, distance, diameter, BFS [No lab]
Week 2 Graph ties Ch.2-3 Stanley Milgram. The small-world problem. Psychology Today, 2:60-67, 1967. clustering coefficient, strong/weak ties, local brigde, neighborhood overlap Connected - How Kevin Bacon Cured Cancer. A. Talas
Week 3 Evolution - Python Ch.3-4 Python 2.7 documentation NetworkX documentation Girvan-Newman, bipartite graph, heterogeneous edge, social influence, selection, closures Graphs
Week 4 Structures Ch.5 Attitudes and Cognitive Organizations. F. Heider 1946. The Journal of Psychology 21:107-112, 1946 signed graph, instability, balanced triangles, weakly balanced network Python and NetworkX
Week 5 Hubs and authorities Ch.13-14 Eugene Garfield. Citation analysis as a tool in journal evaluation. Science, 178:471-479, 1972. bow-tie structure, SCC, eigenvector, eigenvalue, repeated improvement Twitter interactions
Week 6 The PageRank algorithm Ch.14, 16 Google's PageRank and Beyond: The Science of Search Engine Rankings. Amy N. Langville & Carl D. Meyer. ISBN:9780691152660. 2012. scaling factor, random walk, informational/direct-benefit effects, Bayes' rule Web pages popularity
Vacation week
Week 7 Dynamics (information cascades, power law) Ch.16, 18 Ch.17 decision, signal, power law, preferential attachment, long tail, Zipf Mid-term quiz
Week 8 Structural models Ch.20 Ch.19, Navigation in a small world. J. Kleinberg. Nature 406:845, 2000. navigability, Watts-Strogatz model, decentralized search Visualization with Gephi
Week 9 P2P networks Morris, Stoica. Looking up data in P2P systems. Commun. ACM 46:43-48, 2003. Chord. Stoica, Morris, Karger, Kaashoek, Balakrishnan.,
A Scalable Content-Addressable Network. Ratnasamy, Francis, Handley, Karp, Shenker.
locality, shortcuts, Chord, CAN, dynamism Network dynamics
Week 10 Student presentations and Blockchains The Balance Attack or Why Forkable Blockchains Are Ill-Suited for Consortium. Natoli and Gramoli Princeton Bitcoin book. Bitcoin, proof-of-work, consensus, fork, mining
Week 11 Gossip-based protocols Ch.21 Gossip-Based Computation of Aggregate Information. Kempe, Dobra, Gherke. branching process, SIR model, SIS model
Week 12 Guest lecture: Large-Scale Networks in Network Security.
Week 13 Review.

Selected datasets

Lists of datasets

Related scientific articles

Sample of Assignment 2