INTRODUCTION
Nowadays power systems are interconnected for economic benefits, increased
reliability and operational advantages as reported by Senroy
et al. (2006). Deregulation and restructuring have presented new
challenges in power systems. Deregulation has defined new objective for power
system utilities. The utilities want to maximize their profit and are thus inclined
to operate the power system very close to its limits. Moreover, many other factors
such as weak connections; unexpected events; hidden failures in protection system;
human errors, etc., exist, which in case of a fault in a part of the interconnected
power system, may lead it towards instability or complete blackout (Kezunovic
et al., 2005; Vijay and Xiaoming, 2005).
Several instances of such blackout events such as the 1996 Western US events,
the 2004 Northeastern disturbance and the 2004 Italian blackout have bean reported
by Venkatasubramanian and Quintero (2005) and Andersson
et al. (2005). Power systems in developing countries are even more
unreliable and suffer from a large gap between demand and generation; inadequate
transmission capacity and large distances between load centers and generation
units. Thus, if any contingencies occur in these systems, they would have serious
consequences such as complete blackout (Ahmed et al.,
2003). Therefore, power systems must be more intelligent and flexible to
survive such serious events. One of the first measures to avoid such critical
events in interconnected power systems is rapid detection of contingencies followed
by corrective action such as load shedding to limit the extent of the consequences
and prevent islanding or a widespread blackout (Liu and Liu,
2006).
A power system might become unstable if there is any inefficiency in its protection,
monitoring and control. If this occurs the protection relays may act and trip
lines or generators. This might lead to a sequence of events as a result of
which the interconnected power system could involuntarily break up into two
or more islands, or even lead to total blackout. It may even be the case that
generators belonging to a coherent group fall into different islands in which
case the recovery of the islands would be more difficult. Controlled power system
islanding can decrease the effects of severe disturbances and may be considered
a special protection scheme used as the last defense to avoid the occurrence
of catastrophic blackouts. Islands formed by power system controlled islanding
schemes can be more stable than naturally formed islands following the occurrence
of contingencies. Controlled islanding can improve restoration of the power
system since it creates an equilibrium between load and generation (Archer
and Davies, 2002). It also helps coherent groups of generators be placed
in the same island (Kezunovic et al., 2005).
System islanding and load shedding concepts have a long history. For example,
one can cite the Manitoba Hydro case (Archer and Davies,
2002), the India case (Rajamani and Hambarde, 1999)
and the Tokyo case (Agematsu et al., 2001). Several
type of controlled islanding approaches have been presented in power systems
in India without which catastrophic events could have caused serious power system
blackouts (Rajamani and Hambarde, 1999). The controlled
islanding approach based on active and reactive power balancing control installed
in Tokyo prevented a blackout in the metropolitan area in Tokyo in 1999 after
an airplane ran into a 275 kV transmission tie line (Agematsu
et al., 2001).
The main aspects of power system islanding are reviewed by Liu
and Liu (2006) where islanding schemes are outlined according to graph partitioning
and generator grouping. Intentional power system islanding can be used to reduce
the amount of load shedding to close to the theoretical minimum. Controlled
islanding together with generation and/or load shedding can be used to prevent
blackouts in power systems (Liu and Liu, 2006).
Many methods have been proposed for this purpose such as analyzing stability
based on onemachineinfinitebus analysis using Prony function (Senroy
and Heydt, 2006a, b); minimum cut sets (Wang
and Vittal, 2004); graphtheoretic eigenvalue and eigenvector analysis called
the spectral approach (Li et al., 2005; Yang
et al., 2006). Slow coherency methods are often used for intentional
power system islanding (Dola and Chowdhury, 2006; You
et al., 2003). Yusof et al. (1993)
presented a network partitioning method to group generators and load buses into
several coherent areas. Their method uses the slow eigenbasis matrix that includes
load buses. Grouping the load buses with the reference machine can be done by
calculating the nearness of each row eigenvector to the reference row eigenvectors.
The grouping information is useful for network decoupling applications such
as intentional islanding.
In using Prony function based on onemachineinfinitebus, islands are determined
by slow coherency method. Prony function is used to determine when and where
islanding must be done. To analyze dynamic stability for any coherency generator
group, the generator group is considered as one machine and the rest of the
power system is considered as an infinite bus. Therefore, this method is not
suitable for large interconnected power systems. Another limitation of Prony
functions is that they are used for analyzing linear systems whereas power systems
in the face of disturbances are nonlinear systems. A selfhealing strategy has
been reported by You et al. (2003) to deal with
catastrophic events when power system vulnerability analysis indicates that
the system is approaching an extreme emergency state. In this approach, the
system is adaptively divided into smaller islands for quick restoration. Then
a load shedding scheme based on the rate of frequency decline is applied. Two
comprehensive approaches to deal with islanding based on the grouping information
and using minimal cutsets have been reported by Wang and
Vittal (2004) which rely on Breadth First Search (BFS) and Depth First Search
(DFS) techniques. They require a very long time to obtain the solution, particularly
if the size of the power system under study is large. These methods are slow,
whereas islanding must be done rapidly for it to be an effective countermeasure.
The latest approach for controlled islanding of power systems is based on the
spectral method reported by Li et al. (2005).
The methods mentioned so far are either based on search approach, slow coherency
grouping approach, or a combination of the two which are slow compared with
the spectral method. This method is later extended by Chan
et al. (1994) for kway partitioning problems. Kway partitioning
spectral method is applied to the intentional islanding of power systems by
Li et al. (2005). This is the fastest approach
proposed so far for large scale power systems.
Dhillon et al. (2005, 2007)
have presented a graph partitioning method based on a Multilevel Kernel kMeans
approach with a high speed performance in partitioning graphs. They have used
their method on largescale partitioning tasks such as image segmentation; social
network analysis and gene network analysis types of systems. Wang
et al. (2008) presented a searching algorithm for islanding using
a multilevel reduced graph partition algorithm. They only test their approach
on the IEEE 118 bus system and present no evidence that their approach is faster
than existing methods. In this study, an algorithm using Multilevel Kernel kMeans
approach is proposed for fast islanding of large power systems, several test
system are used to show the efficiency of the proposed approach and the results
are compared with the results of the best existing approach presented by Li
et al. (2005) using the spectral approach. The results show that
the proposed method is much faster than other methods which (Wang
et al., 2008) failed to show.
PARTITIONING GRAPH BASED ON SPECTRAL METHOD
Here, the background of the spectral method is presented first and then an example of its performance is presented on kway partitioning.
Background of the spectral method: Spectral method is an approach for
partioning graph. It is used in many areas such as VLSI, FPGA, multichip modules,
integrated circuits, macro cells (Hagen et al., 1992)
and reallife pattern recognition, gene network analysis, social network analysis
and image segmentation and power system (Dhillon et al.,
2007).
The spectral method uses eigenvalues for partitioning graphs as presented by
Hagen et al. (1992). The eigenvalues of the Laplacian
matrix Q are calculated for this purpose. Graphs may be partitioned into two
parts using the second smallest eigenvalues. Chan et al.
(1994) presented the kway partitioning approach based on the spectral method
and demonstrated that the smallest k eigenvalues can be used for partitioning
a graph into k partitions.
This could be easily proved by Eq. 1 as detailed by
Chan et al. (1994):
where, P = {P_{1}, P_{2}, …, P_{k}} is a set of k
partitions of the graph G, Π is the set of all kway partitions of the
graph G and E_{h} is the sum of the weights of the edges in G having
precisely one endpoint in P_{h}. This approach was used by Li
et al. (2005) for intentional power system islanding. An example
of partitioning graphs using this approach is presented below.
An example of the partitioning graph using spectral method: An example is presented here to demonstrate the application of the spectral method for partitioning a graph into 3 partitions, using the smallest 3 eigenvalues. The weighted graph of a 14 bus power system which has been changed for the purposes of illustrating this approach is shown in Fig. 1.
The Laplacian matrix for the above graph is as follows in Eq.
2:
where, e_{ij} is weight of the edge that connects the two vertices
v_{i} and v_{j} (note that e_{ii} = 0). Therefore, the
Laplacian matrix is as shown as follows:

Fig. 1: 
Graph with 14 vertices and 21 edges 

Fig. 2: 
Amount of the second and third eigenvectors with respect to
vertices 
The eigenvalues of Q are as follow:
Figure 2 shows the second and third eigenvectors of Q with
respect to the vertices. It also shows that this graph can divided to three
partitions, as follow:
• 
Partition 1: {1, 2, 3, 4, 5} 
• 
Partition 2: {6, 7, 8, 9} 
• 
Partition 3: {10, 11, 12, 13, 14} 
The spectral method is a useful approach. But along with increasing number
of the vertices of the graph. The time of partitioning also increases since
it depends on the eigenvectors calculation.
PARTITIONING GRAPH BASED ON MULTILEVEL KERNEL kMEANS METHODS
Spectral partitioning and Kernel kMeans are two seemingly different methods
for partitioning graphs. However, they are very similar mathematically. This
mathematical similarity can be used to design a fast kernelbased multilevel
graph partitioning algorithm that is better in terms of speed, memory storage
and quality (Dhillon et al., 2007; Filipponea
et al., 2008). In this study, it is proposed to apply the Multilevel
Kernel kMeans method to the intentional power system islanding problem. Since,
there is no need to calculate eigenvalues and eigenvectors in the Kernel kMeans
method, it is faster than the spectral method.
The basic principles of the Multilevel Kernel kMeans are presented based on
the study of Dhillon et al. (2007). Multilevel
Kernel kMeans algorithm partitions graphs in three phases. Figure
3 provides a graphical overview of the multilevel framework. Suppose G_{0}
= (v_{0}, ε_{0}, A_{0}) is an input graph that
must be partitioned. Multilevel Kernel kMeans algorithm can be divided into
three phases: aggregation, partitioning and retrieval as follows.
Aggregation: Suppose G_{0} is the graph that must be partitioned.
In aggregation phase G_{0} is converted to the graph G_{1} with
a smaller size; G_{1} is converted to G_{2}; … and finally
G_{m–1} is converted to G_{m} such that v_{0}>v_{1}>…>v_{m}.
To aggregate a graph from G_{i} to G_{i+1}, sets of nodes in
G_{i} are merged to single node in G_{i+1}. In merging several
nodes into a single node, the edge weights out of this node are the sum of the
edge weights out of the original nodes (Dhillon et al.,
2007).
Partitioning: The second phase is graph partitioning. Since, the dimension of the graph has been reduced in the previous phase, partitioning the graph can be done in the least time.
Retrieval: Retrieval phase is the last phase of Multilevel Kernel kMeans
method. The initial partitions in G_{i–1} (i1th level) are the
final partitions of G_{i} (ith level). Each node in the ith level splits
up into the nodes that had made it up in the level i1th of aggregation phase.
The partitions in any level i1th in the retrieval phase are refined by the
Kernel kMeans algorithm. The retrieval phase is completed after refining G_{0}.
Since in any level of the retrieval phase, a good initial partition exists,
the retrieval often quickly yields a very efficient partition (Dhillon
et al., 2007).
The principles of the Kernel kMeans are presented as follows:
Given a set of vertices v_{1},v_{2},…v_{n}, that
are placed into initial partitions p_{1},p_{2},…p_{k},
the Kernel kMeans algorithm intends to improve these partitions such that the
following objective function is minimized (Dhillon et
al., 2007):
where,
is the centroid of the p_{c} and ω_{i} is the weight of
v_{i}.
Objective function J can be rewritten as follow:

Fig. 3: 
Process of multilevel graph partitioning 
where, φ is a function to map data point to a higher dimensional feature
space and:
Thus, the nonlinear partitioning problem is converted into a linear partitioning
problem and the kMeans is applied in this feature space. Note that this linear
partitioning in the feature space is corresponding to a nonlinear partitioning
in the input space.
Therefore, one may write:
Indeed, the inner product φ(v_{i}) · φ(v_{j}) can
be written as a Kernel function k_{ij}. Thus one may write:
Multilevel algorithm uses Kernel kMeans for the retrieval steps. Depending
on the graph partitioning objective to be optimized and given the adjacency
matrix for the current level, the weights and the Kernel can be set up appropriately
at each step of the retrieval. At all levels, the initialization for Kernel
kMeans is taken to be the partitioning induced by the previous level.
PROPOSED ALGORITHM FOR INTENTIONAL ISLANDING OF POWER SYSTEM USING MULTILEVEL KERNEL KMEANS
Since, a very high gain in speed can be achieved using the Multilevel Kernel
kMeans method in graph partitioning, it is proposed to apply it to the intentional
islanding of power systems in modern energy management systems that require
realtime performance. To do so, the power system must first be abstracted into
a graph as follows to implement intentional islanding:
• 
Compute the power flow of the power system network 
• 
Convert the power system network into a graph G 
• 
Each bus of the power network is a vertex of the graph G 
• 
Each transmission line of the online power system diagram is an edge of
graph G 
• 
The weight of each edge of graph G is assigned according to the absolute
value of real power flow of the corresponding transmission line 
The created graph of the power system is considered as an input for Multilevel
Kernel kMeans approach. Figure 4a, b
shows the proposed algorithm for intentional islanding of power systems using
Multilevel Kernel kMeans adopted from an earlier method called Metis (Karypis
and Kumar, 1999).

Fig. 4a: 
The first part of the flowchart of finding the optimum form
of intentional islanding of the power system by Multilevel Kernel kMeans 

Fig. 4b: 
The second part (continuation) of the flowchart of finding
the optimum form of intentional islanding of the power system by Multilevel
Kernel kMeans 
CASE STUDY
The IEEE 118 bus system (Dola and Chawdhury, 2006), IEEE 300 bus system and the 2746 bus Polish power system are used for testing the proposed intentional islanding algorithm and comparing the results with the spectral method. The Multilevel Kernel kMeans algorithm is applied for intentional islanding of the IEEE 118 bus test system. The results of comparing the performance of intentional islanding algorithms by spectral method and Multilevel Kernel kMeans applied to the IEEE 118 bus, IEEE 300 bus and the 2746 bus Polish power systems are shown.
In the IEEE 118 bus system, IEEE 300 bus system and the 2746 bus polish power system, there are 118 buses and 186 lines, 300 buses and 417 lines and 2746 buses and 3714 lines, respectively.
Intentional islanding of the IEEE 118 bus test system by Multilevel Kernel
kMeans approach: The proposed intentional islanding approach is applied
to the IEEE 118 bus test system. In the IEEE 118 bus test system shown in Fig.
5 (Dola and Chowdhury, 2006), there are 118 buses
and 186 lines.
The system is operating in a normal state, where all the flows satisfy system operation constraints. The system has a total generation of 4374.86 MW and 795.68 M Var. It has a total load of 4242 MW and 1438 MVar.
Suppose there is a severe fault on the transmission line which is connected
between bus 64 and 65 as indicated in Fig. 4. Since, the
line between bus 64 and 65 supplies a large amount of the demand for buses 56,
57, 62, 66 and 67, its tripping would cause an overflow of lines 6266, 6267
and 6667. After the tripping, the proposed intentional islanding approach is
applied before the tripping of the overloaded transmission lines.
As a result, the proposed intentional islanding approach breaks up the power
system into two islands. The following is a list of the two areas:
Area one = {1 through 78, 81, 113 through 118} 
Area two = {79, 80, 82 through 112} 
Cut set = {8081, 7978, 8077 and 8277} 
The cut set provides the points of separation. Area one has 85 buses and 130
branches. Area two has 33 buses and 50 branches. The two areas are shown in
Fig. 6.
A comparison of the spectral method and this approach based on Multilevel Kernel kMeans method is shown in Table 1 based on computational time for normalized cut. Table 1 shows the computational time for islanding IEEE 118 bus power system, IEEE 300 bus power system and 2746 bus polish power system by spectral method vs. Multilevel Kernel kMeans approach.
The results presented in Table 1 show that although the computational
time increases as the system size increases, the computational time required
using the proposed Multilevel Kernel kMeans method is much less than the spectral
method. The spectral method is highly time consuming especially in large power
systems since islanding requires the calculation of eigenvalues. The fractional
reduction in computational time is very impressive since the proposed approach
does not require the calculation of eigenvalues. Of course, not all of this
indicates a gain in speed since the code used for the Multilevel Kernel kMeans
approach indirectly uses C^{++} and is somewhat faster than the code
that was written for the spectral approach in Matlab.

Fig. 6: 
Islanding the IEEE 118 bus test system into two areas 
Table 1: 
A comparison of computational time 

CONCLUSION
Intentional power system islanding is the last line of defense for avoiding power system blackout. For it to be affective, it must be done fast. The intentional islanding methods presented previously are slow and are therefore not proper for large scale interconnected power systems. In this study, a new algorithm for intentional islanding using Multilevel Kernel kMeans has been proposed and compared with the spectral method. It is shown that the new approach requires much less time compared with earlier methods. Moreover, this time saving is improved as the system size increases. Results of simulations are presented to demonstrate this method. The simulations reported in this study have been carried out on an IBM PC computer with a 2.8 GHz Celeron processor using Matlab for the spectral approach and existing code called Graclus Software, version 1.2 for the Multilevel Kernel kMeans approach.