| dc.description.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. | en_US |
