Stability Preserving Bisection Algorithms in Reaction-Diffusion Complex Networks

Abstract

Reaction-Diffusion complex networks are ubiquitous in many pragmatic models of network of interacting nodes with individual dynamics, such as social interactions, neuronal functions, transportation models, ecological systems and metabolic reactions. In particular case of reaction-diffusion network, with two different agents interacting together by specifi ed inter-node dynamics, coupling between nodes and uniform rate of di usion, under type I instability the network is stable only, Fiedler value(second smallest eigenvalue of Laplacian operator) is greater than certain threshold. Given stable complex network along with dynamics, we want to fi nd partition such that dynamics on the resultant daughter networks are sustainable. These partitions are of practical interest in many real life situations. For example, consider meta-population dynamics of species on ecological network in population habitats. Too often habitats are fragmented by artifi cial invasion (industrial corridors, road and railway networks) of human activities or due to stochastic reasons(genetic, environmental and demographic conditions) which results in extinction of even dominant species. Thus deserving study of existence of minimal cut partition and stability on the resultant networks while preserving the population of species on the partitioned networks. It is well-known in the literature that balanced graph partition problem is NP-complete. Various approximation algorithms and heuristics are used to generate sufficiently good quality local optimum solutions. In this work, we propose a theoretical model of reaction-diffusion network with two different species and study properties of linearized stability and co-existential equilibrium. We argue, pre-existing graph (static) bisection algorithms cannot be used to partition live complex network, such that resultant components have sustainable dynamics. Thus, we design a iterative heuristic algorithm of O(jV j3) time complexity based on Weyl's perturbation theorem, to partition the network into stable components. Throughout the experiments, our test bed for various algorithms are DIMACS10 graph datasets. We exploit, the spectral properties of Laplacian operator(specially algebraic connectivity or Fiedler value) and dynamics of the network topology. Since calculation of eigenvalues are expensive and prone to perturbation in every iteration, we search for further alternatives by looking at the parallels of heuristic graph bisection algorithms. We study various existing global partition algorithms(spectral bisection, multilevel recursive methods etc.) for graph bisection and incorporate results in our algorithm to increase quality of the partitions. Further down the line, we explore various meta-heuristic local search methods such as Kerninghan-Lin, Fiduccia-Mattheyses etc., and incorporate data structures for constant time retrieval of gain of vertices in our algorithm. Simulated annealing is well-known idea in statistical mechanics and motivated by motion of high degrees of freedom of system in presence of heat sink. Due to similarities between combinatorial optimization problem with exponential search space and physical system with high degree of freedom, we propose an adaptation of simulated annealing algorithm to our stability preserving bisection objective. Our empirical results shows that, although the algorithms converges in reasonable time for small graphs but su ers from polynomial growth of execution time with respect to size of graph. In the second part, we present two important theorems regarding the stability of reaction-diffusion network and characterize it completely in terms of external and internal costs, thus avoiding the need for calculation for eigenvalues. Using these theorems and above experimental results, we design a linear time heuristic of O(jV j + jEj) time complexity for stability preserving partition which shows signi cant improvement in partition quality.