Network theory#Network robustness

Network problems that involve finding an optimal way of doing something are studied as 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 program evaluation and review technique.

The analysis of electric power systems could be conducted using network theory from two main points of view:

1. An abstract perspective (i.e., as a graph consists from nodes and edges), regardless of the electric power aspects (e.g., transmission line impedances). Most of these studies focus only on the abstract structure of the power grid using node degree distribution and betweenness distribution, which introduces substantial insight regarding the vulnerability assessment of the grid. Through these types of studies, the category of the grid structure could be identified from the complex network perspective (e.g., single-scale, scale-free). This classification might help the electric power system engineers in the planning stage or while upgrading the infrastructure (e.g., add a new transmission line) to maintain a proper redundancy level in the transmission system.
2. Weighted graphs that blend an abstract understanding of complex network theories and electric power systems properties.

File:Social Network Analysis Visualization.pngSocial network analysis examines the structure of relationships between social entities.Wasserman, Stanley and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press. Rainie, Lee and Barry Wellman, Networked: The New Social Operating System. Cambridge, MA: MIT Press, 2012.

These entities are often persons, but may also be groups, organizations, nation states, web sites, or 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.Newman, M.E.J. Networks: An Introduction. Oxford University Press. 2010 Amongst many other applications, social network analysis has been used to understand the diffusion of innovations, news and rumors.{{cite book | vauthors = Al-Taie MZ, Kadry S |chapter=Information Diffusion in Social Networks |title=Python for Graph and Network Analysis |series=Advanced Information and Knowledge Processing |date=2017 |pages=165–184 |doi=10.1007/978-3-319-53004-8_8 |pmc=7123536 |isbn=978-3-319-53003-1 }} Similarly, it has been used to examine the spread of both diseases and health-related behaviors.{{cite journal | vauthors = Luke DA, Harris JK | title = Network analysis in public health: history, methods, and applications | journal = Annual Review of Public Health | volume = 28 | issue = 1 | pages = 69–93 | date = April 2007 | pmid = 17222078 | doi = 10.1146/annurev.publhealth.28.021406.144132 | doi-access = free }} 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.{{cite journal | vauthors = Odabaş M, Holt TJ, Breiger RL |title=Markets as Governance Environments for Organizations at the Edge of Illegality: Insights From Social Network Analysis |journal=American Behavioral Scientist |date=October 2017 |volume=61 |issue=11 |pages=1267–1288 |doi=10.1177/0002764217734266 |hdl=10150/631238 |s2cid=158776581 |hdl-access=free }} It has been used to study recruitment into political movements, armed groups, and other social organizations.{{cite journal | vauthors = Larson JM |title=Networks of Conflict and Cooperation |journal=Annual Review of Political Science |date=11 May 2021 |volume=24 |issue=1 |pages=89–107 |doi=10.1146/annurev-polisci-041719-102523 |doi-access=free }} It has also been used to conceptualize scientific disagreements{{cite journal | vauthors = Leng RI | title = A network analysis of the propagation of evidence regarding the effectiveness of fat-controlled diets in the secondary prevention of coronary heart disease (CHD): Selective citation in reviews | journal = PLOS ONE | volume = 13 | issue = 5 | pages = e0197716 | date = 24 May 2018 | pmid = 29795624 | pmc = 5968408 | doi = 10.1371/journal.pone.0197716 | doi-access = free | bibcode = 2018PLoSO..1397716L }} as well as academic prestige.{{cite journal | vauthors = Burris V |title=The Academic Caste System: Prestige Hierarchies in PhD Exchange Networks |journal=American Sociological Review |date=April 2004 |volume=69 |issue=2 |pages=239–264 |doi=10.1177/000312240406900205 |s2cid=143724478 |url=https://journals.sagepub.com/doi/10.1177/000312240406900205 |access-date=22 September 2021}} More recently, network analysis (and its close cousin traffic analysis) has gained a significant use in military intelligence,{{cite journal | vauthors = Roberts N, Everton SF |title= Strategies for Combating Dark Networks |journal=Journal of Social Structure |volume=12 |url=https://www.cmu.edu/joss/content/articles/volume12/RobertsEverton.pdf |access-date=22 September 2021}} for uncovering insurgent networks of both hierarchical and leaderless nature.{{citation needed|date=July 2015}}

{{see also|Metabolic network|proteome|metabolome|omics}}

With the recent explosion of publicly available high throughput biological data, the analysis of molecular networks has gained significant interest.{{cite journal | vauthors = Habibi I, Emamian ES, Abdi A | title = Advanced fault diagnosis methods in molecular networks | journal = PLOS ONE | volume = 9 | issue = 10 | pages = e108830 | date = 2014-10-07 | pmid = 25290670 | pmc = 4188586 | doi = 10.1371/journal.pone.0108830 | doi-access = free | bibcode = 2014PLoSO...9j8830H }} The type of analysis in this context is 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. Similarly, activity motifs are patterns in the attributes of nodes and edges in the network that are over-represented given the network structure. Using networks to analyze patterns in biological systems, such as food-webs, allows us to visualize the nature and strength of interactions between species. The analysis of biological networks with respect to diseases has led to the development of the field of network medicine.{{cite journal | vauthors = Barabási AL, Gulbahce N, Loscalzo J | title = Network medicine: a network-based approach to human disease | journal = Nature Reviews. Genetics | volume = 12 | issue = 1 | pages = 56–68 | date = January 2011 | pmid = 21164525 | pmc = 3140052 | doi = 10.1038/nrg2918 }} Recent examples of application of network theory in biology include applications to understanding the cell cycle{{cite journal | vauthors = Jailkhani N, Ravichandran S, Hegde SR, Siddiqui Z, Mande SC, Rao KV | title = Delineation of key regulatory elements identifies points of vulnerability in the mitogen-activated signaling network | journal = Genome Research | volume = 21 | issue = 12 | pages = 2067–2081 | date = December 2011 | pmid = 21865350 | pmc = 3227097 | doi = 10.1101/gr.116145.110 }} as well as a quantitative framework for developmental processes.{{cite journal | vauthors = Jackson MD, Duran-Nebreda S, Bassel GW | title = Network-based approaches to quantify multicellular development | journal = Journal of the Royal Society, Interface | volume = 14 | issue = 135 | pages = 20170484 | date = October 2017 | pmid = 29021161 | pmc = 5665831 | doi = 10.1098/rsif.2017.0484 }}

File:Tripletsnew2012.png

The automatic parsing of textual corpora has enabled the extraction of actors and their relational networks on a vast scale. The resulting narrative networks, which can contain thousands of nodes, are then analyzed by using tools from Network theory to identify the key actors, the key communities or parties, and general properties such as robustness or structural stability of the overall network, or centrality of certain nodes.[http://orcp.hustoj.com/wp-content/uploads/2016/01/2013-Network-analysis-of-narrative-content-in-large-corpora.pdf Network analysis of narrative content in large corpora]; S Sudhahar, G De Fazio, R Franzosi, N Cristianini; Natural Language Engineering, 1–32, 2013 This automates the approach introduced by Quantitative Narrative Analysis,Quantitative Narrative Analysis; Roberto Franzosi; Emory University © 2010 whereby subject-verb-object triplets are identified with pairs of actors linked by an action, or pairs formed by actor-object.

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. Links are also derived from similarity of time behavior in both nodes. Examples include climate networks where the links between two locations (nodes) are determined, for example, by the similarity of the rainfall or temperature fluctuations in both sites.{{cite journal| vauthors = Tsonis AA, Swanson KL, Roebber PJ |title=What Do Networks Have to Do with Climate?|journal=Bulletin of the American Meteorological Society|volume=87|issue=5|year=2006|pages=585–595|issn=0003-0007|doi=10.1175/BAMS-87-5-585|bibcode=2006BAMS...87..585T|doi-access=free}}{{cite journal | vauthors = Boers N, Bookhagen B, Barbosa HM, Marwan N, Kurths J, Marengo JA | title = Prediction of extreme floods in the eastern Central Andes based on a complex networks approach | journal = Nature Communications | volume = 5 | pages = 5199 | date = October 2014 | pmid = 25310906 | doi = 10.1038/ncomms6199 | s2cid = 3032237 | doi-access = free | bibcode = 2014NatCo...5.5199B | author5-link = Jürgen Kurths }}

Several Web search ranking algorithms use link-based centrality metrics, including 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' websites or blogs. Another use is for classifying pages according to their mention in other pages.{{cite journal| vauthors = Attardi G, Di Marco S, Salvi D |title=Categorization by Context|journal=Journal of Universal Computer Science|year=1998|volume=4|issue=9|pages=719–736|url=http://www.jucs.org/jucs_4_9/categorisation_by_context/Attardi_G.pdf}}

Information about the relative importance of nodes and edges in a graph can be obtained through centrality measures, widely used in disciplines like sociology. For example, eigenvector centrality uses the eigenvectors of the adjacency matrix corresponding to a network, to determine nodes that tend to be frequently visited. Formally established measures of centrality are degree centrality, closeness centrality, betweenness centrality, eigenvector centrality, subgraph centrality, and Katz centrality. The purpose or objective of analysis generally determines the type of centrality measure to be used. For example, if one is interested in dynamics on networks or the robustness of a network to node/link removal, often the dynamical importance{{cite journal | vauthors = Restrepo JG, Ott E, Hunt BR | title = Characterizing the dynamical importance of network nodes and links | journal = Physical Review Letters | volume = 97 | issue = 9 | pages = 094102 | date = September 2006 | pmid = 17026366 | doi = 10.1103/PhysRevLett.97.094102 | arxiv = cond-mat/0606122 | s2cid = 18365246 | bibcode = 2006PhRvL..97i4102R }} of a node is the most relevant centrality measure.

{{see|Assortative mixing}}

These concepts are used to characterize the linking preferences of hubs in a network. Hubs are nodes which have a large number of links. Some hubs tend to link to other hubs while others avoid connecting to hubs and prefer to connect to nodes with low connectivity. We say a hub is assortative when it tends to connect to other hubs. A disassortative hub avoids connecting to other hubs. If hubs have connections with the expected random probabilities, they are said to be neutral. There are three methods to quantify degree correlations.M. E. J. Newman (2003). "Mixing patterns in networks". Physical Review E. 67 (2): 026126. arXiv:cond-mat/0209450. Bibcode:2003PhRvE..67b6126N. doi:10.1103/PhysRevE.67.026126. PMID 12636767. S2CID 15186389.

The recurrence matrix of a recurrence plot can be considered as the adjacency matrix of an undirected and unweighted network. This allows for the analysis of time series by network measures. Applications range from detection of regime changes over characterizing dynamics to synchronization analysis.{{cite journal| vauthors = Marwan N, Donges JF, Zou Y, Donner RV, Kurths J |title=Complex network approach for recurrence analysis of time series|journal=Physics Letters A|volume=373|issue=46|year=2009|pages=4246–4254|issn=0375-9601|doi=10.1016/j.physleta.2009.09.042|arxiv=0907.3368|bibcode=2009PhLA..373.4246M|s2cid=7761398}}{{cite journal| vauthors = Donner RV, Heitzig J, Donges JF, Zou Y, Marwan N, Kurths J |title=The Geometry of Chaotic Dynamics – A Complex Network Perspective|journal=European Physical Journal B|volume=84|issue=4|year=2011|pages=653–672|issn=1434-6036|doi=10.1140/epjb/e2011-10899-1|arxiv=1102.1853|bibcode=2011EPJB...84..653D|s2cid=18979395}}{{cite journal| vauthors = Feldhoff JH, Donner RV, Donges JF, Marwan N, Kurths J |title=Geometric signature of complex synchronisation scenarios|journal=Europhysics Letters |volume=102 |issue=3 |year=2013|pages=30007|issn=1286-4854|doi=10.1209/0295-5075/102/30007|arxiv=1301.0806|bibcode=2013EL....10230007F|s2cid=119118006}}

Many real networks are embedded in space. Examples include, transportation and other infrastructure networks, brain neural networks. Several models for spatial networks have been developed.{{cite journal | title = Routing of multipoint connections | doi = 10.1109/49.12889 | vauthors = Waxman BM | journal = IEEE Journal on Selected Areas in Communications | volume = 6 | pages = 1617–1622 | date = 1988| issue = 9 }}

Other networks emphasise the evolution over time of systems of nodes and their interconnections. Temporal networks are used for example to study how financial risk has spread across countries.{{Cite journal| last1= Franch|first1=F.| last2=Nocciola|first2=L.|last3=Vouldis| first3=A.|date=April 2024|title= Temporal networks and financial contagion|url=https://doi.org/10.1016/j.jfs.2024.101224|journal= Journal of Financial Stability| volume=71 |doi= 10.1016/j.jfs.2024.101224|issn=}} In this study, temporal networks are used to also visually trace the intricate dynamics of financial contagion during crises. Unlike traditional network approaches that aggregate or analyze static snapshots, the study uses a time-respecting path methodology to preserve the sequence and timing of financial crises contagion events. This enables the identification of nodes as sources, transmitters, or receivers of financial stress, avoiding mischaracterizations inherent in static or aggregated methods. Following this approach, banks are found to serve as key intermediaries in contagion paths, and temporal analysis pinpoints smaller countries like Greece and Italy as significant origins of shocks during crises—insights obscured by static approaches that overemphasize large economies like the US or Japan.

Temporal networks can also be used to explore how cooperation evolves in dynamic, real-world population structures where interactions are time-dependent.{{Cite journal |last1=Li |first1=A. |last2=Zhou |first2=L. |last3=Su |first3=Q. |last4=Cornelius |first4=S.P.|last5=Liu |first5=Y.|last6=L. |first6=Wang|last7=Levin|first7=S.A.|title=Evolution of cooperation on temporal networks |journal=Nature Communications |volume=11 |issue=2259 |date=8 May 2020|doi=10.1038/s41467-020-16088-w |bibcode=2020NatCo..11.2259L |url=https://doi.org/10.1038/s41467-020-16088-w|arxiv=1609.07569 }} Here the authors find that network temporality enhances cooperation compared to static networks, even though "bursty" interaction patterns typically hinder it. This finding also shows how cooperation and other emergent behaviours can thrive in realistic, time-varying population structures, challenging conventional assumptions rooted in static models.

In psychology, temporal networks enable the understanding of psychological disorders by framing them as dynamic systems of interconnected symptoms rather than outcomes of a single underlying cause. Using "nodes" to represent symptoms and "edges" to signify their direct interactions, symptoms like insomnia and fatigue are shown how they influence each other over time; also, disorders such as depression are shown not to be fixed entities but evolving networks, where identifying "bridge symptoms" like concentration difficulties can explain comorbidity between conditions such as depression and anxiety.{{Cite journal |last1=Jordan |first1=D.G. |last2=Winer |first2=E.S. |last3=Salem |first3=T. |title=The current status of temporal network analysis for clinical science: Considerations as the paradigm shifts? |journal=J Clin Psychol |volume=76 |year=2020 |issue=9 |pages=1591–1612 |doi=10.1002/jclp.22957|pmid=32386334 |url= https://doi.org/10.1002/jclp.22957}}

Lastly, temporal networks enable a better understanding and controlling of the spread of infectious diseases.{{Cite journal |last1=Masuda |first1=N. |last2=Holme |first2=P. |title=Predicting and controlling infectious disease epidemics using temporal networks |journal=F1000Prime Reports |volume=5 |year=2013 |page=6 |doi=10.12703/P5-6|doi-access=free |pmid=23513178 |pmc=3590785 }} Unlike traditional static networks, which assume continuous, unchanging connections, temporal networks account for the precise timing and duration of interactions between individuals. This dynamic approach reveals critical nuances, such as how diseases can spread via time-sensitive pathways that static models miss. Temporal data, such as interactions captured through Bluetooth sensors or in hospital wards, can improve predictions of outbreak speed and extent. Overlooking temporal correlations can lead to significant errors in estimating epidemic dynamics, emphasizing the need for a temporal framework to develop more accurate strategies for disease control.

Content in a complex network can spread via two major methods: conserved spread and non-conserved spread.{{cite book | veditors = Newman M, Barabási AL, Watts DJ | date = 2006 | title = The Structure and Dynamics of Networks. | location = Princeton, N.J. | publisher = Princeton University Press }} 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, neural excitation, information and rumors, etc.

The question of how to immunize efficiently scale free networks which represent realistic networks such as the Internet and social networks has been studied extensively. One such strategy is to immunize the largest degree nodes, i.e., targeted (intentional) attacks{{cite journal | vauthors = Callaway DS, Newman ME, Strogatz SH, Watts DJ | title = Network robustness and fragility: percolation on random graphs | journal = Physical Review Letters | volume = 85 | issue = 25 | pages = 5468–5471 | date = December 2000 | pmid = 11136023 | doi = 10.1103/PhysRevLett.85.5468 | bibcode = 2000PhRvL..85.5468C | arxiv = cond-mat/0007300 | s2cid = 2325768 }} since for this case $pc$ is relatively high and fewer nodes are needed to be immunized.

However, in most realistic networks the global structure is not available and the largest degree nodes are unknown.

{{div col|colwidth=20em}}

• Complex network
• Congestion game
• Quantum complex network
• Dual-phase evolution
• Network partition
• Network science
• Network theory in risk assessment
• Network topology
• Network analyzer
• Seven Bridges of Königsberg
• Small-world networks
• Social network
• Scale-free networks
• Network dynamics
• Sequential dynamical systems
• Pathfinder networks
• Human disease network
• Biological network
• Network medicine
• Graph partition

{{div col end}}

{{Reflist|refs=

{{cite journal | vauthors = Borchers A, Pieler T | title = Programming pluripotent precursor cells derived from Xenopus embryos to generate specific tissues and organs | journal = Genes | volume = 1 | issue = 3 | pages = 413–426 | date = November 2010 | pmid = 24710095 | doi = 10.3390/en11061381 | pmc = 3966229 | doi-access = free }}

{{Cite book|chapter-url=https://ieeexplore.ieee.org/document/8191215|title=Optimal microgrids placement in electric distribution systems using complex network framework - IEEE Conference Publication|pages=1036–1040|publisher=IEEE|language=en-US|access-date=2018-06-07|doi=10.1109/ICRERA.2017.8191215|chapter=Optimal microgrids placement in electric distribution systems using complex network framework|year=2017|last1=Saleh|first1=Mahmoud|last2=Esa|first2=Yusef|last3=Onuorah|first3=Nwabueze|last4=Mohamed|first4=Ahmed A.|isbn=978-1-5386-2095-3|s2cid=44685630|url=https://academicworks.cuny.edu/cgi/viewcontent.cgi?article=1726&context=cc_pubs}}

{{Cite web|url=https://www.pathlms.com/ohbm/courses/12238/sections/15846/video_presentations/137536|title=An Introduction to Network Neuroscience: How to build, model, and analyse connectomes - 0800-10:00 {{!}} OHBM|website=pathlms.com|language=en|author=Alex Fornito|access-date=2020-03-11}}

}}

{{refbegin}}

• {{cite book | vauthors = Dorogovtsev SN, Mendes JR | title = Evolution of Networks: from biological networks to the Internet and WWW | publisher = Oxford University Press | date = 2003 | isbn = 978-0-19-851590-6 }}
• {{cite book | vauthors = Caldarelli G | title = Scale-Free Networks | publisher = Oxford University Press | date = 2007 | isbn = 978-0-19-921151-7}}
• {{cite book | vauthors = Barrat A, Barthelemy M, Vespignani A | title = Dynamical Processes on Complex Networks | publisher = Cambridge University Press | date = 2008 | isbn = 978-0-521-87950-7 }}
• {{cite book | vauthors = Estrada E | title = The Structure of Complex Networks: Theory and Applications | publisher = Oxford University Press | date = 2011 | isbn = 978-0-199-59175-6 }}
• {{cite book | vauthors = Soramaki K, Cook S | title = Network Theory and Financial Risk | publisher = Risk Books | date = 2016 | isbn = 978-1-78272-219-9 }}
• {{cite book | vauthors = Latora V, Nicosia V, Russo G | title = Complex Networks: Principles, Methods and Applications | publisher = Cambridge University Press | date = 2017 | isbn = 978-1-107-10318-4 }}

{{refend}}

{{wikiquote}}

• [http://netwiki.amath.unc.edu/ netwiki] Scientific wiki dedicated to network theory
• [http://www.networkcultures.org/networktheory/ New Network Theory] International Conference on 'New Network Theory'
• [http://nwb.slis.indiana.edu/ Network Workbench]: A Large-Scale Network Analysis, Modeling and Visualization Toolkit
• [https://www.slideshare.net/DmitryIgnatovPhD/network-optimization-82005426 Optimization of the Large Network] doi:10.13140/RG.2.2.20183.06565/6
• [http://www.orgnet.com/SocialLifeOfRouters.pdf Network analysis of computer networks]
• [http://www.orgnet.com/orgnetmap.pdf Network analysis of organizational networks]
• [https://web.archive.org/web/20121123010939/http://firstmonday.org/htbin/cgiwrap/bin/ojs/index.php/fm/article/view/941/863 Network analysis of terrorist networks]
• [https://web.archive.org/web/20080724193037/http://www.orgnet.com/AJPH2007.pdf Network analysis of a disease outbreak]
• [http://linkanalysis.wlv.ac.uk/ Link Analysis: An Information Science Approach] (book)
• [https://web.archive.org/web/20090307155011/http://gephi.org/2008/how-kevin-bacon-cured-cancer/ Connected: The Power of Six Degrees] (documentary)
• [http://havlin.biu.ac.il/course4.php A short course on complex networks]
• [https://web.archive.org/web/20160211200247/http://barabasilab.neu.edu/courses/phys5116/ A course on complex network analysis by Albert-László Barabási]
• [http://www.risk.net/type/technical-paper/source/journal-of-network-theory-in-finance/ The Journal of Network Theory in Finance]
• [https://www.informs.org/About-INFORMS/History-and-Traditions/OR-Methodologies/Networks-and-Graphs Network theory in Operations Research] from the Institute for Operations Research and the Management Sciences (INFORMS)

Category:Networks

Category:Graph theory

fi:Verkkoteoria