Home
Announcements
Homework
Reading
List
References
Datasets
and Code
Interesting
Links
|
Reading
List
The
reading list was copied from the Information
Networks course. The course will go along the same lines, some more
topics may be added, and some others may receive less attention. Not
all papers will be presented in class. The list will be
updated in the process, and papers will be added and removed.
Background - popular science books
Background - books and survey
articles on
networks
- M. E. J. Newman, The
structure and function of complex
networks, SIAM Reviews, 45(2): 167-256, 2003
- A.L. Barabasi, Scale
Free Networks
- S. H. Strogatz,
Exploring Complex Networks
- R. Albert and L.A. Barabasi,
Statistical Mechanics of Complex Networks,
Rev. Mod. Phys. 74, 47-97 (2002).
- S. N. Dorogovstev and J. F. F. Mendez, Evolution of Networks: From
Biological Nets to the Internet and WWW
- Handbook of Graphs and Networks : From
the Genome to the Internet, edited by
Stefan Bornholdt, Heinz Georg Schuster
- R.
Pastor-Satorras and A. Vespignan, Evolution
and Structure of the Internet: A Statistical Physics Approach,
Cambridge Press.
Networks and measurements
- M. E. J. Newman, The
structure and function of complex
networks, SIAM Reviews, 45(2): 167-256, 2003
- E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and
A.-L. Barabási, Hierarchical
organization of modularity in metabolic networks, Science 297,
1551-1555 (2002).
- 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).
Power
Laws and Scale Free networks
- 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
- Michalis Faloutsos, Petros Faloutsos and Christos
Faloutsos.
On Power-Law Relationships of the Internet Topology.
ACM SIGCOMM 1999.
- Albert-Laszlo Barabasi, Reka Albert, Emergence of
Scaling in Random Networks, Science,286, 509-512 (1999).
- B. Bollobas,
Mathematical Results in Scale-Free random Graphs.
- Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, Bernardo
A. Huberman. Search
in Power-Law Networks.
Phys. Rev. E, 64 46135 (2001).
Erdös-Renyi Random Graphs and Extentions
- P.
Erdös and A. Renyi, On the evolution of Random Graphs, Publ. Math.
Inst. Acad. Sci., 5, 17 - 61, 1960
- Bela
Bollobas, Random Graphs, Academic Press, London-New York, 1985
- N.
Alon, J. Spencer, The probabilistic Method
- 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).
- W.
Aiello, F. Chung, L. Lu. Random
evolution of
massive graphs.
Handbook of Massive Data Sets, (Eds. James Abello et al.), Kluwer,
2002, pages 97-122.
- 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.
Small
World networks
Small
World Phenomena and Models
- S. Milgram.
The small world problem.
Psychology Today 1, 1967
- J. Kleinfeld. Could it
be a Big World After All?
The `Six Degrees of Separation' Myth.
Society, April 2002.
- 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 and D. J. Watts, Renormalization group
analysis of the small-world network model, Phys. Lett. A 263,
341-346
(1999).
- M. E. J. Newman, Models of the small
world, J. Stat. Phys. 101, 819-841
(2000).
- V. Nguyen and C. Martel. Analyzing
and characterizing small-world
graphs. To appear in the 2005 ACM-SIAM symposium on Discrete
Algorithms.
Searching in a Small
World
- 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).
- C. Martel and V. Nguyen. Analyzing
Kleinberg's (and other) small-world
models. In the 23rd ACM Symposium on Principles of Distributed
Computing,
pp. 179-188, 2004.
- M. Naor, U. Weider Know thy
Neighbor’s Neighbor: Better Routing for Skip-Graphs and Small Wolds
- P. Fraigniaud, C. Gavoille, and C. Paul, Eclecticism
Shrinks Even Small Worlds, 23rd ACM Symp. on Principles of
Distributed Computing
(PODC 2004).
The Web
Background
- Vannevar Bush, As
we may think,The Atlantic Monthly, July 1945
- World Wide Web Consortium. A Little History of
the World Wide Web, 1945-1995.
- 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.
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.
- Albert-Laszlo Barabasi, Reka Albert, Emergence of
Scaling in Random Networks, Science,286, 509-512 (1999).
- A. Albert, H. Jeong, and A.-L. Barabási, Diameter of
the World Wide Web, Nature,401, 130-131 (1999).
- S. Lawrence, C. L. Gilles, Searching
the World Wide Web, Science 280, 98-100
(1998).
- Steve Lawrence and C. Lee Giles. Accessibility
and Distribution of Information on the Web.
Nature 400(6740): 107-109, July 8, 1999. (click here
for a summary if you cannot access the link)
- J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A.
Tomkins. The
Web as a graph: Measurements, models and methods.
Invited survey at the International Conference
on Combinatorics and Computing, 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.
- D.M. Pennock, G.W. Flake, S. Lawrence, E. J. Glover, C. L.
Giles, Winners
don't take all: Characterizing the competition for links on the web,
Proc. of the National Academy of Sciences, 2002
- 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.
- Nadav
Eiron and Kevin S. McCurley, Link Structure of
Hierarchical Information Networks, Proc. Third Workshop on
Algorithms and Models for the Web-Graph (WAW 2004), Lecture Notes in
Computer Science, 2004.
- Z. BarYossef,
A. Broder, R. Kumar and A. Tomkins. Sic Transit Gloria
Telae: Towards an Understanding of theWeb's Decay. In
Proceedings of the Thirteenth International World Wide Web Conference,
New York, New York, 2004.
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
- Micah Adler, Michael
Mitzenmacher, Towards
Compressing Web Graphs in Proceedings of the IEEE Data
Compression
Conference (DCC), 2001.
Web
Search
- A. Arasu, J. Cho, H. Garcia-Molina, A. Paepcke, S.
Raghavan.
Searching the Web.
ACM Transactions on Internet Technology 1(1): 2-43 (2001)
- 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.
- 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
- S. Chakrabarti, M.
van den Berg, and B. Dom. Focused
crawling: A new approach to topic-specific Web resource discovery.
8th International World Wide Web Conference, May 1999.
- M. Diligenti, F.M.
Coetzee, S. Lawrence, C.L. Giles, M. Gori Focused
Crawling Using Context Graphs.
26th International Conference on Very Large Databases, VLDB 2000.
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. Motwani, P. Raghavan Randomized Algorithms (Random Walks
and MC background)
- 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).
- S. Brin and L. Page. The
Anatomy of a Large-Scale Hypertextual Web Search Engine.
Proc. 7th International World Wide Web Conference, 1998.
- S. Kamvar. T. Haveliwala, C. Manning, G. Golub, Extrapolation
Methods for Accelerating PageRank Computations, WWW 2003
- 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
- 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.
- Davood Rafiei, Alberto Mendelzon.
What is this Page Known for? Computing Web Page Reputations.
Proc. WWW9 Conference, Amsterdam, May 2000
- Taher H. Haveliwala. Topic-Sensitive
PageRank.
11th International World Wide Web Conference, 2002.
- S. Chien, C. Dwork, R. Kumar, D. Simon, and D. Sivakumar, "Link
Evolution: Analysis and Algorithms," accepted to Internet
Mathematics.
- Arvind Arasu, Jasmine Novak, Andrew Tomkins, John Tomlin PageRank
Computation and the Structure of the Web: Experiments and Algorithms.
11th International World Wide Web Conference, 2002.
- David Cohn and Huan Chang
Probabilistically Identifying Authoritative Documents.
17th International Conference on Machine Learning, 2000
- Pedro Domingos, Matt Richardson. The
Intelligent Surfer: Probabilistic Combination of Link and Content
Information in PageRank. Advances in Neural Information Processing
Systems 14, 2002.
- Jeffrey Dean and Monika R. Henzinger.
Finding Related Web Pages in the World Wide Web.
8th International World Wide Web, 1999.
- R. Lempel, A. Soffer. PicASHOW:
Pictorial Authority Search by Hyperlinks on the Web.
10th International World Wide Web Conference, May 2001
- A. Y. Ng, A. X. Zheng, and M. I. Jordan. Link
analysis, eigenvectors, and stability.
International Joint Conference on Artificial Intelligence (IJCAI),
2001.
- A. Y. Ng, A. X. Zheng, and M. I. Jordan. Stable
algorithms for link analysis.
24th International Conference on Research and Development in
Information Retrieval (SIGIR 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.
Rank
Aggregation and Voting
- 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,
Mohammad Mahdian, D. Sivakumar, Erik Vee, Comparing
and aggregating rankings with
ties , PODS 2004
- 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.
- Ron Fagin, Ravi Kumar and D. Sivakumar Comparing
top k
lists, Extended abstract in 2003
ACM-SIAM Symposium on Discrete Algorithms (SODA '03),
pp. 28-36.
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
- David Karger, Eric Lehman, Tom Leighton, Mathhew Levine,
Daniel Lewin, Rina Panigrahy, Consistent
Hashing and Random Trees: Distributed Caching Protocols for Relieving
Hot Spots on the World Wide Web, STOC 1997
- David
Karger,
Alex Sherman ,
Andy Berkheimer, Bill Bogstad, Rizwan Dhanidina
Ken Iwamoto, Brian Kim, Luke Matkins, Yoav Yerushalmi. Web
Cashing with Consistent Hashing, WWW8, 1999
- The
Gnutella Protocol Specification
- I. Clarke,
O. Sandberg, B. Wiley, T. Hong, Freenet: A Distributed
Anonymous Information Storage and Retrieval System
- T. Hong.
Performance. Peer-to-Peer: Harnessing the Power of Disruptive
Technologies.
(A. Oram, editor),
O'Reilly and Associates, 2001.
- I. Stoica,
R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan. Chord:
A Scalable Peer-to-peer Lookup Service for Internet Applications.
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.
- 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).
- S.
Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker. A
Scalable Content-Addressable Network.
ACM SIGCOMM, 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
- B. Y.
Zhao, J. D. Kubiatowicz, A. D. Joseph, Tapestry:
An Infrastructure for Fault-Tolerant Wide-Area
Location and Routing.
UC Berkeley Computer Science Division, Report No. UCB/CSD 01/1141,
April 2001.
- Dalia
Malkhi, Moni Naor, David Ratajczak.
Viceroy: A Scalable and Dynamic Emulation of the Butterfly.
ACM Symposium on Principles of Distributed Computing, 2002.
- A. Goel,
H. Zhang, and R. Govindan.
Using the Small-World Model to Improve Freenet Performance.
IEEE Infocom, 2002.
- David
Liben-Nowell, Hari
Balakrishnan, and David Karger. Analysis
of the Evolution of Peer-to-Peer Networks. In Proceedings
of PODC 2002.
- E.
Cohen, S.
Shenker. Replication
Strategies in Unstructured Peer-to-Peer Networks.
SIGCOMM 2002.
- G.
Manku, M. Naor, and U. Wieder.
Know Thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P
Networks.
In Proc. of ACM Symp. on Theory of Computing (STOC), 2004.
- Sylvia
Ratnasamy, Scott Shenker and Ion Stoica. Routing
Algorithms for DHTs: Some Open Questions.
1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002.
Cascading effects on networks -- Gossip and Epidemics
- 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. Pastor-Satorras
and
A. Vespignani.,
Immunization of
complex networks.
Physical Review E 65, 036104 (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
- R. Karp, C. Schindelhauer, S. Shenker, B. Vocking. Randomized
Rumor Spreading.
41st IEEE Symposium on Foundations of Computer Science, 2000.
- R. van Renesse, K. Birman, W. Vogels.
Astrolabe: A Robust and Scalable Technology For Distributed System
Monitoring, Management, and Data Mining.
to appear in ACM Transactions on Computer Systems, 2003.
- Pedro Domingos, Matt Richardson.
Mining Knowledge-Sharing Sites for Viral Marketing.
Eighth International Conference on Knowledge Discovery and Data Mining,
KDD-2002.
- Pedro Domingos, Matt Richardson.Mining
the Network Value of Customers, Proceedings
of the Seventh International Conference on Knowledge Discovery and Data
Mining (pp. 57-66), 2001. San Francisco, CA: ACM Press.
- P. Dodds and D. J. Watts. Universal
Behavior in a Generalized Model of Contagion.
Phyical Review Letters, 2004.
- H. Peyton Young. The
Diffusion of Innovations in Social Networks.
Santa Fe Institute Working Paper 02-04-018.
- M. Granovetter.
Threshold models of collective behavior.
American Journal of Sociology 83(6):1420-1443, 1978.
Graph Clustering, and Community search
- 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.
- P.
Drineas, Ravi Kannan, Alan Frieze, Santosh Vempala and V. Vinay "Clustering
in large graphs and matrices."
Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms, Baltimore,
1999.
- Ravi Kannan, Santos
Vempala, Adrian Vetta, On
clusterings: good, bad and spectral. Journal of the ACM (JACM)
51(3), 497--515, 2004.
- 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)
- Gary Flake, Steve
Lawrence, C. Lee Giles, Efficient
identification of Web Communities, SIGKDD 2000
- Gary Flake, Steve
Lawrence, C. Lee Giles, Frans Coetzee. Self-Organization
and Identification of Web Communities.
IEEE Computer, 35:3, March 2002.
- J. Hopcroft, O. Khan,
B. Kulis, and B. Selman.
Natural communities in large linked networks.
In Proceedings of the 9th ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, pages 541--546,
- M. Granovetter.
The strength of weak ties.
American Journal of Sociology, 78(6):1360-1380, 1973.
- J. Kleinberg.
An Impossibility Theorem for Clustering.
Advances in Neural Information Processing Systems (NIPS) 15, 2002.
- The METIS
graph clustering algorithms
Other Topics (not covered)
Biological
Networks
Temporal
Analysis of Data
|