In the last years complex networks received a lot of attention by researchers because of their capability of representing the relationships among objects composing many real world systems. One of the main problems in the study of complex networks is the detection of {\it community structure} \cite{Fortunato2010,newman-2004}, i.e. the division of a network into groups of nodes having dense intra-connections, and sparse inter-connections. Many different methods have been proposed to uncover community structure in networks. In this context, \emph{Evolutionary Computation} based approaches have been playing a central role because of their capability of exploring the search space and escaping from local minima during the optimization process. Among evolutionary algorithms, {\it Genetic Algorithms} \cite{GO89} are a class of adaptive general-purpose search techniques inspired by natural evolution. They have been proposed by Holland \cite{Ho75} in the early 1970s as computer programs that simulate the evolution process in nature. In the last few years Genetic Algorithms revealed competitive alternative methods to traditional optimization and search techniques. They have been applied to many problems, in diverse research and application areas, such neural nets evolution, planning and scheduling, machine learning and pattern recognition. Moreover, they showed to be competitive for the study of complex networks. The objective of the tutorial is to introduce the evolutionary computation paradigm as a powerful technique for the community detection problem. After a brief introduction to the concepts at the base of evolutionary computation, with a particular focus on Genetic Algorithms, the identification of a community structure in a network is formalized as an optimization problem that can be solved by using a population-based model, by applying genetic operators that allow the exploration of the search space to find a solution. Several types of networks are considered, such as undirected, directed, weighted, signed, multi-dimensional, time evolving, and the most recent proposals exploiting evolutionary techniques for finding communities in these types of networks, both non-overlapping and overlapping community structure, are described. Moreover, the differences between the different representations adopted by methods, along with single objective versus multi-objective approaches, are discussed. Community detection is a hot topic in social networks. The presentation of a different computational paradigm with respect to traditional approaches can be beneficial for researchers to explore new approaches and principles to deal with this problem. The target audience is constituted by all those researchers interested in approaching the problem of community detection with computational models inspired by evolution in nature. No particular background is expected from the audience since the tutorial provides the concepts necessary for understanding the problem.
Tutorial: Evolutionary Computation for Community Detection in Complex Networks
Clara Pizzuti
2016
Abstract
In the last years complex networks received a lot of attention by researchers because of their capability of representing the relationships among objects composing many real world systems. One of the main problems in the study of complex networks is the detection of {\it community structure} \cite{Fortunato2010,newman-2004}, i.e. the division of a network into groups of nodes having dense intra-connections, and sparse inter-connections. Many different methods have been proposed to uncover community structure in networks. In this context, \emph{Evolutionary Computation} based approaches have been playing a central role because of their capability of exploring the search space and escaping from local minima during the optimization process. Among evolutionary algorithms, {\it Genetic Algorithms} \cite{GO89} are a class of adaptive general-purpose search techniques inspired by natural evolution. They have been proposed by Holland \cite{Ho75} in the early 1970s as computer programs that simulate the evolution process in nature. In the last few years Genetic Algorithms revealed competitive alternative methods to traditional optimization and search techniques. They have been applied to many problems, in diverse research and application areas, such neural nets evolution, planning and scheduling, machine learning and pattern recognition. Moreover, they showed to be competitive for the study of complex networks. The objective of the tutorial is to introduce the evolutionary computation paradigm as a powerful technique for the community detection problem. After a brief introduction to the concepts at the base of evolutionary computation, with a particular focus on Genetic Algorithms, the identification of a community structure in a network is formalized as an optimization problem that can be solved by using a population-based model, by applying genetic operators that allow the exploration of the search space to find a solution. Several types of networks are considered, such as undirected, directed, weighted, signed, multi-dimensional, time evolving, and the most recent proposals exploiting evolutionary techniques for finding communities in these types of networks, both non-overlapping and overlapping community structure, are described. Moreover, the differences between the different representations adopted by methods, along with single objective versus multi-objective approaches, are discussed. Community detection is a hot topic in social networks. The presentation of a different computational paradigm with respect to traditional approaches can be beneficial for researchers to explore new approaches and principles to deal with this problem. The target audience is constituted by all those researchers interested in approaching the problem of community detection with computational models inspired by evolution in nature. No particular background is expected from the audience since the tutorial provides the concepts necessary for understanding the problem.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
