View source for Network science

{{Short description|Academic field}}
{{other uses|Network (disambiguation)}}
{{Network Science}}
{{Complex systems}}
{{InfoMaps}}

'''Network science''' is an academic field which studies [[complex network]]s such as [[telecommunication network]]s, [[computer network]]s, [[biological network]]s, [[Cognitive network|cognitive]] and [[semantic network]]s, and [[social network]]s, 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 statistics|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."<ref name="NRC">{{cite book|title=Network Science |author=Committee on Network Science for Future Army Applications |publisher=National Research Council |isbn=978-0309653886 |year=2006 |url=http://www.nap.edu/catalog/11516.html|doi=10.17226/11516 |s2cid=196021177 }}</ref>

== 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.<ref>{{cite book|title=Theory of finite and infinite graphs |author=Dénes Kőnig|publisher=Birkhäuser Boston |isbn=978-1-4684-8971-2 |year=1990 |pages=45–421|url=https://link.springer.com/content/pdf/10.1007/978-1-4684-8971-2_2.pdf|type=PDF |doi=10.1007/978-1-4684-8971-2 }}</ref>

[[File:Moreno Sociogram 1st Grade.png|thumb|Moreno's sociogram of a 1st grade class.]]In the 1930s [[Jacob Moreno]], a psychologist in the [[Gestalt psychology|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".<ref>{{Cite book |last=Moreno |first=Jacob Levy |title=Who shall survive? Foundations of sociometry, group psychotherapy and socio-drama |publisher=Beacon House |date=2009-04-23 |location=Beacon, N. Y. |publication-date=1953 |language=English}}</ref> 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]].<ref>{{Cite news |date=1933-04-17 |title=EMOTIONS MAPPED BY NEW GEOGRAPHY: CHARTS SEEK TO PORTRAY THE PSYCHOLOGICAL CURRENTS OF HUMAN RELATIONSHIPS. FIRST STUDIES EXHIBITED COLORED LINES SHOW LIKES AND DISLIKES OF INDIVIDUALS AND OF GROUPS. MANY MISFITS REVEALED DR. J.L. MORENO CALCULATES THERE ARE 10 TO 15 MILLION ISOLATED INDIVIDUALS IN NATION |url=https://www.proquest.com/docview/100744844 |access-date=2024-09-26 |work=New York Times |pages=17|id={{ProQuest|100744844}} }}</ref> The sociogram has found many applications and has grown into the field of [[social network analysis]].

Probabilistic theory in network science developed as an offshoot of [[graph theory]] with [[Paul Erdős]] and [[Alfréd Rényi]]'s eight famous papers on [[random graphs]]. For [[social networks]] the [[exponential random graph model]] or p* is a notational framework used to represent the probability space of a tie occurring in a [[social network]]. An alternate approach to network probability structures is the [[network probability matrix]], which models the probability of edges occurring in a network, based on the historic presence or absence of the edge in a sample of networks.

Interest in networks exploded around 2000, following new discoveries that offered novel mathematical framework to describe different network topologies, leading to the term 'network science'.  [[Albert-László Barabási]] and [[Reka Albert]] discovered the [[scale-free network]]s<ref name=":2">{{Cite journal |last1=Barabási |first1=Albert-László |last2=Albert |first2=Réka |date=1999-10-15 |title=Emergence of Scaling in Random Networks |url=https://www.science.org/doi/10.1126/science.286.5439.509 |journal=Science |language=en |volume=286 |issue=5439 |pages=509–512 |doi=10.1126/science.286.5439.509 |issn=0036-8075|arxiv=cond-mat/9910332 }}</ref>  nature of many real networks, from the WWW to the cell. The scale-free property  captures the fact that in real network hubs coexist with many small degree vertices, and the authors offered a dynamical model to explain the origin of this scale-free state.<ref name=":2" /> [[Duncan J. Watts|Duncan Watts]] and [[Steven Strogatz]] reconciled empirical data on networks with mathematical representation, describing the [[small-world network]].<ref>{{Cite journal |last1=Watts |first1=Duncan J. |last2=Strogatz |first2=Steven H. |date=June 1998 |title=Collective dynamics of 'small-world' networks |url=https://www.nature.com/articles/30918 |journal=Nature |language=en |volume=393 |issue=6684 |pages=440–442 |doi=10.1038/30918 |issn=0028-0836}}</ref>

==Network Classification==
===Deterministic Network===
The definition of deterministic network is defined compared with the definition of probabilistic network. In un-weighted deterministic networks, edges either exist or not, usually we use 0 to represent non-existence of an edge while 1 to represent existence of an edge. In weighted deterministic networks, the edge value represents the weight of each edge, for example, the strength level.

===Probabilistic Network===
In probabilistic networks, values behind each edge represent the likelihood of the existence of each edge. For example, if one edge has a value equals to 0.9, we say the existence probability of this edge is 0.9.<ref>{{Cite journal|last1=Kollios|first1=George|date=2011-12-06|title=Clustering Large Probabilistic Graphs|journal=IEEE Transactions on Knowledge and Data Engineering|volume=25|issue=2|pages=325–336|doi=10.1109/TKDE.2011.243|pmid=13188797|s2cid=5650233 }}</ref>

== 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 model]]s 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]].
{{Further|Network homophily}}

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

=== Density ===
The density <math>D</math> of a network is defined as a normalized ratio between 0 and 1 of the number of edges <math>E</math> to the number of possible edges in a network with <math>N</math> nodes. Network density is a measure of the percentage of "optional" edges that exist in the network and can be computed as
<math>D =\frac{E-E_{\mathrm{min}}}{E_{\mathrm{max}}-E_{\mathrm{min}}}</math>
where <math>E_{\mathrm{min}}</math> and <math>E_{\mathrm{max}}</math> are the minimum and maximum number of edges in a connected network with <math>N</math> nodes, respectively. In the case of simple graphs, <math>E_{\mathrm{max}}</math> is given by the [[binomial coefficient]] <math>\tbinom N2</math> and <math>E_{\mathrm{min}} = N-1</math>, giving density
<math>D =\frac{E-(N-1)}{E_{\mathrm{max}} - (N-1)} = \frac{2(E-N+1)}{N(N-3)+2}</math>.
Another possible equation is <math>D = \frac{T-2N+2}{N(N-3)+2},</math> whereas the ties <math>T</math> are unidirectional (Wasserman & Faust 1994).<ref>{{Cite web|url=http://psycnet.apa.org/journals/prs/9/4/172/|title = APA PsycNet}}</ref> This gives a better overview over the network density, because unidirectional relationships can be measured.

=== Planar network density ===
The density <math>D</math> of a network, where there is no intersection between edges, is defined as a ratio of the number of edges <math>E</math> to the number of possible edges in a network with <math>N</math> nodes, given by a graph with no intersecting edges <math>(E_{\max}=3N-6)</math>, giving <math>D = \frac{E-N+1}{2N-5}.</math>

=== Average degree ===
The [[Degree (graph theory)|degree]] <math>k</math> of a node is the number of edges connected to it. Closely related to the density of a network is the average degree, <math>\langle k\rangle = \tfrac{2E}{N}</math> (or, in the case of directed graphs, <math>\langle k\rangle = \tfrac{E}{N}</math>, the former factor of 2 arising from each edge in an undirected graph contributing to the degree of two distinct vertices). In the [[Erdős–Rényi model|ER random graph model]] (<math>G(N,p)</math>) we can compute the expected value of  <math>\langle k \rangle </math> (equal to the expected value of <math>k</math> of an arbitrary vertex): a random vertex has <math>N-1</math> other vertices in the network available, and with probability <math>p</math>, connects to each. Thus, <math>\mathbb{E}[\langle k \rangle]=\mathbb{E}[k]= p(N-1)</math>.

[[Degree distribution|'''<big>Degree distribution</big>''']] 

The degree distribution <math>
P(k)
</math> is a fundamental  property of both real networks, such as the [[Internet]] and [[social networks]], and of theoretical models.  The degree distribution ''P''(''k'') of a network is defined to be the fraction of nodes in the network with degree ''k''. The simplest network model, for example, the (Erdős–Rényi model) [[random graph]], in which each of ''n'' nodes is independently connected (or not) with probability ''p'' (or 1 − ''p''), has a [[binomial distribution]] of degrees ''k'' (or [[Poisson distribution|Poisson]] in the limit of large ''n''). Most real networks, from the WWW to the [[Protein Interaction Networks|protein interaction networks]], however, have a degree distribution that are highly [[Skewness|right-skewed]], meaning that a large majority of nodes have low degree but a small number, known as "hubs", have high degree. For such [[Scale-free network|scale-free networks]] the  degree distribution  approximately follows a [[power law]]: <math>
P(k)\sim k^{-\gamma}
</math>, where ''γ'' is the degree exponent, and is a constant. Such [[scale-free networks]]  have unexpected structural and dynamical properties, rooted in the diverging second moment of the degree distribution. <ref name="BA">{{cite journal |last1=Barabási |first1=Albert-László |last2=Albert |first2=Réka |date=1999-10-15 |title=Emergence of Scaling in Random Networks |journal=Science |volume=286 |issue=5439 |pages=509–512 |arxiv=cond-mat/9910332 |bibcode=1999Sci...286..509B |doi=10.1126/science.286.5439.509 |issn=0036-8075 |pmid=10521342 |s2cid=524106}}</ref><ref name="AB">{{cite journal |last1=Albert |first1=Réka |last2=Barabási |first2=Albert-László |date=2000-12-11 |title=Topology of Evolving Networks: Local Events and Universality |url=https://repository.library.northeastern.edu/files/neu:331099/fulltext.pdf |url-status=live |journal=Physical Review Letters |volume=85 |issue=24 |pages=5234–5237 |arxiv=cond-mat/0005085 |bibcode=2000PhRvL..85.5234A |doi=10.1103/physrevlett.85.5234 |issn=0031-9007 |pmid=11102229 |s2cid=81784 |archive-url=https://web.archive.org/web/20180721070200/https://repository.library.northeastern.edu/files/neu:331099/fulltext.pdf |archive-date=2018-07-21 |access-date=2019-09-25 |hdl=2047/d20000695}}</ref><ref name="Doro">{{cite journal |last1=Dorogovtsev |first1=S. N. |last2=Mendes |first2=J. F. F. |last3=Samukhin |first3=A. N. |date=2001-05-21 |title=Size-dependent degree distribution of a scale-free growing network |journal=Physical Review E |volume=63 |issue=6 |page=062101 |arxiv=cond-mat/0011115 |bibcode=2001PhRvE..63f2101D |doi=10.1103/physreve.63.062101 |issn=1063-651X |pmid=11415146 |s2cid=119063903}}</ref><ref name="PSY">{{cite journal |last1=Pachon |first1=Angelica |last2=Sacerdote |first2=Laura |last3=Yang |first3=Shuyi |year=2018 |title=Scale-free behavior of networks with the copresence of preferential and uniform attachment rules |journal=Physica D: Nonlinear Phenomena |volume=371 |pages=1–12 |arxiv=1704.08597 |bibcode=2018PhyD..371....1P |doi=10.1016/j.physd.2018.01.005 |s2cid=119320331}}</ref>

=== 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 <math>d_{u,v}</math> between the two vertices <math>u,v</math> 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 <math>N</math> of a random network model defines whether that model exhibits the small-world effect; if it scales as <math>O(\ln N)</math>, the model generates small-world nets. For faster-than-logarithmic growth, the model does not produce small worlds. The special case of <math>O(\ln\ln N)</math> is known as ultra-small world effect.

=== Diameter of a network ===
As another means of measuring network graphs, we can define the diameter of a network as the longest of all the calculated shortest paths in a network. It is the shortest distance between the two most distant nodes in the network.  In other words, once the shortest path length from every node to all other nodes is calculated, the diameter is the longest of all the calculated path lengths. The diameter is representative of the linear size of a network. If node A-B-C-D are connected, going from A->D this would be the diameter of 3 (3-hops, 3-links).{{Citation needed|date=November 2019}}

=== 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 experiment|small world]].

The clustering coefficient of the <math>i</math>'th node is
:<math>C_i = {2e_i\over k_i{(k_i - 1)}}\,,</math>
where <math>k_i</math> is the number of neighbours of the <math>i</math>'th node, and <math>e_i</math> is the number of connections between these neighbours. The maximum possible number of connections between neighbors is, then,
:<math>{\binom {k}{2}} = {{k(k-1)}\over 2}\,.</math>

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

=== Connectedness ===
The way in which a network is connected plays a large part into how networks are analyzed and interpreted. Networks are classified in four different categories:
* ''Clique''/''Complete Graph'': a completely connected network, where all nodes are connected to every other node. These networks are symmetric in that all nodes have in-links and out-links from all others.
* ''Giant Component'': A single connected component which contains most of the nodes in the network.
* ''Weakly Connected Component'': A collection of nodes in which there exists a path from any node to any other, ignoring directionality of the edges.
* ''Strongly Connected Component'': A collection of nodes in which there exists a ''directed'' path from any node to any other.

===Node centrality===
{{Main|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 [[Centrality#Eigenvector centrality|eigenvalue centrality]], in contrast, considers a node highly important if many other highly important nodes link to it. Hundreds of such measures have been proposed in the literature.

Centrality indices are only accurate for identifying the most important nodes. The measures are seldom, if ever, meaningful for the remainder of network nodes.<ref name="Lawyer2015">
{{cite journal |last1= Lawyer |first1= Glenn  |title= Understanding the spreading power of all nodes in a network| journal=Scientific Reports 
|volume= 5  |pages= 8665  |date=March 2015
|number=O8665 
| doi=10.1038/srep08665
|pmid= 25727453  |pmc= 4345333  |bibcode= 2015NatSR...5E8665L  |arxiv=1405.6707}}
</ref><ref name="Sikic2013">
{{cite journal 
|last1 = Sikic
|first1=Mile
|last2=Lancic
|first2=Alen
|last3= Antulov-Fantulin
|first3=Nino
|last4=Stefancic
|first4=Hrvoje
|  title = Epidemic centrality – is there an underestimated epidemic impact of network peripheral nodes?
|  journal = European Physical Journal B
|date=October 2013
|  volume = 86
|  pages = 440
|  number = 10
| doi=10.1140/epjb/e2013-31025-5
|arxiv=1110.2558
|bibcode=2013EPJB...86..440S
|s2cid=12052238
}}
</ref> Also, their indications are only accurate within their assumed context for importance, and tend to "get it wrong" for other contexts.<ref name="Borgatti2005">
{{cite journal |last1= Borgatti |first1= Stephen P.|year= 2005 |title= Centrality and Network Flow |journal=Social Networks |volume= 27|pages= 55–71|doi=10.1016/j.socnet.2004.11.008 |citeseerx= 10.1.1.387.419}}
</ref> For example, imagine two separate communities whose only link is an edge between the most junior member of each community. Since any transfer from one community to the other must go over this link, the two junior members will have high betweenness centrality. But, since they are junior, (presumably) they have few connections to the "important" nodes in their community, meaning their eigenvalue centrality would be quite low.

===Node influence===
{{Main|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,<ref name="Travencolo2008">{{ cite journal| last1=Travençolo |first1=B. A. N. |last2=da F. Costa| first2 =L.| title=Accessibility in complex networks| journal=Physics Letters A| year=2008|volume=373|issue=1|pages=89–95 |doi=10.1016/j.physleta.2008.10.069 |bibcode=2008PhLA..373...89T }}</ref>
and the '''expected force''',  derived from the expected value of the [[force of infection]] generated by a node.<ref name="Lawyer2015"/>
Both of these measures can be meaningfully computed from the structure of the network alone.

=== Community structure ===
{{Main|Community structure}}
[[Image:Network Community Structure.svg|right|thumb|Fig. 1: A sketch of a small [[Complex networks|network]] displaying '''community structure''', with three groups of nodes with dense internal connections and sparser connections between groups.]]
Nodes in a network may be partitioned into groups representing communities. Depending on the context, communities may be distinct or overlapping. Typically, nodes in such communities will be strongly connected to other nodes in the same community, but weakly connected to nodes outside the community. In the absence of a [[ground truth]] describing the [[community structure]] of a specific network, several algorithms have been developed to infer possible community structures using either supervised of unsupervised clustering methods.

== Network models ==
Network models serve as a foundation to understanding interactions within empirical complex networks.  Various [[random graph]] generation models produce network structures that may be used in comparison to real-world complex networks.

=== Erdős–Rényi random graph model ===
[[File:ER model.svg|thumb|This [[Erdős–Rényi model]] is generated with {{math|<VAR>N</VAR> {{=}} 4}} nodes. For each edge in the complete graph formed by all {{mvar|N}} nodes, a random number is generated and compared to a given probability. If the random number is less than {{mvar|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 graph]]s 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 <math>G(n, p)

</math> two parameters must be specified: the total number of nodes {{mvar|n}} and the probability {{mvar|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 <math>v</math>, 
: <math>P(\deg(v) = k) = {n-1\choose k} p^k (1-p)^{n-1-k}.</math>

In this model the clustering coefficient is {{math|0}} [[Almost surely|a.s]]. The behavior of <math>G(n, p)

</math>  can be broken into three regions.

''Subcritical'' <math>n p < 1

</math>: All components are simple and very small, the largest component has size <math>|C_1| = O(\log n)

</math>;

''Critical'' <math>n p = 1

</math>: <math>|C_1| = O(n^\frac{2}{3})

</math>;

''Supercritical'' <math>n p >1

</math>:<math>|C_1| \approx yn
</math> where <math>y = y(n p)

</math> is the positive solution to the equation <math>e^{-p n y }=1-y

</math>.

The largest connected component has high complexity. All other components are simple and small <math>|C_2| = O(\log n)

</math>.

=== Configuration model ===
The configuration model takes a degree sequence<ref>{{Cite journal|last1=Bender|first1=Edward A|last2=Canfield|first2=E.Rodney|date=May 1978|title=The asymptotic number of labeled graphs with given degree sequences|journal=Journal of Combinatorial Theory, Series A|volume=24|issue=3|pages=296–307|doi=10.1016/0097-3165(78)90059-6|issn=0097-3165|doi-access=free}}</ref><ref name=":0">{{Cite journal|last1=Molloy|first1=Michael|last2=Reed|first2=Bruce|date=March 1995|title=A critical point for random graphs with a given degree sequence|journal=Random Structures & Algorithms|language=en|volume=6|issue=2–3|pages=161–180|doi=10.1002/rsa.3240060204|issn=1042-9832|citeseerx=10.1.1.24.6195}}</ref> or degree distribution<ref>{{Cite web |title=Configuration Models and Complex Networks |url=https://danlarremore.com/configurationmodels/ |access-date=2025-01-15 |website=danlarremore.com}}</ref><ref name=":1">{{Cite journal|last1=Newman|first1=M. E. J.|last2=Strogatz|first2=S. H.|last3=Watts|first3=D. J.|date=2001-07-24|title=Random graphs with arbitrary degree distributions and their applications|journal=Physical Review E|volume=64|issue=2|pages=026118|doi=10.1103/PhysRevE.64.026118|pmid=11497662|arxiv=cond-mat/0007235|bibcode=2001PhRvE..64b6118N|s2cid=360112}}</ref> (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 <math>k</math> of a randomly chosen vertex is an [[Independent and identically distributed random variables|independent and identically distributed]] random variable with integer values. When  <math display="inline">\mathbb E [k^2] - 2 \mathbb E [k]>0</math>, the configuration graph contains the [[Giant component|giant connected component]], which has infinite size.<ref name=":0" /> The rest of the components have finite sizes, which can be quantified with the notion of the size distribution. The probability <math>w(n)</math> that a randomly sampled node is connected to a component of size <math>n</math> is given by [[convolution power]]s of the degree distribution:<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-05-02|title=General expression for the component size distribution in infinite configuration networks|journal=Physical Review E|volume=95|issue=5|pages=052303|doi=10.1103/PhysRevE.95.052303|pmid=28618550|arxiv=1703.05413|bibcode=2017PhRvE..95e2303K|s2cid=8421307}}</ref><math display="block">w(n)=\begin{cases}
\frac{\mathbb E [k]}{n-1} u_1^{*n}(n-2),& n>1, \\
u(0) & n=1,
\end{cases}</math>where <math>u(k)</math> denotes the degree distribution and <math>u_1(k)=\frac{(k+1)u(k+1)}{\mathbb E[k]}</math>. The giant component can be destroyed by randomly removing the critical fraction <math>p_c</math> of all edges. This process is called [[Percolation theory|percolation on random networks]]. When the second moment of the degree distribution is finite, <math display="inline">\mathbb E [k^2]<\infty</math>, this critical edge fraction is given by<ref>{{Cite journal|last=Kryven|first=Ivan|date=2018-01-01|title=Analytic results on the polymerisation random graph model|journal=Journal of Mathematical Chemistry|language=en|volume=56|issue=1|pages=140–157|doi=10.1007/s10910-017-0785-1|issn=0259-9791|doi-access=free|arxiv=1603.07154}}</ref> <math>p_c=1-\frac{\mathbb E[k]}{ \mathbb E [k^2] - \mathbb E[k]}</math>, and the [[Average path length|average vertex-vertex distance]] <math>l</math> in the giant component scales logarithmically with the total size of the network, <math>l = O(\log N) </math>.<ref name=":1" />

In the directed configuration model, the degree of a node is given by two numbers, in-degree <math>k_\text{in}</math> and out-degree <math>k_\text{out}</math>, and consequently, the degree distribution is two-variate. The expected number of in-edges and out-edges coincides, so that <math display="inline">\mathbb E [k_\text{in}]=\mathbb E [k_\text{out}]</math>. The directed configuration model contains the [[giant component]] iff<ref>{{Cite journal|last=Kryven|first=Ivan|date=2016-07-27|title=Emergence of the giant weak component in directed random graphs with arbitrary degree distributions|journal=Physical Review E|volume=94|issue=1|pages=012315|doi=10.1103/PhysRevE.94.012315|pmid=27575156|arxiv=1607.03793|bibcode=2016PhRvE..94a2315K|s2cid=206251373}}</ref><math display="block">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.</math>Note that <math display="inline">\mathbb E [k_\text{in}]</math> and <math display="inline">\mathbb E [k_\text{out}]</math> are equal and therefore interchangeable in the latter inequality. The probability that a randomly chosen vertex belongs to a component of size <math>n</math> is given by:<ref>{{Cite journal|last=Kryven|first=Ivan|date=2017-11-02|title=Finite connected components in infinite directed and multiplex networks with arbitrary degree distributions|journal=Physical Review E|volume=96|issue=5|pages=052304|doi=10.1103/PhysRevE.96.052304|pmid=29347790|arxiv=1709.04283|bibcode=2017PhRvE..96e2304K|s2cid=20741516}}</ref><math display="block">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}),</math>for in-components, and

: <math>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}\geq0}u(k_\text{in},k_\text{out}+1),

</math>

for out-components.

=== Watts–Strogatz small world model ===
[[File:Watts-Strogatz-rewire.png|thumb|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 change its connected vertices according to a given rewiring probability. <math>\langle k\rangle = 4</math> 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 <math>\langle k\rangle</math> closest neighbors. Another parameter is specified as the rewiring probability.  Each edge has a probability <math>p</math> that it will be rewired to the graph as a random edge.  The expected number of rewired links in the model is <math>pE = pN\langle k\rangle/2</math>.

As the Watts–Strogatz model begins as a non-random lattice structure, it has a very high clustering coefficient along with a 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 slight decreases in the 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''<sub>0</sub> nodes.  ''m''<sub>0</sub>&nbsp;≥&nbsp;2 and the degree of each node in the initial network should be at least&nbsp;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 <math>m</math> existing nodes with a probability that is proportional to the number of links that the existing nodes already have. Formally, the probability ''p''<sub>''i''</sub> that the new node is connected to node ''i'' is<ref name=RMP>{{Cite journal
 |url         = http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/StatisticalMechanics_Rev%20of%20Modern%20Physics%2074,%2047%20(2002).pdf
 |author1     = R. Albert
 |author2     = A.-L. Barabási
 |title       = Statistical mechanics of complex networks
 |journal     = [[Reviews of Modern Physics]]
 |volume      = 74
 |issue     = 1
 |pages       = 47–97
 |year        = 2002
 |doi         = 10.1103/RevModPhys.74.47
 |bibcode     = 2002RvMP...74...47A
 |arxiv       = cond-mat/0106096
 |url-status     = dead
 |archive-url  = https://web.archive.org/web/20150824235818/http://www3.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/StatisticalMechanics_Rev%20of%20Modern%20Physics%2074,%2047%20(2002).pdf
 |archive-date = 2015-08-24
|citeseerx     = 10.1.1.242.4753
 |s2cid = 60545
 }}</ref>

: <math>p_i = \frac{k_i}{\sum_j k_j},</math>

where ''k''<sub>''i''</sub> 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.

[[File:Barabasi-albert model degree distribution.svg|thumb|The degree distribution of the BA Model, which follows a power law. In loglog scale the power law function is a straight line.<ref name=Barabasi1999>{{Cite journal
 |url         = http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/EmergenceRandom_Science%20286,%20509-512%20(1999).pdf
 |author      = [[Albert-László Barabási]] & [[Réka Albert]]
 |title       = Emergence of scaling in random networks
 |journal     = [[Science (journal)|Science]]
 |volume      = 286
 |pages       = 509–512
 |date        = October 1999
 |doi         = 10.1126/science.286.5439.509
 |issue       = 5439
 |pmid        = 10521342
 |arxiv       = cond-mat/9910332
 |bibcode     = 1999Sci...286..509B
 |s2cid = 524106
 |url-status     = dead
 |archive-url  = https://web.archive.org/web/20120417112354/http://www.nd.edu/~networks/Publication%20Categories/03%20Journal%20Articles/Physics/EmergenceRandom_Science%20286,%20509-512%20(1999).pdf
 |archive-date = 2012-04-17
}}</ref>]]
The degree distribution resulting from the BA model is scale free, in particular, for large degree it is a power law of the form:
: <math>P(k)\sim k^{-3} \, </math>

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.

The [[Barabási–Albert model]]<ref name="Barabasi1999" /> was developed for undirected networks, aiming to explain the universality of the scale-free property, and applied to a wide range of different networks and applications. The directed version of this model is the [[Price's model|Price model]]<ref>{{Cite journal |last=Price |first=Derek J. de Solla |date=1965-07-30 |title=Networks of Scientific Papers: The pattern of bibliographic references indicates the nature of the scientific research front. |url=https://www.science.org/doi/10.1126/science.149.3683.510 |journal=Science |language=en |volume=149 |issue=3683 |pages=510–515 |doi=10.1126/science.149.3683.510 |pmid=14325149 |bibcode=1965Sci...149..510D |issn=0036-8075}}</ref><ref>{{Cite journal |last=Price |first=Derek De Solla |date=1976 |title=A general theory of bibliometric and other cumulative advantage processes |url=https://onlinelibrary.wiley.com/doi/10.1002/asi.4630270505 |journal=Journal of the American Society for Information Science |language=en |volume=27 |issue=5 |pages=292–306 |doi=10.1002/asi.4630270505|s2cid=8536863 }}</ref> which was developed to just citation networks.

====Non-linear preferential attachment====
{{Main|Non-linear preferential attachment}}

In non-linear preferential attachment (NLPA), existing nodes in the network gain new edges proportionally to the node degree raised to a constant positive power, <math> \alpha </math>.<ref>{{cite journal |last1=Krapivsky |first1=P. L. |last2=Redner |first2=S. |last3=Leyvraz |first3=F. |title=Connectivity of Growing Random Networks |journal=Physical Review Letters |date=20 November 2000 |volume=85 |issue=21 |pages=4629–4632 |doi=10.1103/PhysRevLett.85.4629|pmid=11082613 |arxiv=cond-mat/0005139 |bibcode=2000PhRvL..85.4629K |s2cid=16251662 }}</ref> Formally, this means that the probability that node <math> i </math> gains a new edge is given by

: <math>p_i = \frac{k_i^{\alpha}}{\sum_j k_j^{\alpha}}.</math>

If <math>\alpha=1</math>, NLPA reduces to the BA model and is referred to as "linear". If <math>0<\alpha<1</math>, NLPA is referred to as "sub-linear" and the degree distribution of the network tends to a [[Stretched exponential function|stretched exponential distribution]]. If <math>\alpha>1</math>, NLPA is referred to as "super-linear" and a small number of nodes connect to almost all other nodes in the network. For both <math>\alpha<1</math> and <math>\alpha>1</math>, the scale-free property of the network is broken in the limit of infinite system size. However, if <math>\alpha</math> is only slightly larger than <math>1</math>, NLPA may result in [[degree distribution]]s which appear to be transiently scale free.<ref>{{cite journal |last1=Krapivsky |first1=Paul |last2=Krioukov |first2=Dmitri |title=Scale-free networks as preasymptotic regimes of superlinear preferential attachment |journal=Physical Review E |date=21 August 2008 |volume=78 |issue=2 |pages=026114 |doi=10.1103/PhysRevE.78.026114|pmid=18850904 |arxiv=0804.1366 |bibcode=2008PhRvE..78b6114K |s2cid=14292535 }}</ref>

====Mediation-driven attachment (MDA) model====

In the [[mediation-driven attachment model|mediation-driven attachment (MDA) model]] in which a new node coming with <math>m</math> edges picks an existing connected node at random and then connects itself not with that one but with <math>m</math> of its neighbors chosen also at random. The probability <math>\Pi(i)</math> that the node <math>i</math> of the existing node picked is

: <math> \Pi(i) = \frac{k_i} N \frac{ \sum_{j=1}^{k_i} \frac 1 {k_j} }{k_i}.</math>

The factor <math>\frac{\sum_{j=1}^{k_i}{\frac{1}{k_j}}}{k_i}</math> is the inverse of the harmonic mean
(IHM) of degrees of the <math>k_i</math> neighbors of a node <math>i</math>. Extensive numerical investigation suggest that for an approximately <math>m> 14</math> the mean IHM value in the large <math>N</math> limit becomes a constant which means <math>\Pi(i) \propto k_i</math>. 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.<ref>{{cite journal | last1 = Hassan | first1 = M. K. | last2 = Islam | first2 = Liana | last3 = Arefinul Haque | first3 = Syed | date = March 2017  | title = Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks | doi = 10.1016/j.physa.2016.11.001 | journal = Physica A | volume = 469 | pages = 23–30 | arxiv = 1411.3444 | bibcode = 2017PhyA..469...23H | s2cid = 51976352 }}</ref>

However,  for <math>m=1</math> it describes the winner takes it all mechanism as we find that almost <math>99\%</math> of the total nodes have degree one and one is super-rich in degree. As <math>m</math> value increases the disparity between the super rich and poor decreases and as <math>m>14</math> 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.<ref>Caldarelli G.,   A. Capocci, P. De Los Rios, M.A. Muñoz, Physical Review Letters 89, 258702 (2002)</ref> Here a link is created between two vertices <math>i,j</math> with a probability given by a linking function <math>f(\eta_i,\eta_j)</math> of the [[Fitness model (network theory)|fitnesses]] of the vertices involved.
The degree of a vertex i is given by <ref>Servedio V.D.P., G. Caldarelli, P. Buttà, Physical Review E 70, 056126 (2004)</ref>

:<math>k(\eta_i)=N\int_0^\infty f(\eta_i,\eta_j) \rho(\eta_j) \, d\eta_j </math>

If <math>k(\eta_i)</math> is an invertible and increasing function of <math>\eta_i</math>, then
the probability distribution <math>P(k)</math> is given by

:<math>P(k)=\rho(\eta(k)) \cdot \eta'(k)</math>

As a result, if the fitnesses <math>\eta</math> are distributed as a power law, then also the node degree does.

Less intuitively with a fast decaying probability distribution as
<math>\rho(\eta)=e^{-\eta}</math> together with a linking function of the kind

:<math> f(\eta_i,\eta_j)=\Theta(\eta_i+\eta_j-Z)</math>

with <math>Z</math> a constant and <math>\Theta</math> 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 <math>i,j</math> and a linking function of the kind
<ref>Garlaschelli D., M I Loffredo Physical Review Letters 93, 188701 (2004)</ref><ref>Cimini G., T. Squartini, D. Garlaschelli and A. Gabrielli, Scientific Reports 5, 15758 (2015)</ref>

:<math> \frac{\delta \eta_i\eta_j}{1+ \delta \eta_i\eta_j}.</math>

=== Exponential random graph models ===

[[Exponential family random graph models|'''Exponential Random Graph Models''' (ERGMs)]] are a family of [[statistical model]]s for analyzing data from [[social network|social]] and other networks.<ref name="lusher2012exponential">{{Cite book|title= Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications (Structural Analysis in the Social Sciences)|last1=Lusher|first1=Dean|last2=Koskinen|first2=Johan|last3=Robins|first3=Garry|date=2012|isbn= 9780521141383|language=English|oclc=1120539699|doi=10.1017/CBO9780511894701}}</ref> The [[Exponential family]] is a broad family of models for covering many types of data, not just networks. An ERGM is a model from this family which describes networks.

We adopt the notation to represent a [[random graph]] <math>Y \in \mathcal{Y}</math> via a set of <math>n</math> nodes and a collection of [[Social network|tie]] variables <math>\{ Y_{ij}: i=1,\dots,n; j=1,\dots,n\}</math>, indexed by pairs of nodes <math>ij</math>, where <math>Y_{ij}=1</math> if the nodes <math>(i,j)</math> are connected by an edge and <math>Y_{ij}=0</math> otherwise.

The basic assumption of ERGMs is that the structure in an observed graph <math>y</math> can be explained by a given vector of [[sufficient statistic]]s <math>s(y)</math> which are a function of the observed network and, in some cases, nodal attributes. The probability of a graph <math>y\in\mathcal{Y}</math> in an ERGM is defined by:

<math>
P(Y = y | \theta) = \frac{\exp(\theta^{T} s(y))}{c(\theta)}
</math>

where <math>\theta</math> is a vector of model parameters associated with <math>s(y)</math> and <math>c(\theta) = \sum_{y'\in\mathcal{Y}}\exp(\theta^{T} s(y'))</math> is a normalising constant.

==Network analysis==

===Social network analysis===
'''[[Social network]] analysis''' examines the structure of relationships between social entities.<ref name="Wasserman_Faust">[[Wasserman, Stanley]] and Katherine Faust. 1994. ''Social Network Analysis: Methods and Applications.'' Cambridge: Cambridge University Press.
</ref> These entities are often persons, but may also be [[Group (sociology)|groups]], [[organizations]], [[nation states]], [[web sites]], [[scientometrics|scholarly publications]].

Since the 1970s, the empirical study of networks has played a central role in social science, and many of the [[Mathematics|mathematical]] and [[Statistics|statistical]] tools used for studying networks have been first developed in [[sociology]].<ref name="Newman">Newman, M.E.J. ''Networks: An Introduction.'' Oxford University Press. 2010, {{ISBN|978-0199206650}}</ref>  Amongst many other applications, social network analysis has been used to understand the diffusion of [[Diffusion of innovations|innovation]], news and [[rumor spread in social network|rumors]].  Similarly, it has been used to examine the spread of both [[epidemiology|diseases]] and [[Medical sociology|health-related behaviors]].  It has also been applied to the [[Economic sociology|study of markets]], where it has been used to examine the role of trust in [[Social exchange|exchange relationships]] and of social mechanisms in setting prices.  Similarly, it has been used to study recruitment into [[political movement]]s 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 resistance|leaderless]] nature.<ref name=GT-33/><ref>{{Cite web |url=http://firstmonday.org/htbin/cgiwrap/bin/ojs/index.php/fm/article/view/941/863 |title=Network analysis of terrorist networks |access-date=2011-12-12 |archive-url=https://web.archive.org/web/20121123010939/http://firstmonday.org/htbin/cgiwrap/bin/ojs/index.php/fm/article/view/941/863 |archive-date=2012-11-23 |url-status=dead }}</ref> In [[Social network analysis (criminology)|criminology]], it is being used to identify influential actors in criminal gangs, offender movements, co-offending, predict criminal activities and make policies.<ref>{{Cite book|last1=PhD|first1=Martin Bouchard|last2=PhD|first2=Aili Malm|title=Oxford Handbooks Online: Criminology and Criminal Justice |date=2016-11-02|chapter=Social Network Analysis and Its Contribution to Research on Crime and Criminal Justice|chapter-url=https://www.oxfordhandbooks.com/view/10.1093/oxfordhb/9780199935383.001.0001/oxfordhb-9780199935383-e-21|language=en|doi=10.1093/oxfordhb/9780199935383.013.21|isbn=978-0-19-993538-3}}</ref>

===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.<ref name="dynamic3">Gross, T. and Sayama, H. (Eds.). 2009. ''Adaptive Networks: Theory, Models and Applications.'' Springer.</ref><ref name="dynamic4">Holme, P. and Saramäki, J. 2013. ''Temporal Networks.'' Springer.</ref><ref>Xanthos, Aris, Pante, Isaac, Rochat, Yannick, Grandjean, Martin (2016). [http://dh2016.adho.org/abstracts/407 Visualising the Dynamics of Character Networks]. In Digital Humanities 2016: Jagiellonian University & Pedagogical University, Kraków, pp. 417–419.</ref>  Dynamic Network Analysis focuses on meta-networks composed of multiple types of nodes (entities) and [[Multidimensional network|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 motif]]s 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 network]]s has led to the development of [[network medicine]], which looks at the effect of diseases in the [[interactome]].<ref>{{cite journal | last1 = Barabási | first1 = A. L. | last2 = Gulbahce | first2 = N. | last3 = Loscalzo | first3 = J. | year = 2011 | title = Network medicine: a network-based approach to human disease | journal = Nature Reviews Genetics | volume = 12 | issue = 1| pages = 56–68 | doi=10.1038/nrg2918 | pmid=21164525 | pmc=3140052}}</ref>

===Semantic network analysis===
[[Semantic network]] analysis is a sub-field of network analysis that focuses on the relationships between words and [[concept]]s in a network. Words are represented as nodes and their proximity or co-occurrences in the text are represented as edges. Semantic networks are therefore graphical representations of knowledge and are commonly used in [[neurolinguistics]] and [[natural language processing]] applications. Semantic network analysis is also used as a method to analyze large texts and identify the main themes and topics (e.g., of [[social media]] posts), to reveal biases (e.g., in news coverage), or even to map an entire research field.<ref>{{cite book |last1=Segev |first1=Elad |title=Semantic Network Analysis in Social Sciences |date=2022 |publisher=Routledge |location=London |isbn=9780367636524 |url=https://www.routledge.com/Semantic-Network-Analysis-in-Social-Sciences/Segev/p/book/9780367636524 |access-date=5 December 2021 |archive-date=5 December 2021 |archive-url=https://web.archive.org/web/20211205140726/https://www.routledge.com/Semantic-Network-Analysis-in-Social-Sciences/Segev/p/book/9780367636524 |url-status=live }}</ref>

===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, financial transactions they have partaken in during a given timeframe, and the familial relationships between these subjects as a part of the police investigation. Link analysis here provides the crucial relationships and associations between 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 [[bank]]s and [[insurance]] agencies in [[fraud]] detection, by telecommunication operators in telecommunication network analysis, by medical sector in [[epidemiology]] and [[pharmacology]], in law enforcement [[Criminal procedure|investigation]]s, by [[search engine]]s for [[relevance]] rating (and conversely by the [[search engine spammer|spammers]] for [[spamdexing]] and by business owners for [[search engine optimization]]), and everywhere else where relationships between many objects have to be analyzed.

===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====
: <math>S = \beta\left(\frac 1 N \right)</math>

The formula above describes the "force" of infection for each susceptible unit in an infectious population, where {{math|β}} is equivalent to the transmission rate of said disease.

To track the change of those susceptible in an infectious population:

: <math>\Delta S = \beta \times S {1\over N} \, \Delta t</math>

====Infected to recovered====

: <math>\Delta I = \mu I \, \Delta t</math>

Over time, the number of those infected fluctuates by: the specified rate of recovery, represented by <math>\mu</math> but deducted to one over the average infectious period <math>{1\over \tau}</math>, the numbered of infectious individuals, <math>I</math>, and the change in time, <math>\Delta t</math>.

====Infectious period====
Whether a population will be overcome by a pandemic, with regards to the SIR model, is dependent on the value of <math>R_0</math> or the "average people infected by an infected individual."

: <math>R_0 = \beta\tau = {\beta\over\mu}</math>

===Web link analysis===
Several [[Web search]] [[ranking]] algorithms use link-based centrality metrics, including (in order of appearance) [[Massimo Marchiori|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, <math>x_i</math>, has a PageRank as defined by the sum of pages <math>j</math> that link to <math>i</math> times one over the outlinks or "out-degree" of <math>j</math> times the "importance" or PageRank of <math>j</math>.

: <math>x_i = \sum_{j\rightarrow i}{1\over N_j}x_j^{(k)}</math>

=====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 <math>\alpha</math>, or the probability that a random jump will occur. Contrasting is the "damping factor", or <math>1 - \alpha</math>.

: <math>R{(p)} = {\alpha\over N} + (1 - \alpha) \sum_{j\rightarrow i} {1\over N_j} x_j^{(k)}</math>

Another way of looking at it:

: <math>R(A) = \sum {R_B\over B_\text{(outlinks)}} + \cdots + {R_n \over n_\text{(outlinks)}}</math>

===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.<ref name="Wasserman_Faust"/>

*'''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.<ref>Newman, M., Barabási, A.-L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.</ref>  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. The pitcher represents the source, and the water represents the spread content. 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 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 source is infinite. Also, any funnels 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: <math>S(t)</math>, infected, <math>I(t)</math>, and recovered, <math>R(t)</math>. The compartments used for this model consist of three classes:

* <math>S(t)</math> is used to represent the number of individuals not yet infected with the disease at time t, or those susceptible to the disease
* <math>I(t)</math> 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
* <math>R(t)</math> 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:

: <math>\mathcal{S} \rightarrow \mathcal{I} \rightarrow \mathcal{R} </math>

Using a fixed population, <math>N = S(t) + I(t) + R(t)</math>, Kermack and McKendrick derived the following equations:

: <math>
\begin{align}
\frac{dS}{dt} & = - \beta S I \\[8pt]
\frac{dI}{dt} & = \beta S I - \gamma I \\[8pt]
\frac{dR}{dt} & = \gamma I
\end{align}
</math>

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 <math>\beta</math>, 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 <math>\beta N</math> others per unit time and the fraction of contacts by an infected with a susceptible is <math>S/N</math>.  The number of new infections in unit time per infective then is <math>\beta N (S/N)</math>, giving the rate of new infections (or those leaving the susceptible category) as <math>\beta N (S/N)I = \beta SI</math> (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, infectives are leaving this class per unit time to enter the recovered/removed class at a rate <math>\gamma</math> per unit time (where <math>\gamma</math> represents the mean recovery rate, or <math>1/\gamma</math>  the mean infective period). These processes which occur simultaneously are referred to as the [[Law of mass action|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 <math>t = 2</math>, this configuration is necessary only to simplify further calculations, so at time <math>t = n</math> the network have <math>n</math> nodes and <math>n</math> links.

The master equation for this network is:

: <math>p(k,s,t+1) = \frac 1 t p(k-1,s,t) + \left(1 - \frac 1 t \right)p(k,s,t),</math>

where <math>p(k,s,t)</math> is the probability to have the node <math>s</math> with degree <math>k</math> at time <math>t+1</math>, and <math>s</math> is the time step when this node was added to the network. Note that there are only two ways for an old node <math>s</math> to have <math>k</math> links at time <math>t+1</math>:

* The node <math>s</math> have degree <math>k-1</math> at time <math>t</math> and will be linked by the new node with probability <math>1/t</math>
* Already has degree <math>k</math> at time <math>t</math> and will not be linked by the new node.

After simplifying this model, the degree distribution is <math>P(k) = 2^{-k}. </math><ref name="dorogovtsev-mendes">{{cite book|last1=Dorogovtsev|first1=S N|last2=Mendes|first2=J F F|title=Evolution of Networks: From Biological Nets to the Internet and WWW|date=2003|publisher=Oxford University Press, Inc.|location=New York, NY, USA|isbn=978-0198515906}}</ref>

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:

: <math>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),</math>

where <math>r_t</math> represents the decision to infect (<math>r_t = 1</math>) or not (<math>r_t = 0</math>). Solving this master equation, the following solution is obtained: <math>\tilde{P}_r(k) = \left(\frac r 2 \right)^k. </math><ref name="cotacallapa-hase">{{cite journal|last1=Cotacallapa|first1=M|last2=Hase|first2=M O|title=Epidemics in networks: a master equation approach|journal=Journal of Physics A|date=2016|volume=49|issue=6|page=065001|doi=10.1088/1751-8113/49/6/065001|bibcode=2016JPhA...49f5001C|arxiv=1604.01049|s2cid=119206200}}</ref>

==Multilayer networks==
{{main|Multidimensional network}}

'''Multilayer networks''' are networks with multiple kinds of relations.<ref>{{cite book |last1=De Domenico |first1=Manlio |title= Multilayer Networks: Analysis and Visualization |date=March 31, 2022 |publisher=Springer |edition=1st}}</ref> Attempts to model real-world systems as multidimensional networks have been used in various fields such as social network analysis,<ref>{{cite book |last1=Rossi |first1=Luca |last2=Dickison |first2=Mark E. |last3=Magnani |first3=Matteo |title=Multilayer Social Networks |date=July 18, 2016 |publisher=Cambridge University Press |edition=1st}}</ref> 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 [[flow network|network flow]], [[shortest path problem]], [[transport problem]], [[transshipment problem]], [[Optimal facility location|location problem]], [[Matching (graph theory)|matching problem]], [[assignment problem]], [[packing problem]], [[routing|routing problem]], [[critical path analysis]] and [[PERT]] (Program Evaluation & Review Technique).
{{Further|Optimization mechanism}}

==Interdependent networks==

[[Interdependent networks]] are networks where the functioning of nodes in one network depends on the functioning of nodes in another network. In nature, networks rarely appear in isolation, rather, usually networks are typically elements in larger systems, and interact with elements in that complex system. Such complex dependencies can have non-trivial effects on one another. A well studied example is the interdependency of infrastructure networks,<ref>{{cite journal |title=Identifying, understanding, and analyzing critical infrastructure interdependencies |journal=IEEE Control Systems Magazine |pages=11–25 |doi=10.1109/37.969131 |date=December 2001|volume=21 |issue=6 }}</ref> the power stations which form the nodes of the power grid require fuel delivered via a network of roads or pipes and are also controlled via the nodes of communications network. Though the transportation network does not depend on the power network to function, the communications network does. In such infrastructure networks, the disfunction of a critical number of nodes in either the power network or the communication network can lead to cascading failures across the system with potentially catastrophic result to the whole system functioning.<ref>{{cite journal |last1=Buldyrev |first1=Sergey V. |title=Catastrophic cascade of failures in interdependent networks |journal=Nature |display-authors=etal|pages=1025–1028 |doi=10.1038/nature08932 |date=April 2010|volume=464 |issue=7291 |pmid=20393559 |arxiv=0907.1182 |bibcode=2010Natur.464.1025B |s2cid=1836955 }}</ref> If the two networks were treated in isolation, this important feedback effect would not be seen and predictions of network robustness would be greatly overestimated.

==See also==
{{div col|colwidth=20em}}
* [[Cascading failure]]
* [[Climate as complex networks]]
* [[Collaborative innovation network]]
* [[Communicative ecology]]
* [[Complex network]]
* [[Core-periphery structure]]s in networks
* [[Dual-phase evolution]]
* [[Erdős–Rényi model]]
* [[Glossary of graph theory]]
* [[Gradient network]]
* [[Higher category theory]]
* [[Immune network theory]]
* [[Irregular warfare]]
* [[Network management|Network analyzer]]
* [[Network dynamics]]
* [[Network formation]]
* [[Network theory in risk assessment]]
* [[Network topology]]
* [[Networks in labor economics]]
* [[Non-linear preferential attachment]]
* [[Percolation]]
* [[Percolation theory]]
* [[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]]
{{div col end}}

==References==
{{reflist|refs=
<ref name=GT-33>{{cite web|title=Toward a Complex Adaptive Intelligence Community The Wiki and the Blog|url=https://www.cia.gov/library/center-for-the-study-of-intelligence/csi-publications/csi-studies/studies/vol49no3/html_files/Wik_and_%20Blog_7.htm|archive-url=https://web.archive.org/web/20070613110629/https://www.cia.gov/library/center-for-the-study-of-intelligence/csi-publications/csi-studies/studies/vol49no3/html_files/Wik_and_%20Blog_7.htm|url-status=dead|archive-date=June 13, 2007|work=D. Calvin Andrus|publisher=cia.gov|access-date=25 August 2012}}</ref>
}}

==Further reading==
* ''[https://www.cambridge.org/us/academic/subjects/physics/statistical-physics/first-course-network-science A First Course in Network Science]'', [[Filippo Menczer|F. Menczer]], S. Fortunato, C.A. Davis. (Cambridge University Press, 2020). {{ISBN|9781108471138}}. [https://github.com/CambridgeUniversityPress/FirstCourseNetworkScience GitHub site] with tutorials, datasets, and other resources
* "Connected: The Power of Six Degrees," https://web.archive.org/web/20111006191031/http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
* {{cite journal | last1 = Cohen | first1 = R. | last2 = Erez | first2 = K. | year = 2000 | title = Resilience of the Internet to random breakdown | url = http://havlin.biu.ac.il/Publications.php?keyword=Resilience+of+the+Internet+to+random+breakdown&year=*&match=all | journal = Phys. Rev. Lett. | volume = 85 | issue = 21 | pages = 4626–4628 | doi = 10.1103/physrevlett.85.4626 | bibcode = 2000PhRvL..85.4626C | pmid = 11082612 | arxiv = cond-mat/0007048 | citeseerx = 10.1.1.242.6797 | s2cid = 15372152 | access-date = 2011-04-12 | archive-date = 2013-05-12 | archive-url = https://web.archive.org/web/20130512011815/http://havlin.biu.ac.il/Publications.php?keyword=Resilience+of+the+Internet+to+random+breakdown&year=*&match=all | url-status = dead }}
*{{cite journal | last1 = Pu | first1 = Cun-Lai | last2 = Wen- | last3 = Pei | first3 = Jiang | last4 = Michaelson | first4 = Andrew | year = 2012 | title = Robustness analysis of network controllability | url = http://www.barabasilab.com/pubs/CCNR-ALB_Publications/201204-24_PhysicaA-RobustnessControllability/201204-24_PhysicaA-RobustnessControllability.pdf | journal = Physica A | volume = 391 | issue = 18 | pages = 4420–4425 | doi = 10.1016/j.physa.2012.04.019 | bibcode = 2012PhyA..391.4420P | access-date = 2013-09-18 | archive-url = https://web.archive.org/web/20161013130539/http://www.barabasilab.com/pubs/CCNR-ALB_Publications/201204-24_PhysicaA-RobustnessControllability/201204-24_PhysicaA-RobustnessControllability.pdf | archive-date = 2016-10-13 | url-status = dead }}
* 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)
* '[https://global.oup.com/academic/product/scale-free-networks-9780199665174?q=Caldarelli&lang=en&cc=it Scale-Free Networks]'', G. Caldarelli (Oxford University Press, Oxford)
* ''[http://www.nap.edu/catalog.php?record_id=11516 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}}

{{Social networking}}

[[Category:Cybernetics]]
[[Category:Networks]]
[[Category:Network theory]]
[[Category:Network science| ]]
[[Category:Management theory]]