For the sociological theory, see Social network

Social network

A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...

Network theory is an area of computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 and network science

Network science

Network science is a new and emerging scientific discipline that examines the interconnections among diverse physical or engineered networks, information networks, biological networks, cognitive and semantic networks, and social networks. This field of science seeks to discover common principles,...

 and part of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

. It has application in many disciplines including statistical physics, particle physics

Particle physics

Particle physics is a branch of physics that studies the existence and interactions of particles that are the constituents of what is usually referred to as matter or radiation. In current understanding, particles are excitations of quantum fields and interact following their dynamics...

, computer science, biology

Biology

Biology is a natural science concerned with the study of life and living organisms, including their structure, function, growth, origin, evolution, distribution, and taxonomy. Biology is a vast subject containing many subdivisions, topics, and disciplines...

, economics

Economics

Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...

, operations research

Operations research

Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...

, and sociology

Sociology

Sociology is the study of society. It is a social science—a term with which it is sometimes synonymous—which uses various methods of empirical investigation and critical analysis to develop a body of knowledge about human social activity...

. Network theory concerns itself with the study of graphs

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 as a representation of either symmetric relation

Symmetric relation

In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...

s or, more generally, of asymmetric relations

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

 between discrete objects. Applications of network theory include logistical

Logistics

Logistics is the management of the flow of goods between the point of origin and the point of destination in order to meet the requirements of customers or corporations. Logistics involves the integration of information, transportation, inventory, warehousing, material handling, and packaging, and...

 networks, the World Wide Web

World Wide Web

The World Wide Web is a system of interlinked hypertext documents accessed via the Internet...

, Internet, gene regulatory network

Gene regulatory network

A gene regulatory network or genetic regulatory network is a collection of DNA segments in a cell whichinteract with each other indirectly and with other substances in the cell, thereby governing the rates at which genes in the network are transcribed into mRNA.In general, each mRNA molecule goes...

s, metabolic networks, social networks, epistemological networks, etc. See list of network theory topics for more examples.

Network optimization

Network problems that involve finding an optimal way of doing something are studied under the name of combinatorial optimization

Combinatorial optimization

In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...

. Examples include network flow

Flow network

In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...

, shortest path problem

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...

, transport problem, transshipment problem, location problem, matching problem, assignment problem

Assignment problem

The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics...

, packing problem

Packing problem

Packing problems are a class of optimization problems in mathematics which involve attempting to pack objects together , as densely as possible. Many of these problems can be related to real life packaging, storage and transportation issues...

, routing problem

Routing

Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...

, Critical Path Analysis and PERT (Program Evaluation & Review Technique).

Social network analysis

Social network

Social network

A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...

 analysis examines the structure of relationships between social entities. These entities are often persons, but may also be groups

Group (sociology)

In the social sciences a social group can be defined as two or more humans who interact with one another, share similar characteristics and collectively have a sense of unity...

, organizations, nation states, web sites, scholarly publications

Scientometrics

Scientometrics is the science of measuring and analysing science. In practice, scientometrics is often done using bibliometrics which is a measurement of the impact of publications. Modern scientometrics is mostly based on the work of Derek J. de Solla Price and Eugene Garfield...

.

Since the 1970s, the empirical study of networks has played a central role in social science, and many of the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 and statistical

Statistics

Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....

 tools used for studying networks have been first developed in sociology

Sociology

Sociology is the study of society. It is a social science—a term with which it is sometimes synonymous—which uses various methods of empirical investigation and critical analysis to develop a body of knowledge about human social activity...

. Amongst many other applications, social network analysis has been used to understand the diffusion of innovations

Diffusion of innovations

Diffusion of Innovations is a theory that seeks to explain how, why, and at what rate new ideas and technology spread through cultures. Everett Rogers, a professor of rural sociology, popularized the theory in his 1962 book Diffusion of Innovations...

, news and rumors. Similarly, it has been used to examine the spread of both diseases

Epidemiology

Epidemiology is the study of health-event, health-characteristic, or health-determinant patterns in a population. It is the cornerstone method of public health research, and helps inform policy decisions and evidence-based medicine by identifying risk factors for disease and targets for preventive...

 and health-related behaviors

Medical sociology

Medical sociology is the sociological analysis of medical organizations and institutions; the production of knowledges and selection of methods, the actions and interactions of healthcare professionals, and the social or cultural effects of medical practice...

. It has also been applied to the study of markets

Economic sociology

Economic sociology studies both the social effects and the social causes of various economic phenomena. The field can be broadly divided into a classical period and a contemporary one. The classical period was concerned particularly with modernity and its constituent aspects...

, where it has been used to examine the role of trust in exchange relationships and of social mechanisms in setting prices. Similarly, it has been used to study recruitment into political movement

Political movement

A political movement is a social movement in the area of politics. A political movement may be organized around a single issue or set of issues, or around a set of shared concerns of a social group...

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

Traffic analysis

Traffic analysis is the process of intercepting and examining messages in order to deduce information from patterns in communication. It can be performed even when the messages are encrypted and cannot be decrypted. In general, the greater the number of messages observed, or even intercepted and...

) has gained a significant use in military intelligence, for uncovering insurgent networks of both hierarchical and leaderless

Leaderless resistance

Leaderless resistance, or phantom cell structure, is a political resistance strategy in which small, independent groups , including individuals , challenge an established adversary such as a government. Leaderless resistance can encompass anything from non-violent disruption and civil disobedience...

 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 content are closely related to social network analysis, but often focusing on local patterns in the network. For example network motif

Network motif

Network motifs are connectivity-patterns that occur much more often than they do in random networks. Most networks studied in biology, ecology and other fields have been found to show a small set of network motifs; surprisingly, in most cases the networks seem to be largely composed of these...

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.

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

Bank

A bank is a financial institution that serves as a financial intermediary. The term "bank" may refer to one of several related types of entities:...

s and insurance

Insurance

In law and economics, insurance is a form of risk management primarily used to hedge against the risk of a contingent, uncertain loss. Insurance is defined as the equitable transfer of the risk of a loss, from one entity to another, in exchange for payment. An insurer is a company selling the...

 agencies in fraud

Fraud

In criminal law, a fraud is an intentional deception made for personal gain or to damage another individual; the related adjective is fraudulent. The specific legal definition varies by legal jurisdiction. Fraud is a crime, and also a civil law violation...

 detection, by telecommunication operators in telecommunication network analysis, by medical sector in epidemiology

Epidemiology

Epidemiology is the study of health-event, health-characteristic, or health-determinant patterns in a population. It is the cornerstone method of public health research, and helps inform policy decisions and evidence-based medicine by identifying risk factors for disease and targets for preventive...

 and pharmacology

Pharmacology

Pharmacology is the branch of medicine and biology concerned with the study of drug action. More specifically, it is the study of the interactions that occur between a living organism and chemicals that affect normal or abnormal biochemical function...

, in law enforcement investigation

Criminal procedure

Criminal procedure refers to the legal process for adjudicating claims that someone has violated criminal law.-Basic rights:Currently, in many countries with a democratic system and the rule of law, criminal procedure puts the burden of proof on the prosecution – that is, it is up to the...

s, by search engine

Search engine

A search engine is an information retrieval system designed to help find information stored on a computer system. The search results are usually presented in a list and are commonly called hits. Search engines help to minimize the time required to find information and the amount of information...

s for relevance

Relevance

-Introduction:The concept of relevance is studied in many different fields, including cognitive sciences, logic and library and information science. Most fundamentally, however, it is studied in epistemology...

 rating (and conversely by the spammers for spamdexing

Spamdexing

In computing, spamdexing is the deliberate manipulation of search engine indexes...

 and by business owners for search engine optimization

Search engine optimization

Search engine optimization is the process of improving the visibility of a website or a web page in search engines via the "natural" or un-paid search results...

), and everywhere else where relationships between many objects have to be analyzed.

Network robustness

The structural robustness of networks is studied using percolation theory

Percolation theory

In mathematics, percolation theory describes the behavior of connected clusters in a random graph. The applications of percolation theory to materials science and other domains are discussed in the article percolation.-Introduction:...

. When a critical fraction of nodes is removed the network becomes fragmented into small clusters. This phenomenon is called percolation and it represents an order-disorder type of phase transition

Phase transition

A phase transition is the transformation of a thermodynamic system from one phase or state of matter to another.A phase of a thermodynamic system and the states of matter have uniform physical properties....

 with critical exponents.

Web link analysis

Several Web search ranking

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....

 algorithms use link-based centrality metrics, including (in order of appearance) Marchiori

Massimo Marchiori

Massimo Marchiori is an Italian computer scientist who made major contributions to the development of the World Wide Web.-Biography:...

's Hyper Search

Hyper Search

Hyper Search has been the first published technique to introduce link analysis for search engines, opening the way for the second-generation of search engines...

, Google

Google

Google Inc. is an American multinational public corporation invested in Internet search, cloud computing, and advertising technologies. Google hosts and develops a number of Internet-based services and products, and generates profit primarily from advertising through its AdWords program...

's PageRank

PageRank

PageRank is a link analysis algorithm, named after Larry Page and used by the Google Internet search engine, that assigns a numerical weighting to each element of a hyperlinked set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set...

, Kleinberg's HITS algorithm

HITS algorithm

Hyperlink-Induced Topic Search is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. It was a precursor to PageRank...

, the CheiRank

CheiRank

The CheiRank is an eigenvector with a maximal real eigenvalue of the Google matrix G^* constructed for a directed network with the inverted directions of links. It is similar to the PageRank vector, which ranks the network nodes in average proportionally to a number of incoming links being the...

 and TrustRank

TrustRank

TrustRank is a link analysis technique described in a paper by Stanford University and Yahoo! researchers for semi-automatically separating useful webpages from spam.Many Web spam pages are created only with the intention of misleading search engines...

 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.

Centrality measures

Information about the relative importance of nodes and edges in a graph can be obtained through centrality

Centrality

Within graph theory and network analysis, there are various measures of the centrality of a vertex within a graph that determine the relative importance of a vertex within the graph...

 measures, widely used in disciplines like sociology

Sociology

Sociology is the study of society. It is a social science—a term with which it is sometimes synonymous—which uses various methods of empirical investigation and critical analysis to develop a body of knowledge about human social activity...

. For example, eigenvector centrality uses the eigenvectors of the adjacency matrix

Adjacency matrix

In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...

 to determine nodes that tend to be frequently visited.

Spread of content in networks

Content in a complex network

Complex network

In the context of network theory, a complex network is a graph with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in real graphs...

 can spread via two major methods: conserved spread and non-conserved spread. 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.

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.

Implementations

• Graph-tool
  Graph-tool
  graph-tool is an efficient Python module for manipulation and statistical analysis of graphs . Contrary to most other python modules with similar functionality, the core data structures and algorithms of graph-tool are implemented in C++, making extensive use of metaprogramming, based heavily on...
  
   and NetworkX
  NetworkX
  NetworkX is a Python library for studying graphs and networks. NetworkX is free software released under the BSD-new license.- Features :* Classes for graphs and digraphs.* Conversion of graphs to and from several formats....
  
  , free
  Free software
  Free software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
  
   and efficient Python modules for manipulation and statistical analysis of networks. http://graph-tool.skewed.de/ http://networkx.lanl.gov/
• Orange
  Orange (software)
  Orange is a component-based data mining and machine learning software suite, featuring friendly yet powerful and flexible visual programming front-end for explorative data analysis and visualization, and Python bindings and libraries for scripting...
  
  , a free data mining software suite, module orngNetwork
• Pajek, program for (large) network analysis and visualization.
• Tulip
  Tulip (software)
  Tulip is an information visualization framework dedicated to the analysis and visualization of relational data. Tulip aims to provide the developer with a complete library, supporting the design of interactive information visualization applications for relational data that can be tailored to the...
  
  , a free data mining and visualization software dedicated to the analysis and visualization of relational data. http://tulip.labri.fr/

See also

• Complex network
  Complex network
  In the context of network theory, a complex network is a graph with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in real graphs...
  
  
• Constructal law
• Percolation
  Percolation
  In physics, chemistry and materials science, percolation concerns the movement and filtering of fluids through porous materials...
  
  
• Network science
  Network science
  Network science is a new and emerging scientific discipline that examines the interconnections among diverse physical or engineered networks, information networks, biological networks, cognitive and semantic networks, and social networks. This field of science seeks to discover common principles,...
  
  
• Network Theory in Risk Assessment
  Network Theory in Risk Assessment
  A network is an abstract structure capturing only the basics of connection patterns and little else. Because it is a generalized pattern, tools developed for analyzing, modeling and understanding networks can theoretically be implemented across disciplines...
  
  
• Network topology
  Network topology
  Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
  
  
• Network analyzer
  Network analyzer
  Network analyzer may mean:* Packet analyzer, used on a computer data network* Network analyzer , a type of electronic test equipment...
  
  
• Small-world networks
• Social circles
  Social-circles network model
  The generative model of feedback networks , studied by White, Kejžar, Tsallis, Farmer, or social-circles network model, defines a class of random graphs generated by simple processes that are common to edge formation and feedback loops in social circles...
  
  
• Scale-free networks
• Sequential dynamical system
  Sequential dynamical system
  Sequential dynamical systems 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 processes over graphs...
  
  s

External links

• netwiki Scientific wiki dedicated to network theory
• New Network Theory International Conference on 'New Network Theory'
• Network Workbench: A Large-Scale Network Analysis, Modeling and Visualization Toolkit
• 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)
• Influential Spreaders in Networks, M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, H.A. Makse, Nature Physics 6, 888 (2010)
• A short course on complex networks