Simulation of spontaneous emergence process of complex optimal networks by genetic algorithm

Pengxiang Li, Mengwu Zhang, Youmin Xi*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


In order to simulate the whole process of the network evolution from the tree to complete graph and to solve the problem that existing adjacency nodes encoding was only suitable for the network with low density, and the traditional crossover and mutation would give rise to a lot of infeasible solution, a variable length gene encoding based on triangle matrix and operators including crossover between gene segments, mutation and balance among gene segments is proposed. Because only the triangle matrix information is encoded in the symmetric matrix that describes all possible changes of the undirected network, the length of coding string is moderate and there is no limitation of edges for modeling the whole evolution from the tree to complete graph. Crossover between gene segments only exchanges the adjacent connection at node level and the mutation balance within gene segment rewires old edge. Hence, this kind of crossover and mutation not only satisfies the demands of genetic algorithm, but also ensures the connectivity of evolving networks. Compared with the adjacency node encoding and the traditional crossover and mutation, this method has wider application range and faster convergent speed.

Original languageEnglish
Pages (from-to)908-912
Number of pages5
JournalHsi-An Chiao Tung Ta Hsueh/Journal of Xi'an Jiaotong University
Issue number8
Publication statusPublished - Aug 2005
Externally publishedYes


  • Complex optimal network
  • Genetic algorithm
  • Spontaneous emergence

Cite this