Call Number 98461

Spring 2008

Thursdays 6:10-8 PM

Place 233 Mudd

Dragomir R. Radev

- Project 1

Analysis of a network (6 PR-style pages), assignment, examples, list of analyzed datasets - Project 2

Replicating an existing paper (6 pages), assignment, examples, list of replicated papers - Project 3

Final project (10 pages) and presentation, assignment, datasets, list of final projects - Course Book

Compilations of all lectures and projects. assignment, sample chapters, table of contents

- 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.
- 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.

- Pajek: CS account instructions, wiki and manual
- Jung: java package, CS account instructions, website
- NetworkX: python package, CS account instructions, wiki
- Guess: CS account instructions, website, ppt tutorial
- Clairlib: perl package, CS account instructions, utilities tutorial, website
- Simple Pajek Network
- WebGraph Bibliography
- PR Style paper (for assignments): Tutorial
- Scribing: Tutorial
- PageRank Datasets: http://www.cofc.edu/~langvillea/PRDataCode/index.html#Data

- 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

Jan 31 | Albert/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 7 | Lada 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 14 | D. 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 21 | Doyle/Snell Random Walks and Electric Networks pages 1-14, 29-37 (required), 37-51 (optional) |

Feb 28 | David 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 6 |
Ferrer 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 13 | Xiaojin Zhu SSL Survey pages 1-30, 33-34 M. Seeger Learning with Labeled and Unlabeled Data (optional) |

Mar 27 | McPherson et al. Birds of a feather - homophily in social network (2001) Kossinets and Watts, Empirical Analysis of an Evolving Social Network (2006) |

Apr 10 | Derek 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 17 | Inderjit 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[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)] |

- Diffusion on graphs and the heat kernel
- Finding motifs and graph mining
- Generating functions
- Graphs with predefined degree sequences
- Relational learning

- 15 Views of a Node Link Graph: An Information Visualization Portfolio (Google engEDU)
- An interesting story about social network visualization: http://www.technologyreview.com/Biztech/20223/
- The Bible as a network: http://www.chrisharrison.net/projects/bibleviz/index.html

- Cornell (Jon Kleinberg) The Structure of Information Networks
- Michigan (Mark Newman and Lada Adamic) Networks: Theory and Applications, Network Theory
- Penn State (Reka Albert) Graphs and Networks in Systems Biology
- UMass (Andrew McCallum) Computational Social Network Analysis
- Penn (Michael Kearns) Networked Life
- USC (David Kempe) Structure and Dynamics of Networked Information
- IIT - Kharagpur (Niloy Ganguly) Complex Networks