Overlapping community detection in complex networks with memetic algorithms

Intricate relationships exist among the billions of individuals who form our society. The interactions that occur between thousands of genes within our cells comprise our biology. Millions of financial institutions perform billions of transactions daily, creating complex networks of entities. These are just a few examples of the many complex systems surrounding us. Network science comprehends the collection, management, analysis, interpretation and presentation of complex systems that employ networks. Collections of interconnected items that are usually represented by a graph showing a set of nodes joined by edges. Complex networks often present community structures where nodes preferentially link to one another. Examples of community structures include groups of friends in society, groups of co-functioning genes in gene networks and groups of similar products in co-purchasing networks, among many others. Detecting the community structure in networks offers important information about the organisation and functioning of such groups. For many phenomena represented by networks, communities can be overlapping, with nodes participating in multiple communities. For example, a person participates in several social organisations; a gene is related to different biological functions; a product can be sold in different markets.Revealing the community structure in complex networks is no trivial task and can lead to a non-deterministic polynomial-time hardness (NP-hard) computational problem. In this thesis, we approach the overlapping community detection problem using memetic algorithms, metaheuristics that employ a population-based search and local-search inspired by Darwinian principles of natural evolution and Dawkins's notion of a meme defined as a unit of cultural evolution. We detail the construction of two different memetic algorithms, present computational results, compare our methods with other state-of-the-art metaheuristics and present applications of our methods as case studies.