Models and Algorithms for Complex Networks

Models and Algorithms for Complex Networks
Reading List

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

Albert-Lazlo Barabasi, Linked: How Everything Is Connected to Everything Else and What It Means
Duncan J. Watts, Six Degrees: The Science of a Connected Age
Steven Strogatz, Sync: The Emerging Science of Spontaneous Order
Mark Buchanan, Nexus: Small Worlds and the Groundbreaking Theory of Networks

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