Genetic Programming for the Automatic Inference of Graph Models for Complex Networks

Complex networks are becoming an integral tool for our understanding of an enormous variety of natural and artificial systems. A number of human-designed network generation procedures have been proposed that reasonably model specific real-life phenomena in structure and dynamics. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications, and the social sciences have recently resulted. A graph model is an algorithm capable of constructing arbitrarily sized networks, whose end structure will exhibit certain statistical and structural properties. The process of deriving an accurate graph model is very time intensive and challenging and may only yield highly accurate models for very specific phenomena. An automated approach based on genetic programming was recently proposed by the authors. However, this initial system suffered from a number of drawbacks, including an under-emphasis on creating hub vertices, the requirement of user intervention to determine objective weights, and the arbitrary approach toward selecting the most representative model from a population of candidate models. In this paper, we propose solutions to these problems and show experimentally that the new system represents a significant improvement and is very capable of reproducing existing common graph models from even a single small initial network.