Network theory is the study of
graphs as a representation of either
symmetric relations or
asymmetric relations between discrete objects. In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
and
network science, network theory is a part of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
: 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
Particle physics or high energy physics is the study of fundamental particles and forces that constitute matter and radiation. The fundamental particles in the universe are classified in the Standard Model as fermions (matter particles) an ...
, computer science,
electrical engineering
Electrical engineering is an engineering discipline concerned with the study, design, and application of equipment, devices, and systems which use electricity, electronics, and electromagnetism. It emerged as an identifiable occupation in the l ...
,
biology
Biology is the scientific study of life. It is a natural science with a broad scope but has several unifying themes that tie it together as a single, coherent field. For instance, all organisms are made up of cells that process hereditary ...
,
archaeology
Archaeology or archeology is the scientific study of human activity through the recovery and analysis of material culture. The archaeological record consists of artifacts, architecture, biofacts or ecofacts, sites, and cultural landsc ...
,
economics
Economics () is the social science that studies the production, distribution, and consumption of goods and services.
Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics anal ...
,
finance
Finance is the study and discipline of money, currency and capital assets. It is related to, but not synonymous with economics, the study of production, distribution, and consumption of money, assets, goods and services (the discipline of f ...
,
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...
,
climatology
Climatology (from Greek , ''klima'', "place, zone"; and , '' -logia'') or climate science is the scientific study of Earth's climate, typically defined as weather conditions averaged over a period of at least 30 years. This modern field of stu ...
,
ecology
Ecology () is the study of the relationships between living organisms, including humans, and their physical environment. Ecology considers organisms at the individual, population, community, ecosystem, and biosphere level. Ecology overl ...
,
public health
Public health is "the science and art of preventing disease, prolonging life and promoting health through the organized efforts and informed choices of society, organizations, public and private, communities and individuals". Analyzing the det ...
,
sociology
Sociology is a social science that focuses on society, human social behavior, patterns of social relationships, social interaction, and aspects of culture associated with everyday life. It uses various methods of empirical investigation an ...
, and
neuroscience
Neuroscience is the science, scientific study of the nervous system (the brain, spinal cord, and peripheral nervous system), its functions and disorders. It is a Multidisciplinary approach, multidisciplinary science that combines physiology, an ...
.
Applications of network theory include
logistical networks, the
World Wide Web,
Internet
The Internet (or internet) is the global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a '' network of networks'' that consists of private, p ...
,
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.
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
The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:
:The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any ta ...
,
packing problem,
routing problem,
critical path analysis, and
PERT (Program Evaluation & Review Technique).
Network analysis
Electric network analysis
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.
Social network analysis
Social network analysis examines the structure of relationships between social entities. These entities are often persons, but may also be
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
,
organizations,
nation states
A nation state is a political unit where the state and nation are congruent. It is a more precise concept than "country", since a country does not need to have a predominant ethnic group.
A nation, in the sense of a common ethnicity, may ...
,
web sites
A website (also written as a web site) is a collection of web pages and related content that is identified by a common domain name and published on at least one web server. Examples of notable websites are Google, Facebook, Amazon, and Wiki ...
, 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
Statistics (from German: '' Statistik'', "description of a state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a scientific, industr ...
tools used for studying networks have been first developed in
sociology
Sociology is a social science that focuses on society, human social behavior, patterns of social relationships, social interaction, and aspects of culture associated with everyday life. It uses various methods of empirical investigation an ...
.
[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.
Similarly, it has been used to examine the spread of both
diseases and
health-related behaviors.
It has also been applied to the
study of markets, where it has been used to examine the role of trust in
exchange relationships and of social mechanisms in setting prices.
It has been used to study recruitment into
political movements, armed groups, and other 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.
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 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
Activity may refer to:
* Action (philosophy), in general
* Human activity: human behavior, in sociology behavior may refer to all basic human actions, economics may study human economic activities and along with cybernetics and psychology may stu ...
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
Network medicine is the application of network science towards identifying, preventing, and treating diseases. This field focuses on using network topology and network dynamics towards identifying diseases and developing medical drugs. Biological ...
. Recent examples of application of network theory in biology include applications to understanding the
cell cycle
The cell cycle, or cell-division cycle, is the series of events that take place in a cell that cause it to divide into two daughter cells. These events include the duplication of its DNA (DNA replication) and some of its organelles, and sub ...
as well as a quantitative framework for developmental processes.
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 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. This automates the approach introduced by Quantitative Narrative Analysis, whereby subject-verb-object triplets are identified with pairs of actors linked by an action, or pairs formed by actor-object.
Link analysis
Link analysis is a subset of network analysis, exploring associations between objects. An example may be examining the addresses of suspects and victims, the telephone numbers they have dialed, and financial transactions that they have partaken in during a given timeframe, and the familial relationships between these subjects as a part of police investigation. Link analysis here provides the crucial relationships and associations between very many objects of different types that are not apparent from isolated pieces of information. Computer-assisted or fully automatic computer-based link analysis is increasingly employed by
bank
A bank is a financial institution that accepts Deposit account, deposits from the public and creates a demand deposit while simultaneously making loans. Lending activities can be directly performed by the bank or indirectly through capital m ...
s and
insurance
Insurance is a means of protection from financial loss in which, in exchange for a fee, a party agrees to compensate another party in the event of a certain loss, damage, or injury. It is a form of risk management, primarily used to hedge ...
agencies in
fraud detection, by telecommunication operators in telecommunication network analysis, by medical sector in
epidemiology
Epidemiology is the study and analysis of the distribution (who, when, and where), patterns and determinants of health and disease conditions in a defined population.
It is a cornerstone of public health, and shapes policy decisions and evi ...
and
pharmacology, in law enforcement
investigations, by
search engines for
relevance
Relevance is the concept of one topic being connected to another topic in a way that makes it useful to consider the second topic when considering the first. The concept of relevance is studied in many different fields, including cognitive sc ...
rating (and conversely by the
spammers for
spamdexing and by business owners for
search engine optimization
Search engine optimization (SEO) is the process of improving the quality and quantity of website traffic to a website or a web page from search engines. SEO targets unpaid traffic (known as "natural" or "organic" results) rather than dire ...
), 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.
Web link analysis
Several
Web search ranking
A ranking is a relationship between a set of items such that, for any two items, the first is either "ranked higher than", "ranked lower than" or "ranked equal to" the second.
In mathematics, this is known as a weak order or total preorder of o ...
algorithms use link-based centrality metrics, including
Google
Google LLC () is an American Multinational corporation, multinational technology company focusing on Search Engine, search engine technology, online advertising, cloud computing, software, computer software, quantum computing, e-commerce, ar ...
'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.
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
Sociology is a social science that focuses on society, human social behavior, patterns of social relationships, social interaction, and aspects of culture associated with everyday life. It uses various methods of empirical investigation an ...
. For example,
eigenvector centrality uses the
eigenvectors of the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
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
In graph theory, betweenness centrality (or "betweeness centrality") is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices suc ...
,
eigenvector centrality,
subgraph centrality, and
Katz centrality
In graph theory, the Katz centrality of a node is a measure of centrality in a network. It was introduced by Leo Katz in 1953 and is used to measure the relative degree of influence of an actor (or node) within a social network. Unlike typical ce ...
. 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 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.
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.
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.
Spread
Content in a
complex network can spread via two major methods: conserved spread and non-conserved spread.
[Newman, M., Barabási, A.-L., Watts, D.J. ds.(2006) The Structure and Dynamics of Networks. Princeton, N.J.: 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
An infection is the invasion of tissues by pathogens, their multiplication, and the reaction of host tissues to the infectious agent and the toxins they produce. An infectious disease, also known as a transmissible disease or communicable di ...
, 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
since for this case
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
*
Complex network
*
Congestion game
*
Quantum complex network
*
Dual-phase evolution
*
Network partition
A network partition is a division of a computer network into relatively independent subnets, either by design, to optimize them separately, or due to the failure of network devices. Distributed software must be designed to be partition-tolerant, t ...
*
Network science
*
Network theory in risk assessment
*
Network topology
*
Network analyzer
*
Seven Bridges of Königsberg
*
Small-world networks
*
Social network
A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods fo ...
*
Scale-free networks
A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction ''P''(''k'') of nodes in the network having ''k'' connections to other nodes goes for large values of ''k'' as
:
P(k ...
*
Network dynamics
Network dynamics is a research field for the study of networks whose status changes in time. The dynamics may refer to the structure of connections of the units of a network, to the collective internal state of the network, or both. The networked ...
*
Sequential dynamical system
Sequential dynamical systems (SDSs) are a class of graph dynamical systems. They are discrete dynamical systems which generalize many aspects of for example classical cellular automata, and they provide a framework for studying asynchronous proces ...
s
*
Pathfinder network
A pathfinder network is a psychometric scaling method based on graph theory and used in the study of expertise, knowledge acquisition, knowledge engineering, scientific citation patterns, information retrieval, and data visualization. Pathfinder ...
s
*
Human disease network
*
Biological network
*
Network medicine
Network medicine is the application of network science towards identifying, preventing, and treating diseases. This field focuses on using network topology and network dynamics towards identifying diseases and developing medical drugs. Biological ...
*
Graph partition
References
Books
*S.N. Dorogovtsev and J.F.F. Mendes, ''Evolution of Networks: from biological networks to the Internet and WWW'', Oxford University Press, 2003,
*G. Caldarelli, "Scale-Free Networks", Oxford University Press, 2007,
*A. Barrat, M. Barthelemy, A. Vespignani, "Dynamical Processes on Complex Networks", Cambridge University Press, 2008,
*E. Estrada, "The Structure of Complex Networks: Theory and Applications", Oxford University Press, 2011,
*K. Soramaki and S. Cook, "Network Theory and Financial Risk", Risk Books, 2016
*V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Cambridge University Press, 2017,
External links
{{wikiquote
netwikiScientific wiki dedicated to network theory
New Network TheoryInternational Conference on 'New Network Theory'
Network Workbench A Large-Scale Network Analysis, Modeling and Visualization Toolkit
Optimization of the Large Network doi:10.13140/RG.2.2.20183.06565/6Network analysis of computer networksNetwork analysis of organizational networksNetwork analysis of terrorist networksNetwork analysis of a disease outbreakLink Analysis: An Information Science Approach(book)
Connected: The Power of Six Degrees(documentary)
A short course on complex networksA course on complex network analysis by Albert-László BarabásiThe Journal of Network Theory in FinanceNetwork theory in Operations Researchfrom the Institute for Operations Research and the Management Sciences (INFORMS)
Networks
Graph theory
fi:Verkkoteoria