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 "non-trivial" topological features. Let's first review some trivial features for regular or random networks, as they are known from graph theory.

Trivial Network Features

Trivial 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 Distribution

The 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 right-skewed, meaning that a large majority of nodes have low degree but a small number, known as "hubs", have high degree (see scale-free-networks below).

The degree sequence is a non-increasing 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 Coefficient

The 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 small-world 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.

Connectivity

Connectivity 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 edge-connectivities of a disconnected graph are both 0. The complete graph on n vertices has edge-connectivity equal to n − 1. Every other simple graph on n vertices has strictly smaller edge-connectivity. In a tree, the local edge-connectivity 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. 

Non-trivial Network Features

Most 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.

Assortativity

Assortativity 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. 

Scale-free networks

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 power-law behavior holds. Commonly used methods for analyzing power-law data, such as least-squares fitting, can produce substantially inaccurate estimates of parameters for power-law 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 power-law behavior in empirical data. The approach combines maximum-likelihood fitting methods with goodness-of-fit 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.

Small-world networks

A small-world network (in analogy to six degrees of separation phenomenon) is a regular graph with the addition of only a small number of long-range 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 small-world 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 small-world property, e.g., random graphs and scale-free networks. Real world networks such as the World Wide Web and the metabolic network also exhibit this property.

Network Data Sets

Social Networks

online social networks, edges represent interactions between people

Communication Networks

email communication networks with edges representing communication

Citation Networks

nodes represent papers, edges represent citations

Collaboration Networks

nodes represent scientists, edges represent collaborations (co-authoring a paper)