Feature Column

Complex Networks


7. References

Aingworth, D. and C. Chekuri, P. Indyk, R. Motwani, Fast estimation of diameter and shortest paths (without matrix multiplication), SIAM J. Comput., 28 (1999) 1167-1181.

Albert, B and A.-L. Barabási, Topology of evolving networks: Local events and universality, Phys. Rev. Lett., 85 (2000) 5234-5237.

Alon, N. and J. Spencer, The Probabilistic Method, John Wiley, New York, 1992.

Barabási. A., Linked, Perseus, New York, 2002.

Bavelas, A., A mathematical model for group structures, Human Organization, 7 (1948) 16-30.

Bavelas, A., Communications patterns in task oriented groups, J. Acoust. Soc. Amer., 10 (1965) 271-282.

Beauchamp, M., Elements of Mathematical Sociology, Random House, New York, 1970.

Bollobás, B., Random Graphs, Academic Press, London, 1985 (2nd edition, 2001).

Bollobás, B. and F. Chung, The diameter of a cycle plus a random matching, SIAM J. Discrete Math., 1 (1988) 328-

Chung, F. and M. Garey, Diameter bounds for altered graphs, J. Graph Theory, 8 (1984) 511-534.

Coleman, J., Introduction to Mathematical Sociology, Free Press, New York, 1964.

Dezsõ, Z. and A. Barabási, Halting viruses in scale free networks, Physical Review E, 65 (2002) 055103R.

Diestel, R., Graph Theory, Springer-Verlag, New York, 1997.

Dorogovtsev, S. and J. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW, Oxford U. Press, Oxford, 2003.

Eppstein, D. and J. Wang, Fast approximation of centrality, in Proceeding of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, New York and Philadelphia, 2001, p. 228-229,

Erdös, P., Some remarks on the theory of graphs, Bull. Amer. Math. Soc., 53 (1947) 292-294.

Erdös, P. and A. Rényi, On the evolution of random graphs, Mat. Kutató Int. Közl., 5 (1960) 17-60.

Erdös, P. and G Szekeres, A combinatorial problem in geometry, Compositio Math., 2 (1935) 463-470.

Flament, C., Applications of Graph Theory to Group Structure, Prentice-Hall, Englewood Cliffs, 1963.

Freeman, L., Centrality in social networks: I. conceptual clarification, Social Networks, 1 (1979) 215-239.

Frieze, A. and G. Grimmett, The shortest-path problem for graphs with random arc-lengths, Discrete Applied Math., 10 (1985) 57-77.

Guare, J., Six Degrees of Separation: A Play, Vintage Books, New York, 1990.

Hage, P. and F. Harary, Structural Models in Anthropology, Cambridge U. Press, New York, 1963.

Harary, F. and R. Norman, D. Cartwright, Structural Models, John Wiley, New York, 1965.

Hayes, B., Graph theory in practice: Part I, Amer. Sci., 88 (2000) 9-13.

Hayes, B., Graph theory in practice: Part: II, Amer. Sci., 88 (2000) 104-109.

Janson, S. and T. Luczak, A. Rucinski, Random Graphs, John Wiley, New York 1999.

Killworth, P. and H. Barnard, Reverse small world experiment, Social Networks 1 (1978) 159-192.

Kleinberg, J., The small-world phenomenon: An algorithmic perspective, in Proc. 32nd Annual ACM Symposium in the Theory of Computing, ACM, New York, 2000, p. 163-170.

Kleinberg, J., Navigation in a small world, Nature 406 (2000), p. 485.

Kochen, M., (ed.), The Small World, Ablex, Norwood, 1989.

Leik, R. and B. Meeker, Mathematical Sociology, Prentice-Hall, Englewood Cliffs, 1975.

Milgram, S., The small world problem, Psychology Today 2 (1967) 60-67.

Milo, R. and S. Itzkowitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Sheffer, U. Alon, Superfamiles of evolved and designed networks, Science, 303 (2004) 1538-1542.

Newman, M., The structure and function of complex networks, SIAM Review, 45 (2003) 167-256.

Palmer, E., Graphical Evolution, John Wiley, New York, 1985.

Travers, J., and S. Milgram, An experimental study of the small world problem, Sociometry 32 (1969) 425-443.

West, D., Introduction to Graph Theory, 2nd. edition, Prentice-Hall, Upper Saddle River, 2001.

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Information related to some of the papers above can accessed via the ACM Portal.


  1. Introduction
  2. Some history and a network primer
  3. Random networks
  4. Networks and epidemics
  5. Insights from probability and statistics
  6. The Erdös graph
  7. References

Welcome to the
Feature Column!

These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Read more . . .

Search Feature Column

Feature Column at a glance


Show Archive

Browse subjects


American Mathematical Society