## Mathematics Illuminated

# Connecting with Networks

## Virtually everything we experience — in nature as well as human activity — involves a series of connections that link one thing to another. Networks, you might say, make the world go 'round.

Connections can be physical, as with bridges, or immaterial, as with friendships. Both types of connections can be understood using the same mathematical framework called network theory, or graph theory, which is a way to abstract and quantify the notion of connectivity. This unit looks at how this branch of mathematics provides insights into extremely complicated networks such as ecosystems.

### Unit Goals

- Networks can be represented by graphs, which can be analyzed mathematically.
- A graph is a set of elements along with another set that defines how the elements are connected.
- The degree of a node is how many connections it has.
- A path is a sequence of edges connecting two nodes.
- A connected component of a graph is a maximal collection of nodes and edges that are mutually connected.
- Random graphs can undergo “connectivity avalanches” during construction.
- Distance on a graph is a measure of the fewest number of edges needed to travel between two given nodes.
- The clustering coefficient is a measure of how many of a node’s neighbors are connected to each other (e.g., the fraction of a given individual’s friends who are also friends with each other).
- Small-world networks have higher-than-expected clustering coefficients and short mean distances.
- Scale-free networks follow a power law when describing the distribution of degrees.

### Unit Glossary

### ADDITIONAL UNIT RESOURCES: BIBLIOGRAPHY

# Bibliography

## WEBSITES

Barabási, Albert-László. *Linked: The New Science of Networks*. Cambridge, MA: Perseus Publishing, 2002.

Brose U., E.L. Berlow, and N.D. Martinez. “Scaling Up Keystone Effects From Simple to Complex Ecological Networks,” *Ecology Letters,* vol. 8, no. 12 (December 2005).

Brose, U., R.J. Williams, and N.D. Martinez. “Comment on Foraging Adaptation and the Relationship Between Food-Web Complexity and Stability,” *Science*, vol. 301, no. 5635 (August 2003).

Buchanan, Mark. *Nexus: Small Worlds and the Groundbreaking Science of Networks*. New York: W.W. Norton and Company, 2002.

Colinvaux, Paul. *Why Big Fierce Animals Are Rare: An Ecologist’s Perspective*. (Princeton Science Library) Princeton, NJ: Princeton University Press, 1978.

Erdös, Paul and Alfréd Rényi. “On the Evolution of Random Graphs,” *Publications of the Mathematical Institute of the Hungarian Academy of Sciences*, Series A 5 (1960).

Goh, Kwang-II, Eulsik Oh, Hawoong Jeong, Byungnam Kahng, and Doochul Kim. “Classification of Scale-Free Networks,” *Proceedings of the National Academy of Science*, USA, vol. 99, no. 20 (October 2002).

Hartsfield, Nora and Gerhard Ringel. *Pearls in Graph Theory: A Comprehensive Approach*. San Diego, CA: Academic Press, 1990.

Hill, S., D. Agarwal, R. Bell, and C. Volinsky. “Building an Effective Representation for Dynamic Networks,” *Journal of Computational and Graphical Statistics*, vol. 25 (2006).

Latora V. and M. Marchiori. “Is the Boston Subway a Small-World Network?” *Physica A*, vol. 314, no. 1 (1 November 2002).

Liben-Nowell, D., J. Novak, R. Kumar, P. Raghavan, and A. Tomkins.”Geographic Routing in Social Networks,” *Proceedings of the National Academy of Sciences*, USA, vol. 102, no. 33 (2005).

Martinez, N.D. “Effects of Resolution on Food Web Structure,” *Oikos*, 66 (1993).

Martinez, N.D. “Scale-Dependent Constraints on Food-Web Structure,” *American Naturalist,* 144 (1994).

Milgram, S. “The Small-World Problem,” *Psychology Today*, vol. 1, no. 1 (1967).

Montoya, José M., Stuart L. Pimm, and Ricard V. Solé. “Ecological Networks and Their Fragility,” *Nature*, 442 (20 July 2006)

Newman, James R. *Volume 1 of The World of Mathematics: A Small Library of the Literature of Mathematics from A’h-mose the Scribe to Albert Einstein, Presented with Commentaries and Notes*. New York: Simon and Schuster, 1956.

Newman, M.E.J., D.J. Watts, and S. H. Strogatz. “Random Graph Models of Social Networks,” *Proceedings of the National Academy of Sciences*, USA, vol. 99, Supplement 1 (2002).

Proulx, Stephen R., Daniel E.L. Promislow, and Patrick C. Phillips. “Network Thinking in Ecology and Evolution,” *Trends in Ecology and Evolution*, vol. 20, no. 6 (2005).

Schechter, Bruce. *My Brain Is Open: The Mathematical Journeys of Paul Erdös*. New York: Touchstone (Simon and Schuster, Inc.), 2000.

Skyrms, Brian and Robin Pemantle. “A Dynamic Model of Social Network Formation,” *Proceedings of the National Academy of Sciences*, USA, vol. 97, no. 16 (August 1, 2000).

Springer, A.M., J.A. Estes, G.B. van Vliet, T.M. Williams, D.F. Doak, E.M. Danner, K.A. Forney, and B. Pfister. “Sequential Megafaunal Collapse in the North Pacific Ocean: An Ongoing Legacy of Industrial Whaling?” *Proceedings of the National Academy of Sciences, USA*, vol. 100, no. 21 (October 2003).

Steinberg, PD, J.A. Estes, and F.C. Winter. “Evolutionary Consequences of Food Chain Length in Kelp Forest Communities,” *Proceedings of the National Academy of Sciences, USA*, vol. 92 (1995).

Tannenbaum, Peter. *Excursions in Modern Mathematics*, 5^{th} ed. Upper Saddle River, NJ: Pearson Education, Inc., 2004.

Wallis, W.D. *A Beginner’s Guide to Graph Theory*. New York: Birkhauser Boston, 2000.

Watts, Duncan. *Six Degrees: The Science of the Connected Age*. New York: W.W. Norton and Co., 2003.

Watts, Duncan. *Small Worlds: The Dynamics of Networks Between Order and Randomness.*(Princeton Studies in Complexity). Princeton, NJ: Princeton University Press, 1999.

Watts, D.J. and S.H. Strogatz. “Collective Dynamics of Small-World Networks,” *Nature* 393 (1998).

Williams, R.J., E.L. Berlow, J.A. Dunne, A.-L. Barabási, and N.D. Martinez. “Two Degrees of Separation in Complex Food Webs,” *Proceedings of the National Academy of Sciences, USA,* vol. 99, no. 20 (2002).

## LECTURE

D’Souza, R.M. “The Science of Complex Networks.” CSE Seminar at University of California – Davis, February 2006. http://breeze.ucdavis.edu/p44405257/ (accessed 2007).