Search This Blog

Network Theory

COMS 6998-006 Network Theory

Call Number 98461

Spring 2008

Thursdays 6:10-8 PM

Place 233 Mudd

Dragomir R. Radev

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.

Format

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.

Assignments

  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.

Resources

Readings

  • 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). http://www-personal.umich.edu/~mejn/pubs.html
  • Modularity and community structure in networks, M. E. J. Newman, Proc. Natl. Acad. Sci. USA 103, 85778582 (2006). http://www-personal.umich.edu/~mejn/pubs.html
  • Finding and evaluating community structure in networks, M. E. J. Newman and M. Girvan, Phys. Rev. E 69, 026113 (2004). http://www-personal.umich.edu/~mejn/pubs.html
  • Finding community structure in very large networks, Aaron Clauset, M. E. J. Newman, and Cristopher Moore, Phys. Rev. E 70, 066111 (2004). http://www-personal.umich.edu/~mejn/pubs.html
  • 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
  • http://www.cs.cornell.edu/~lars/kdd06-comm.pdf
  • http://www.sciencemag.org/cgi/content/full/311/5757/88
  • + 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 W. Glanzel, BIBLIOMETRICS AS A RESEARCH FIELD (2003)
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

Syllabus

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

Instructor

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
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)