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
- 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
- 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
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.
- 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**
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.
- 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**
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
- 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).
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.
- 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
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.
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.
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.
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.
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
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
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)
Back to top |