Information Networks References

Home Announcements Homework Reading List References Datasets and Code Interesting Links

References Lecture 1 - Introduction Lecture 2 - Networks and Measurements Lecture 3 - Power laws and Network Models Lecture 4 - Generative processes for Power Laws and Scale Free Netowrks Lecture 5 - Small World Networks Lecture 6 - The Web graph Lecture 7 - Searching on the Web. The anatomy of a search engine Lecture 8 - Link Analysis Ranking I Lecture 9 - Link Analysis Ranking II Lecture 10 - Rank Aggregation and Voting Lecture 11-12 -- Searching in P2P networks Lecture 12-13 -- Failures, Viruses, and Gossip propagation in networks Lecture 14 - Graph Clustering Lecture 1 - Introduction This was a short and basic introduction into the various "real" networks, and some very basic graph theory, probability and linear algeba terminology. The introduction to networks was based on the following review: M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 For basic definitions and an introduction to graph theory, probability theory, and linear algebra, any textbook is appropriate. The following are suggestions. Cormen, Leiserson, Rivest (Sten), Introduction to algorithms Douglas B. West, Introduction to Graph Theory (includes also a small part about linear algebra) Horn and Johnson, Matrix analysis Lecture slides (PPT, PDF) Back to top Lecture 2 - Networks and Measurements Characteristics and measurements over networks M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 Introduction to (Erdös-Renyi) random graphs N. Alon, J. Spencer, The Probabilistic Method (the outline of the proof for the giant component was taken from here).  M. E. J. Newman,  Random graphs as models of networks, in Handbook of Graphs and Networks, S. Bornholdt and H. G. Schuster (eds.), Wiley-VCH, Berlin (2003). B. Bollobas, Random Graphs Lecture slides (PPT, PDF) Back to top Lecture 3 - Power laws and Network Models Random graphs with given degree sequences M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 M. Mihail, N. Vishnoi,   On Generating Graphs with Prescribed Degree Sequences for Complex Network Modeling Applications, Position Paper, ARACNE (Approx. and Randomized Algorithms for Communication Networks) 2002, Rome, IT, 2002. Power-Laws  M. E. J. Newman,  Power laws, Pareto distributions and Zipf's law, Contemporary Physics. M. Mitzenmacher,  A Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Mathematics, 2004 Lecture slides (PPT, PDF) Back to top Lecture 4 - Generative processes for Power Laws and Scale Free Netowrks Scale-free random graphs M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 R. Albert and L.A. Barabasi, Statistical Mechanics of Complex Networks, Rev. Mod. Phys. 74, 47-97 (2002). B. Bollobas, Mathematical Results in Scale-Free random Graphs. Power-Laws  M. E. J. Newman,  Power laws, Pareto distributions and Zipf's law, Contemporary Physics. M. Mitzenmacher,  A Brief History of Generative Models for Power Law and Lognormal Distributions, Internet Mathematics, 2004 Lecture slides (PPT, PDF) Back to top Lecture 5 - Small World Networks Small-world networks D.J. Watts. Networks, Dynamics and Small-World Phenomenon, American Journal of Sociology, Vol. 105, Number 2, 493-527, 1999 Watts, D. J. and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature 393:440-42, 1998 M. E. J. Newman, Models of the small world, J. Stat. Phys. 101, 819-841 (2000). B. Bollobas, Mathematical Results in Scale-Free random Graphs. M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 Searching in small worlds J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000 J. Kleinberg. Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS) 14, 2001.  D. J. Watts, P. S. Dodds, and M. E. J. Newman, Identity and search in social networks,  Science 296, 1302-1305 (2002). Lecture slides (PPT, PDF) Back to top Lecture 6 - The Web graph The Web graph K. Bharat and A. Broder. A technique for measuring the relative size and overlap of public Web search engines. Proc. 7th International World Wide Web Conference, 1998. M. Henzinger, A. Heydon, M. Mitzenmacher, and M. Najork. On Near-Uniform URL Sampling . 9th International World Wide Web Conference, May 2000. S. Lawrence, C. L. Gilles, Searching the World Wide Web, Science 280, 98-100 (1998). A. Albert, H. Jeong, and A.-L. Barabási, Diameter of the World Wide Web, Nature,401, 130-131 (1999). A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener. Graph structure in the web. 9th International World Wide Web Conference, May 2000. S. Dill, R. Kumar, K. McCurley, S. Rajagopalan, D. Sivakumar, A. Tomkins. Self-similarity in the Web. 27th International Conference on Very Large Data Bases, 2001. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Trawling the Web for cyber communities, Proc.  8th WWW , Apr 1999. Nadav Eiron and Kevin S. McCurley, Locality, Hierarchy, and Bidirectionality on the Web, Workshop on Web Algorithms and Models, 2003.  Compressing the Web graph  K. Bharat, A. Broder, M. Henzinger, P. Kumar, and S. Venkatasubramanian. The connectivity server: fast access to linkage information on the web, Proc. 7th  WWW, 1998. K. H. Randall, R. Stata, R. G. Wickremesinghe, and J. L. Wiener. The LINK database: Fast access to graphs of the Web. Research Report 175, Compaq Systems Research Center, Palo Alto, CA, 2001. Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. In Proc. of the Thirteenth International World Wide Web Conference, pages 595-601, Manhattan, USA, 2004. ACM Press. Paolo Boldi and Sebastiano Vigna. The WebGraph framework II: Codes for the World Wide Web. To appear in Internet Mathematics Lecture slides (PPT, PDF) Back to top Lecture 7 - Searching on the Web. The anatomy of a search engine  S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998. A. Broder. On the resemblance and containment of documents, Technical Report, Digital Research Center. Arvind Arasu, Junghoo Cho, Hector Garcia-Molina, Andreas Paepcke, Sriram Raghavan "Searching the Web." ACM Transactions on Internet Technology, 1(1): August 2001. Junghoo Cho, Hector Garcia-Molina, Lawrence Page "Efficient Crawling Through URL Ordering." In Proceedings of the 7th World Wide Web conference (WWW7), Brisbane, Australia, April 1998. Junghoo Cho, Hector Garcia-Molina "The Evolution of the Web and Implications for an incremental Crawler." In Proceedings of 26th International Conference on Very Large Databases (VLDB), September 2000.  Marc Najork, Allan Heydon High Performance Web Crawling, SRC Research Report, 2001 Dennis Fetterly, Mark Manasse, Marc Najork, and Janet Wiener. A Large-Scale Study of the Evolution of Web Pages. 12th International World Wide Web Conference (May 2003), pages 669-678 Marc Najork and Janet L. Wiener. Breadth-First Search Crawling Yields High-Quality Pages. 10th International World Wide Web Conference (May 2001), pages 114-118. Lecture Slides (PPT,PDF) Back to top Lecture 8 - Link Analysis Ranking I S. Motwani, P. Raghavan Randomized Algorithms (Random walks and Markov Chains) S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998. (The PageRank algorithm) J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). (The HITS algorithm) S. Kamvar. T. Haveliwala, C. Manning, G. Golub, Extrapolation Methods for Accelerating PageRank Computations, WWW 2003 (efficient algorithm for the computation of PageRank) A. Langville, C. Meyer Deeper Inside Pagerank, Internet Mathematics L. Katz. A new status index derived from sociometric analysis. Psychometrika 18(1953). G. Pinski, F. Narin. Citation influence for journal aggregates of scientific publications: Theory, with application to the literature of physics. Information Processing and Management, 12(1976), pp. 297--312. Garfield, E. "Citation analysis as a tool in journal evaluation" Science, 178 (4060) p.471-479, 1972. Lecture Slides (PPT,PDF) Back to top Lecture 9 - Link Analysis Ranking II S. Motwani, P. Raghavan Randomized Algorithms (Random walks and Markov Chains) S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998. (The PageRank algorithm) J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). (The HITS algorithm) S. Kamvar. T. Haveliwala, C. Manning, G. Golub, Extrapolation Methods for Accelerating PageRank Computations, WWW 2003 (efficient algorithm for the computation of PageRank) A. Langville, C. Meyer Deeper Inside Pagerank, Internet Mathematics Krishna Bharat and Monika R. Henzinger. Improved algorithms for topic distillation in a hyperlinked environment. 21st International Conference on Research and Development in Information Retrieval (SIGIR 1998). R. Lempel, S. Moran. The Stochastic Approach for Link-Structure Analysis (SALSA) and the TKC Effect. 9th International World Wide Web Conference, May 2000. A. Langville, C. Meyer Deeper Inside Pagerank, Internet Mathematics A. Borodin, G. Roberts, J. Rosenthal, P. Tsaparas, Link Analysis Ranking: Algorithms, Theory and Experiments, ACM Transactions on Internet Technologies (TOIT), 5(1), 2005 P. Tsaparas, Using Non-Linear Dynamical Systems for Web Searching and Ranking , Principles of Database Systems (PODS), Paris, 2004 A. Y. Ng, A. X. Zheng, and M. I. Jordan. Link analysis, eigenvectors, and stability. International Joint Conference on Artificial Intelligence (IJCAI), 2001. Hyun Chul Lee, Allan Borodin: Perturbation of the Hyper-Linked Environment. COCOON 2003: 272-283 M. Bianchini, M. Gori, and F. Scarselli, " Inside PageRank", ACM Transactions on Internet Technology Ron Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar,  Erik Vee, Comparing and aggregating rankings with ties , PODS 2004 Azar, Fiat, Karlin, McSherry, and Saia,Spectral Analysis of Data,  STOC, 2001 R. Lempel and S. Moran, Rank Stability and Rank Similarity of Link-Based Web Ranking Algorithms in Authority Connected Graphs, Information Retrieval 8 (special issue on advances in mathematics/formal methods in information retrieval), pp. 245-264, 2005. Lecture Slides (PPT,PDF) Back to top Lecture 10 - Rank Aggregation K. Arrow. Social Choice and Individual Values. Wiley, 1951. A. Tabarrok, Lecture Notes Ron Fagin, Amnon Lotem and Moni Naor, Optimal aggregation algorithms for middleware, J. Computer and System Sciences 66 (2003), pp. 614-656. Extended abstract appeared in Proc. 2001 ACM Symposium on Principles of Database Systems (PODS '01), pp. 102-113. Cynthia Dwork, Ravi Kumar, Moni Naor, D. Sivakumar. Rank Aggregation Methods for the Web. 10th International World Wide Web Conference, May 2001. Cynthia Dwork, Ravi Kumar, Moni Naor, D. Sivakumar. Rank Aggregation Revisited Ron Fagin, Ravi Kumar and D. Sivakumar, Efficient similarity search and classification via rank aggregation,  Proc. 2003 ACM SIGMOD Conference (SIGMOD '03), pp. 301-312. Lecture Slides (PPT,PDF) Back to top Lecture 11-12 - Searching in P2P networks D. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne, B. Richard, S. Rollins, Z. Xu, Peer to Peer computing, HP technical report, 2002 Rüdiger Schollmeier, "A Definition of Peer-to-Peer Networking for the Classification of Peer-to-Peer Architectures and Applications," Proceedings of the IEEE 2001 International Conference on Peer-to-Peer Computing (P2P2001), Linköping, Sweden, August 27-29, 2001. G. Giakkoupis, Routing algorithms for Distributed Hash Tables, Technical Report, Univeristy of Toronto, 2003 I. Clarke, O. Sandberg, B. Wiley, T. Hong, Freenet: A Distributed Anonymous Information Storage and Retrieval System I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. ACM SIGCOMM, 2001. S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker. A Scalable Content-Addressable Network. ACM SIGCOMM, 2001 C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. ACM Symposium on Parallel Algorithms and Architectures, SPAA 1997. A. Rowstron, P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001). Dalia Malkhi, Moni Naor, David Ratajczak. Viceroy: A Scalable and Dynamic Emulation of the Butterfly. ACM Symposium on Principles of Distributed Computing, 2002. Manku, Gurmeet; Bawa, Mayank; Raghavan, Prabhakar, Symphony: Distributed Hashing in a Small World, USENIX Symposium on Internet Technologies and Systems (USITS), 2003 Lecture Slides (PPT,PDF) Back to top Lecture 12-13 -- Failures, Viruses, and Gossip propagation in networks M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 R. Albert and L.A. Barabasi, Statistical Mechanics of Complex Networks, Rev. Mod. Phys. 74, 47-97 (2002). Y.-C. Lai, A. E. Motter, T. Nishikawa, Attacks and Cascades in Complex Networks, Complex Networks, Springer Verlag D.J. Watts. Networks, Dynamics and Small-World Phenomenon, American Journal of Sociology, Vol. 105, Number 2, 493-527, 1999 R. Pastor-Satorras and A. Vespignani, Epidemics and immunization in scale-free networks. In "Handbook of Graphs and Networks: From the Genome to the Internet", eds. S. Bornholdt and H. G. Schuster, Wiley-VCH, Berlin,   pp. 113-132  (2002) R. Cohen, S. Havlin, D. Ben-Avraham,Efficient Immunization Strategies for Computer Networks and Populations Phys Rev Lett. 2003 Dec 12;91(24):247901. Epub 2003 Dec 9 Y.ang Wang, Deepayan Chakrabarti, Chenxi Wang, Christos Faloutsos, Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint, SDRS, 2003 D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003. (In PDF.) D. Kempe, J. Kleinberg, A. Demers. Spatial gossip and resource location protocols. Proc. 33rd ACM Symposium on Theory of Computing, 2001 Lecture Slides (PPT,PDF) Back to top Lecture 14 -- Graph Clustering J. Kleinberg. Lecture notes on spectral clustering Daniel A. Spielman and Shang-Hua Teng. Spectral Partitioning Works: Planar graphs and finite element meshes. Proceedings of the 37th Annual IEEE Conference on Foundations of Computer Science, 1996. and UC Berkeley Technical Report number UCB CSD-96-898. Ravi Kannan, Santos Vempala, Adrian Vetta,  On clusterings: good, bad and spectral. Journal of the ACM (JACM) 51(3), 497--515, 2004. Gary Flake, Steve Lawrence, C. Lee Giles, Efficient identification of Web Communities,  SIGKDD 2000 G.W. Flake, K. Tsioutsiouliklis, R.E. Tarjan, Graph Clustering Techniques based on Minimum Cut Trees,Technical Report 2002-06, NEC, Princeton, NJ, 2002. (click here for the version that appeared in Internet Mathematics) Lecture Slides (PPT,PDF) Back to top