A genetic algorithm-based approach to mapping the diversity of networks sharing a given degree distribution and global clustering

Overbury, Peter, Kiss, Istvan Z and Berthouze, Luc (2016) A genetic algorithm-based approach to mapping the diversity of networks sharing a given degree distribution and global clustering. In: Cherifi, Hocine, Gaito, Sabrina, Quattrociocchi, Walter and Sala, Alessandra (eds.) Complex networks & their applications V: proceedings of the 5th international workshop on complex networks and their applications. Studies in computational intelligence, 693 . Springer, pp. 223-233. ISBN 9783319509006

[img] PDF - Accepted Version
Download (435kB)

Abstract

The structure of a network plays a key role in the outcome of dynamical processes operating on it. Two prevalent network descriptors are the degree distribution and the global clustering. However, when generating networks with a prescribed degree distribution and global clustering, it has been shown that changes in structural properties other than that controlled for are induced and these changes have been found to alter the outcome of spreading processes on the network. This therefore begs the question of our understanding of the potential diversity of networks sharing a given degree distribution and global clustering. As the space of all possible networks is too large to be systematically explored, a heuristic approach is needed. In our genetic algorithm-based approach, networks are encoded by their subgraph counts from a chosen family of subgraphs. Coverage of the space of possible networks is then maximised by focusing the search through optimising the diversity of counts by the Map-Elite algorithm. We provide preliminary evidence of our approach’s ability to sample from the space of possible networks more widely than some state of the art methods.

Item Type: Book Section
Keywords: Network generation; degree distribution; clustering; higher-order structure; novelty search; graph diversity; multi-objective optimisation
Schools and Departments: School of Engineering and Informatics > Informatics
School of Mathematical and Physical Sciences > Mathematics
Research Centres and Groups: Centre for Computational Neuroscience and Robotics
Subjects: Q Science > QA Mathematics > QA0075 Electronic computers. Computer science
Depositing User: Luc Berthouze
Date Deposited: 05 Dec 2016 13:03
Last Modified: 05 Dec 2016 13:03
URI: http://sro.sussex.ac.uk/id/eprint/65312

View download statistics for this item

📧 Request an update