When a disaster hits a network, network service disruptions can occur even if the network facilities have survived and battery and power generators are provided. This is because in the event of a disaster, the power supply will not be restarted within the lifetime of the battery or oil transportation will not be restarted before running out of oil and power will be running out. Therefore, taking a power grid into account is important. This paper proposes a polynomial-time algorithm to identify the critical location C*D of a communications network Nc when a disaster hits. Electrical power grid Np supplies power to the nodes of Nc, and a link in Nc is disconnected when a node or a link in Nc or Np fails. Here, the disaster area is modeled as co-centric disks and the failure probability is higher in the inner disk than the outer one. The location of the center of the disaster with the greatest expected number of disconnected links in Nc is taken as the critical location C*D.

Considering that the traditional local-world evolving network model cannot fully reflect the characteristics of real-world power grids, this Letter proposes a new evolving model based on geographical location clusters. The proposed model takes into account the geographical locations and degree values of nodes, and the growth process is in line with the characteristics of the power grid. Compared with the characteristics of real-world power grids, the results show that the proposed model can simulate the degree distribution of China's power grids when the number of nodes is small. When the number of nodes exceeds 800, our model can simulate the USA western power grid's degree distribution. And the average distances and clustering coefficients of the proposed model are close to that of the real world power grids. All these properties confirm the validity and rationality of our model.

The application of complex network theory to power grid analysis has been a hot topic in recent years, which mainly manifests itself in four aspects. The first aspect is to model power system networks. The second aspect is to reveal the topology of the grid itself. The third aspect is to reveal the inherent vulnerability and weakness of the power network itself and put forward the pertinent improvement measures to provide guidance for the construction of power grid. The last aspect is to analyze the mechanism of cascading failure and establish the cascading fault model of large power failure. In the past ten years, by using the complex network theory, many researchers have investigated the structural vulnerability of power grids from the point of view of topology. This letter studies the structural vulnerability of power grids according to the effect of selective node removal. We apply several kinds of node centralities including recently-presented second-order centrality (SOC) to guide the node removal attack. We test the effectiveness of all these centralities in guiding the node removal based on several IEEE power grids. Simulation results show that, compared with other node centralities, the SOC is relatively effective in guiding the node removal and can destroy the power grid with negative degree-degree correlation in less steps.

Many important problems in communication networks, transportation networks, and logistics networks are solved by the minimization of cost functions. In general, these can be complex optimization problems involving many variables. However, physicists noted that in a network, a node variable (such as the amount of resources of the nodes) is connected to a set of link variables (such as the flow connecting the node), and similarly each link variable is connected to a number of (usually two) node variables. This enables one to break the problem into local components, often arriving at distributive algorithms to solve the problems. Compared with centralized algorithms, distributed algorithms have the advantages of lower computational complexity, and lower communication overhead. Since they have a faster response to local changes of the environment, they are especially useful for networks with evolving conditions. This review will cover message-passing algorithms in applications such as resource allocation, transportation networks, facility location, traffic routing, and stability of power grids.

Changing attitudes toward energy security and energy conservation have led to the introduction of distributed power systems such as photovoltaic, gas-cogeneration, biomass, water, and wind power generators. The mass installation of distributed energy generators often causes instability in the voltage and frequency of the power grid. Moreover, the power quality of distributed power grids can become degraded when system faults or the activation of highly loaded machines cause rapid changes in power load. To avoid such problems and maintain an acceptable power quality, it is important to detect the source of these rapid changes. To address these issues, next-generation power grids that can detect the fault location have been proposed. Fault location demands accurate time synchronization. Conventional techniques use the Global Positioning System (GPS) and/or IEEE 1588v2 for time synchronization. However, both methods have drawbacks — GPS cannot be used in indoor situations, and the installation cost of IEEE 1588v2 devices is high. In this paper, a time synchronization technique using the broadcast function of an Ethernet Passive Optical Network (EPON) system is proposed. Experiments show that the proposed technique is low-cost and useful for smart grid applications that use time synchronization in EPON-based next-generation power grids.

The power grid defines one of the most important technological networks of our times and has been widely studied as a kind of complex network. It has been developed for more than one century and becomes an extremely huge and seemingly robust system. But it becomes extremely fragile as well because some unexpected minimal failures may lead to sudden and massive blackouts. Many works have been carried out to investigate the structural vulnerability of power grids from the topological point of view based on the complex network theory. This Letter focuses on the structural vulnerability of the power grid under the effect of selective node removal. We propose a new kind of node centrality called overall information centrality (OIC) to guide the node removal attack. We test the effectiveness of our centrality in guiding the node removal based on several IEEE power grids. Simulation results show that, compared with other node centralities such as degree centrality (DC), betweenness centrality (BC) and closeness centrality (CC), our OIC is more effective to guide the node removal and can destroy the power grid in less steps.

The controllability of complex networks has attracted increasing attention within various scientific fields. Many power grids are complex networks with some common topological characteristics such as small-world and scale-free features. This Letter investigate the controllability of some real power grids in comparison with classical complex network models with the same number of nodes. Several conclusions are drawn after detailed analyses using several real power grids together with Erdös-Rényi (ER) random networks, Wattz-Strogatz (WS) small-world networks, Barabási-Albert (BA) scale-free networks and configuration model (CM) networks. The main conclusion is that most driver nodes of power grids are hub-free nodes with low nodal degree values of 1 or 2. The controllability of power grids is determined by degree distribution and heterogeneity, and power grids are harder to control than WS networks and CM networks while easier than BA networks. Some power grids are relatively difficult to control because they require a far higher ratio of driver nodes than ER networks, while other power grids are easier to control for they require a driver node ratio less than or equal to ER random networks.

In this paper, a Stochastic Non-Homogeneous ARnoldi (SNHAR) method is proposed for the analysis of the on-chip power grid networks in the presence of process variations. In SNHAR method, the polynomial chaos based stochastic method is employed to handle the variations of power grids. Different from the existing StoEKS method which uses extended Krylov Subspace (EKS) method to compute the coefficients of the polynomial chaos, a computation-efficient and numerically stable Non-Homogeneous ARnoldi (NHAR) method is employed in SNHAR method to compute the coefficients of the polynomial chaos. Compared with EKS method, NHAR method has superior numerical stability and can achieve remarkably higher accuracy with even lower computational cost. As a result, SNHAR can capture the stochastic characteristics of the on-chip power grid networks with higher accuracy, but even lower computational cost than StoEKS.

In this paper, we present a novel analysis approach for large on-chip power grid circuit analysis. The new approach, called ETBR for extended truncated balanced realization, is based on model order reduction techniques to reduce the circuit matrices before the simulation. Different from the (improved) extended Krylov subspace methods EKS/IEKS, ETBR performs fast truncated balanced realization on response Gramian to reduce the original system. ETBR also avoids the adverse explicit moment representation of the input signals. Instead, it uses spectrum representation in frequency domain for input signals by fast Fourier transformation. The proposed method is very amenable for threading-based parallel computing, as the response Gramian is computed in a Monte-Carlo-like sampling style and each sampling can be computed in parallel. This contrasts with all the Krylov subspace based methods like the EKS method, where moments have to be computed in a sequential order. ETBR is also more flexible for different types of input sources and can better capture the high frequency contents than EKS, and this leads to more accurate results especially for fast changing input signals. Experimental results on a number of large networks (up to one million nodes) show that, given the same order of the reduced model, ETBR is indeed more accurate than the EKS method especially for input sources rich in high-frequency components. If parallel computing is explored, ETBR can be an order of magnitude faster than the EKS/IEKS method.

With the advent of the deep submicron age, circuit performance is strongly impacted by process variations and the influence on the circuit delay to the power-supply voltage increases more and more due to CMOS feature size shrinkage. Power grid optimization which considers the timing error risk caused by the variations and IR drop becomes very important for stable and hi-speed operation of system-on-chip. Conventionally, a lot of power grid optimization algorithms have been proposed, and most of them use IR drop as their object functions. However, the IR drop is an indirect metric and we suspect that it is vague metric for the real goal of LSI design. In this paper, first, we propose an approach which uses the "timing error risk caused by IR drop" as a direct objective function. Second, the critical path map is introduced to express the existence of critical paths distributed in the entire chip. The timing error risk is decreased by using the critical path map and the new objective function. Some experimental results show the effectiveness.