Collective intelligence

Collective action

Self-organized criticality

Herd mentality

Phase transition

Agent-based modelling

Synchronization

Ant colony optimization

Particle swarm optimization

Swarm behaviour

Evolution and adaptation

**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."^{[1]}

Evolution and adaptation

- 1 Background and history
- 2 Network properties
- 3 Network models
- 4 Network analysis
- 5 Spread of content in networks
- 6 Interdependent networks
- 7 Multilayer networks
- 8 Network optimization
- 9 See also
- 10 References
- 11 Further reading
- Mathematical models of network behavior to predict performance with network size, complexity, and environment
- Optimized human performance required for network-enabled warfare
- Networking within ecosystems and at the molecular level in cells.
- ${\binom {k}{2}}={{k(k-1)} \over 2}\,.$
*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.*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 theCentrality 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 central nodes. The measures are seldom, if ever, meaningful for the remainder of network nodes.

^{[5]}^{[6]}Also, their indications are only accurate within their assumed context for importance, and tend to "get it wrong" for other contexts.^{[7]}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.The concept of centrality in the context of static netw

Centrality indices are only accurate for identifying the most central nodes. The measures are seldom, if ever, meaningful for the remainder of network nodes.

^{[5]}^{[6]}Also, their indications are only accurate within their assumed context for importance, and tend to "get it wrong" for other contexts.^{[7]}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.The concept of centrality in the context of static networks was extended, based on empirical and theoretical research, to dynamic centrality

^{[8]}in the context of time-dependent and temporal networks.^{[9]}^{[10]}^{[11]}Nodes centrality can be evaluated by the k-shell method. The k-shell method was applied successfully to the Internet identifying the central of the different nodes.

^{[12]}The method is found useful to identify influential spreaders in a network .^{[13]}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,^{[14]}and the**expected force**, derived from the expected value of the force of infection generated by a node.^{[5]}Both of these measures can be meaningfully computed from the structure of the network alone.## Network models

Network models serve as a foundation to understanding interactions within empirical complex networks. Various random gr

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

n ) {\displaystyle |C_{1}|=O(\log n)} ;*Critical*$np<1$: All components are simple and very small, the largest component has size $|C_{1}|=O(\log n)$;*Critical*$np=1$: $|C_{1}|=O(n^{\frac {2}{3}})$;*Supercritical*$np>1$:$|C_{1}|\approx yn$ where $y=y(np)$ is the positive solution to the equation $e^{-pny}=1-y$.The largest connected component has high complexity. All other components are simple and small $|C_{2}|=O(\log n)$.

The configuration model takes a degree sequence

^{[15]}^{[16]}or degree distribution^{[17]}(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$ of a randomly chosen vertex is an independent and identically distributed random variable with integer values. When ${\textstyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0}$, the configuration graph contains the giant connected component, which has infinite size.^{[16]}The rest of the components have finite sizes, which can be quantified with the notion of the size distribution. The probability $w(n)$ that a randomly sampled node is connected to a component of size $n$ is given by convolution powers of the degree distribution:^{[18]}where $u(k)$ denotes the degree distribution and $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}$ of all edges. This process is called percolation on random networks. When the second moment of the degree distribution is finite, ${\textstyle \mathbb {E} [k^{2}]<\infty }$, this critical edge fraction is given by$w(n)={\begin{cases}{\frac {\mathbb {E} [k]}{n-1}}u_{1}^{*n}(n-2),&n>1,\\u(0)&n=1,\end{cases}}$^{[19]}$p_{c}=1-{\frac {\mathbb {E} [k]}{\mathbb {E} [k^{2}]-\mathbb {E} [k]}}$, and the average vertex-vertex distance $l$ in the giant component scales logarithmically with the total size of the network, $l=O(\log N)$.^{[17]}In the directed configuration model, the degree of a node is given by two numbers, in-degree $$$k_{\text{in}}$ and out-degree $k_{\text{out}}$, and consequently, the degree distribution is two-variate. The expected number of in-edges and out-edges coincides, so that ${\textstyle \mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]}$. The directed configuration model contains the giant component iff

^{[20]}Note that ${\textstyle \mathbb {E} [k_{\text{in}}]}$ and ${\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$ is given by:$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.$^{[21]}for in-components, and$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}}),$$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.

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 $\langle k\rangle$ closest neighbors. Another parameter is specified as the rewiring probability. Each edge has a probability $p$ that it will be rewired to the graph as a random edge. The expected number of rewired links in the model is $pE=pN\u27e8k\u27e9An\; initial\; lattice\; structure\; is\; used\; to\; generate\; a\; Watts\u2013Strogatz\; model.\; Each\; node\; in\; the\; network\; is\; initially\; linked\; to\; its$$\langle k\rangle$ closest neighbors. Another parameter is specified as the rewiring probability. Each edge has a probability $p$ that it will be rewired to the graph as a random edge. The expected number of rewired links in the model is $pE=pN\langle k\rangle /2$.

As the Watts–Strogatz model begins as non-random lattice structure, it has a very high clustering coefficient along with high average path length. Each rewire is likely to create a shortcut between highly connected clusters. As the rewiring probability increases, the clustering coefficient decreases slower than the average path length. In effect, this allows the average path length of the network to decrease significantly with only slightly decreases in clustering coefficient. Higher values of p force more rewired edges, which in effect makes the Watts–Strogatz model a random network.

The Barabási–Albert model is a random network model used to demonstrate a preferential attachment or a "rich-get-richer" effect. In this model, an edge is most likely to attach to nodes with higher degrees. The network begins with an initial network of

*m*_{0}nodes.*m*_{0}≥ 2 and the degree of each node in the initial network should be at least 1, otherwise it will always remain disconnected from the rest of the network.In the BA model, new nodes are added to the network one at a time. Each new node is connected to $m$

In the BA model, new nodes are added to the network one at a time. Each new node is connected to $m$ existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability

*p*_{i}that the new node is connected to node*i*is^{[22]}where

*k*_{i}is the degree of node*i*. Heavily linked nodes ("hubs") tend to quickly accumulate even more links, while nodes with only a few links are unlikely to be chosen as the destination for a new link. The new nodes have a "preference" to attach themselves to the already heavily linked nodes.The degree distribution resulting from the BA model is scale free, in particular, it is a power law of the form:

- $P(k)\sim k^{-3}\,$

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 ^{[2]}

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" (Moreno, 1953). 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 (April 3, 1933, page 17). 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.

In 1998, David Krackhardt and Kathleen Carley introduced the idea of a meta-network with the PCANS Model. They suggest that "all organizations are structured along these three domains, Individuals, Tasks, and Resources". Their paper introduced the concept that networks occur across multiple domains and that they are interrelated. This field has grown into another sub-discipline of network science called dynamic network analysis.

More recently other network science efforts have focused on mathematically describing different network topologies. Duncan Watts reconciled empirical data on networks with mathematical representation, describing the small-world network. Albert-László Barabási and Reka Albert developed the scale-free network which is a loosely defined network topology that contains hub vertices with many connections, that grow in a way to maintain a constant ratio in the number of the connections versus all other nodes. Although many networks, such as the internet, appear to maintain this aspect, other networks have long tailed distributions of nodes that only approximate scale free ratios.

The U.S. military first became interested in network-centric warfare as an operational concept based on network science in 1996. John A. Parmentola, the U.S. Army Director for Research and Laboratory Management, proposed to the Army's Board on Science and Technology (BAST) on December 1, 2003 that Network Science become a new Army research area. The BAST, the Division on Engineering and Physical Sciences for the National Research Council (NRC) of the National Academies, serves as a convening authority for the discussion of science and technology issues of importance to the Army and oversees independent Army-related studies conducted by the National Academies. The BAST conducted a study to find out whether identifying and funding a new field of investigation in basic research, Network Science, could help close the gap between what is needed to realize Network-Centric Operations and the current primitive state of fundamental knowledge of networks.

As a result, the BAST issued the NRC study in 2005 titled Network Science (referenced above) that defined a new field of basic research in Network Science for the Army. Based on the findings and recommendations of that study and the subsequent 2007 NRC report titled Strategy for an Army Center for Network Science, Technology, and Experimentation, Army basic research resources were redirected to initiate a new basic research program in Network Science. To build a new theoretical foundation for complex networks, some of the key Network Science research efforts now ongoing in Army laboratories address:

As initiated in 2004 by Frederick I. Moxley with support he solicited from David S. Alberts, the Department of Defense helped to establish the first Network Science Center in conjunction with the U.S. Army at the United States Military Academy (USMA). Under the tutelage of Dr. Moxley and the faculty of the USMA, the first interdisciplinary undergraduate courses in Network Science were taught to cadets at West Point. In order to better instill the tenets of network science among its cadre of future leaders, the USMA has also instituted a five-course undergraduate minor in Network Science.

In 2006, the U.S. Army and th

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 ^{[2]}

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" (Moreno, 1953). 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 (April 3, 1933, page 17). 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

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.

In 1998, David Krackhardt and Kathleen Carley introduced the idea of a meta-network with the PCANS Model. They suggest that "all organizations are structured along these three domains, Individuals, Tasks, and Resources". Their paper introduced the concept that networks occur across multiple domains and that they are interrelated. This field has grown into another sub-discipline of network science called dynamic network analysis.

More recently other network science efforts have focused on mathematically describing different network topologies. Duncan Watts reconciled empirical data on networks with mathematical representation, describing the small-world network. Albert-László Barabási and Reka Albert developed the scale-free network which is a loosely defined network topology that contains hub vertices with many connections, that grow in a way to maintain a constant ratio in the number of the connections versus all other nodes. Although many networks, such as the internet, appear to maintain this aspect, other networks have long tailed distributions of nodes that only approximate scale free ratios.

The U.S. military first became interested in network-centric warfare as an operational concept based on network science in 1996. John A. Parmentola, the U.S. Army Director for Research and Laboratory Management, proposed to the Army's Board on Science and Technology (BAST) on December 1, 2003 that Network Science become a new Army research area. The BAST, the Division on Engineering and Physical Sciences for the National Research Council (NRC) of the National Academies, serves as a convening authority for the discussion of science and technology issues of importance to the Army and oversees independent Army-related studies conducted by the National Academies. The BAST conducted a study to find out whether identifying and funding a new field of investigation in basic research, Network Science, could help close the gap between what is needed to realize Network-Centric Operations and the current primitive state of fundamental knowledge of networks.

As a result, the BAST issued the NRC study in 2005 titled Network Science (referenced above) that defined a new field of basic research in Network Science for the Army. Based on the findings and recommendations of that study and the subsequent 2007 NRC report titled Strategy for an Army Center for Network Science, Technology, and Experimentation, Army basic research resource

As a result, the BAST issued the NRC study in 2005 titled Network Science (referenced above) that defined a new field of basic research in Network Science for the Army. Based on the findings and recommendations of that study and the subsequent 2007 NRC report titled Strategy for an Army Center for Network Science, Technology, and Experimentation, Army basic research resources were redirected to initiate a new basic research program in Network Science. To build a new theoretical foundation for complex networks, some of the key Network Science research efforts now ongoing in Army laboratories address:

As initiated in 2004 by Frederick I. Moxley with support he solicited from David S. Alberts, the Department of Defense helped to establish the first Network Science Center in conjunction with the U.S. Army at the United States Military Academy (USMA). Under the tutelage of Dr. Moxley and the faculty of the USMA, the first interdisciplinary undergraduate courses in Network Science were taught to cadets at West Point. In order to better instill the tenets of network science among its cadre of future leaders, the USMA has also instituted a five-course undergraduate minor in Network Science.

In 2006, the U.S. Army and the United Kingdom (UK) formed the Network and Information Science International Technology Alliance, a collaborative partnership among the Army Researc

In 2006, the U.S. Army and the United Kingdom (UK) formed the Network and Information Science International Technology Alliance, a collaborative partnership among the Army Research Laboratory, UK Ministry of Defense and a consortium of industries and universities in the U.S. and UK. The goal of the alliance is to perform basic research in support of Network- Centric Operations across the needs of both nations.

In 2009, the U.S. Army formed the Network Science CTA, a collaborative research alliance among the Army Research Laboratory, CERDEC, and a consortium of about 30 industrial R&D labs and universities in the U.S. The goal of the alliance is to develop a deep understanding of the underlying commonalities among intertwined social/cognitive, information, and communications networks, and as a result improve our ability to analyze, predict, design, and influence complex systems interweaving many kinds of networks.

Subsequently, as a result of these efforts, the U.S. Department of Defense has sponsored numerous research projects that support Network Science.

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.

The size of a network can refer to the

The size of a network can refer to the number of nodes $N$ or, less commonly, the number of edges $E$ which (for connected graphs with no multi-edges) can range from $N-1$ (a tree) to $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 }={\tbinom {N}{2}}=N(N-1)/2$; for directed graphs (with no self-connected nodes), $E_{\max }=N(N-1)$; for directed graphs with self-connections allowed, $E_{\max }=N^{2}$. In the circumstance of a graph within which multiple edges may exist between a pair of vertices, $E_{\max }=\infty$.

The degree The degree $k$ of a node is the number of edges connected to it. Closely related to the density of a network is the average degree, $\langle k\rangle ={\tfrac {2E}{N}}$ (or, in the case of directed graphs, $\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)$) we can compute the expected value of $\langle k\rangle$ (equal to the expected value of $k$ of an arbitrary vertex): a random vertex has $N-1$ other vertices in the network available, and with probability $p$, connects to each. Thus, $\mathbb {E} [\langle k\rangle ]=\mathbb {E} [k]=p(N-1)$.

When the links or nodes are weighted one can consider the optimal path between nodes.^{[4]}

The clustering coefficient of the $i$

The clustering coefficient of the $i$'th node is

where $k_{i}$ is the number of neighbours of the $i$'th node, and $e_{i}$ is the number of connections between these neighbours. The maximum possible number of connections between neighbors is, then,

From a probabilistic standpoint, the expected local clustering coefficient is the likelihood of a link existing between two arbitrary neighbors of the same node.

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:

Main article: Centrality

Centrality indices produce rankings which seek to identify the most important nodes in a network model. Diffe

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: