Study of graphs as a representation of relations between discrete objects
A small example network with eight vertices (nodes) and ten edges (links)
In mathematics , computer science and network science , network theory is a part of graph theory . It defines networks as graphs where the nodes or edges possess attributes. Network theory analyses these networks over the symmetric relations or asymmetric relations between their (discrete) components.
Network theory has applications in many disciplines, including
for more examples.
is considered to be the first true proof in the theory of networks.
Network optimization
Network problems that involve finding an optimal way of doing something are studied as
.
Network analysis
Electric network analysis
The analysis of electric power systems could be conducted using network theory from two main points of view:
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.[1]
Weighted graphs that blend an abstract understanding of complex network theories and electric power systems properties.[2]
Social network analysis
.
Since the 1970s, the empirical study of networks has played a central role in social science, and many of the
exchange relationships and of social mechanisms in setting prices.
[21] It has been used to study recruitment into
political movements , armed groups, and other social organizations.
[22] It has also been used to conceptualize scientific disagreements
[23] as well as academic prestige.
[24] More recently, network analysis (and its close cousin
traffic analysis ) has gained a significant use in military intelligence,
[25] 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.[26] 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 .[27] Recent examples of application of network theory in biology include applications to understanding the cell cycle [28] as well as a quantitative framework for developmental processes.[29]
Narrative network analysis
Narrative network of US Elections 2012[30]
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.[31] This automates the approach introduced by Quantitative Narrative Analysis,[32] whereby subject-verb-object triplets are identified with pairs of actors linked by an action, or pairs formed by actor-object.[30]
Link analysis
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.
[33] [34]
Web link analysis
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.
[35]
Centrality measures
Information about the relative importance of nodes and edges in a graph can be obtained through
of a node is the most relevant centrality measure.
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.[37]
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.[38] [39] [40]
Spatial networks
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.[41]
Spread
Content in a
infectious diseases
, neural excitation, information and rumors, etc.
Network immunization
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[43] since for this case
p
c
{\displaystyle 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.
See also
References
^ .
^ . Retrieved 2018-06-07 .
.
^ Sindbæk S (2007). Networks and nodal points: the emergence of towns in early Viking Age Scandinavia - Antiquity 81(311) . Cambridge University Press. pp. 119–132.
.
.
.
.
.
.
.
.
.
^ Alex Fornito. "An Introduction to Network Neuroscience: How to build, model, and analyse connectomes - 0800-10:00 | OHBM" . pathlms.com . Retrieved 2020-03-11 .
.
. Retrieved 2014-10-15 .
MIT
Press, 2012.
^ Newman, M.E.J. Networks: An Introduction. Oxford University Press. 2010
.
.
.
.
.
. Retrieved 22 September 2021 .
^ Roberts N, Everton SF. "Strategies for Combating Dark Networks" (PDF) . Journal of Social Structure . 12 . Retrieved 22 September 2021 .
.
.
.
.
^ 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
.
.
^ Attardi G, Di Marco S, Salvi D (1998). "Categorization by Context" (PDF) . Journal of Universal Computer Science . 4 (9): 719–736.
.
S2CID
15186389.
.
.
.
.
^ Newman M, Barabási AL, Watts DJ, eds. (2006). The Structure and Dynamics of Networks . Princeton, N.J.: Princeton University Press.
.
Books
Dorogovtsev SN, Mendes JR (2003). Evolution of Networks: from biological networks to the Internet and WWW . Oxford University Press. .
Caldarelli G (2007). Scale-Free Networks . Oxford University Press. .
Barrat A, Barthelemy M, Vespignani A (2008). Dynamical Processes on Complex Networks . Cambridge University Press. .
Estrada E (2011). The Structure of Complex Networks: Theory and Applications . Oxford University Press. .
Soramaki K, Cook S (2016). Network Theory and Financial Risk . Risk Books. .
Latora V, Nicosia V, Russo G (2017). Complex Networks: Principles, Methods and Applications . Cambridge University Press. .
External links