Network theory
It has been suggested that this article be merged with Network science. (Discuss) Proposed since November 2016.

Network science  



Network types  
Graphs  


Models  




Network theory is the study of graphs as a representation of either symmetric relations or asymmetric relations between discrete objects. In computer science and network science, network theory is a part of graph theory: a network can be defined as a graph in which nodes and/or edges have attributes (e.g. names).
Network theory has applications in many disciplines including statistical physics, particle physics, computer science, electrical engineering, biology,^{[1]} economics, finance, operations research, climatology and sociology. Applications of network theory include logistical networks, the World Wide Web, Internet, gene regulatory networks, metabolic networks, social networks, epistemological networks, etc.; see List of network theory topics for more examples.
Euler's solution of the Seven Bridges of Königsberg problem is considered to be the first true proof in the theory of networks.^{[2]}
Contents
Network optimization
Network problems that involve finding an optimal way of doing something are studied under the name combinatorial optimization. Examples include network flow, shortest path problem, transport problem, transshipment problem, location problem, matching problem, assignment problem, packing problem, routing problem, critical path analysis and PERT (Program Evaluation & Review Technique). In order to break a NPhard task of network optimization down into subtasks the network is decomposed into relatively independent subnets.^{[3]}
Network analysis
Social network analysis
Social network analysis examines the structure of relationships between social entities.^{[5]} 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.^{[6]} Amongst many other applications, social network analysis has been used to understand the diffusion of innovations, news and rumors. Similarly, it has been used to examine the spread of both diseases and healthrelated behaviors. It has also been applied to the study of markets, where it has been used to examine the role of trust^{[citation needed]} in exchange relationships and of social mechanisms in setting prices. Similarly, it has been used to study recruitment into political movements and social organizations. It has also been used to conceptualize scientific disagreements as well as academic prestige. More recently, network analysis (and its close cousin traffic analysis) has gained a significant use in military intelligence, for uncovering insurgent networks of both hierarchical and leaderless nature.^{[citation needed]}
Biological network analysis
With the recent explosion of publicly available high throughput biological data, the analysis of molecular networks has gained significant interest.^{[7]} 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 overrepresented in the network. Similarly, activity motifs are patterns in the attributes of nodes and edges in the network that are overrepresented given the network structure. The analysis of biological networks with respect to diseases has led to the development of the field of network medicine.^{[8]} Recent examples of application of network theory in biology include applications to understanding the cell cycle.^{[9]} The interactions between physiological systems like brain, heart, eyes, etc. can be regarded as a physiological network.^{[10]}
Narrative network analysis
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 analysed 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.^{[12]} This automates the approach introduced by Quantitative Narrative Analysis,^{[13]} whereby subjectverbobject triplets are identified with pairs of actors linked by an action, or pairs formed by actorobject.^{[11]}
Link analysis
Link analysis is a subset of network analysis, exploring associations between objects. An example may be examining the addresses of suspects and victims, the telephone numbers they have dialed and financial transactions that they have partaken in during a given timeframe, and the familial relationships between these subjects as a part of police investigation. Link analysis here provides the crucial relationships and associations between very many objects of different types that are not apparent from isolated pieces of information. Computerassisted or fully automatic computerbased 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.^{[14]}^{[15]}^{[16]}
Network robustness
The structural robustness of networks is studied using percolation theory.^{[17]} When a critical fraction of nodes (or links) is removed the network becomes fragmented into small disconnected clusters. This phenomenon is called percolation,^{[18]} and it represents an orderdisorder type of phase transition with critical exponents. Percolation theory can predict the size of the largest component (called giant component), the critical threshold and the critical exponents.
Web link analysis
Several Web search ranking algorithms use linkbased 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' web sites or blogs. Another use is for classifying pages according to their mention in other pages.^{[19]}
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. 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^{[20]} of a node is the most relevant centrality measure.For a centrality measure based on kcore analysis see ref.^{[21]}
Assortative and disassortative 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.
Recurrence networks
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.^{[22]}^{[23]}^{[24]}
Spread
Content in a complex network can spread via two major methods: conserved spread and nonconserved spread.^{[25]} 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 nonconserved spread, the amount of content changes as it enters and passes through a complex network. The model of nonconserved 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 nonconserved model is the most suitable for explaining the transmission of most infectious diseases, neural excitation, information and rumors, etc.
Interdependent networks
Interdependent networks is a system of coupled networks where nodes of one or more networks depend on nodes in other networks. Such dependencies are enhanced by the developments in modern technology. Dependencies may lead to cascading failures between the networks and a relatively small failure can lead to a catastrophic breakdown of the system. Blackouts are a fascinating demonstration of the important role played by the dependencies between networks. A recent study developed a framework to study the cascading failures in an interdependent networks system.^{[26]}^{[27]}
Implementations
 igraph, an open source C library for the analysis of largescale complex networks, with interfaces to R, Python and Ruby.
 Graphtool and NetworkX, free and efficient Python modules for manipulation and statistical analysis of networks.
 Orange, an opensource data mining software suite with its Network addon.
 Pajek, program for (large) network analysis and visualization.
 GraphMatcher, a Java program to align two or more networks.
 Tulip, a free data mining and visualization software dedicated to the analysis and visualization of relational data.
 SEMOSS, an RDFbased open source contextaware analytics tool written in Java leveraging the SPARQL query language.
 GraphStream is a Java library for the modeling and analysis of dynamic graphs. You can generate, import, export, measure, layout and visualize them.
See also
 Complex network
 Congestion game
 Quantum complex network
 Dualphase evolution
 Percolation
 Network partition
 Network science
 Network theory in risk assessment
 Network topology
 Network analyzer
 Seven Bridges of Königsberg
 Smallworld networks
 Social network
 Scalefree networks
 Network dynamics
 Sequential dynamical systems
 Pathfinder networks
 Human disease network
 Biological network
 Network medicine
References
 ^ Habibi, Iman; Emamian, Effat S.; Abdi, Ali (20140101). "Quantitative analysis of intracellular communication and signaling errors in signaling networks". BMC Systems Biology. 8: 89. doi:10.1186/s129180140089z. ISSN 17520509. PMC 4255782 . PMID 25115405.
 ^ Newman, M. E. J. "The structure and function of complex networks" (PDF). Department of Physics, University of Michigan.
 ^ ^{a} ^{b} Ignatov, D.Yu.; Filippov, A.N.; Ignatov, A.D.; Zhang, X. (2016). "Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks" (PDF). Proc. ISP RAS. 28: 141–152. arXiv:1701.06595 . doi:10.15514/ISPRAS201628(6)10.
 ^ Grandjean, Martin (2014). "La connaissance est un réseau". Les Cahiers du Numérique. 10 (3): 37–54. doi:10.3166/lcn.10.3.3754. Retrieved 20141015.
 ^ 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.
 ^ Newman, M.E.J. Networks: An Introduction. Oxford University Press. 2010
 ^ Habibi, Iman; Emamian, Effat S.; Abdi, Ali (20141007). "Advanced Fault Diagnosis Methods in Molecular Networks". PLOS ONE. 9 (10): e108830. doi:10.1371/journal.pone.0108830. ISSN 19326203. PMC 4188586 . PMID 25290670.
 ^ Barabási, A. L.; Gulbahce, N.; Loscalzo, J. (2011). "Network medicine: a networkbased approach to human disease". Nature Reviews Genetics. 12 (1): 56–68. doi:10.1038/nrg2918. PMC 3140052 . PMID 21164525.
 ^ Jailkhani, N.; Ravichandran, N.; Hegde, S. R.; Siddiqui, Z.; Mande, S. C.; Rao, K. V. "Delineation of key regulatory elements identifies points of vulnerability in the mitogenactivated signaling network". Genome Research. 21 (12): 2067–81. doi:10.1101/gr.116145.110. PMC 3227097 .
 ^ Bashan, Amir; Bartsch, Ronny P.; Kantelhardt, Jan. W.; Havlin, Shlomo; Ivanov, Plamen Ch. (2012). "Network physiology reveals relations between network topology and physiological function". Nature Communications. 3: 702. doi:10.1038/ncomms1705. ISSN 20411723. PMC 3518900 . PMID 22426223.
 ^ ^{a} ^{b} Automated analysis of the US presidential elections using Big Data and network analysis; S Sudhahar, GA Veltri, N Cristianini; Big Data & Society 2 (1), 1–28, 2015
 ^ Network analysis of narrative content in large corpora; S Sudhahar, G De Fazio, R Franzosi, N Cristianini; Natural Language Engineering, 1–32, 2013
 ^ Quantitative Narrative Analysis; Roberto Franzosi; Emory University © 2010
 ^ Tsonis, Anastasios A.; Swanson, Kyle L.; Roebber, Paul J. (2006). "What Do Networks Have to Do with Climate?". Bulletin of the American Meteorological Society. 87 (5): 585–595. doi:10.1175/BAMS875585. ISSN 00030007.
 ^ Yamasaki, K.; Gozolchiani, A.; Havlin, S. (2008). "Climate Networks around the Globe are Significantly Affected by El Niño". Physical Review Letters. 100 (22): 228501. Bibcode:2008PhRvL.100v8501Y. doi:10.1103/PhysRevLett.100.228501. ISSN 00319007. PMID 18643467.
 ^ Boers, N.; Bookhagen, B.; Barbosa, H.M.J.; Marwan, N.; Kurths, J. (2014). "Prediction of extreme floods in the eastern Central Andes based on a complex networks approach". Nature Communications. 5: 5199. doi:10.1038/ncomms6199. ISSN 20411723. PMID 25310906.
 ^ R. Cohen; S. Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press.
 ^ A. Bunde; S. Havlin (1996). Fractals and Disordered Systems. Springer.
 ^ Attardi, G.; S. Di Marco; D. Salvi (1998). "Categorization by Context" (PDF). Journal of Universal Computer Science. 4 (9): 719–736.
 ^ Restrepo, Juan; E. Ott; B. R. Hunt (2006). "Characterizing the Dynamical Importance of Network Nodes and Links". Phys. Rev. Lett. 97 (9): 094102. arXiv:condmat/0606122 . doi:10.1103/PhysRevLett.97.094102. PMID 17026366.
 ^ Carmi, S.; Havlin, S.; Kirkpatrick, S.; Shavitt, Y.; Shir, E. (2007). "A model of Internet topology using kshell decomposition". Proceedings of the National Academy of Sciences. 104 (27): 11150–11154. doi:10.1073/pnas.0701175104. ISSN 00278424. PMC 1896135 . PMID 17586683.
 ^ Marwan, N.; Donges, J.F.; Zou, Y.; Donner, R.V.; Kurths, J. (2009). "Complex network approach for recurrence analysis of time series". Physics Letters A. 373 (46): 4246–4254. arXiv:0907.3368 . doi:10.1016/j.physleta.2009.09.042. ISSN 03759601.
 ^ Donner, R.V.; Heitzig, J.; Donges, J.F.; Zou, Y.; Marwan, N.; Kurths, J. (2011). "The Geometry of Chaotic Dynamics – A Complex Network Perspective". European Physical Journal B. 84: 653–672. doi:10.1140/epjb/e2011108991. ISSN 14346036.
 ^ Feldhoff, J.H.; Donner, R.V.; Donges, J.F.; Marwan, N.; Kurths, J. (2013). "Geometric signature of complex synchronisation scenarios". Europhysics Letters. 102 (3): 30007. doi:10.1209/02955075/102/30007. ISSN 12864854.
 ^ Newman, M., Barabási, A.L., Watts, D.J. [eds.] (2006) The Structure and Dynamics of Networks. Princeton, N.J.: Princeton University Press.
 ^ S. V. Buldyrev; R. Parshani; G. Paul; H. E. Stanley; S. Havlin (2010). "Catastrophic cascade of failures in interdependent networks". Nature. 464 (7291): 1025–28. doi:10.1038/nature08932. PMID 20393559.
 ^ Jianxi Gao; Sergey V. Buldyrev; Shlomo Havlin; H. Eugene Stanley (2011). "Robustness of a Network of Networks". Phys. Rev. Lett. 107 (19): 195701. doi:10.1103/PhysRevLett.107.195701. PMID 22181627.
Books
 S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: from biological networks to the Internet and WWW, Oxford University Press, 2003, ISBN 0198515901
 G. Caldarelli, "ScaleFree Networks", Oxford University Press, 2007, ISBN 9780199211517
 A. Barrat, M. Barthelemy, A. Vespignani, "Dynamical Processes on Complex Networks", Cambridge University Press, 2008, ISBN 9780521879507
 E. Estrada, "The Structure of Complex Networks: Theory and Applications", Oxford University Press, 2011, ISBN 9780199591756
 K. Soramaki and S. Cook, "Network Theory and Financial Risk", Risk Books, 2016 ISBN 9781782722199 ^{[1]}
 V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Cambridge University Press, 2017, ISBN 9781107103184
External links
Wikiquote has quotations related to: Network theory 
 netwiki Scientific wiki dedicated to network theory
 New Network Theory International Conference on 'New Network Theory'
 Network Workbench: A LargeScale Network Analysis, Modeling and Visualization Toolkit
 Optimization of the Large Network doi:10.13140/RG.2.2.20183.06565/6
 Network analysis of computer networks
 Network analysis of organizational networks
 Network analysis of terrorist networks
 Network analysis of a disease outbreak
 Link Analysis: An Information Science Approach (book)
 Connected: The Power of Six Degrees (documentary)
 Kitsak, M.; Gallos, L. K.; Havlin, S.; Liljeros, F.; Muchnik, L.; Stanley, H. E.; Makes, H.A. (2010). "Influential Spreaders in Networks". Nature Physics. 6: 888. doi:10.1038/nphys1746.
 A short course on complex networks
 A course on complex network analysis by AlbertLászló Barabási
 The Journal of Network Theory in Finance

Network theory in Operations Research from the Institute for Operations Research and the Management Sciences (INFORMS)
 ^ Kimmo., Soramäki, (2016). Network theory and financial risk. Cook, Samantha (Statistician). [London]: Risk Books. ISBN 9781782722199. OCLC 973733901.