350 rub
Journal Dynamics of Complex Systems - XXI century №3 for 2013 г.
Article in number:
Heuristic algorithms for modeling and optimization of complex networks structures
Authors:
V.V. Kashirin - Junior Research Scientist, National Research University of information technologies, mechanics and optics. E-mail: kashirin.victor@gmail.com
S.V. Ivanov - Ph. D., Senior Research Scientist, National Research University of information technologies, mechanics and optics. E-mail: sergei.v.ivanov@gmail.com
A.V. Boukhanovsky - Dr. Sci., Professor, Leading Research Scientist, National Research University of information technologies, mechanics and optics. E-mail: avb_mail@mail.ru
Abstract:
Complex networks modeling, represented as graphs, is applied for checking the hypotheses about structure of its probabilistic model and to simulation of different processes on them. Existing algorithms of complex networks modeling are oriented to represent different classes of complex networks, and couldn-t be used to model more generic objects, especially heterogeneous structures. Present work suggests universal approach to modeling of complex networks with certain probabilistic properties as an global optimization task which is solved with heuristic algorithms. We consider a functional ? a metric of graph . All possible metrics of such type could be divided into topological, which express certain structural property of complex network (diameter, clusterisation, degree distribution etc.) and functional, which express characteristics of some process that happens on this network. Requirements for characteristics of modeled network are defined as set of pairs of functionals and their desired values. Optimality of network structure is evaluated as cumulative difference between desired and present values of functionals on current network. The choice of optimization algorithms depends on definition of modeling problem. In present work heuristic algorithms (simulated annealing, genetic algorithm) are utilized, having specific advantages due to discreetness of optimization space and possibility to find global maximum. With simulated annealing method it is demonstrated possibility to build the network with certain topological characteristics, which are not present in the networks, built with traditional complex networks modeling algorithms. With genetic algorithm we show the possibility to optimize the structure of the network in more effective way, comparing to the traditional optimization strategies based on centrality metrics. Realization of proposed modeling methods does not depend on functionals, which characterize properties of complex networks and processes on them, which makes them useful in multiple subject areas.
Pages: 41-45
References

  1. Strogatz S. H. Exploring complex networks // Nature 2001. V. 410. R. 268 - 276.
  2. Boccaletti S. et al. Complex networks: Structure and dynamics // Physics Reports. 2006. V. 424. № 4 - 5. R. 175 - 308.
  3. Dolan W. B., Cummings P. T., LeVan M. D. Process optimization via simulated annealing: Application to network design // AIChE Journal. 1989. V. 35. № 5. R. 725 - 736.
  4. US Air Transportation Network [http://sites.google.com/site/cxnets/usairtransportationnetwork]
  5. Sivanandam S. N., Deepa S. N. Introduction to Genetic Algorithms // Springer Publishing Company, Incorporated. 2008.
  6. Isham V., Harden S., Nekovee M. Stochastic epidemics and rumours on finite random networks // Physica A: Statistical Mechanics and its Applications. 2010. V. 389. R. 561 - 576.
  7. Kashirin V. V., Ivanov S. V., Buxanovskij A. V. Sloot P. M. A. Planirovanie vozdejstviya na kriminal'ny'e sistemy' na osnove apparata kompleksny'x setej // Informaczionno-izmeritel'ny'e i upravlyayushhie sistemy'. 2012. № 11. S. 34 - 39.
  8. Sloot P. M. A., Ivanov S. V., Boukhanovsky A. V., Van De Vijver D., Boucher C. A. B. Stochastic simulation of HIV population dynamics through complex network modeling // International Journal of Computer Mathematics, 2008. R. 1175 - 1187.