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.

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.

This paper addresses the problem of job scheduling in volunteer computing (VC) systems where each computation job is replicated and allocated to multiple participants (workers) to remove incorrect results by a voting mechanism. In the job scheduling of VC, the number of workers to complete a job is an important factor for the system performance; however, it cannot be fixed because some of the workers may secede in real VC. This is the problem that existing methods have not considered in the job scheduling. We propose a dynamic job scheduling method which considers the expected probability of completion (EPC) for each job based on the probability of worker's secession. The key idea of the proposed method is to allocate jobs so that EPC is always greater than a specified value (SPC). By setting SPC as a reasonable value, the proposed method enables to complete jobs without excess allocation, which leads to the higher performance of VC systems. We assume in this paper that worker's secession probability follows Weibull-distribution which is known to reflect more practical situation. We derive parameters for the distribution using actual trace data and compare the performance of the proposed and the previous method under the Weibull-distribution model, as well as the previous constant probability model. Simulation results show that the performance of the proposed method is up to 5 times higher than that of the existing method especially when the time for completing jobs is restricted, while keeping the error rate lower than a required value.

Differential games are considered an extension of optimal control problems, which are used to formulate centralized control problems in smart grids. Optimal control theory is used to study systems consisting of one agent with one objective, whereas differential games are used to formulate systems consisting of multiple agents with multiple objectives. Therefore, a differential-game-theoretic approach is appropriate for formulating decentralized demand-side energy management systems where there are multiple decision-making entities interacting with each other. Moreover, in many smart grid applications, we need to obtain information for control via communication systems. To formulate the influence of communication availability, differential game theory is also promising because the availability of communication is considered as part of an information structure (i.e., feedback or open-loop) in differential games. The feedback information structure is adopted when information for control can be obtained, whereas the open-loop information structure is applied when the information cannot be obtained because of communication failure. This paper proposes a comprehensive framework for evaluating the performance of demand-side actors in a demand-side management system using each control scheme according to both communication availability and sampling frequency. Numerical analysis shows that the proposed comprehensive framework allows for an analysis of trade-off for decentralized and centralized control schemes.

A queue layout of a graph G consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The queuenumber qn(G) is the minimum number of queues required in a queue layout of G. The Cartesian product of two graphs G1 = (V1,E1) and G2 = (V2,E2), denoted by G1 × G2, is the graph with {:v1 ∈ V1 and v2 ∈ V2} as its vertex set and an edge (,) belongs to G1×G2 if and only if either (u1,v1) ∈ E1 and u2 = v2 or (u2,v2) ∈ E2 and u1 = v1. Let Tk1,k2,...,kn denote the n-dimensional toroidal grid defined by the Cartesian product of n cycles with varied lengths, i.e., Tk1,k2,...,kn = Ck1 × Ck2 × … × Ckn, where Cki is a cycle of length ki ≥ 3. If k1 = k2 = … = kn = k, the graph is also called the k-ary n-cube and is denoted by Qnk. In this paper, we deal with queue layouts of toroidal grids and show the following bound: qn(Tk1,k2,...,kn) ≤ 2n-2 if n ≥ 2 and ki ≥ 3 for all i = 1,2,...,n. In particular, for n = 2 and k1,k2 ≥ 3, we acquire qn(Tk1,k2) = 2. Recently, Pai et al. (Inform. Process. Lett. 110 (2009) pp.50-56) showed that qn(Qnk) ≤ 2n-1 if n ≥1 and k ≥9. Thus, our result improves the bound of qn(Qnk) when n ≥2 and k ≥9.

Genetic algorithms are a general problem-solving technique that has been widely used in computational biology. In this paper, we present a framework to map hierarchical parallel genetic algorithms for protein folding problems onto computational grids. By using this framework, the two level communication parts of hierarchical parallel genetic algorithms are separated. Thus both parts of the algorithm can evolve independently. This permits users to experiment with alternative communication models on different levels conveniently. The underlying programming techniques are based on generic programming, a programming technique suited for the generic representation of abstract concepts. This allows the framework to be built in a generic way at application level and thus provides good extensibility and flexibility. Experiments show that it can lead to significant runtime savings on PC clusters and computational grids.

This paper presents a prototype of a distributed 3D rendering system in a hierarchical Grid environment. 3D rendering with massive data sets is a computationally intensive task. In order to make full use of computational resources on Grids, a hierarchical system architecture is designed to run over multiple clusters. This architecture involves both sort-first and sort-last parallel rendering algorithms to achieve excellent scalability, rendering performance and load balance.

In this paper, we investigate how to initialise cellular automata implemented in the hyperbolic plane. We generalise a technique which was indicated in to the case of any rectangular regular grid of the hyperbolic plane. This allows us to construct the initial configuration of any cellular automaton belonging to a rather large class of problems.

Improvement of the absorbing boundary conditions for triangle-hexagonal dual cell grids in the time domain method is described in this paper. The magnetic field components, which are evaluated by the electric fields at the circumcenters of the triangle cells, are conformed to Berenger's perfectly matched layer absorbing boundary conditions. The electric field is linearly interpolated by the fields at the vertices. The lower reflection coefficients in the frequency range for the equilateral and non-equilateral triangle cells are demonstrated.

It has been known that an N-vertex binary tree can be embedded into the path and grid with dilation O(N/logN) and O((N/logN)), respectively. This paper shows that an N-vertex binary tree with proper pathwidth at most k can be embedded into the path grid with dilation O(N/N1/k) and O((N/N1/2k)), respectively.