The study of complex networks is a more resent activity in complex systems science. It is largely inspired by empirical studies of real world networks like social, gene, neuronal, and computer networks. A complex network is essentially a graph with "nontrivial" topological features. Let's first review some trivial features for regular or random networks, as they are known from graph theory. Trivial Network FeaturesTrivial networks such as lattices and random graphs have been studies extensively in the past. Lattices are regular graphs whose drawing corresponds to some grid/mesh/lattice. A random graph is a graph that is generated by a random process. Some of the more prominent graph properties will be discussed. Graph properties or invariants depend on the abstract structure only, not on the representation. They include degree, clustering coefficient, connectivity (scalars); degree sequence, characteristic polynomial, Tutte polynominal (sequences/polynominals). Degree / Degree DistributionThe degree of a node is the number of connections it has to other nodes. There is a maximum degree, a minimum degree and a degree sum of a graph. A vertex with degree 0 is called an isolated vertex, a vertex with degree 1 is called a leaf vertex and the edge connected to that vertex is called a pendant edge. The degree distribution is the probability distribution of these degrees over the whole network. This is an important property of both real world networks and theoretical networks. For example the random graph has a binomial distribution of degrees or a Poisson distribution for lage networks. Most real world networks are highly rightskewed, meaning that a large majority of nodes have low degree but a small number, known as "hubs", have high degree (see scalefreenetworks below). The degree sequence is a nonincreasing sequence of vertex degrees. Graphs with the same degree sequence are isomorphic. Isomorphism captures the idea that the structure of the graphs is the same  ignoring individual distinctions, e.g. the number of cycles in the isomorphic graphs is the same, however node coloring and graph drawings may differ. Clustering CoefficientThe clustering coefficient assesses the degree to which nodes tend to cluster together, e.g. in social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties  greater than the average probability of a tie randomly established between two nodes. There is a global and a local version of this measure. The global clustering coefficient gives an overall indication of the clustering in the network, whereas the local one gives an indication of the embeddedness of single nodes. The global clustering coefficient is based on triplets of nodes  three nodes that are connected by either two (open triplet) or three (closed triplet) undirected ties. It is calculated as the ratio of the number of closed triplets and the total number of triplets (both open and closed). The local clustering coefficient of a node quantifies how close its neighbors are to being a clique (complete graph). It is used to determine whether a graph is a smallworld network (below). The local clustering coefficient for a node is then given by the proportion of links between the vertices within its neighbourhood divided by the number of links that could possibly exist between them. The measure is 1 if every neighbour connected to the node is also connected to every other vertex within the neighbourhood, and 0 if no vertex that is connected to the node connects to any other vertex that is connected to the node. ConnectivityConnectivity of a graph is a measure of robustness as a network. Two vertices are connected, if there is a path between them. Otherwise they are disconnected. A graph is connected if every pair of vertices is connected. Vertex connectivity is the smallest vertex cut of a connected graph  the number of vertexes that must be removed in order to disconnect the graph. Local connectivity is the size of a smallest vertex cut separating two vertexes in a graph. Graph connectivity equals the minimal local connectivity. Edge connectivity is the smallest number of edge cuts that renders the graph disconnected. Local edge connectivity is the smallest number of edge cuts, that disconnect the two edges. Again, the smallest local edge connectivity in a graph is the graph egde connectivity. The vertex and edgeconnectivities of a disconnected graph are both 0. The complete graph on n vertices has edgeconnectivity equal to n − 1. Every other simple graph on n vertices has strictly smaller edgeconnectivity. In a tree, the local edgeconnectivity between every pair of vertices is 1. Edge connectivity is bounded by vertex connectivity and the latter is bounded by the minimum degree of the graph. Nontrivial Network FeaturesMost real world networks show topological features like a heavy tail in the degree distribution, a high clustering coefficient, assortativity or disassortativity among vertices, community structure, and hierarchical structure. AssortativityAssortativity refers to a preference of a node to attach to other nodes that are similar or different. Similarity is often but not necessarily expressed in terms of a nodes degree, i.e. in social networks, highly connected nodes prefer to attach to other highly connected nodes (assortativity). The oposite effect can be observed in technological and biological networks, where highly connected nodes tend to attach to low degree nodes (dissortativity). Assortativity is measured as correlation between two nodes. The most common measures are assortativity coefficient and neighbor connectivity. The assortativity coefficient is a Pearson correlation coefficient between pais of nodes. The range of the measure r is from 1 for perfect assortative mixing patterns to 1 for completely disassortative. Scalefree networksIn scalefree networks the degree distribution follows the power law. The degree distribution of these networks has no characteristic scale  some vertices have a degree that is orders of magnitude larger than the average (hubs). Networks exhibiting such a distribution are very different from networks, where edges existed independently and at random (Poisson process). Scalefree networks can be created with the Yule process (Gibrat principle, Matthew effect, cumulative advantage, preferential attachement).
These networks show a high robustness to the random vertex cut, i.e., the vast majority of vertices remain connected together in a giant component. However, they are clearly sensible to targeted attacks on hubs. Also, these critical vertices are the ones with the highest degree, and have thus been implicated in the spread of disease (natural and artificial) in social and communication networks, and in the spread of fads. The detection and characterization of power laws is complicated by the large fluctuations that occur in the tail of the distribution—the part of the distribution representing large but rare events—and by the difficulty of identifying the range over which powerlaw behavior holds. Commonly used methods for analyzing powerlaw data, such as leastsquares fitting, can produce substantially inaccurate estimates of parameters for powerlaw distributions, and even in cases where such methods return accurate answers they are still unsatisfactory because they give no indication of whether the data obey a power law at all. Finally, A. Clauset at all. [1] got there brilliant paper published, where they present a principled statistical framework for discerning and quantifying powerlaw behavior in empirical data. The approach combines maximumlikelihood fitting methods with goodnessoffit tests based on the Kolmogorov–Smirnov (KS) statistic and likelihood ratios. The linked page hosts implementations of the methods described in the article and this site contains the 24 data sets.
[1] A. Clauset, C. R. Shalizi, and M. E. J. Newman. Powerlaw distributions in empirical data. SIAM Review, 51(4):661–703, 2009. Smallworld networksA smallworld network (in analogy to six degrees of separation phenomenon) is a regular graph with the addition of only a small number of longrange links. Even if the diameter of a regular graph is proportional to the size of the network, it can be transformed into a "small world" in which the average number of edges between any two vertices is very small. In smallworld networks the diameter should grow as the logarithm of the size of the network, while the clustering coefficient stays large. A wide variety of abstract graphs exhibit the smallworld property, e.g., random graphs and scalefree networks. Real world networks such as the World Wide Web and the metabolic network also exhibit this property. Network Data SetsThe SNAP project on Stanford University maintains a collection of network data sets. Here is a subset of it.
Social Networksonline social networks, edges represent interactions between people
Communication Networksemail communication networks with edges representing communication
Citation Networksnodes represent papers, edges represent citations
Collaboration Networksnodes represent scientists, edges represent collaborations (coauthoring a paper)

Announcements >