Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes (or vertices) and the connections between the elements or actors as links (or edges). The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."
Background and history The study of networks has emerged in diverse disciplines as a means of analyzing complex relational data. The earliest known paper in this field is the famous Seven Bridges of Königsberg written by Leonhard Euler in 1736. Euler's mathematical description of vertices and edges was the foundation of graph theory, a branch of mathematics that studies the properties of pairwise relations in a network structure. The field of graph theory continued to develop and found applications in chemistry. Dénes Kőnig, a Hungarian mathematician and professor, wrote the first book in Graph Theory, entitled "Theory of finite and infinite graphs", in 1936.
In the 1930s Jacob Moreno, a psychologist in the Gestalt tradition, arrived in the United States. He developed the sociogram and presented it to the public in April 1933 at a convention of medical scholars. Moreno claimed that "before the advent of sociometry no one knew what the interpersonal structure of a group 'precisely' looked like". The sociogram was a representation of the social structure of a group of elementary school students. The boys were friends of boys and the girls were friends of girls with the exception of one boy who said he liked a single girl. The feeling was not reciprocated. This network representation of social structure was found so intriguing that it was printed in The New York Times. The sociogram has found many applications and has grown into the field of social network analysis. Probabilistic theory in network science developed as an offshoot of graph theory with Paul Erdős and Alfréd Rényi's eight famous papers on random graphs. For social networks the exponential random graph model or p* is a notational framework used to represent the probability space of a tie occurring in a social network. An alternate approach to network probability structures is the network probability matrix, which models the probability of edges occurring in a network, based on the historic presence or absence of the edge in a sample of networks. Interest in networks exploded around 2000, following new discoveries that offered novel mathematical framework to describe different network topologies, leading to the term 'network science'. Albert-László Barabási and Reka Albert discovered the scale-free networks nature of many real networks, from the WWW to the cell. The scale-free property captures the fact that in real network hubs coexist with many small degree vertices, and the authors offered a dynamical model to explain the origin of this scale-free state. Social networks in particular tend to be weakly scale-free. Duncan Watts and Steven Strogatz reconciled empirical data on networks with mathematical representation, describing the small-world network.
Network classification
Deterministic network The definition of deterministic network is defined compared with the definition of probabilistic network. In un-weighted deterministic networks, edges either exist or not, usually we use 0 to represent non-existence of an edge while 1 to represent existence of an edge. In weighted deterministic networks, the edge value represents the weight of each edge, for example, the strength level.
Probabilistic network In probabilistic networks, values behind each edge represent the likelihood of the existence of each edge. For example, if one edge has a value equals to 0.9, we say the existence probability of this edge is 0.9.
Network properties Often, networks have certain attributes that can be calculated to analyze the properties & characteristics of the network. The behavior of these network properties often define network models and can be used to analyze how certain models contrast to each other. Many of the definitions for other terms used in network science can be found in Glossary of graph theory.
Size The size of a network can refer to the number of nodes N {\displaystyle N} or, less commonly, the number of edges E {\displaystyle E} which (for connected graphs with no multi-edges) can range from N − 1 {\displaystyle N-1} (a tree) to E max {\displaystyle E_{\max }} (a complete graph). In the case of a simple graph (a network in which at most one (undirected) edge exists between each pair of vertices, and in which no vertices connect to themselves), we have E max = ( N 2 ) = N ( N − 1 ) / 2 {\displaystyle E_{\max }={\tbinom {N}{2}}=N(N-1)/2} ; for directed graphs (with no self-connected nodes), E max = N ( N − 1 ) {\displaystyle E_{\max }=N(N-1)} ; for directed graphs with self-connections allowed, E max = N 2 {\displaystyle E_{\max }=N^{2}} . In the circumstance of a graph within which multiple edges may exist between a pair of vertices, E max = ∞ {\displaystyle E_{\max }=\infty } .
Density The density D {\displaystyle D} of a network is defined as a normalized ratio between 0 and 1 of the number of edges E {\displaystyle E} to the number of possible edges in a network with N {\displaystyle N} nodes. Network density is a measure of the percentage of "optional" edges that exist in the network and can be computed as
D = E − E m i n E m a x − E m i n {\displaystyle D={\frac {E-E_{\mathrm {min} }}{E_{\mathrm {max} }-E_{\mathrm {min} }}}}
where E m i n {\displaystyle E_{\mathrm {min} }} and E m a x {\displaystyle E_{\mathrm {max} }} are the minimum and maximum number of edges in a connected network with N {\displaystyle N} nodes, respectively. In the case of simple graphs, E m a x {\displaystyle E_{\mathrm {max} }} is given by the binomial coefficient ( N 2 ) {\displaystyle {\tbinom {N}{2}}} and E m i n = N − 1 {\displaystyle E_{\mathrm {min} }=N-1} , giving density
D = E − ( N − 1 ) E m a x − ( N − 1 ) = 2 ( E − N + 1 ) N ( N − 3 ) + 2 {\displaystyle D={\frac {E-(N-1)}{E_{\mathrm {max} }-(N-1)}}={\frac {2(E-N+1)}{N(N-3)+2}}} . Another possible equation is D = T − 2 N + 2 N ( N − 3 ) + 2 , {\displaystyle D={\frac {T-2N+2}{N(N-3)+2}},} whereas the ties T {\displaystyle T} are unidirectional (Wasserman & Faust 1994). This gives a better overview over the network density, because unidirectional relationships can be measured.
Planar network density The density D {\displaystyle D} of a network, where there is no intersection between edges, is defined as a ratio of the number of edges E {\displaystyle E} to the number of possible edges in a network with N {\displaystyle N} nodes, given by a graph with no intersecting edges ( E max = 3 N − 6 ) {\displaystyle (E_{\max }=3N-6)} , giving D = E − N + 1 2 N − 5 . {\displaystyle D={\frac {E-N+1}{2N-5}}.}
Average degree The degree k {\displaystyle k} of a node is the number of edges connected to it. Closely related to the density of a network is the average degree, ⟨ k ⟩ = 2 E N {\displaystyle \langle k\rangle ={\tfrac {2E}{N}}} (or, in the case of directed graphs, ⟨ k ⟩ = E N {\displaystyle \langle k\rangle ={\tfrac {E}{N}}} , the former factor of 2 arising from each edge in an undirected graph contributing to the degree of two distinct vertices). In the ER random graph model ( G ( N , p ) {\displaystyle G(N,p)} ) we can compute the expected value of ⟨ k ⟩ {\displaystyle \langle k\rangle } (equal to the expected value of k {\displaystyle k} of an arbitrary vertex): a random vertex has N − 1 {\displaystyle N-1} other vertices in the network available, and with probability p {\displaystyle p} , connects to each. Thus, E [ ⟨ k ⟩ ] = E [ k ] = p ( N − 1 ) {\displaystyle \mathbb {E} [\langle k\rangle ]=\mathbb {E} [k]=p(N-1)} .
Degree distribution The degree distribution P ( k ) {\displaystyle P(k)} is a fundamental property of both real networks, such as the Internet and social networks, and of theoretical models. The degree distribution P(k) of a network is defined to be the fraction of nodes in the network with degree k. The simplest network model, for example, the (Erdős–Rényi model) random graph, in which each of n nodes is independently connected (or not) with probability p (or 1 − p), has a binomial distribution of degrees k (or Poisson in the limit of large n). Most real networks, from the WWW to protein interaction networks, however, have a degree distribution that are highly right-skewed, meaning that a large majority of nodes have low degree but a small number, known as "hubs", have high degree. For such scale-free networks the degree distribution approximately follows a power law: P ( k ) ∼ k − γ {\displaystyle P(k)\sim k^{-\gamma }} , where γ is the degree exponent, and is a constant. Such scale-free networks have unexpected structural and dynamical properties, rooted in the diverging second moment of the degree distribution.
Average shortest path length (or characteristic path length) The average shortest path length is calculated by finding the shortest path between all pairs of nodes, and taking the average over all paths of the length thereof (the length being the number of intermediate edges contained in the path, i.e., the distance d u , v {\displaystyle d_{u,v}} between the two vertices u , v {\displaystyle u,v} within the graph). This shows us, on average, the number of steps it takes to get from one member of the network to another. The behavior of the expected average shortest path length (that is, the ensemble average of the average shortest path length) as a function of the number of vertices N {\displaystyle N} of a random network model defines whether that model exhibits the small-world effect; if it scales as O ( ln N ) {\displaystyle O(\ln N)} , the model generates small-world nets. For faster-than-logarithmic growth, the model does not produce small worlds. The special case of O ( ln ln N ) {\displaystyle O(\ln \ln N)} is known as ultra-small world effect.
Diameter of a network As another means of measuring network graphs, we can define the diameter of a network as the longest of all the calculated shortest paths in a network. It is the shortest distance between the two most distant nodes in the network. In other words, once the shortest path length from every node to all other nodes is calculated, the diameter is the longest of all the calculated path lengths. The diameter is representative of the linear size of a network. If node A-B-C-D are connected, going from A->D this would be the diameter of 3 (3-hops, 3-links).
Clustering coefficient The clustering coefficient is a measure of an "all-my-friends-know-each-other" property. This is sometimes described as the friends of my friends are my friends. More precisely, the clustering coefficient of a node is the ratio of existing links connecting a node's neighbors to each other to the maximum possible number of such links. The clustering coefficient for the entire network is the average of the clustering coefficients of all the nodes. A high clustering coefficient for a network is another indication of a small world. The clustering coefficient of the i {\displaystyle i} 'th node is
C i = 2 e i k i ( k i − 1 ) , {\displaystyle C_{i}={2e_{i} \over k_{i}{(k_{i}-1)}}\,,}
where k i {\displaystyle k_{i}} is the number of neighbours of the i {\displaystyle i} 'th node, and e i {\displaystyle e_{i}} is the number of connections between these neighbours. The maximum possible number of connections between neighbors is, then,
( k 2 ) = k ( k − 1 ) 2 . {\displaystyle {\binom {k}{2}}={{k(k-1)} \over 2}\,.}
From a probabilistic standpoint, the expected local clustering coefficient is the likelihood of a link existing between two arbitrary neighbors of the same node.
Connectedness The way in which a network is connected plays a large part into how networks are analyzed and interpreted. Networks are classified in four different categories:
Clique/Complete Graph: a completely connected network, where all nodes are connected to every other node. These networks are symmetric in that all nodes have in-links and out-links from all others. Giant Component: A single connected component which contains most of the nodes in the network. Weakly Connected Component: A collection of nodes in which there exists a path from any node to any other, ignoring directionality of the edges. Strongly Connected Component: A collection of nodes in which there exists a directed path from any node to any other.
Node centrality
Centrality indices produce rankings which seek to identify the most important nodes in a network model. Different centrality indices encode different contexts for the word "importance." The betweenness centrality, for example, considers a node highly important if it form bridges between many other nodes. The eigenvalue centrality, in contrast, considers a node highly important if many other highly important nodes link to it. Hundreds of such measures have been proposed in the literature. Centrality indices are only accurate for identifying the most important nodes. The measures are seldom, if ever, meaningful for the remainder of network nodes. Also, their indications are only accurate within their assumed context for importance, and tend to "get it wrong" for other contexts. For example, imagine two separate communities whose only link is an edge between the most junior member of each community. Since any transfer from one community to the other must go over this link, the two junior members will have high betweenness centrality. But, since they are junior, (presumably) they have few connections to the "important" nodes in their community, meaning their eigenvalue centrality would be quite low.
Node influence
Limitations to centrality measures have led to the development of more general measures. Two examples are the accessibility, which uses the diversity of random walks to measure how accessible the rest of the network is from a given start node, and the expected force, derived from the expected value of the force of infection generated by a node. Both of these measures can be meaningfully computed from the structure of the network alone.
Community structure
Nodes in a network may be partitioned into groups representing communities. Depending on the context, communities may be distinct or overlapping. Typically, nodes in such communities will be strongly connected to other nodes in the same community, but weakly connected to nodes outside the community. In the absence of a ground truth describing the community structure of a specific network, several algorithms have been developed to infer possible community structures using either supervised of unsupervised clustering methods.
Network models Network models serve as a foundation to understanding interactions within empirical complex networks. Various random graph generation models produce network structures that may be used in comparison to real-world complex networks.
Erdős–Rényi random graph model
The Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is used for generating random graphs in which edges are set between nodes with equal probabilities. It can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs. To generate an Erdős–Rényi model G ( n , p ) {\displaystyle G(n,p)} two parameters must be specified: the total number of nodes n and the probability p that a random pair of nodes has an edge. Because the model is generated without bias to particular nodes, the degree distribution is binomial: for a randomly chosen vertex v {\displaystyle v} ,
P ( deg ( v ) = k ) = ( n − 1 k ) p k ( 1 − p ) n − 1 − k . {\displaystyle P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k}.}
In this model the clustering coefficient is 0 a.s. The behavior of G ( n , p ) {\displaystyle G(n,p)} can be broken into three regions. Subcritical n p < 1 {\displaystyle np<1} : All components are simple and very small, the largest component has size | C 1 | = O ( log n ) {\displaystyle |C_{1}|=O(\log n)} ; Critical n p = 1 {\displaystyle np=1} : | C 1 | = O ( n 2 3 ) {\displaystyle |C_{1}|=O(n^{\frac {2}{3}})} ; Supercritical n p > 1 {\displaystyle np>1} : | C 1 | ≈ y n {\displaystyle |C_{1}|\approx yn} where y = y ( n p ) {\displaystyle y=y(np)} is the positive solution to the equation e − p n y = 1 − y {\displaystyle e^{-pny}=1-y} . The largest connected component has high complexity. All other components are simple and small | C 2 | = O ( log n ) {\displaystyle |C_{2}|=O(\log n)} .
Configuration model The configuration model takes a degree sequence or degree distribution (which subsequently is used to generate a degree sequence) as the input, and produces randomly connected graphs in all respects other than the degree sequence. This means that for a given choice of the degree sequence, the graph is chosen uniformly at random from the set of all graphs that comply with this degree sequence. The degree k {\displaystyle k} of a randomly chosen vertex is an independent and identically distributed random variable with integer values. When E [ k 2 ] − 2 E [ k ] > 0 {\textstyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0} , the configuration graph contains the giant connected component, which has infinite size. The rest of the components have finite sizes, which can be quantified with the notion of the size distribution. The probability w ( n ) {\displaystyle w(n)} that a randomly sampled node is connected to a component of size n {\displaystyle n} is given by convolution powers of the degree distribution: w ( n ) = { E [ k ] n − 1 u 1 ∗ n ( n − 2 ) , n > 1 , u ( 0 ) n = 1 , {\displaystyle w(n)={\begin{cases}{\frac {\mathbb {E} [k]}{n-1}}u_{1}^{*n}(n-2),&n>1,\\u(0)&n=1,\end{cases}}} where u ( k ) {\displaystyle u(k)} denotes the degree distribution and u 1 ( k ) = ( k + 1 ) u ( k + 1 ) E [ k ] {\displaystyle u_{1}(k)={\frac {(k+1)u(k+1)}{\mathbb {E} [k]}}} . The giant component can be destroyed by randomly removing the critical fraction p c {\displaystyle p_{c}} of all edges. This process is called percolation on random networks. When the second moment of the degree distribution is finite, E [ k 2 ] < ∞ {\textstyle \mathbb {E} [k^{2}]<\infty } , this critical edge fraction is given by p c = 1 − E [ k ] E [ k 2 ] − E [ k ] {\displaystyle p_{c}=1-{\frac {\mathbb {E} [k]}{\mathbb {E} [k^{2}]-\mathbb {E} [k]}}} , and the average vertex-vertex distance l {\displaystyle l} in the giant component scales logarithmically with the total size of the network, l = O ( log N ) {\displaystyle l=O(\log N)} . In the directed configuration model, the degree of a node is given by two numbers, in-degree k in {\displaystyle k_{\text{in}}} and out-degree k out {\displaystyle k_{\text{out}}} , and consequently, the degree distribution is two-variate. The expected number of in-edges and out-edges coincides, so that E [ k in ] = E [ k out ] {\textstyle \mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]} . The directed configuration model contains the giant component iff 2 E [ k in ] E [ k in k out ] − E [ k in ] E [ k out 2 ] − E [ k in ] E [ k in 2 ] + E [ k in 2 ] E [ k out 2 ] − E [ k in k out ] 2 > 0. {\displaystyle 2\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}k_{\text{out}}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}^{2}]+\mathbb {E} [k_{\text{in}}^{2}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}k_{\text{out}}]^{2}>0.} Note that E [ k in ] {\textstyle \mathbb {E} [k_{\text{in}}]} and E [ k out ] {\textstyle \mathbb {E} [k_{\text{out}}]} are equal and therefore interchangeable in the latter inequality. The probability that a randomly chosen vertex belongs to a component of size n {\displaystyle n} is given by: h in ( n ) = E [ k i n ] n − 1 u ~ in ∗ n ( n − 2 ) , n > 1 , u ~ in = k in + 1 E [ k in ] ∑ k out ≥ 0 u ( k in + 1 , k out ) , {\displaystyle h_{\text{in}}(n)={\frac {\mathbb {E} [k_{in}]}{n-1}}{\tilde {u}}_{\text{in}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{in}}={\frac {k_{\text{in}}+1}{\mathbb {E} [k_{\text{in}}]}}\sum \limits _{k_{\text{out}}\geq 0}u(k_{\text{in}}+1,k_{\text{out}}),} for in-components, and
h out ( n ) = E [ k out ] n − 1 u ~ out ∗ n ( n − 2 ) , n > 1 , u ~ out = k out + 1 E [ k out ] ∑ k in ≥ 0 u ( k in , k out + 1 ) , {\displaystyle h_{\text{out}}(n)={\frac {\mathbb {E} [k_{\text{out}}]}{n-1}}{\tilde {u}}_{\text{out}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{out}}={\frac {k_{\text{out}}+1}{\mathbb {E} [k_{\text{out}}]}}\sum \limits _{k_{\text{in}}\geq 0}u(k_{\text{in}},k_{\text{out}}+1),}
for out-components.
Watts–Strogatz small world model
The Watts and Strogatz model is a random graph generation model that produces graphs with small-world properties. An initial lattice structure is used to generate a Watts–Strogatz model. Each node in the network is initially linked to its ⟨ k ⟩ {\displaystyle \langle k\rangle } closest neighbors. Another parameter is specified as the rewiring prob