Network Science - wikipedia Network Science For other uses, see Network ( disambiguation ). Network science Theory Graph Complex network Contagion Small - world Scale - free Community structure Percolation Evolution Controllability Graph drawing Social capital Link analysis Optimization Reciprocity Closure Homophily Transitivity Preferential attachment Balance theory Network effect Social influence Network types Informational ( computing ) Telecommunication Transport Social Scientific collaboration Biological Artificial neural Interdependent Semantic Spatial Dependency Flow on - Chip Graphs Features Clique Component Cut Cycle Data structure Edge Loop Neighborhood Path Vertex Adjacency list / matrix Incidence list / matrix Types Bipartite Complete Directed Hyper Multi Random Weighted Metrics Algorithms Centrality Degree Betweenness Closeness PageRank Motif Clustering Degree distribution Assortativity Distance Modularity Efficiency Models Topology Random graph Erdős -- Rényi Barabási -- Albert Fitness model Watts -- Strogatz Exponential random ( ERGM ) Random geometric ( RGG ) Hyperbolic ( HGN ) Hierarchical Stochastic block model Lancichinetti -- Fortunato -- Radicchi benchmark Dynamics Boolean network agent based Epidemic / SIR Lists Categories Topics Software Network scientists Category : Network theory Category : Graph theory 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. '' Contents 1 Background and history 1.1 Department of Defense initiatives 2 Network properties 2.1 Size 2.2 Density 2.3 Planar Network Density 2.4 Average degree 2.5 Average shortest path length ( or characteristic path length ) 2.6 Diameter of a network 2.7 Clustering coefficient 2.8 Connectedness 2.9 Node centrality 2.10 Node influence 3 Network models 3.1 Erdős -- Rényi random graph model 3.2 Configuration model 3.3 Watts -- Strogatz small world model 3.4 Barabási -- Albert ( BA ) preferential attachment model 3.4. 1 Mediation - driven attachment ( MDA ) model 3.5 Fitness model 4 Network analysis 4.1 Social network analysis 4.2 Dynamic network analysis 4.3 Biological network analysis 4.4 Link analysis 4.4. 1 Network robustness 4.4. 2 Pandemic analysis 4.4. 2.1 Susceptible to infected 4.4. 2.2 Infected to recovered 4.4. 2.3 Infectious period 4.4. 3 Web link analysis 4.4. 3.1 PageRank 4.4. 3.1. 1 Random jumping 4.5 Centrality measures 5 Spread of content in networks 5.1 The SIR model 5.2 The master equation approach 6 Interdependent networks 7 Multilayer networks 8 Network optimization 9 See also 10 References 11 Further reading 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 ( Sylvester, 1878 ). 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. Moreno 's sociogram of a 1st grade class. 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. Department of Defense initiatives 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 : 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. 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 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. 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 ratio of the number of edges E ( displaystyle E ) to the number of possible edges in a network with N ( displaystyle N ) nodes, given ( in the case of simple graphs ) by the binomial coefficient ( N 2 ) ( displaystyle ( \tbinom ( N ) ( 2 ) ) ), giving D = 2 ( E − N + 1 ) N ( N − 3 ) + 2. ( displaystyle D = ( \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 ) ). 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. 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 probabalistic 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 Main article : 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 central 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. The concept of centrality in the context of static networks was extended, based on empirical and theoretical research, to dynamic centrality in the context of time - dependent and temporal networks. Node influence Main article : Node influence metric 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. 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 This Erdős -- Rényi model is generated with N = 4 nodes. For each edge in the complete graph formed by all N nodes, a random number is generated and compared to a given probability. If the random number is less than p, an edge is formed on the 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 uses the concept of rewiring to achieve its structure. The model generator will iterate through each edge in the original lattice structure. An edge may changed its connected vertices according to a given rewiring probability. ⟨ k ⟩ = 4 ( displaystyle langle k \rangle = 4 ) in this example. 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 probability. Each edge has a probability p ( displaystyle p ) that it will be rewired to the graph as a random edge. The expected number of rewired links in the model is p E = p N ⟨ k ⟩ / 2 ( displaystyle 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. Barabási -- Albert ( BA ) preferential attachment model 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 nodes. m ≥ 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 ( displaystyle m ) existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability p that the new node is connected to node i is p i = k i ∑ j k j, ( displaystyle p_ ( i ) = ( \frac ( k_ ( i ) ) ( sum _ ( j ) k_ ( j ) ) ), ) where k 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 of the BA Model, which follows a power law. In loglog scale the power law function is a straight line. The degree distribution resulting from the BA model is scale free, in particular, it is a power law of the form : P ( k ) ∼ k − 3 ( displaystyle P ( k ) sim k ^ ( - 3 ) , ) Hubs exhibit high betweenness centrality which allows short paths to exist between nodes. As a result, the BA model tends to have very short average path lengths. The clustering coefficient of this model also tends to 0. While the diameter, D, of many models including the Erdős Rényi random graph model and several small world networks is proportional to log N, the BA model exhibits D ~ loglogN ( ultrasmall world ). Note that the average path length scales with N as the diameter. Mediation - driven attachment ( MDA ) model In the mediation - driven attachment ( MDA ) model in which a new node coming with m ( displaystyle m ) edges picks an existing connected node at random and then connects itself not with that one but with m ( displaystyle m ) of its neighbors chosen also at random. The probability Π ( i ) ( displaystyle Pi ( i ) ) that the node i ( displaystyle i ) of the existing node picked is Π ( i ) = k i N ∑ j = 1 k i 1 k j k i. ( displaystyle Pi ( i ) = ( \frac ( k_ ( i ) ) ( N ) ) ( \frac ( sum _ ( j = 1 ) ^ ( k_ ( i ) ) ( \frac ( 1 ) ( k_ ( j ) ) ) ) ( k_ ( i ) ) ). ) The factor ∑ j = 1 k i 1 k j k i ( displaystyle ( \frac ( sum _ ( j = 1 ) ^ ( k_ ( i ) ) ( \frac ( 1 ) ( k_ ( j ) ) ) ) ( k_ ( i ) ) ) ) is the inverse of the harmonic mean ( IHM ) of degrees of the k i ( displaystyle k_ ( i ) ) neighbors of a node i ( displaystyle i ). Extensive numerical investigation suggest that for an approximately m > 14 ( displaystyle m > 14 ) the mean IHM value in the large N ( displaystyle N ) limit becomes a constant which means Π ( i ) ∝ k i ( displaystyle Pi ( i ) propto k_ ( i ) ). It implies that the higher the links ( degree ) a node has, the higher its chance of gaining more links since they can be reached in a larger number of ways through mediators which essentially embodies the intuitive idea of rich get richer mechanism ( or the preferential attachment rule of the Barabasi -- Albert model ). Therefore, the MDA network can be seen to follow the PA rule but in disguise. However, for m = 1 ( displaystyle m = 1 ) it describes the winner takes it all mechanism as we find that almost 99 % ( displaystyle 99 % ) of the total nodes have degree one and one is super-rich in degree. As m ( displaystyle m ) value increases the disparity between the super rich and poor decreases and as m > 14 ( displaystyle m > 14 ) we find a transition from rich get super richer to rich get richer mechanism. Fitness model Another model where the key ingredient is the nature of the vertex has been introduced by Caldarelli et al. Here a link is created between two vertices i, j ( displaystyle i, j ) with a probability given by a linking function f ( η i, η j ) ( displaystyle f ( eta _ ( i ), eta _ ( j ) ) ) of the fitnesses of the vertices involved. The degree of a vertex i is given by k ( η i ) = N ∫ 0 ∞ f ( η i, η j ) ρ ( η j ) d η j ( displaystyle k ( eta _ ( i ) ) = N int _ ( 0 ) ^ ( infty ) f ( eta _ ( i ), eta _ ( j ) ) \rho ( eta _ ( j ) ) , d eta _ ( j ) ) If k ( η i ) ( displaystyle k ( eta _ ( i ) ) ) is an invertible and increasing function of η i ( displaystyle eta _ ( i ) ), then the probability distribution P ( k ) ( displaystyle P ( k ) ) is given by P ( k ) = ρ ( η ( k ) ) ⋅ η ′ ( k ) ( displaystyle P ( k ) = \rho ( eta ( k ) ) cdot eta ' ( k ) ) As a result, if the fitnesses η ( displaystyle eta ) are distributed as a power law, then also the node degree does. Less intuitively with a fast decaying probability distribution as ρ ( η ) = e − η ( displaystyle \rho ( eta ) = e ^ ( - eta ) ) together with a linking function of the kind f ( η i, η j ) = Θ ( η i + η j − Z ) ( displaystyle f ( eta _ ( i ), eta _ ( j ) ) = Theta ( eta _ ( i ) + eta _ ( j ) - Z ) ) with Z ( displaystyle Z ) a constant and Θ ( displaystyle Theta ) the Heavyside function, we also obtain scale - free networks. Such model has been successfully applied to describe trade between nations by using GDP as fitness for the various nodes i, j ( displaystyle i, j ) and a linking function of the kind δ η i η j 1 + δ η i η j. ( displaystyle ( \frac ( delta eta _ ( i ) eta _ ( j ) ) ( 1 + delta eta _ ( i ) eta _ ( j ) ) ). ) Network analysis Social network analysis Social network analysis examines the structure of relationships between social entities. These entities are often persons, but may also be groups, organizations, nation states, web sites, scholarly publications. Since the 1970s, the empirical study of networks has played a central role in social science, and many of the mathematical and statistical tools used for studying networks have been first developed in sociology. Amongst many other applications, social network analysis has been used to understand the diffusion of innovations, news and rumors. Similarly, it has been used to examine the spread of both diseases and health - related behaviors. It has also been applied to the study of markets, where it has been used to examine the role of trust in exchange relationships and of social mechanisms in setting prices. Similarly, it has been used to study recruitment into political movements and social organizations. It has also been used to conceptualize scientific disagreements as well as academic prestige. More recently, network analysis ( and its close cousin traffic analysis ) has gained a significant use in military intelligence, for uncovering insurgent networks of both hierarchical and leaderless nature. Dynamic network analysis Dynamic network analysis examines the shifting structure of relationships among different classes of entities in complex socio - technical systems effects, and reflects social stability and changes such as the emergence of new groups, topics, and leaders. Dynamic Network Analysis focuses on meta - networks composed of multiple types of nodes ( entities ) and multiple types of links. These entities can be highly varied. Examples include people, organizations, topics, resources, tasks, events, locations, and beliefs. Dynamic network techniques are particularly useful for assessing trends and changes in networks over time, identification of emergent leaders, and examining the co-evolution of people and ideas. Biological network analysis With the recent explosion of publicly available high throughput biological data, the analysis of molecular networks has gained significant interest. The type of analysis in this content are closely related to social network analysis, but often focusing on local patterns in the network. For example, network motifs are small subgraphs that are over-represented in the network. Activity motifs are similar over-represented patterns in the attributes of nodes and edges in the network that are over represented given the network structure. The analysis of biological networks has led to the development of network medicine, which looks at the effect of diseases in the interactome. Link analysis Link analysis is a subset of network analysis, exploring associations between objects. An example may be examining the addresses of suspects and victims, the telephone numbers they have dialed and financial transactions that they have partaken in during a given timeframe, and the familial relationships between these subjects as a part of police investigation. Link analysis here provides the crucial relationships and associations between very many objects of different types that are not apparent from isolated pieces of information. Computer - assisted or fully automatic computer - based link analysis is increasingly employed by banks and insurance agencies in fraud detection, by telecommunication operators in telecommunication network analysis, by medical sector in epidemiology and pharmacology, in law enforcement investigations, by search engines for relevance rating ( and conversely by the spammers for spamdexing and by business owners for search engine optimization ), and everywhere else where relationships between many objects have to be analyzed. Network robustness The structural robustness of networks is studied using percolation theory. When a critical fraction of nodes is removed the network becomes fragmented into small clusters. This phenomenon is called percolation and it represents an order - disorder type of phase transition with critical exponents. Pandemic analysis The SIR model is one of the most well known algorithms on predicting the spread of global pandemics within an infectious population. Susceptible to infected S = β ( 1 N ) ( displaystyle S = \beta left ( ( \frac ( 1 ) ( N ) ) \right ) ) The formula above describes the `` force '' of infection for each susceptible unit in an infectious population, where β is equivalent to the transmission rate of said disease. To track the change of those susceptible in an infectious population : Δ S = β × S 1 N Δ t ( displaystyle Delta S = \beta \times S ( 1 over N ) , Delta t ) Infected to recovered Δ I = μ I Δ t ( displaystyle Delta I = mu I , Delta t ) Over time, the number of those infected fluctuates by : the specified rate of recovery, represented by μ ( displaystyle mu ) but deducted to one over the average infectious period 1 τ ( displaystyle ( 1 over \tau ) ), the numbered of infectious individuals, I ( displaystyle I ), and the change in time, Δ t ( displaystyle Delta t ). Infectious period Whether a population will be overcome by a pandemic, with regards to the SIR model, is dependent on the value of R 0 ( displaystyle R_ ( 0 ) ) or the `` average people infected by an infected individual. '' R 0 = β τ = β μ ( displaystyle R_ ( 0 ) = \beta \tau = ( \beta over mu ) ) Web link analysis Several Web search ranking algorithms use link - based centrality metrics, including ( in order of appearance ) Marchiori 's Hyper Search, Google 's PageRank, Kleinberg 's HITS algorithm, the CheiRank and TrustRank algorithms. Link analysis is also conducted in information science and communication science in order to understand and extract information from the structure of collections of web pages. For example, the analysis might be of the interlinking between politicians ' web sites or blogs. PageRank PageRank works by randomly picking `` nodes '' or websites and then with a certain probability, `` randomly jumping '' to other nodes. By randomly jumping to these other nodes, it helps PageRank completely traverse the network as some webpages exist on the periphery and would not as readily be assessed. Each node, x i ( displaystyle x_ ( i ) ), has a PageRank as defined by the sum of pages j ( displaystyle j ) that link to i ( displaystyle i ) times one over the outlinks or `` out - degree '' of j ( displaystyle j ) times the `` importance '' or PageRank of j ( displaystyle j ). x i = ∑ j → i 1 N j x j ( k ) ( displaystyle x_ ( i ) = sum _ ( j \rightarrow i ) ( 1 over N_ ( j ) ) x_ ( j ) ^ ( ( k ) ) ) Random jumping As explained above, PageRank enlists random jumps in attempts to assign PageRank to every website on the internet. These random jumps find websites that might not be found during the normal search methodologies such as Breadth - First Search and Depth - First Search. In an improvement over the aforementioned formula for determining PageRank includes adding these random jump components. Without the random jumps, some pages would receive a PageRank of 0 which would not be good. The first is α ( displaystyle alpha ), or the probability that a random jump will occur. Contrasting is the `` damping factor '', or 1 − α ( displaystyle 1 - alpha ). R ( p ) = α N + ( 1 − α ) ∑ j → i 1 N j x j ( k ) ( displaystyle R ( ( p ) ) = ( alpha over N ) + ( 1 - alpha ) sum _ ( j \rightarrow i ) ( 1 over N_ ( j ) ) x_ ( j ) ^ ( ( k ) ) ) Another way of looking at it : R ( A ) = ∑ R B B ( outlinks ) + ⋯ + R n n ( outlinks ) ( displaystyle R ( A ) = sum ( R_ ( B ) over B_ ( \text ( ( outlinks ) ) ) ) + cdots + ( R_ ( n ) over n_ ( \text ( ( outlinks ) ) ) ) ) Centrality measures Information about the relative importance of nodes and edges in a graph can be obtained through centrality measures, widely used in disciplines like sociology. Centrality measures are essential when a network analysis has to answer questions such as : `` Which nodes in the network should be targeted to ensure that a message or information spreads to all or most nodes in the network ? '' or conversely, `` Which nodes should be targeted to curtail the spread of a disease ? ''. Formally established measures of centrality are degree centrality, closeness centrality, betweenness centrality, eigenvector centrality, and katz centrality. The objective of network analysis generally determines the type of centrality measure ( s ) to be used. Degree centrality of a node in a network is the number of links ( vertices ) incident on the node. Closeness centrality determines how `` close '' a node is to other nodes in a network by measuring the sum of the shortest distances ( geodesic paths ) between that node and all other nodes in the network. Betweenness centrality determines the relative importance of a node by measuring the amount of traffic flowing through that node to other nodes in the network. This is done by measuring the fraction of paths connecting all pairs of nodes and containing the node of interest. Group Betweenness centrality measures the amount of traffic flowing through a group of nodes. Eigenvector centrality is a more sophisticated version of degree centrality where the centrality of a node not only depends on the number of links incident on the node but also the quality of those links. This quality factor is determined by the eigenvectors of the adjacency matrix of the network. Katz centrality of a node is measured by summing the geodesic paths between that node and all ( reachable ) nodes in the network. These paths are weighted, paths connecting the node with its immediate neighbors carry higher weights than those which connect with nodes farther away from the immediate neighbors. Spread of content in networks Content in a complex network can spread via two major methods : conserved spread and non-conserved spread. In conserved spread, the total amount of content that enters a complex network remains constant as it passes through. The model of conserved spread can best be represented by a pitcher containing a fixed amount of water being poured into a series of funnels connected by tubes. Here, the pitcher represents the original source and the water is the content being spread. The funnels and connecting tubing represent the nodes and the connections between nodes, respectively. As the water passes from one funnel into another, the water disappears instantly from the funnel that was previously exposed to the water. In non-conserved spread, the amount of content changes as it enters and passes through a complex network. The model of non-conserved spread can best be represented by a continuously running faucet running through a series of funnels connected by tubes. Here, the amount of water from the original source is infinite Also, any funnels that have been exposed to the water continue to experience the water even as it passes into successive funnels. The non-conserved model is the most suitable for explaining the transmission of most infectious diseases. The SIR model In 1927, W.O. Kermack and A.G. McKendrick created a model in which they considered a fixed population with only three compartments, susceptible : S ( t ) ( displaystyle S ( t ) ), infected, I ( t ) ( displaystyle I ( t ) ), and recovered, R ( t ) ( displaystyle R ( t ) ). The compartments used for this model consist of three classes : S ( t ) ( displaystyle S ( t ) ) is used to represent the number of individuals not yet infected with the disease at time t, or those susceptible to the disease I ( t ) ( displaystyle I ( t ) ) denotes the number of individuals who have been infected with the disease and are capable of spreading the disease to those in the susceptible category R ( t ) ( displaystyle R ( t ) ) is the compartment used for those individuals who have been infected and then recovered from the disease. Those in this category are not able to be infected again or to transmit the infection to others. The flow of this model may be considered as follows : S → I → R ( displaystyle ( mathcal ( S ) ) \rightarrow ( mathcal ( I ) ) \rightarrow ( mathcal ( R ) ) ) Using a fixed population, N = S ( t ) + I ( t ) + R ( t ) ( displaystyle N = S ( t ) + I ( t ) + R ( t ) ), Kermack and McKendrick derived the following equations : d S d t = − β S I d I d t = β S I − γ I d R d t = γ I ( displaystyle ( \begin ( aligned ) ( \frac ( dS ) ( dt ) ) & = - \beta SI ( 8pt ) ( \frac ( dI ) ( dt ) ) & = \beta SI - gamma I ( 8pt ) ( \frac ( dR ) ( dt ) ) & = gamma I end ( aligned ) ) ) Several assumptions were made in the formulation of these equations : First, an individual in the population must be considered as having an equal probability as every other individual of contracting the disease with a rate of β ( displaystyle \beta ), which is considered the contact or infection rate of the disease. Therefore, an infected individual makes contact and is able to transmit the disease with β N ( displaystyle \beta N ) others per unit time and the fraction of contacts by an infected with a susceptible is S / N ( displaystyle S / N ). The number of new infections in unit time per infective then is β N ( S / N ) ( displaystyle \beta N ( S / N ) ), giving the rate of new infections ( or those leaving the susceptible category ) as β N ( S / N ) I = β S I ( displaystyle \beta N ( S / N ) I = \beta SI ) ( Brauer & Castillo - Chavez, 2001 ). For the second and third equations, consider the population leaving the susceptible class as equal to the number entering the infected class. However, a number equal to the fraction ( γ ( displaystyle gamma ) which represents the mean recovery rate, or 1 / γ ( displaystyle 1 / gamma ) the mean infective period ) of infectives are leaving this class per unit time to enter the removed class. These processes which occur simultaneously are referred to as the Law of Mass Action, a widely accepted idea that the rate of contact between two groups in a population is proportional to the size of each of the groups concerned ( Daley & Gani, 2005 ). Finally, it is assumed that the rate of infection and recovery is much faster than the time scale of births and deaths and therefore, these factors are ignored in this model. More can be read on this model on the Epidemic model page. The master equation approach A master equation can express the behaviour of an undirected growing network where, at each time step, a new node is added to the network, linked to an old node ( randomly chosen and without preference ). The initial network is formed by two nodes and two links between them at time t = 2 ( displaystyle t = 2 ), this configuration is necessary only to simplify further calculations, so at time t = n ( displaystyle t = n ) the network have n ( displaystyle n ) nodes and n ( displaystyle n ) links. The master equation for this network is : p ( k, s, t + 1 ) = 1 t p ( k − 1, s, t ) + ( 1 − 1 t ) p ( k, s, t ), ( displaystyle p ( k, s, t + 1 ) = ( \frac ( 1 ) ( t ) ) p ( k - 1, s, t ) + left ( 1 - ( \frac ( 1 ) ( t ) ) \right ) p ( k, s, t ), ) where p ( k, s, t ) ( displaystyle p ( k, s, t ) ) is the probability to have the node s ( displaystyle s ) with degree k ( displaystyle k ) at time t + 1 ( displaystyle t + 1 ), and s ( displaystyle s ) is the time step when this node was added to the network. Note that there are only two ways for an old node s ( displaystyle s ) to have k ( displaystyle k ) links at time t + 1 ( displaystyle t + 1 ) : The node s ( displaystyle s ) have degree k − 1 ( displaystyle k - 1 ) at time t ( displaystyle t ) and will be linked by the new node with probability 1 / t ( displaystyle 1 / t ) Already has degree k ( displaystyle k ) at time t ( displaystyle t ) and will not be linked by the new node. After simplifying this model, the degree distribution is P ( k ) = 2 − k. ( displaystyle P ( k ) = 2 ^ ( - k ). ) Based on this growing network, an epidemic model is developed following a simple rule : Each time the new node is added and after choosing the old node to link, a decision is made : whether or not this new node will be infected. The master equation for this epidemic model is : p r ( k, s, t ) = r t 1 t p r ( k − 1, s, t ) + ( 1 − 1 t ) p r ( k, s, t ), ( displaystyle p_ ( r ) ( k, s, t ) = r_ ( t ) ( \frac ( 1 ) ( t ) ) p_ ( r ) ( k - 1, s, t ) + left ( 1 - ( \frac ( 1 ) ( t ) ) \right ) p_ ( r ) ( k, s, t ), ) where r t ( displaystyle r_ ( t ) ) represents the decision to infect ( r t = 1 ( displaystyle r_ ( t ) = 1 ) ) or not ( r t = 0 ( displaystyle r_ ( t ) = 0 ) ). Solving this master equation, the following solution is obtained : P ~ r ( k ) = ( r 2 ) k. ( displaystyle ( \tilde ( P ) ) _ ( r ) ( k ) = left ( ( \frac ( r ) ( 2 ) ) \right ) ^ ( k ). ) Interdependent networks Main article : Interdependent networks An interdependent network is a system of coupled networks where nodes of one or more networks depend on nodes in other networks. Such dependencies are enhanced by the developments in modern technology. Dependencies may lead to cascading failures between the networks and a relatively small failure can lead to a catastrophic breakdown of the system. Blackouts are a fascinating demonstration of the important role played by the dependencies between networks. A recent study developed a framework to study the cascading failures in an interdependent networks system. Multilayer networks Main article : Multidimensional network Multilayer networks are networks with multiple kinds of relations. Increasingly sophisticated attempts to model real - world systems as multidimensional networks have yielded valuable insight in the fields of social network analysis, economics, history, urban and international transport, ecology, psychology, medicine, biology, commerce, climatology, physics, computational neuroscience, operations management, and finance. Network optimization Network problems that involve finding an optimal way of doing something are studied under the name of combinatorial optimization. Examples include network flow, shortest path problem, transport problem, transshipment problem, location problem, matching problem, assignment problem, packing problem, routing problem, Critical Path Analysis and PERT ( Program Evaluation & Review Technique ). See also Climate as complex networks Collaborative innovation network Communicative ecology Complex network Core - periphery structures in networks Dual - phase evolution Erdős -- Rényi model Glossary of graph theory Higher category theory Immune network theory Irregular warfare Network analyzer Network dynamics Network formation Network theory in risk assessment Network topology Networks in labor economics Non-linear preferential attachment Percolation Policy network analysis Polytely Quantum complex network Random networks Rumor spread in social network Scale - free networks Sequential dynamical system Service network Small - world networks Structural cut - off Systems theory References Jump up ^ Committee on Network Science for Future Army Applications ( 2006 ). Network Science. National Research Council. ISBN 0309653886. Jump up ^ http://psycnet.apa.org/journals/prs/9/4/172/ ^ Jump up to : Lawyer, Glenn ( March 2015 ). `` Understanding the spreading power of all nodes in a network ''. Scientific Reports. 5 ( O8665 ) : 8665. arXiv : 1405.6707. Bibcode : 2015NatSR... 5E8665L. doi : 10.1038 / srep08665. PMC 4345333. PMID 25727453. Jump up ^ Sikic, Mile ; Lancic, Alen ; Antulov - Fantulin, Nino ; Stefancic, Hrvoje ( October 2013 ). `` Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes ? ''. European Physical Journal B. 86 ( 10 ) : 1 -- 13. arXiv : 1110.2558. Bibcode : 2013EPJB... 86... 440S. doi : 10.1140 / epjb / e2013 - 31025 - 5. Jump up ^ Borgatti, Stephen P. ( 2005 ). `` Centrality and Network Flow ''. Social Networks. Elsevier. 27 : 55 -- 71. doi : 10.1016 / j. socnet. 2004.11. 008. ^ Jump up to : Braha, D. ; Bar - Yam, Y. ( 2006 ). `` From Centrality to Temporary Fame : Dynamic Centrality in Complex Networks ''. Complexity. 12 : 59 -- 63. arXiv : physics / 0611295. Bibcode : 2006Cmplx... 12b... 59B. doi : 10.1002 / cplx. 20156. ^ Jump up to : Hill, S.A. ; Braha, D. ( 2010 ). `` Dynamic Model of Time - Dependent Complex Networks ''. Physical Review E. 82 : 046105. arXiv : 0901.4407. Bibcode : 2010PhRvE... 82d6105H. doi : 10.1103 / physreve. 82.046105. ^ Jump up to : Gross, T. and Sayama, H. ( Eds. ). 2009. Adaptive Networks : Theory, Models and Applications. Springer. ^ Jump up to : Holme, P. and Saramäki, J. 2013. Temporal Networks. Springer. Jump up ^ Travençolo, B.A.N. ; da F. Costa, L. ( 2008 ). `` Accessibility in complex networks ''. Physics Letters A. 373 ( 1 ) : 89 -- 95. Bibcode : 2008PhLA... 373... 89T. doi : 10.1016 / j. physleta. 2008.10. 069. Jump up ^ Bender, Edward A ; Canfield, E. Rodney ( May 1978 ). `` The asymptotic number of labeled graphs with given degree sequences ''. Journal of Combinatorial Theory, Series A. 24 ( 3 ) : 296 -- 307. doi : 10.1016 / 0097 - 3165 ( 78 ) 90059 - 6. ISSN 0097 - 3165. ^ Jump up to : Molloy, Michael ; Reed, Bruce ( March 1995 ). `` A critical point for random graphs with a given degree sequence ''. Random Structures & Algorithms. 6 ( 2 -- 3 ) : 161 -- 180. doi : 10.1002 / rsa. 3240060204. ISSN 1042 - 9832. ^ Jump up to : Newman, M.E.J. ; Strogatz, S.H. ; Watts, D.J. ( 2001 - 07 - 24 ). `` Random graphs with arbitrary degree distributions and their applications ''. Physical Review E. 64 ( 2 ) : 026118. arXiv : cond - mat / 0007235. Bibcode : 2001PhRvE... 64b6118N. doi : 10.1103 / PhysRevE. 64.026118. Jump up ^ Kryven, Ivan ( 2017 - 05 - 02 ). `` General expression for the component size distribution in infinite configuration networks ''. Physical Review E. 95 ( 5 ) : 052303. arXiv : 1703.05413. Bibcode : 2017PhRvE... 95e2303K. doi : 10.1103 / PhysRevE. 95.052303. Jump up ^ Kryven, Ivan ( 2018 - 01 - 01 ). `` Analytic results on the polymerisation random graph model ''. Journal of Mathematical Chemistry. 56 ( 1 ) : 140 -- 157. doi : 10.1007 / s10910 - 017 - 0785 - 1. ISSN 0259 - 9791. Jump up ^ Kryven, Ivan ( 2016 - 07 - 27 ). `` Emergence of the giant weak component in directed random graphs with arbitrary degree distributions ''. Physical Review E. 94 ( 1 ) : 012315. arXiv : 1607.03793. Bibcode : 2016PhRvE... 94a2315K. doi : 10.1103 / PhysRevE. 94.012315. Jump up ^ Kryven, Ivan ( 2017 - 11 - 02 ). `` Finite connected components in infinite directed and multiplex networks with arbitrary degree distributions ''. Physical Review E. 96 ( 5 ) : 052304. arXiv : 1709.04283. Bibcode : 2017PhRvE... 96e2304K. doi : 10.1103 / PhysRevE. 96.052304. Jump up ^ R. Albert ; A. - L. Barabási ( 2002 ). `` Statistical mechanics of complex networks '' ( PDF ). Reviews of Modern Physics. 74 : 47 -- 97. arXiv : cond - mat / 0106096. Bibcode : 2002RvMP... 74... 47A. doi : 10.1103 / RevModPhys. 74.47. Archived from the original ( PDF ) on 2015 - 08 - 24. Jump up ^ Albert - László Barabási & Réka Albert ( October 1999 ). `` Emergence of scaling in random networks '' ( PDF ). Science. 286 ( 5439 ) : 509&ndash, 512. arXiv : cond - mat / 9910332. Bibcode : 1999Sci... 286... 509B. doi : 10.1126 / science. 286.5439. 509. PMID 10521342. Archived from the original ( PDF ) on 2012 - 04 - 17. Jump up ^ Cohen, R. ; Havlin, S. ( 2003 ). `` Scale - free networks are ultrasmall ''. Phys. Rev. Lett. 90 ( 5 ) : 058701. arXiv : cond - mat / 0205476. Bibcode : 2003PhRvL... 90e8701C. doi : 10.1103 / PhysRevLett. 90.058701. PMID 12633404. Jump up ^ Hassan, M.K. ; Islam, Liana ; Arefinul Haque, Syed ( March 2017 ). `` Degree distribution, rank - size distribution, and leadership persistence in mediation - driven attachment networks ''. Physica A. 469 : 23 -- 30. arXiv : 1411.3444. Bibcode : 2017PhyA... 469... 23H. doi : 10.1016 / j. physa. 2016.11. 001. Jump up ^ Caldarelli G., A. Capocci, P. De Los Rios, M.A. Muñoz, Physical Review Letters 89, 258702 ( 2002 ) Jump up ^ Servedio V.D.P., G. Caldarelli, P. Buttà, Physical Review E 70, 056126 ( 2004 ) Jump up ^ Garlaschelli D., MI Loffredo Physical Review Letters 93, 188701 ( 2004 ) Jump up ^ Cimini G., T. Squartini, D. Garlaschelli and A. Gabrielli, Scientific Reports 5, 15758 ( 2015 ) ^ Jump up to : Wasserman, Stanley and Katherine Faust. 1994. Social Network Analysis : Methods and Applications. Cambridge : Cambridge University Press. Jump up ^ Newman, M.E.J. Networks : An Introduction. Oxford University Press. 2010, ISBN 978 - 0199206650 Jump up ^ `` Toward a Complex Adaptive Intelligence Community The Wiki and the Blog ''. D. Calvin Andrus. cia.gov. Retrieved 25 August 2012. Jump up ^ Network analysis of terrorist networks Jump up ^ Xanthos, Aris, Pante, Isaac, Rochat, Yannick, Grandjean, Martin ( 2016 ). Visualising the Dynamics of Character Networks. In Digital Humanities 2016 : Jagiellonian University & Pedagogical University, Kraków, pp. 417 -- 419. Jump up ^ Barabási, A.L. ; Gulbahce, N. ; Loscalzo, J. ( 2011 ). `` Network medicine : a network - based approach to human disease ''. Nature Reviews Genetics. 12 ( 1 ) : 56 -- 68. doi : 10.1038 / nrg2918. PMC 3140052. PMID 21164525. Jump up ^ R. Cohen ; S. Havlin ( 2010 ). Complex Networks : Structure, Robustness and Function. Cambridge University Press. Jump up ^ A. Bunde ; S. Havlin ( 1996 ). Fractals and Disordered Systems. Springer. Jump up ^ Puzis, R. ; Yagil, D. ; Elovici, Y. ; Braha, D. ( 2009 ). `` Collaborative attack on Internet users ' anonymity '' ( PDF ). Internet Research. 19 : 1. Jump up ^ Newman, M., Barabási, A. - L., Watts, D.J. ( eds. ) ( 2006 ) The Structure and Dynamics of Networks. Princeton, N.J. : Princeton University Press. Jump up ^ Dorogovtsev, SN ; Mendes, JFF ( 2003 ). Evolution of Networks : From Biological Nets to the Internet and WWW. New York, NY, USA : Oxford University Press, Inc. ISBN 0198515901. Jump up ^ Cotacallapa, M ; Hase, MO ( 2016 ). `` Epidemics in networks : a master equation approach ''. Journal of Physics A. 49 ( 6 ) : 065001. arXiv : 1604.01049. Bibcode : 2016JPhA... 49f5001C. doi : 10.1088 / 1751 - 8113 / 49 / 6 / 065001. Retrieved 2 August 2016. Jump up ^ S.V. Buldyrev ; R. Parshani ; G. Paul ; H.E. Stanley ; S. Havlin ( 2010 ). `` Catastrophic cascade of failures in interdependent networks ''. Nature. 464 ( 7291 ) : 1025 -- 28. arXiv : 0907.1182. Bibcode : 2010Natur. 464.1025 B. doi : 10.1038 / nature08932. PMID 20393559. Jump up ^ Gao, Jianxi ; Buldyrev, Sergey V. ; Havlin, Shlomo ; Stanley, H. Eugene ( 2011 ). `` Robustness of a Network of Networks ''. Phys. Rev. Lett. 107 ( 19 ) : 195701. arXiv : 1010.5829. Bibcode : 2011PhRvL. 107s5701G. doi : 10.1103 / PhysRevLett. 107.195701. PMID 22181627. Jump up ^ Coscia, Michele ; Rossetti, Giulio ; Pennacchioli, Diego ; Ceccarelli, Damiano ; Giannotti, Fosca ( 2013 ). `` '' You Know Because I Know `` : A Multidimensional Network Approach to Human Resources Problem ''. Advances in Social Network Analysis and Mining ( ASONAM ). 2013 : 434. arXiv : 1305.7146. doi : 10.1145 / 2492517.2492537. ISBN 9781450322409. ^ Jump up to : De Domenico, M. ; Solé - Ribalta, A. ; Cozzo, E. ; Kivelä, M. ; Moreno, Y. ; Porter, M. ; Gómez, S. ; Arenas, A. ( 2013 ). `` Mathematical Formulation of Multilayer Networks '' ( PDF ). Physical Review X. 3 ( 4 ) : 041022. arXiv : 1307.4977. Bibcode : 2013PhRvX... 3d1022D. doi : 10.1103 / PhysRevX. 3.041022. ^ Jump up to : Battiston, F. ; Nicosia, V. ; Latora, V. ( 2014 ). `` Structural measures for multiplex networks ''. Physical Review E. 89 ( 3 ) : 032804. arXiv : 1308.3182. Bibcode : 2014PhRvE... 89c2804B. doi : 10.1103 / PhysRevE. 89.032804. Jump up ^ Kivela, M. ; Arenas, A. ; Barthelemy, M. ; Gleeson, J.P. ; Moreno, Y. ; Porter, M.A. ( 2014 ). `` Multilayer networks ''. Journal of Complex Networks. 2 ( 3 ) : 203 -- 271. doi : 10.1093 / comnet / cnu016. Jump up ^ Boccaletti, S. ; Bianconi, G. ; Criado, R. ; del Genio, C.I. ; Gómez - Gardeñes, J. ; Romance, M. ; Sendiña - Nadal, I. ; Wang, Z. ; Zanin, M. ( 2014 ). `` The structure and dynamics of multilayer networks ''. Physics Reports. 544 ( 1 ) : 1 -- 122. arXiv : 1407.0742. Bibcode : 2014PhR... 544... 1B. doi : 10.1016 / j. physrep. 2014.07. 001. Jump up ^ Battiston, Federico ; Nicosia, Vincenzo ; Latora, Vito ( 2017 - 02 - 01 ). `` The new challenges of multiplex networks : Measures and models ''. The European Physical Journal Special Topics. 226 ( 3 ) : 401 -- 416. arXiv : 1606.09221. Bibcode : 2017EPJST. 226... 401B. doi : 10.1140 / epjst / e2016 - 60274 - 8. ISSN 1951 - 6355. Jump up ^ Mucha, P. ; et al. ( 2010 ). `` Community structure in time - dependent, multiscale, and multiplex networks '' ( PDF ). Science. 328 ( 5980 ) : 876 -- 878. arXiv : 0911.1824. Bibcode : 2010Sci... 328... 876M. doi : 10.1126 / science. 1184819. PMID 20466926. Jump up ^ De Domenico, M. ; Lancichinetti, A. ; Arenas, A. ; Rosvall, M. ( 2015 ). `` Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems ''. Physical Review X. 5 : 011027. arXiv : 1408.2925. Bibcode : 2015PhRvX... 5a1027D. doi : 10.1103 / PhysRevX. 5.011027. Jump up ^ De Domenico, M. ; Sole - Ribalta, A. ; Omodei, E. ; Gomez, S. ; Arenas, A. ( 2015 ). `` Ranking in interconnected multilayer networks reveals versatile nodes ''. Nature Communications. 6 : 6868. Bibcode : 2015NatCo... 6E6868D. doi : 10.1038 / ncomms7868. PMID 25904405. Jump up ^ Battiston, Federico ; Iacovacci, Jacopo ; Nicosia, Vincenzo ; Bianconi, Ginestra ; Latora, Vito ( 2016 - 01 - 27 ). `` Emergence of Multiplex Communities in Collaboration Networks ''. PLOS ONE. 11 ( 1 ) : e0147451. arXiv : 1506.01280. Bibcode : 2016PLoSO... 1147451B. doi : 10.1371 / journal. pone. 0147451. ISSN 1932 - 6203. PMC 4731389. PMID 26815700. Jump up ^ Grandjean, Martin ( 2016 ). Archives Distant Reading : Mapping the Activity of the League of Nations ' Intellectual Cooperation. In Digital Humanities 2016 : Jagiellonian University & Pedagogical University, Kraków, pp. 531 -- 534. Jump up ^ Cardillo, A. ; et al. ( 2013 ). `` Emergence of network features from multiplexity ''. Scientific Reports. 3 : 1344. arXiv : 1212.2153. Bibcode : 2013NatSR... 3E1344C. doi : 10.1038 / srep01344. PMC 3583169. PMID 23446838. Jump up ^ Boeing, G. ( 2017 ). `` OSMnx : New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks ''. Computers, Environment and Urban Systems. 65 : 126 -- 139. arXiv : 1611.01890. doi : 10.1016 / j. compenvurbsys. 2017.05. 004. SSRN 2865501. Retrieved 2017 - 08 - 26. Jump up ^ Gallotti, R. ; Barthelemy, M. ( 2014 ). `` Anatomy and efficiency of urban multimodal mobility ''. Scientific Reports. 4 : 6911. arXiv : 1411.1274. Bibcode : 2014NatSR... 4E6911G. doi : 10.1038 / srep06911. PMC 4220282. PMID 25371238. Jump up ^ De Domenico, M. ; Sole - Ribalta, A. ; Gomez, S. ; Arenas, A. ( 2014 ). `` Navigability of interconnected networks under random failures ''. PNAS. 111 ( 23 ) : 8351 -- 8356. Bibcode : 2014PNAS... 111.8351 D. doi : 10.1073 / pnas. 1318469111. PMC 4060702. PMID 24912174. Jump up ^ Pilosof, S. ; Porter, M.A. ; Pascual, M. ; Kefi, S. ( 2015 ). `` The Multilayer Nature of Ecological Networks ''. Nature Ecology & Evolution. 1 : 0101. arXiv : 1511.04453 ( q - bio. QM ). doi : 10.1038 / s41559 - 017 - 0101. Cite uses deprecated parameter class = ( help ) Jump up ^ Kouvaris, N.E. ; Hata, S. ; Diaz - Guilera, A. ( 2015 ). `` Pattern Formation in Multiplex Networks ''. Scientific Reports. 5 ( 1 ) : 10840. arXiv : 1412.2923. Bibcode : 2015NatSR... 510840K. doi : 10.1038 / srep10840. Jump up ^ Fiori, K.L. ; Smith, J ; Antonucci, T.C. ( 2007 ). `` Social network types among older adults : A multidimensional approach ''. The Journals of Gerontology Series B. 62 ( 6 ) : P322 -- 30. doi : 10.1093 / geronb / 62.6. p322. PMID 18079416. Jump up ^ De Domenico, M. ; Nicosia, V. ; Arenas, A. ; Latora, V. ( 2015 ). `` Structural reducibility of multilayer networks ''. Nature Communications. 6 : 6864. Bibcode : 2015NatCo... 6E6864D. doi : 10.1038 / ncomms7864. PMID 25904309. Jump up ^ Gao ; Buldyrev ; Stanley ; Havlin ( 22 December 2011 ). `` Networks formed from interdependent networks ''. Nature Physics. 8 : 40 -- 48. Bibcode : 2012NatPh... 8... 40G. doi : 10.1038 / nphys2180. Jump up ^ De Domenico, M. ; Granell, C. ; Porter, Mason A. ; Arenas, A. ( 7 April 2016 ). `` The physics of multilayer networks ''. Nature Physics. 12 : 901 -- 906. arXiv : 1604.02021 ( physics. soc - ph ). Bibcode : 2016NatPh... 12... 901D. doi : 10.1038 / nphys3865. Cite uses deprecated parameter class = ( help ) Jump up ^ Timme, N. ; Ito, S. ; Myroshnychenko, M. ; Yeh, F.C. ; Hiolski, E. ; Hottowy, P. ; Beggs, J.M. ( 2014 ). `` Multiplex Networks of Cortical and Hippocampal Neurons Revealed at Different Timescales ''. PLoS ONE. 9 ( 12 ) : e115764. Bibcode : 2014PLoSO... 9k5764T. doi : 10.1371 / journal. pone. 0115764. PMC 4275261. PMID 25536059. Jump up ^ De Domenico, M. ; Sasai, S. ; Arenas, A. ( 2016 ). `` Mapping multiplex hubs in human functional brain networks ''. Frontiers in Neuroscience. 10. doi : 10.3389 / fnins. 2016.00326. Jump up ^ Battiston, F. ; Nicosia, V. ; Chavez, M. ; Latora, V. ( 2016 ). `` Multilayer motif analysis of brain networks ''. Chaos : An Interdisciplinary Journal of Nonlinear Science. 27 : 047404. arXiv : 1606.09115 ( physics. soc - ph ). Bibcode : 2017Chaos... 27d7404B. doi : 10.1063 / 1.4979282. Cite uses deprecated parameter class = ( help ) Further Reading `` A Very Short Introduction to Networks, '' G. Caldarelli, M. Catanzaro ( Oxford University Press, Oxford 2007 ) `` Network Science Center, '' http://www.dodccrp.org/files/Network_Science_Center.asf `` Connected : The Power of Six Degrees, '' http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov Cohen, R. ; Erez, K. ; Havlin, S. ( 2000 ). `` Resilience of the Internet to random breakdown ''. Phys. Rev. Lett. 85 ( 21 ) : 4626 -- 4628. arXiv : cond - mat / 0007048. Bibcode : 2000PhRvL... 85.4626 C. doi : 10.1103 / physrevlett. 85.4626. PMID 11082612. Pu, Cun - Lai ; Wen - ; Pei, Jiang ; Michaelson, Andrew ( 2012 ). `` Robustness analysis of network controllability '' ( PDF ). Physica A. 391 ( 18 ) : 4420 -- 4425. Bibcode : 2012PhyA... 391.4420 P. doi : 10.1016 / j. physa. 2012.04. 019. `` Leader Profile : The Burgeoning Field of Network Science, The Military Engineer recently had the opportunity to speak with Frederick I. Moxley, Ph. D, '' http://themilitaryengineer.com/index.php/item/160-leader-profile-the-burgeoning-field-of-network-science S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks : From biological networks to the Internet and WWW, Oxford University Press, 2003, ISBN 0 - 19 - 851590 - 1 Linked : The New Science of Networks, A. - L. Barabási ( Perseus Publishing, Cambridge ) ' Scale - Free Networks, G. Caldarelli ( Oxford University Press, Oxford ) Network Science, Committee on Network Science for Future Army Applications, National Research Council. 2005. The National Academies Press ( 2005 ) ISBN 0 - 309 - 10026 - 7 Network Science Bulletin, USMA ( 2007 ) ISBN 978 - 1 - 934808 - 00 - 9 The Structure and Dynamics of Networks Mark Newman, Albert - László Barabási, & Duncan J. Watts ( The Princeton Press, 2006 ) ISBN 0 - 691 - 11357 - 2 Dynamical processes on complex networks, Alain Barrat, Marc Barthelemy, Alessandro Vespignani ( Cambridge University Press, 2008 ) ISBN 978 - 0 - 521 - 87950 - 7 Network Science : Theory and Applications, Ted G. Lewis ( Wiley, March 11, 2009 ) ISBN 0 - 470 - 33188 - 7 Nexus : Small Worlds and the Groundbreaking Theory of Networks, Mark Buchanan ( W.W. Norton & Company, June 2003 ) ISBN 0 - 393 - 32442 - 7 Six Degrees : The Science of a Connected Age, Duncan J. Watts ( W.W. Norton & Company, February 17, 2004 ) ISBN 0 - 393 - 32542 - 3 Kitsak, M. ; Gallos, L.K. ; Havlin, S. ; Liljeros, F. ; Muchnik, L. ; Stanley, H.E. ; Makse, H.A. ( 2010 ). `` Influential Spreaders in Networks ''. Nature Physics. 6 : 888 -- 893. arXiv : 1001.5285. Bibcode : 2010NatPh... 6... 888K. doi : 10.1038 / nphys1746. Social networks and social media Types City Personal Professional Sexual Value Networks Distributed social network ( list ) Enterprise social networking Mobile social network Personal knowledge networking Services List of social networking websites List of virtual communities with more than 1 million users List of virtual communities with more than 100 million active users Concepts and theories Assortative mixing Interpersonal bridge Organizational network analysis Small - world experiment Social aspects of television Social capital Social data revolution Social exchange theory Social identity theory Social network analysis Social web Structural endogamy Models and processes Aggregation Change detection Collaboration graph Collaborative consumption Giant Global Graph Lateral communication Social graph Social network analysis software Social networking potential Social television Structural cohesion Economics Collaborative finance Social commerce Phenomena Community recognition Complex contagion Consequential strangers Friend of a friend Friendship paradox Six degrees of separation Social invisibility Social network game Social occultation Tribe Related topics Researchers User profile Viral messages Virtual community Retrieved from `` https://en.wikipedia.org/w/index.php?title=Network_science&oldid=864056840 '' Categories : Cybernetics Networks Network theory Hidden categories : CS1 errors : deprecated parameters All articles with unsourced statements Articles with unsourced statements from December 2017 Talk Contents About Wikipedia Deutsch Español فارسی Français 한국어 Ido मराठी Nederlands Português Suomi 中文 4 more Edit links This page was last edited on 14 October 2018, at 20 : 33 ( UTC ). Text is available under the Creative Commons Attribution - ShareAlike License ; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia ® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. About Wikipedia

Question: what data structure is used to represent connections in a network
Answer: links (or edges)