{'fraction_non_alphanumeric': 0.03546710473164032, 'fraction_numerical': 0.009641020116877171, 'mean_word_length': 4.424981738495252, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Ecologically Sustainable Partitioning of a Metapopulations Network

A stable populations' network is hard to interrupt without any ecological consequences. A communication blockage between patches may have a negative impact on populations' stability or it may destabilize the populations in the ecological network. This paper deals with the construction of a safe way passing through the metapopulations habitat such that populations remain stable. To our best knowledge, this is a completely novel idea, which uses a combined approach of dynamical system stability analysis and graph partitioning algorithms. Our study finds that such safe construction is possible if algebraic connectivity of the graph components is stronger than the spatially local instabilities in respective components. Dynamical system stability analysis determines the threshold value for the stability, while a graph partitioning algorithm ensures the populations' stability in graph components after the partitioning. The dynamics of the populations on spatially discrete patches (graph nodes) and their spatial communication with other patches is described by a set of differential equations with the general kinetics. By reversing the Turing-instability definition, the stability conditions of the considered discrete diffusive system carried out and are noted to depend upon the local dynamics of the metapopulations and the network connectivity \emph{i.e.,} the Fielder value of the Laplacian matrix of the graph. In the paper, necessary and sufficient conditions on the removal of some graph edges are determined to establish the stability in the remaining graph network. The exhaustive procedure and an efficient heuristic bisection graph partitioning algorithm are proposed to get the desired partition. By the exhaustive procedure, all desired partitions can be obtained and the best possible partition around a given arbitrary partition is provided by the heuristic bisection partitioning algorithm.


INTRODUCTION
Distributions of the populations over a range of spatially discrete patches are the fundamental and inseparable aspect of their interactions in the ecological domain. Set of spatially isolated populations which are linked by dispersal of multiple potentially interacting species is called metapopulations [1,2]. Human activities, like, construction of roads (railway line) or fencing across the border affects the dispersal of species among their habitat patches. This interference may lead the metapopulations to extinction, even if some suitable habitat patches remain there. Construction of new infrastructure in between populations habitat reduces both the quantity and quality of wildlife habitat [3]. Large continuous habitats become highly fragmented and leaving small habitat patches dispersed throughout the landscape. Populations in such small, isolated habitats have a higher risk to become extinct, and simultaneously recolonization chance is reduced [4,5]. Thus inappropriate intervention either by man or nature on population habitats can severely affect the existence of species. In such scenario precautionary steps are needed to avoid the negative environmental impacts of spatial developments (such as the construction of roads) on the survival of species.
Theoretical studies have shown that metapopulations persistence depends upon an interaction between local density-dependence, dispersal, and spatial heterogeneity [6,7,8]. The work [9] examined the influences of dispersal (density-independent and density-dependent) in local dynamics considering the spatially heterogeneous environment and mortality during dispersal. The study found that with logistic dynamics, dispersal changes the strength of it within patches, while Allee dynamics creates between-patch effects. Role of space and diffusion in the dynamics, stability, and persistence of populations is studied by [10] and it has been shown that the larger the spatial domain or diffusion, the more unstable the dynamics. Connectivity or species dispersal movement is a controversial thing in long-term survival (stability) of the metapopulations. Dispersal of species in metapopulations network plays the role in both stabilizing and destabilizing metapopulations depends on dispersal intensity [11]. The mode of density-dependence dispersal is the key factor for viability of sources and long-term persistence of source-sink systems [12]. In [10,13] shown that increased dispersal can destabilize the previously stable systems, whereas study of [14,15,16], concluded that it (density-independent dispersal) does not affect the stability.
In this paper, we assumed that the whole spatially structured populations are stable only if there is dispersal movement among populations' habitats by individuals. One example of such species is butterfly Melitaea cinixa, their dispersal among patches affect the dynamics substantially and there are chances of the existence of alternative stable equilibrium points [17]. There are many research studies (a few mentioned above) that support this assumption. It is kind of the reverse of the Turing-instability condition, which is proposed by Turing in his seminal work [18]. Turing instability condition is the condition that equilibrium solution is (linearly) stable in the absence of diffusion, while unstable in the presence of diffusion.
We investigate the dynamics of 2n species spread over n spatial habitat patches by using general approach of modeling and explore the stability criteria. Populations assumed to be distributed in spatial habitat patches and populations' dispersal among these habitats is considered crucial factor for their stability in the network. In other words, populations are assumed unstable in every patch and stable only if there is dispersal movement of populations among habitat patches in a network. This paper provides an approach to find out the appropriate partition(s) i.e., human-made cut(s) of an ecological metapopulations network such that populations remain stable after the partition(s). A combination of qualitative theory of differential equations and graph-theory turned out to be a very useful in providing such desired partition(s).
Role of graph theory is not new in ecology; there are many applications of it in conservation biology and landscape ecology. A theoretical analysis of stability and persistence of ecological metapopulations especially focusing on a marine system has been done in [19]. The authors determined the conditions of the persistence of metapopulations (age-structured patch populations where patch subpopulations are connected by larval dispersal) by the graph-theoretic way and found that among various factor, migration of individuals between patches is a very critical factor for overall stability of the metapopulations. By using graph theory approach, in paper [20] it is shown that population can persist despite the substantial losses of habitat area, as long as there exists a minimum spanning tree.
Metapopulations constitute a complex network and spectra of the complex network (in particular, the second smallest eigenvalue of a Laplacian matrix) carry a lot of information about them. For example, the second smallest eigenvalue of the Laplacian associated with the connectivity of the graph (network), more it is more the connectivity of the graph. Master stability function (MSF) technique, to analyze the stability of the synchronized state of coupled oscillators depends upon the ratio of the largest to the secondsmallest eigenvalue of the Laplacian [21]. The second smallest eigenvalue of Laplacian emerged as a critical parameter in systems and control. Works [22,23] in networked dynamic system observed that it (second smallest eigenvalue) is a measure of stability and robustness. Laplacian spectrum of the graph of certain molecules can be used to predict chemical properties [24,25]. Our analysis too, shows the significant role played by the second-smallest Laplacian eigenvalue (also called Fiedler value) in metapopulations stability.
The problem of graph partitioning (a graph is to partition into smaller components) in science and engineering has much significant practical importance. One practical example is arranging the electronic components on printed circuit boards in such way that the number of connection between two boards is minimum [26]. This paper aims to propose two ways to graph partitioning, so that after partition stability of populations remains intact in smaller subnetworks. One is the exhaustive procedure that can give variety of desired partitions by determining all partitions of the graph. Another one is a heuristic bisection algorithm with a local convergence subjected to the Fiedler value of components. Unfortunately, graph partitioning is a NP-hard (a complexity class of decision problems that are intrinsically harder than those which can be solved in polynomial time) problem [27]. Graph partition or cut is thought of a transport road or railway line passing through metapopulations network which breaks the communications between subnetworks obtained after partition.
The outline of the paper is as follows; in the next section metapopulations' dynamics in a network is considered and stability conditions are explored and analyzed. Section 3 provides the graph partitioning exhaustive procedure with illustrative numerical examples. In section 4, an efficient heuristic graph bisection algorithm is presented and its implementation shown in Erdős-Rényi model generated random graph. Finally, the paper is concluded in the last section with a further possible exploration of the problem.

MODEL & LINEAR STABILITY ANALYSIS
A classic approach to metapopulations dynamics is patch occupancy models, where a fraction of occupied patches is considered and explicit local population dynamics is ignored [28]. Within-patch dynamics along with populations' dispersal among patches considered in numerous studies, a few of them are [29,30,31,32]. The regional persistence of predator-prey interactions has been considered in patch occupancy models [33,34] and also in models with explicit local dynamics [35].
We consider an ecological network of prey and predator populations, where both the populations occupy each spatial discrete patch of the network and diffusing over the corridors that link them. Each ecological populations patch represents a node in the graph G. Hence an ecological network of n patches is a graph with n nodes. At each node of the graph G, the dynamics of prey and predator populations governed by a set of two differential equations (for example, a Lotka-Volterra model equations). Dispersal movement of species among patches represents the links (edges) among nodes in the graph and amount of dispersal between patches is proportional to the difference of populations densities [29], and proportional constant (dispersal rate) is described by the weight on the corresponding edge. Thus the dynamics of predator-prey population in i-th habitat patch with passive migration from/to other patches of the populations is given by following set of 2n ordinary differential equations [6], where x i (t) and y i (t) are the prey and predator densities respectively, at time t in patch i. Real-valued functions f i ∈ C 1 ([0, ∞) 2 ) and g i ∈ C 1 ([0, ∞) 2 ) represent the dynamics of prey and predator species respectively within the i th patch, and they are assumed to be arbitrary non-negative continuous differentiable functions over feasible domain. Net diffusion rate for prey population between patch i and patch j assumed same in both the directions, i.e., d x ij = d x ji which means the representation of an ecological network will be an undirected weighted graph. Similarly, predator's net diffusion rate is assumed equal from patch i to patch j and patch j to patch i.
We assume populations are (locally) stable in the connected network, while there is no population stability (including oscillatory behavior) within an isolated habitat patch. For the instability at any individual graph node, any one of two below conditions must hold true at each point of (x i , y i )-state space except x i = 0 or y i = 0. Proof of this statement is straightforward, it is a just direct consequence of Dulac-Bendixson Criterion [36]. We shall drop the second condition soon to ensure diffusion induced stability in spatially structured populations.
In interest to determine the condition(s) for stable populations in a network, rewriting the system (2.1) in vector form as follows,Ẋ . . , f n ) ⊤ , G = (g 1 , g 2 , . . . , g n ) ⊤ , and L x and L y are Laplacian of the graph corresponds to prey and predator respectively. Here we are considering L x = L y = L, that is, both prey and predators are having same diffusion rate between patches that are connected. The Laplacian of the graph is defined as follows, The weight d i = i∼j w ij is the sum of the weights of edges incident on node i. By linearizing the system (2.2) around its nontrivial equilibrium solution and maintaining the same symbols, we get where Φ j ∈ R n is an eigenvector of the Laplacian matrix L of the graph G correspond to the eigenvalue λ j , i.e, LΦ j = λ j Φ j and ξ i (t), i = 1, 2 is the scalar valued function of time. Then the above system becomes .
For each eigenvalue λ j of the Laplacian L, let the eigenvalue of the coefficient matrix is denoted by σ jk , k = 1, 2, . . . 2n. These eigenvalues determine the temporal growth is given by the roots of the characteristic polynomial of the coefficient matrix A − λ j I, i.e., where J i is the jacobian of the reaction terms of the prey and predator populations in i-th patch calculated at the co-existential equilibrium point of the system (2.1), that is, Thus from (2.3), it is clear that we require following conditions hold true for stability of the system (2.1), In last result it is considered that 0 = λ 1 ≤ λ 2 ≤ · · · ≤ λ n is the spectrum of the Laplacian matrix L of the graph G. From these stability conditions, we conclude that in order to have stability in populations after partition of the graph network, Fiedler value (second smallest eigenvalue) of the Laplacian of each components must be greater than equal to threshold value (condition 2) and both the eigenvalues of the jacobian matrix of the reaction term must be complex number with positive real part as det J i ≥ 0, ∀ i (conditions 1), which implies that tr J i ≥ 0 to have populations instability in the patch. Also from condition 2, 0.5 tr J i = 0.5(sum of positive real part eigenvalues ofJ i ) ≤ λ 2 , it infers that local instability within a patch Lower Bound

|S|(n−|S|)
i and j are non-adjacent vertices Table 1: Various bounds for the second-smallest eigenvalue of Laplacian matrix of a graph G. must not be greater than the of algebraic connectivity i.e., λ 2 (L) of the graph. In ecological terms, sustainable separations of patches possible provided the populations' dynamics inside each patch and populations' dispersal movement among patches have some appropriate relations.
Conclusively, stability conditions for considered metapopulations system, depend upon dispersal movement of species (connectivity of the network) and local populations dynamics. Since dispersal movement of species in the network is assumed to be an important stability factor, our analysis shows that more it is, better the stability of the populations. Thus one should aim for higher Fiedler value components for the metapopulations persistence.
Let C 1 and C 2 are resulted partitions after a cut and let 1 2 τ, i = 1, 2, then this condition automatically ensures that the stability condition holds for both the components (metapopulations subnetwork). This infers that we do not require the model's parameters (such as growth and mortality rate of populations) except dispersal parameters to conclude about the populations stability in components.
There are many easily computable lower and upper bounds for the λ 2 (L(G)) in the existing literature [24,37,38]. Some of these bounds of λ 2 (L(G)) are listed in the Table 1, where δ(G) is minimum sum of weights of edges that incident on a node, S ⊆ V (G), E(S, S) is weight on edge cut, D is the diameter of the graph, d is the mean distance, and d i is sum of weights of edges that incident on node i. If τ is compared with those bounds (see below results; Theorem 1 and Theorem 2), then the bounds provide an easy way on an otherwise hard to check populations stability on a graph network. Also, there are some special graphs (with edges having weight one) whose second-smallest eigenvalues are known and given in Table 2.
Theorem 1. If τ is larger than the upper bounds λ 2 (L(C)), then the partitioned component C is unstable.
If τ is lower than the lower bounds λ 2 (L(C)), then the partitioned component C is stable. Proof. We know that L ii = d i = i∼j w ij is the sum of the weights of edges incident on node i. Thus That tells that the average weight of edges incident on any node must be greater than or equal to n−1 n τ .
From stability condition, it is clear that if the gap between Fiedler values of graph Laplacian L(G) and edge-cut induced graph component Laplacian L(C) is not more than the gap between the Fiedler value of L(G) and τ , then the graph component C will be stable (in the sense that populations will be stable in C). Though we have interlacing theorem that tells us the Laplacian eigenvalues after removal of an edge in a graph lies in between two consecutive Laplacian eigenvalues of the original graph. But, it is hard to say about the exact gap between these eigenvalues. As a special case, following theorem tell us that a graph structure can be stable after the removal of an edge subject to some condition on edge weight.
is an eigenvector of L(G) corresponds to eigenvalue λ = 0. Then the obtained subgraph G ′ by deleting the edge of weight w ij = λ that links i-th and j-th node of graph G (it is a rank-one perturbation in a Laplacian matrix of graph G), is stable provided Here ε i is unit vector in R n , whose i-th component is 1 and 0 everywhere else.
Proof. We know that change in labeling of nodes does not affect the properties of L, hence we relabel the node i and j as node 1 and 2 respectively. The Laplacian matrix of a subgraph G ′ that induced from a graph G by deleting an edge, is a symmetric rank-one updated Laplacian matrix of graph G. That can be written as follows, where vv T = (ε 1 − ε 2 )(ε 1 − ε 2 ) ⊤ is a symmetric rank-one perturbation matrix with entries a 11 = a 22 = 1, a 12 = a 21 = −1 and rest of the entries are zero. w 12 is the weight of the edge that connects nodes 1 and 2. From equation (2.4) it is easy to see that v is an eigenvector of L(G ′ ) and corresponding eigenvalue is λ − w 12 v T v. Thus λ is reduced by the amount w 12 v T v and from Theorem 2.1 [39], rest of the eigenvalues will remain same. Thus for stability of the subgraph G ′ , we need to have λ(L(G)) − w 12 v T v ≥ τ . Hence theorem established.
For stability, Theorem 4 provides an upper cap on the weight of an edge which to be removed from a graph when graph Laplacian matrix has a special form of eigenvectors. One example of graph whose Laplacian is having eigenvectors of the form ε i − ε j , 1 ≤ i ≤ n, i = j, is a complete graph with equal weight on its edges. Hence for purpose of populations stability in a complete graph, it is easy to see the whether an edge removal can be tolerated or not. Figure (1(a)), shows a complete graph K 4 with all edges having equal weight 1, whose only non-zero eigenvalue is 4 with multiplicity 3 and corresponding eigenvectors to it, are form of (0, −1, 0, 1) = ε 4 − ε 2 , (0, −1, 1, 0) = ε 3 − ε 2 , (1, −1, 0, 0) = ε 1 − ε 2 and their linear combinations. So, Theorem 4 says that we can delete any edge of the graph K 4 safely as long as τ ≤ 2.
Also note that in order to L(G) have eigenvector of the form ε i − ε j , entry a ii and a jj in L(G) must be equal. This information is helpful in deciding whether the matrix has eigenvector in desired form or not. If a ii = a jj for any pair (i, j), i = j, then matrix can not have the eigenvectors of the form ε i − ε j , and if a ii = a jj , then we check only i-th and j-th columns difference.
Theorem 4 can be generalized as follows by making use of Theorem 3.1 [40].
Theorem 5. (Sufficient Condition on r Edges Removal) Let G(V, E) is a connected and undirected graph with |V | = n(≥ 3), and let there are r edges e(i k , j k ), 1 ≤ k ≤ r that link nodes i k and j k , 1 ≤ k ≤ r respectively. Let {v k = ε i k − ε j k , i k = j k , 1 ≤ k ≤ r} is a list of eigenvectors of L(G) corresponds to eigenvalues λ k = 0, 1 ≤ k ≤ r respectively. Then the obtained subgraph G ′ by deleting the r edges e(i k , j k ), 1 ≤ k ≤ r of weights w i k j k = λ k has the Laplacian L(G ′ ) which is a rank-r perturbation in a Laplacian matrix of graph G i.e., L( In Theorem 5, if all of r edges are non-adjacent, then all the pairs of nodes (i k , j k ), 1 ≤ k ≤ r are distinct. That ensures us the list {v k , 1 ≤ k ≤ r} is a set of orthogonal eigenvectors of L as (ε k − ε k )(ε l − ε l ) T = 0. Then the list of eigenvalues of rank-r updated matrix i.e., L(G) − r k=1 w i k j k v k v ⊤ k becomes {λ 1 − 2w i 1 j 1 , λ 2 − 2w i 2 j 2 . . . λ r − 2w irjr , λ r+1 , . . . , λ n }. Thus stability of populations in graph G ′ simply requires min For particular cases, below two principles by Merris [41] can be helpful in deciding edge deletion from the graph safely. To apply these results, we consider an eigenvector corresponding to eigenvalue λ 2 and see its components according to mentioned in these results. Figure 1 Edge Principle: Let G be a graph, and x is an eigenvector of L(G) corresponding to eigenvalue λ such that x(u) = x(v) for some adjacent nodes u and v. Let G ′ be the graph obtained by removing the edge uv. Then x is an eigenvector of G ′ corresponding to eigenvalue λ.
Alternating Principle: Let G be a graph, and x is an eigenvector of L(G) corresponding to eigenvalue λ. Let the adjacent vertices i and j of G in such way that x(i) = −x(j)( = 0). Let G ′ be the graph obtained by deleting the edges between all such paired vertices i and j. Then x is an eigenvector of G ′ corresponding to eigenvalue λ − 2.

EXHAUSTIVE PROCEDURE FOR GRAPH PARTITIONING
In this section, we present a graph partitioning way that gives all possible stability condition satisfied graph components after a cut. Before that below given are some preliminaries [42] that required to introduce this procedure.
Definition 3.1. Cut-Set of a graph G is a set of edges whose removal from G leaves G disconnected, provided no proper subset of these edges disconnects (in the same way) the graph. Definition 3.2. Fundamental Cut-Set with respect to spanning tree T , is a cut-set containing exactly one branch of spanning tree T . Definition 3.3. Ring Sum of two graphs G 1 (V 1 , E 1 ) and G 2 (V 2 , E 2 ) is a graph consisting of the vertex set V 1 ∪ V 2 and edges that one either in G 1 or G 2 , but not in both.
Vector space associated with a graph: Let us consider the graph G with edges e 1 , e 2 , · · · , e n . Any subset g of these n edges can be represented by a n− tuple X = (x 1 , x 2 , · · · , x n ) such that x i = 1 if e i is in g and x i = 0 otherwise.
There is vector space W G over Galois field modulo 2 associated with every graph G, where vector addition is taken as ring sum of corresponding graphs, defined as X ⊕ Y = (x 1 + y 1 , x 2 + y 2 , . . . , x n + y n ) and scalar multiplication defined as c · X = (c · x 1 , c · x 2 , . . . c · x n ).

Result [d]:
The ring sum of any two cut-sets in a graph is a either a third cut-set or an edge-disjoint union of cut-sets.
With this terminology and preliminaries, we are now ready to discuss the exhaustive procedure for partitioning the graph appropriately. Below are steps to get the desired partition of the graph such that each obtained component has stable populations.
1. select a spanning tree T of the given connected graph G.
2. determine all n − 1 fundamental cut-sets with respect to spanning tree T .

generate remaining all cut-sets by applying Result [d], as Result [b]
says that the set of fundamental cut-sets is the basis of cut-subspace W S .
• STEP2: Reject all the cut-sets which give the isolated node as a component (as we want stable population in each component).
To decide whether a cut-set gives an isolated patch or not, we consider the vertices that are connected by an edge corresponds to the entry of first 1 in the cut-set vector. Let say, first 1 is at the i-th place in a cut-set vector, which corresponds to the edge e i . We know each edge connects two vertices in the graph. Let say, vertices v p and v q are connected by edge e i . If all edges that are incident on either v p or v q falls in the considered cut-set vector, which means one or both of two vertices is isolated by the cut-set vector, hence we drop that cut-set from the list. If not, then go to the next 1 entry in same cut-set vector and repeat the above procedure until concluded about the isolation of any patch from the remaining graph through this cut-set.
• STEP3: For remaining cut-sets, check whether second-smallest eigenvalue of Laplacian of each component follows stability conditions or not.
• STEP4: List all the cut-sets that give stable populations components.
In case if we treat the problem as to minimize (maximize) the cost of edge cutting, then we shall choose the cut-set which has minimum (maximum) weight among all cut-sets obtained in STEP4. This exhaustive procedure certainly having the complexity which increases with the number of nodes in the graph but determines all desired partitions. We now discuss an example of the implementation of this exhaustive procedure.
Example: Consider the graph G(5, 6) with weight on it's edges, shown in the Figure 2(a).
• STEP1: In order to determine all cut-sets, first we determine the basis elements of cut-subspace W s of W G , which is the set of fundamental cut-sets with respect to a spanning tree. There are four fundamental cut-sets of the given graph (shown in red dashed lines in Figure 2  Now remaining cut-sets can be generated by taking ring sum (modulo 2) of these four fundamental cut-sets. The total number of cut-sets generated by fundamental cut-sets is equal to the number of ways ring-sums of fundamental cut-sets, which is equal to 4 C 2 + 4 C 3 + 4 C 4 = 11 and these are given as follows  Table 3: Table shows all the cut-sets of the graph G(5, 6) and their respective components. Cut-sets highlighted in red color shows no isolation of a patch. For each these cut-set, the corresponding components' Laplacian matrix is given as follows, respectively and the second-smallest eigenvalue of these Laplacian matrices is given by The weight associated with each cut-set (obtained in step 4) is 7 and 5 respectively. Thus the maximum weighted cut-set that system can tolerate is one and only the S 3 with given condition. If the aim is to minimize the cost of edge cutting along the sustainable cut-set then we we will choose lowest weighted cut-set, which is here (S 1 S 2 ) S 3 .
Another example we have illustrated is the random graph of 25 vertices, shown in Figure 3. We have considered ErdősRényi model (p = 0.5) to stochastically generate it. This model generate the graph by starting with a set of distinct vertices and adding successive edges between them at random with probability p [31]. Using exhaustive procedure, the most stable components (correspond to maximum possible Fiedler value) of ErdősRényi model generated graph, is shown in Figure 4.

HEURISTIC BISECTION GRAPH PARTITIONING
In the previous section we have discussed the exhaustive procedure to get the desired graph cut for purpose of safe cutting an ecological network, no other partitioning algorithm can be as accurate, extensive and elaborative as this algorithm, but as it mentioned earlier it has high complexity. For large networks, one  may feel to opt existing min-cut algorithms such as spectral bisection partitioning method [43] or Kernighan-Lin algorithm [26]. Since a min-cut algorithm keeps the edges with more weights on components side and edges with minimum weight on the cut-set and we know more the weight on edges in a component more it gives the Fiedler value because of the following result.
Weyl's Monotonicity Theorem [44]: Let λ j is the j-th eigenvalue of a matrix of order n × n. If P is positive semidefinite matrix, then λ j (A + P ) ≥ λ j (A), 1 ≤ j ≤ n.
In graph theory sense this theorem can be interpreted as, if we increase the weight on an edge of the graph then the eigenvalues of graph's Laplacian either will increase or remain as it is. Note that an increment on edge weight is represented by a positive semidefinite matrix, exactly like a perturbation matrix discussed in earlier section.
Unfortunately, these min-cut algorithms do not guarantee the well-connectedness (large Fiedler value) of components. For example, Figure 5 is bisection partition of the ErdősRényi model graph i.e., Figure  3 obtained by spectral bi-partitioning way, can be seen as comparatively with Figure 6 (we will come to it shortly, how it obtained). In Figure 6, components are having more Fiedler value than in the Figure  5. Determined graph cut by spectral min-cut algorithm certainly has minimum weights on the cut, but it contains edges that stopping to give components with highest possible fielder value. So, min-cut algorithms are not the right choice for our desired partitioning of the network. Thus, in this section, we provide a graph bi-partitioning algorithm, which starts with a random partition and searches locally around it an appropriate partitioning that provides the stable components. This algorithm also set up the basis for general partitioning problems such as k-way partitioning and partitioning into unequal size components. We mainly focus on bisection partitioning algorithm. Motivation for this algorithm is again Weyl's Monotonicity Theorem (mentioned above).
Let G be a graph with n nodes, we wish to partition the graph into two components C 1 and C 2 with at most one node difference in their sizes (i.e., ||C 1 | − |C 2 || ≤ 1), such that the λ 2 (L(C i )), i = 1, 2 is maximized. Starting with an arbitrary partition of G, the appropriate partition can be achieved by pushing the large weighted edges which lie on the graph cut into graph components. This is done by swapping the set of pairs of nodes associated with large weighted edges on the cut, while making sure these nodes taking minimal weights away from their respective origin components to the graph cut.
Let A is set of nodes from component C 1 and B is set of nodes from component C 2 , by swapping them we are getting the desired partition. To identify these pair of sets A and B, we adopt here a sequential approach that is described in following steps.
• STEP1: Determine the difference of external cost and internal cost for each node of both components, which are defined as follows, External cost of node x : E x = y w xy , where x and y belong to different components.
Internal cost of node x : I x = y w xy , where x and y both belong to same component.
• STEP4: Repeat the STEP3 until all nodes exhausted in any of the component.
• STEP5: List all a i ∈ C 1 and b i ∈ C 2 , that are obtained in the STEP2.
• STEP7: Choose the number k for which λ C i 2 (L){k} ≥ θ, i = 1, 2, and swap these k-pairs of nodes for desired partition. Here θ = max This way we can generate as many ecologically sustainable partitions as we please, by starting with different-different partitions. Also, by considering many initial random partitions we can choose best among all provided desired partitions by this method. Taking 100 initial random partitions of graph Figure 3, Figure  6 shows the best graph partitioning obtained by using our proposed algorithm with θ = τ + r = 37.03, where threshold value τ = 28. Whereas Figure 7 is the arbitrary initial graph partition algorithm started with, corresponds to desired partition Figure 6. Clearly, the proposed heuristic algorithm gives the better result (more Fiedler value on both components) than the spectral bisection graph partitioning, Figure 5.

CONCLUSION & DISCUSSION
In this paper, we analyzed the stability of ecological metapopulations and determined the threshold value for it to see the existence of a way that crosses the metapopulations network without any harm to populations' stability. The ecological metapopulations network is considered as a weighted graph G(V, E), where |V | is the total number of populations patch habitats and |E| is the total number of communication links among these habitats. Weight on edge signifies the diffusion rate between the nodes that connected by the edge, more the weight means more the communication between the habitat patches. Interaction of two populations (predator and prey) on each habitat patch of a network and their diffusion from one spatial habitat patch to other habitat patches is taken into account in the considered differential equation model with the general kinetics. It is assumed that populations are unstable in each of the nodes of a graph and populations are stable only if there is diffusion among nodes (population patch habitats), otherwise partitioning of an ecological network is meaningless. It is sort of the reverse of Turing-instability concept, i.e., system becomes stable while adding the diffusion term in the system.
Local stability of the metapopulations model governed by the system of ordinary differential equations (consist of reaction and diffusion terms) is determined by linearizing the system. Community matrix of the system has come in a very nice structure which is comprised of four diagonal matrices of order n × n each, where n = |V |. Eigenvalues of this community matrix are actually determined by the eigenvalues of the community matrix at each node, which basically depends upon the local dynamics of both the species i.e., the interaction of both species at each habitat patch. There are significant roles of second smallest eigenvalue (Fiedler value) cited in past literature and in this paper too, its importance observed in deciding the metapopulations stability. Our study found that Laplacian Fiedler value must be greater than the threshold value 1 2 max i {tr J i } , i = 1, 2, . . . , n for achieving stability in spatially distributed populations. In ecological terms, sustainable separations of patches into two non-communicative groups possible provided the populations' dynamics inside each habitat patch and populations' dispersal movement among patches have some appropriate relations. Dispersal movement of species in the network is found to be a crucial factor, more it is better the stability of the populations. Thus aim should be high Fiedler value components of the network for metapopulations persistence.
Paper discussed the exhaustive procedure and an efficient heuristic bisection algorithm that provide a graph cut (network partition) such that metapopulations remain stable even after it is divided into two subnetworks without any communication between them. The exhaustive procedure determines all possible cuts of a graph before deciding an appropriate cut, thus complexity of the procedure will increase with the size of the network. Whereas heuristic bisection algorithm gives the best possible graph cut in the neighborhood of an arbitrary cut where from algorithm starts and this locally best possible graph cut is achieved by swapping a certain number of pair of nodes (loosely, at most n/2 nodes). Through heuristic bisection algorithm many ecologically sustainable partitions can be obtained by starting with different-different partitions. Also, by considering many initial random partitions we can achieve global partition by this proposed method.
A detailed example of an application of exhaustive procedure has been discussed. We considered a network which is made of five population habitat patches that represented by a weighted graph G(5, 6). To generate all cut sets, first fundamental cut-sets (a basis of cut-sets) of this graph determined by considering a spanning tree of the graph, and then the ring-sums are taken of these fundamental cut sets. All suitable graph cuts (safe metapopulations network partitioning) were shown, which are the cuts that provide us graph components with stable populations. Also, an Erdős Rényi model generated random graph shown and it's computer generated partition shown by using both exhaustive procedure and heuristic bisection algorithm.
Well, this is the starting point in determining the sustainable partitioning of ecological networks, developing algorithms for more complexity added system, like, considering directed graph for the inclusion of both sided diffusion and/or taking predator's diffusion rate as prey gradient dependent makes the problem more interesting and challenging. We hope that these aspects will get some importance among other researchers as well and soon be resolved.