This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000766409 Reproduction Date:
In computer and network science, network theory is the study of graphs as a representation of either symmetric relations or, more generally, of asymmetric relations between discrete objects. Network theory is a part of graph theory.
It has applications in many disciplines including statistical physics, particle physics, computer science, electrical engineering, biology, economics, operations research, 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.^{[1]}
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).
examines the structure of relationships between social entities.^{[3]} These entities are often persons, but may also be 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 traffic analysis) has gained a significant use in military intelligence, for uncovering insurgent networks of both hierarchical and leaderless nature.
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 are patterns in the attributes of nodes and edges in the network that are over-represented given the network structure. The analysis of biological networks with respect to diseases has led to the development of the field of network medicine.^{[5]}
The automatic parsing of textual corpora has enabled the extraction of actors and their relational networks on a vast scale. The resulting 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.^{[7]} This automates the approach introduced by Quantitative Narrative Analysis,^{[8]} whereby subject-verb-object triplets are identified with pairs of actors linked by an action, or pairs formed by actor-object.^{[9]}
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.
The structural robustness of networks is studied using percolation theory.^{[10]} When a critical fraction of nodes (or links) is removed the network becomes fragmented into small disconnected clusters. This phenomenon is called percolation,^{[11]} and it represents an order-disorder type of phase transition with critical exponents.
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' web sites or blogs. Another use is for classifying pages according to their mention in other pages.^{[12]}
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^{[13]} of a node is the most relevant centrality measure.
These concepts were made because of the nature of hubs in a network. Hubs are nodes which have lots of links. If we see one link in the hub, there is no difference between the hubs, however, some differences are exited between those nodes; some hubs tend to link to the other nodes and other hubs avoid connecting to the other nodes. We say a hub is assortative when it tends to connect to the other hubs. A dissortative hub avoids connecting to other hubs. If some nodes have some connections with the expected random probabilities, the hubs are neutral. There are three methods to quantify degree correlations.
Content in a complex network can spread via two major methods: conserved spread and non-conserved spread.^{[14]} 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.
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.^{[15]}^{[16]}
Cryptography, Artificial intelligence, Software engineering, Science, Machine learning
Graph theory, Open source, Python (programming language), Sociology, Complex network
Statistics, September 11 attacks, Computer security, Search engine optimization, Artificial intelligence
Computer science, Mathematics, Topology, Combinatorics, Numerical analysis
Network theory, Applied mathematics, List of graph theory topics, Max flow min cut theorem, Menger's theorem
Network theory, Network analysis (electronics), Social network analysis, Network planning and design