Network theory notes and materials

 Network theory notes and materials

Goal of the course

To allow graduate students to catch up with recent developments in network theory, focusing on existing networks such as the web and protein interaction networks and the methods and algorithms for analysing them.

Brief description

The course is about naturally occurring networks such as the Web, social networks, citation networks, protein interaction networks, lexical networks, movie actors, etc. The course will cover the mathematical and computational models that explain the behavior of these networks. Specific topics include random graphs, small worlds, scale-free networks, random walks and harmonic functions, spectral methods, descriptive analysis of networks, information diffusion and learning on graphs, etc.


The class will meet once a week for 2 hours in order for MS students to be able to attend regularly. The students will be responsible for scribing, 3 assignments, including a final project, and a final exam.


  1. Project 1
    Analysis of a network (6 PR-style pages), assignment, examples, list of analyzed datasets
  2. Project 2
    Replicating an existing paper (6 pages), assignment, examples, list of replicated papers
  3. Project 3
    Final project (10 pages) and presentation, assignment, datasets, list of final projects
  4. Course Book
    Compilations of all lectures and projects. assignment, sample chapters, table of contents

Final project

An open-ended research project in one of two categories:
  1. Research paper - using the SIGIR format. Students will be in charge of problem formulation, literature survey, hypothesis formulation, experimental design, implementation, and possibly submission to a conference like SIGIR, Sunbelt, ICWSM, or WWW.
  2. Software system - develop a working, useful system (including an API). Students will be responsible for identifying a niche problem, implementing it and deploying it, either on the Web or as an open-source downloadable tool.



  • Mark Newman, Albert-Laszlo Barabasi, & Duncan J. Watts "The Structure and Dynamics of Networks" (paper collection) 2006
  • Xiaojin Zhu "Semi-Supervised Learning Literature Survey" 2006
  • Fortunato and Castellano "Community structure in graphs" 2007
  • Ulrike von Luxburg "A Tutorial on Spectral Clustering" Statistics and Computing 2007
  • Gunes Erkan and Dragomir Radev "Lexrank" JAIR 2004
  • Mark Newman "The structure and function of complex networks" SIAM Review 2003
  • A. Mehler "Large text networks as an object of corpus linguistic studies" 2007
  • L. Barabasi and R. Albert "Emergence of scaling in random networks" Science 1999
  • Mark Newman "A measure of betweenness centrality based on random walks" 2005
  • Masucci and Rodgers "Network properties of written human language" 2006
  • Steven Strogatz "Exploring complex networks" Nature 2001
  • Sergey Dorogovtsev and Jose Mendes "Evolution of networks" Advances in Physics 2002
  • Mark Newman "Random graphs as models of networks" 2002
  • Laszlo Lovasz "Random Walks on Graphs: A Survey" 1996
  • Mark Newman "Who is the best connected scientist? A study of scientific coauthorship networks," 2004
  • Aaron Clauset et al "Power-law distributions in empirical data" 2007
  • Mark Newman "Power laws, Pareto distributions and Zipf's law, M." 2005
  • Faloutsos, Faloutsos, and Faloutsos "On Power-Law Relationships of the Internet Topology" SIGCOMM 1999
  • Peter Doyle and Laurie Snell "Random walks and electric networks" 1984
  • Amy Langville and Carl Meyer "Google's pagerank and beyond" 2006
  • Jianbo Shi and Jitendra Malik "Normalized Cuts and Image Segmentation" IEEE PAMI 2000
  • Michael Mitzenmacher " Brief History of Generative Models for Power Law and Lognormal Distributions" Internet Mathematics 2004
  • P. Ipeirotis, E. Agichtein, P. Jain, and L. Gravano "Towards a Query Optimizer for Text-Centric Tasks" ACM TODS 2007
  • Inderjit Dhillon "Co-clustering documents and words using Bipartite Spectral Graph Partitioning" SIGKDD 2001
  • Lada A. Adamic Zipf, Power-laws, and Pareto - a ranking tutorial, Information Dynamics Lab, HP Labs
  • M. E. J. Newman, Power laws, Pareto distributions and Zipf's law, Contemporary Physics 46, 323-351 (2005)
  • Finding community structure in networks using the eigenvectors of matrices, M. E. J. Newman, Phys. Rev. E 74, 036104 (2006).
  • Modularity and community structure in networks, M. E. J. Newman, Proc. Natl. Acad. Sci. USA 103, 85778582 (2006).
  • Finding and evaluating community structure in networks, M. E. J. Newman and M. Girvan, Phys. Rev. E 69, 026113 (2004).
  • Finding community structure in very large networks, Aaron Clauset, M. E. J. Newman, and Cristopher Moore, Phys. Rev. E 70, 066111 (2004).
  • Mark Newman, Detecting community structure in networks, Eur. Phys. J. B 38, 321330 (2004)
  • F Wu, BA Huberman: Finding communities in linear time: a physics approach The European Physical Journal B-Condensed Matter, 2004
  • Six degrees of messaging Leskovec, J. & Horvitz, E. Planetary-scale views on an instant-messaging network (2008).
  • James Moody Race, School Integration, and Friendship Segregation in America1
  • + many others

Assigned Reading

Jan 31Albert/Barabasi 2002, Statistical Mechanics of Complex Networks sections I, II, III (pages 48-59)
Newman 2003, The structure and function of complex networks sections I, II, IV (pages 1-9 and 20-26)
Feb 7Lada A. Adamic Zipf, Power-laws, and Pareto - a ranking tutorial, Information Dynamics Lab, HP Labs
Newman 2002, Random graphs as models of networks pages 1-11 (required), pages 12-19 (optional), Kalevi Kilkki, A practical model for analyzing long tails (optional)
Feb 14D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks, Nature, 393:440-442 (1998)
A. Barrat and M. Weigt, On the properties of small-world network models, Europ. Phys. J. B 13, 547 (2000) pages 1-8
Feb 21Doyle/Snell Random Walks and Electric Networks pages 1-14, 29-37 (required), 37-51 (optional)
Feb 28David Austin How Google Finds Your Needle in the Web's Haystack
Amy N. Langville and Carl D. Meyer Deeper Inside PageRank. Internet Mathematics, Vol. 1(3):335-380, 2005. pages 1-20
Mar 6Ferrer i Cancho, Sole, Koehler, Patterns in syntactic dependency networks, Phys Rev E. 69, 051915 (2004)
Dorogovtsev and Mendes, Language as an evolving word web, Proc. Royal Soc. London B 268, 2603-2606 (2001) (optional)
Motter et al., Topology of the conceptual network of language, Phys Rev E. 65, 065102 (2002)
Masucci and Rodgers, Network properties of written human language, Phys Rev E.74. 026102, (2006)
Sole et al., Language networks: their structure, function, and evolution, Trends in Cognitive Sciences (2005)
Sigman and Cecchi, Global organization of the Wordnet lexicon, Proc Natl Acad Sci U S A, 99(3):1742-7, February 2002
Caldeira et al., The network of concepts in written texts (2005)
Mar 13Xiaojin Zhu SSL Survey pages 1-30, 33-34
M. Seeger Learning with Labeled and Unlabeled Data (optional)
Mar 27McPherson et al. Birds of a feather - homophily in social network (2001)
Kossinets and Watts, Empirical Analysis of an Evolving Social Network (2006)
Apr 10Derek de Solla Price, Networks of Scientific papers
Epidemics and percolation in small-world networks (2000)
J.E. Hirsch An index to quantify an individual's scientific research output
Apr 17Inderjit Dhillon, Co-clustering documents and Words using Bipartite Spectral Graph Partitioning, KDD (2001)
Martin Gardner, The fantastic combinations of John Conway's new solitaire game "life" Scientific American 223 (October 1970): 120-123.
Jon Kleinberg, Navigation in a small world, Nature 2000


Jan 24
Introduction to networks [notes], Real networks [notes]
Jan 31
Random graphs [notes (draft)], Software for network analysis [notes (draft)]
Feb 7
Properties of networks [notes (draft)], Power law degree distributions [notes (draft)]
Feb 14
Power Law (cont.) [notes (draft)], Self Similarity [notes (draft)], Small world networks [notes (draft)]
Feb 21
Random Walks and Electrical Networks [nodes (draft)], Method of relaxations and other methods for computing harmonic functions, Eigenvector methods[notes (draft)]
Feb 28
Community Identification [notes (draft)], Spectral clustering [notes (draft)]
Mar 6
Lexical networks [notes (draft)], Eigenvectors, Eigenvalues and Stochastic Matrices [notes (draft)]
Mar 13
Applications to information retrieval and NLP [notes (draft)],[notes (draft)]
Mar 27
Social networks, Cascading Behavior, Strength of weak ties, Assortativity and homophily [notes (draft)],[notes (draft)]
Apr 3
Biological, Technological and other networks [notes (draft)], Network traversal
Apr 10
Bibliometrics, The Ising model, Percolation on Graphs [notes (draft)]
Apr 17
Cellular Automata, Network evolution, Search on Networks, Co-clustering [notes (draft)]
Apr 24
Dependancy Parsing using Graphs (Guest Lecturer: Ryan McDonald) [notes (draft)]
Semisupervised learning on graphs (Guest Lecturer: Gunes Erkan) [notes (draft)]


Dragomir R. Radev obtained a PhD in Computer Science from Columbia in 1999. He is currently an associate professor at the University of Michigan with a joint appointment in the Department of Electrical Engineering and Computer Science and the School of Information. He has taught numerous courses in Natural Language Processing, Databases, and Information Retrieval. He has received a number of awards including the Columbia CS department award for graduate student teaching, the University of Michigan UROP award for outstanding research mentorship, as well as the Gosnell Prize for excellence in political methodology. As undergraduate he has been on a team that finished in the top 10 at the ACM international computer programming contest and, later, has been the coach of Columbia's team for 4 years, taking it to three international finals. Dragomir has worked in different capacities for places like Microsoft Research, IBM Research, MITRE, AT&T Bell Labs, and Yahoo!

Related courses elsewhere


Note: If any materials or notes or books or lab programs not run or link failure you can now search from the following box ,it will directly download all files. This is new file server

See Below Link