Graph Theory Network

[Sourabh Doherty]

Networktopology is a graphical representation of electric circuits. It is useful for analyzing complex electric circuits by converting them into network graphs. Network topology is also called as Graph theory.

Network graph is simply called as graph. It consists of a set of nodes connected by branches. In graphs, a node is a common point of two or more branches. Sometimes, only a single branch may connect to the node. A branch is a line segment that connects two nodes.

Any electric circuit or network can be converted into its equivalent graph by replacing the passive elements and voltage sources with short circuits and the current sources with open circuits. That means, the line segments in the graph represent the branches corresponding to either passive elements or voltage sources of electric circuit.

If there exists at least one branch between any of the two nodes of a graph, then it is called as a connected graph. That means, each node in the connected graph will be having one or more branches that are connected to it. So, no node will present as isolated or separated.

If there exists at least one node in the graph that remains unconnected by even single branch, then it is called as an unconnected graph. So, there will be one or more isolated nodes in an unconnected graph.

If all the branches of a graph are represented with arrows, then that graph is called as a directed graph. These arrows indicate the direction of current flow in each branch. Hence, this graph is also called as oriented graph.

If the branches of a graph are not represented with arrows, then that graph is called as an undirected graph. Since, there are no directions of current flow, this graph is also called as an unoriented graph.

A part of the graph is called as a subgraph. We get subgraphs by removing some nodes and/or branches of a given graph. So, the number of branches and/or nodes of a subgraph will be less than that of the original graph. Hence, we can conclude that a subgraph is a subset of a graph.

This Tree has only three branches out of six branches of given graph. Because, if we consider even single branch of the remaining branches of the graph, then there will be a loop in the above connected subgraph. Then, the resultant connected subgraph will not be a Tree.

Co-Tree is a subgraph, which is formed with the branches that are removed while forming a Tree. Hence, it is called as Complement of a Tree. For every Tree, there will be a corresponding Co-Tree and its branches are called as links or chords. In general, the links are represented with dotted lines.

This Co-Tree has only three nodes instead of four nodes of the given graph, because Node 4 is isolated from the above Co-Tree. Therefore, the Co-Tree need not be a connected subgraph. This Co-Tree has three branches and they form a loop.

The number of branches that are present in a co-tree will be equal to the difference between the number of branches of a given graph and the number of twigs. Mathematically, it can be written as

In mathematics, computer science and network science, network theory is a part of graph theory. It defines networks as graphs where the vertices 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 statistical physics, particle physics, computer science, electrical engineering,[1][2] biology,[3] archaeology,[4] linguistics,[5][6][7] economics, finance, operations research, climatology, ecology, public health,[8][9][10] sociology,[11] psychology,[12] and neuroscience.[13][14][15] 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.

Network problems that involve finding an optimal way of doing something are studied as 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 program evaluation and review technique.

Social network analysis examines the structure of relationships between social entities.[17] 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.[18] Amongst many other applications, social network analysis has been used to understand the diffusion of innovations, news and rumors.[19] Similarly, it has been used to examine the spread of both diseases and health-related behaviors.[20] 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.[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]

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]

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

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]

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[36] of a node is the most relevant centrality measure.

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]

3a8082e126