Networks naturally describe data arising in a number of fields, and there has been considerable interest over the last few years in understanding the structure and evolution of networked systems.

This set of modules does not contain step-by-step hints on how to build simulation and analysis tools, but rather points to some interesting papers analyzing network structure, growth and evolution in a number of settings. These projects are more open-ended, and other papers of interests may also be suggested.

Rather than having to build network analysis code from scratch, students may find the NetworkX package useful: NetworkX is a Python-based network construction and analysis package developed at Los Alamos National Labs. NetworkX has been installed along with the default Python installation in the Physics Educational Computing Facility (PECF) at Cornell, for use with Physics 7682.

Papers and Projects

A.-L. Barabasi and R. Albert: Emergence of scaling in random networks Science 286, 509 (1999). [Network data available at http://www.nd.edu/~networks/resources.htm]

This is an early paper in the emerging field of complex networks focused on power-law degree distributions and a simple model of network growth via preferential attachment. The actor network studied in this paper suggests an interesting twist in its computational implementation. While an ordinary undirected graph connecting co-starts would seem natural, it is also somewhat inefficient, since every movie involves a complete (all-to-all) graph of all actors who appeared in that movie. More useful here is a bipartite graph of actors and movies. Use the graph classes developed in NetworkX to define a new BipartiteGraph class to store and manipulate such data.

---

D.S. Callaway, J.E. Hopcroft, J.M. Kleinberg, M.E.J. Newman, and S.H. Strogatz, Are randomly grown graphs really random?, Phys. Rev. E 64, 041902 (2001).

This paper explores a simple model of network growth that has connections to percolation phenomena on networks. Whereas randomly-wired graphs exhibit a transition to a large connected component with a square-root singularities, this model exhibits a transition with an essential singularity - continuous to all powers.

---

H. Yu, P. Kim, E. Sprecher, V. Trifonov, and M. Gerstein, The Importance of Bottlenecks in Protein Networks: Correlation with Gene Essentiality and Expression Dynamics [Network data available at www.gersteinlab.org/proj/bottleneck]

This paper analyzes bottlenecks in various biological networks, focusing on nodes with large betweenness, rather than hubs with large degree, and argues that betweenness correlates strongly with gene essentiality. The SmallWorld exercise had you implement an algorithm for node betweenness, but NetworkX also provides one for you. (Note, however, that there are varying definitions of betweenness floating around in the literature, depending on whether endpoints are included in the calculation of shortest paths.) Download network data from the supplementary website and work to reproduce the results in the paper.

---

M. Kaiser and C.C. Hilgetag, Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems

Many networks lie in an abstract space with no intrinsic geometry, but this paper considers the embedding of networks in 3D space (specifically, neural networks), and asks whether observed neural networks in nature are optimal, insofar as minimizing total wiring length. To study such problems, we need to augment graphs with information about their spatial embedding; the XGraph and XDiGraph classes in NetworkX are useful in this regard. The Materials and Methods section describes a process by which the raw data from various databases were filtered for analysis, but the filtered data themselves appear not to be available. If reconstruction of the dataset(s) is not straightforward, we can contact the authors about getting the filtered data.

---