Network theory

The electric power systems analysis 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.[1]

(2) weighted graphs that blend an abstract understanding of complex network theories and electric power systems properties.[2]

Visualization of social network analysis[6]

Social network analysis examines the structure of relationships between social entities.[7] 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.[8] 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. Similarly, it has been used to study recruitment into political movements 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) 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.[9] 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 analyse 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.[10] Recent examples of application of network theory in biology include applications to understanding the cell cycle[11] as well as a quantitative framework for developmental processes.[12] The interactions between physiological systems like brain, heart, eyes, etc. can be regarded as a physiological network.[13]

Narrative network of US Elections 2012[14]

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 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.[15] This automates the approach introduced by Quantitative Narrative Analysis,[16] whereby subject-verb-object triplets are identified with pairs of actors linked by an action, or pairs formed by actor-object.[14]

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.[17][18][19]

The structural robustness of networks is studied using percolation theory.[20] When a critical fraction of nodes (or links) is removed randomly (random failures), the network becomes fragmented into small disconnected clusters. This phenomenon is called percolation,[21] and it represents an order-disorder type of phase transition with critical exponents. Percolation theory can predict the size of the largest component (called giant component), the critical percolation threshold and the critical exponents. The failures discussed above are random, as usually assumed in percolation theory. However, when generalizing percolation also to non-random but targeted attacks, e.g., on highest degree nodes, the results, such as p${\displaystyle c}$, change significantly[22][23] .Recently, a new type of failures in networks has been developed, called localized attacks.[24] In this case one randomly chooses a node and remove its neighbors and next nearest neighbors until a fraction of 1-p nodes are removed. One such realistic example of random percolation is the use of percolation theory to predict the fragmentation of biological virus shells (capsids), with the percolation threshold of Hepatitis B Virus capsid predicted and detected experimentally: a molecular, randomly played game of Jenga on a rhombically tiled sphere. [25] [26]

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

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[28] of a node is the most relevant centrality measure. For a centrality measure based on k-core analysis see ref.[29]

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.

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.[30][31][32]

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 [23][22] since for this case ${\displaystyle pc}$ is relatively high and less nodes are needed to be immunized. However, in most realistic nodes the global structure is not available and the largest degree nodes are not known. For this case the method of acquaintance immunization has been developed.[36] In this case, which is very efficient one randomly chooses nodes but immunize their neighbors. Another and even more efficient method is based on graph parition method.[37]