Models and Algorithms for Complex Networks References

Home Announcements Homework Reading List References Datasets and Code Interesting Links

References References, slides and reading material for each lecture will be posted here. Last year's references and slides can be found here. Lectures 1-2: Introduction Lecture 3: Networks and Measurements Lecture 4: Power laws and Generative Processes Lectures 5-6: Network models Lecture 7: Searching in small world networks Lectures 8-9: Searching in P2P networks Lecture 10: The Web graph Lecture 11: Searching the Web Lecture 12: Link Analysis Ranking Lecture 13: Theory and algorithms for Link Analysis Ranking, Rank Aggregation and Voting. Lecture 14: Failures, Viruses, and Gossip propagation in networks Lectures 15-16: Graph Clustering and Network Communities. Lectures 1-2: Introduction and Mathematical Background This was an overview of the various topics that will be covered in the course that was (partially) based on the following reviews: M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 S. N. Dorogovstev and J. F. F. Mendez,  Evolution of Networks: From Biological Nets to the Internet and WWW We also reviewed of some basic mathematical background in graph theory, linear algebra, and probabilities. For basic definitions any textbook is appropriate. Below are some suggestions and some links to notes. Cormen, Leiserson, Rivest (Sten), Introduction to algorithms (Covers asymptotic notation, basic graph theory, basic probabilities) Douglas B. West, Introduction to Graph Theory (includes also a small part about linear algebra) Horn and Johnson, Matrix analysis Linear Algebra methods for data mining, University of Helsinki, Spring 2005 (Lectures 1 and 2 are a good introduction) Notes on basic linear algebra background (by Saara Hyvönen) M. Mitzenmacher and E. Upfal, Probability and Computing. Lecture slides (PPT, PDF) Back to top Lecture 3: Networks and Measurements Real networks, and measurements on networks. M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 S. N. Dorogovstev and J. F. F. Mendez,  Evolution of Networks: From Biological Nets to the Internet and WWW E. Ravasz and A.-L. Barabási, Hierarchical organization in complex networks, Physical Review E 67, 026112 (2003). M. E. J. Newman, Assortative mixing in networks, Phys. Rev. Lett. 89, 208701 (2002). R. Pastor-Satorras, A. Vázquez, and A. Vespignani. Dynamical and correlation properties of the Internet.Physical Review Letters 87, 258701 (2001)  R Milo, S Itzkovitz, N Kashtan, R Levitt, S Shen-Orr, I Ayzenshtat, M Sheffer & U Alon, Superfamilies of designed and evolved networks. Science, 303:1538-42 (2004). R Milo, S Shen-Orr, S Itzkovitz, N Kashtan, D Chklovskii & U Alon, Network Motifs: Simple Building Blocks of Complex Networks. Science, 298:824-827 (2002). Lecture slides (PPT, PDF) Back to top Lecture 4: Power laws and Generative Processes 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 L. Adamic, Zipf, Power-laws, and Pareto - a ranking tutorial Lecture slides (PPT, PDF) Back to top Lectures 5-6: Network models M. E. J. Newman,  Power laws, Pareto distributions and Zipf's law, Contemporary Physics. 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. D. S. Callaway, J. E. Hopcroft, J. M. Kleinberg, M. E. J. Newman, and S. H. Strogatz, Are randomly grown graphs really random? Phys. Rev. E 64, 041902 (2001). 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 Jure Leskovec, Jon Kleinberg and Christos Faloutsos Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations KDD 2005, Chicago, IL. Lecture slides (PPT, PDF) Back to top Lecture 7: Searching in small-world networks 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). Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, Bernardo A. Huberman. Search in Power-Law Networks. Phys. Rev. E, 64 46135 (2001). Lecture slides (PPT, PDF) Back to top Lectures 8-9: 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. Petar Maymounkov and David Mazieres, Kademlia: A Peer-to-peer Information System Based on the XOR Metric, ITPTS 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 10: 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.  D. Donato, S. Leonardi, P. Tsaparas, Mining the inner structure of the Web, WebDB 2005. A. Gulli and A. Signorini. The indexable web is more than 11.5 billion pages. In Proceedings of 14th International World Wide Web Conference, pages 902–903, Chiba, Japan, 2005. 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 11: Searching the Web Ricardo Baeza-Yates, Berthier Ribeirio-Neto, Modern Information Retrieval, Adison-Wesley, 1999 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. A. Broder. On the resemblance and containment of documents, Technical Report, Digital Research Center. 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 P. Boldi, B. Codenotti, M. Santini, S. Vigna, UbiCrawler: a scalable fully distributed web crawler, 8th Australian World Wide Web Conference, 2002. 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. S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proc. 7th International World Wide Web Conference, 1998 Lecture slides (PPT, PDF) Back to top Lecture 12: Link Analysis Ranking 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. S. Wasserman and K. Faust, Social Network Analysis, Cambridge University Press, 1994. 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 13: Theory and algorithms for Link Analysis Ranking, Rank Aggregation, and Voting A. Borodin, G. Roberts, J. Rosenthal, P. Tsaparas, Link Analysis Ranking: Algorithms, Theory and Experiments, ACM Transactions on Internet Technologies (TOIT), 5(1), 2005 Ron Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar,  Erik Vee, Comparing and aggregating rankings with ties , PODS 2004 M. Tennenholtz, and Alon Altman, "On the Axiomatic Foundations of Ranking Systems", Proceedings of IJCAI, 2005 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 14: Failures and Epidemics 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 G. Giakkoupis, A. Gionis, E. Terzi, P. Tsaparas, Models and algorithms for network immunization. Technical Report C-2005-75, Department of Computer Science, University of Helsinki, 2005. 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 Lectures 15-16: Graph Clustering and Network Communities 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. David Cheng, Ravi Kannan, Santos Vempala, Grant Wang, A Divide and Merge methodology for clustering, PODS 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, Internet Mathematics, Vol 1, Issue 4, 2004. Lecture slides (PPT, PDF) Back to top