Artificial Intelligence (AI), since the onset of the COVID-19 pandemic at the beginning of the last year, is playing an important role in supporting physicians and health authorities in different difficult tasks such as virus spreading, patient diagnosing and monitoring, contact tracing. In this paper, we provide an overview of the methods based on AI technologies proposed for COVID-19 forecasting. Summary statistics of the techniques adopted by researchers, categorized on the base of the underlying AI sub-area, are reported, along with publication venue of papers. The effectiveness of these approaches is investigated and their capabilities or weaknesses in providing reliable predictions are discussed. Future challenges are finally analyzed and research directions for improving current tools are suggested.

Methods for detecting the community structure in complex networks have mainly focused on network topology, neglecting the rich content information often associated with nodes. In the last few years, the compositional dimension contained in many real-world networks has been recognized fundamental to find network divisions which better reflect group organization. In this paper, we propose a multiobjective genetic framework which integrates the topological and compositional dimensions to uncover community structure in attributed networks. The approach allows to experiment different structural measures to search for densely connected communities, and similarity measures between attributes to obtain high intracommunity feature homogeneity. An efficient and efficacious post-processing local merge procedure enables the generation of high quality solutions, as confirmed by the experimental results on both synthetic and real-world networks, and the comparison with several state-of-the-art methods.

Social media are playing an increasingly important role in reporting major events happening in the world. However, detecting events and topics of interest from social media is a challenging task due to the huge magnitude of the data and the complex semantics of the language being processed. The paper proposes an online algorithm to discover topics that incrementally groups short text by incorporating the textual content with latent feature vector representations of words appearing in the text, trained on very large corpora to improve the check-in topic mapping learnt on a smaller corpus. Experimental results show that by using information from the external corpora, the approach obtains significant improvements with respect to classical topic detection methods.

Social media, in recent years, have become an invaluable source of information for both public and private organizations to enhance the comprehension of people interests and the onset of new events. Twitter, especially, allows a fast spread of news and events happening real time that can contribute to situation awareness during emergency situations, but also to understand trending topics of a period. The article proposes an online algorithm that incrementally groups tweet streams into clusters. The approach summarizes the examined tweets into the cluster centroid by maintaining a number of textual and temporal features that allow the method to effectively discover groups of interest on particular themes. Experiments on messages posted by users addressing different issues, and a comparison with state-of-the-art approaches show that the method is capable to detect discussions regarding topics of interest, but also to distinguish bursty events revealed by a sudden spreading of attention on messages published by users.

Improving seasonal influenza forecasting combining official data sources with web search and social media is a recent research topic which can enhance situational awareness of healthcare organizations when monitoring the outbreak of seasonal flu. In this paper, a prediction model based on autoregression that combines data coming from official influenza surveillance system, with data from web search and social media regarding influenza is proposed. The model is evaluated on the two influenza seasons 2016-2017 and 2017-2018, restricted to Italy. The results show that by using Web-based social data, like Google search queries and tweets, we can obtain accurate weekly influenza predictions up to four weeks in advance. The proposed approach improves real-time influenza forecast compared to traditional surveillance systems based on data from sentinel doctors: the prediction error is reduced up to 47%, while the Pearson's correlation is improved of about 24%.

Contact networks have been recognized to have a central role in the dynamic behavior of spreading processes. The availability of cost-optimal curing strategies, able to control the epidemic propagation, are of primary importance for the design of efficient treatments reducing the number of infected individuals and the extinction time of the infection. In this paper, we investigate the use of Genetic Algorithms for solving the problem of finding an optimal curing strategy in a network where a virus spreads following the Susceptible-Infected-Susceptible (SIS) epidemic model. Exploiting the N-Intertwined Mean-Field Approximation (NIMFA) of the SIS spreading process, we propose a constrained genetic algorithm which determines specific curing rates to each node composing the network, in order to minimize the total curing cost, while suppressing the epidemic. Experiments on both synthetic and real-world networks show that the approach finds solutions whose curing cost is lower than that obtained by a classical baseline method.

A method to enhance the robustness of a network, based on Genetic Algorithms, is proposed. The approach optimizes the effective graph resistance of a network, a measure of robustness derived from the field of electric circuit analysis, that can be computed as a cumulative sum of the eigenvalues of the Laplacian matrix associated with the network. Specialized variation operators allow the method to find a solution almost always coinciding with that obtained by the exhaustive search. Experiments on synthetic and real life networks show that the approach outperforms heuristic strategies extensively investigated, by giving the exact solution in a high percentage of the considered networks.

Influenza surveillance through social media data is becoming an important research topic because it could enhance the capabilities of official surveillance systems in monitoring the outbreak of seasonal flu, by providing healthcare organization with improved situational awareness. In this paper, the two influenza seasons 2016-2017 and 2017-2018, restricted to Italy, are investigated by analyzing the tweets posted by users regarding influenza-like illness. Two types of analysis are performed. The first studies the correlation between the tweets containing the most frequent flu related words with the data provided by the Italian InfluNet surveillance system. The second one examines the sentiment of people on the medicines used to heal flu. We show that there is a strict correlation between the reports published on the InfluNet system, and the contents posted by Twitter users about their symptoms and health state. Moreover, we found that the sentiment expressed by people regarding the treatment, in terms of medicines, taken to heal seems rather negative.

In today's world, the interconnections among objects in many domains are often modeled as networks, with nodes representing the objects and edges the existing relationships among them. A key feature of complex networks is the tendency of entities to group together to form communities. The detection of communities has been receiving a great deal of interest by researchers. In fact, the knowledge of how objects organize allows a better understanding of a network, and gives a deeper insight of interesting characteristics, that could not be caught if considering the network as a whole. In the last decade, evolutionary computation techniques have given a significant contribution in this context. The aim of this paper is to present the approaches based on evolutionary computation to uncover community structure. Especially, the representation schemes with the genetic operators apt for them are described, and the most popular fitness functions employed by the methods are discussed. The survey covers the most recent proposals optimizing either a single objective or multiple objectives for different types of network models, such as signed, dynamic, and multidimensional.

After the impressive diffusion of social media and microblogging websites of the last few years, the identification of users having the capability of influencing other users' choices is an important research topic because of the opportunities it can offer to many business companies. Most of the existing approaches, however, detect influencers by relying on centrality measures computed on networks that connect users having different types of inter-relationships. In this paper, we propose a method capable of finding influential users by exploiting the contents of the messages posted by them to express opinions on items, by modeling these contents with a three-layer network. Layers represent users, items, and keywords, along with intra-layer interactions among the actors of the same layer. Inter-layer connections are triples (u, i, k) expressing the information that a user u comments on an item i by using a keyword k. By exploiting multilinear algebra, we present a method capable of extracting the most active users stating their point of view about dominant items tagged with dominant keywords. We conduct a series of experiments on different realworld datasets collected from Twitter and Yelp Social Networks about different topics. Experimental results show the ability of our approach to find influential users that are both authoritative in the user network and very active in posting opinions about the topic of interest.

A many-objective optimization algorithm for community detection in multi-layer networks is proposed. The method exploits the modularity concept as function to be simultaneously optimized on all the network layers to uncover multi-layer communities. In addition, three different strategies to choice the best solution from the set of solutions of the Pareto front are presented. Simulations on several synthetic networks reveal that our method is able to extract high quality communities. A comparison with state-of-the-art approaches shows that the method is competitive and, in many cases, it is also able to outperform existing community detection algorithms for multi-layer networks.

This article proposes a framework for community discovery in temporal multiplex networks by extending the evolutionary clustering approach to encompass both time and multiple dimensions. In this extended framework, the problem of finding community structures for time‐evolving networks with multiple types of ties is reformulated by adding the concept of dimensional smoothness, relative to a single timestamp, to that of temporal smoothness, at the base of evolutionary clustering. At each timestamp, the method tries to maximize the quality of the clustering obtained for the current multidimensional network and to minimize the differences with respect to that obtained at the previous timestamp. Moreover, the evolution of a community between two consecutive timestamps is maintained by exploiting the Hungarian approach, which determines the best cluster correspondence between two consecutive timestamps. Experiments on synthetic and real‐world networks show the capability of the approach in discovering and tracking group organization of actors constituting the network.

Normalized mutual information (NMI) is a widely used measure to compare community detection methods. Recently, however, the need of adjustment for information theory‐based measures has been argued because of the so‐called selection bias problem, that is, they show the tendency in choosing clustering solutions with more communities. In this article, an experimental evaluation of these measures is performed to deeply investigate the problem, and an adjustment that scales the values of these measures is proposed. Experiments on synthetic networks, for which the ground‐truth division is known, highlight that scaled NMI does not present the selection bias behavior. Moreover, a comparison among some well‐known community detection methods on synthetic generated networks shows a fairer behavior of scaled NMI, especially when the network topology does not present a clear community structure. The experimentation also on two real‐world networks reveals that the corrected formula allows to choose, among a set, the method finding a network division that better reflects the ground‐truth structure.

These Keynotes speeches the following: Evolutionary Computation for Community Detection in Complex Networks; Introduction to Social Media Network Analysis with NodeXL and Identifying Malicious Actors on Social Media.

Microblogs have become an important origin of information regarding events happening in a location during a time period. Analyzing and clustering these streams of short textual messages is an important research activity which is attracting the interest of both public and private organizations, since the extracted knowledge can be exploited to enhance the comprehension of people behavior and the onset of emergency situations. Clustering these streams requires efficient algorithms capable of analyzing this continuos deluge of data. The paper proposes an online algorithm that incrementally groups tweet streams into clusters. The approach summarizes the examined tweets into the cluster centroids generated so far. The assignment of a tweet to a centroid uses a similarity measure that takes into account both the cluster age and the terms occurring in the tweet. Experiments on messages posted by users in the Manhattan area show that the method is able to extract events effectively taking place in the examined period.

Normalized mutual information (NMI) is a widely used measure to compare community detection methods. Recently, however, the need of adjustment for information theoretic based measures has been argued because of their tendency in choosing clustering solutions with more communities. In this paper an experimental evaluation is performed to investigate this problem, and an adjustment that scales the values of NMI is proposed. Experiments on synthetic generated networks highlight the unbiased behavior of scaled NMI.

Nowadays, the increasing popularity of micro-blogging websites such as Twitter, makes available an impressive amount of information about users and their social behavior. These media contents give the opportunity to study opinions, sentiments, attitudes, reactions towards particular events. In this paper the sentiment of Italian Twitter users in the period of 2014 European elections has been investigated, and an analysis of the opinions regarding parties and leaders along a period of three months is presented. Moreover, hashtag networks have been generated and clustered, and communities of users, who posted tweets containing the hashtags appearing in these clusters, have been extracted with the aim of unveiling and tracking thematic discussion groups.

The paper proposes a new approach to detect shared community structure in multidimensional networks based on the combination of multiobjective genetic algorithms, local search, and the concept of temporal smoothness, coming from evolutionary clustering. A multidimensional network is clustered by running on each slice a multiobjective genetic algorithm that maximizes the modularity on such a slice and, at the same time, minimizes the difference between the community structure obtained for the current layer and that found on the already considered dimensions. Experiments on synthetic and real-world datasets show the ability of the approach in discovering latent shared clustering of objects.

MOTIVATION: Protein-protein interaction (PPI) networks are powerful models to represent the pairwise protein interactions of the organisms. Clustering PPI networks can be useful for isolating groups of interacting proteins that participate in the same biological processes or that perform together specific biological functions. Evolutionary orthologies can be inferred this way, as well as functions and properties of yet uncharacterized proteins. RESULTS: We present an overview of the main state-of-the-art clustering methods that have been applied to PPI networks over the past decade. We distinguish five specific categories of approaches, describe and compare their main features and then focus on one of them, i.e. population-based stochastic search. We provide an experimental evaluation, based on some validation measures widely used in the literature, of techniques in this class, that are as yet less explored than the others. In particular, we study how the capability of Genetic Algorithms (GAs) to extract clusters in PPI networks varies when different topology-based fitness functions are used, and we compare GAs with the main techniques in the other categories. The experimental campaign shows that predictions returned by GAs are often more accurate than those produced by the contestant methods. Interesting issues still remain open about possible generalizations of GAs allowing for cluster overlapping. AVAILABILITY AND IMPLEMENTATION: We point out which methods and tools described here are publicly available. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The paper explores the use of evolutionary techniques in dealing with the image segmentation problem. An image is modeled as a weighted undirected graph, where nodes correspond to pixels, and edges connect similar pixels. A genetic algorithm that uses a fitness function based on an extension of the normalized cut criterion is proposed. The algorithm employs the locus-based representation of individuals, which allows for the partitioning of images without setting the number of segments beforehand. A new concept of nearest neighbor that takes into account not only the spatial location of a pixel, but also the affinity with the other pixels contained in the neighborhood, is also defined. Experimental results show that our approach is able to segment images in a number of regions that conform well to human visual perception. The visual perceptiveness is substantiated by objective evaluation methods based on uniformity of pixels inside a region, and comparison with ground-truth segmentations available for part of the used test images.

The discovery of evolving communities in dynamic networks is an important research topic that poses challenging tasks. Evolutionary clustering is a recent framework for clustering dynamic networks that introduces the concept of temporal smoothness inside the community structure detection method. Evolutionary-based clustering approaches try to maximize cluster accuracy with respect to incoming data of the current time step, and minimize clustering drift from one time step to the successive one. In order to optimize both these two competing objectives, an input parameter that controls the preference degree of a user towards either the snapshot quality or the temporal quality is needed. In this paper the detection of communities with temporal smoothness is formulated as a multiobjective problem and a method based on genetic algorithms is proposed. The main advantage of the algorithm is that it automatically provides a solution representing the best trade-off between the accuracy of the clustering obtained, and the deviation from one time step to the successive. Experiments on synthetic data sets show the very good performance of the method when compared with state-of-the-art approaches.

Community detection in signed complex networks is a challenging research problem aiming at finding groups of entities having positive connections within the same cluster and negative relationships between different clusters. Most of the proposed approaches have been developed for networks having only positive edges. In this paper we propose a multiobjective approach to detect communities in signed networks. The method partitions a network in groups of nodes such that two objectives are contemporarily optimized. The former is that the partitioning should have dense positive intra-connections and sparse negative interconnections, the latter is that it should have as few as possible negative intra-connections and positive inter-connections. We show that the concepts of signed modularity and frustration fulfill these objectives, and that the maximization of signed modularity and the minimization of frustration allow to obtain very good solutions to the problem. An extensive set of experiments on both real-life and synthetic signed networks shows the efficacy of the approach.

DynamicNet, an effective and efficient algorithm for supporting community evolution detection in time-evolving information networks is presented and experimentally evaluated in this paper. DynamicNet introduces a graph-based model-theoretic approach to represent time-evolving information networks, and to capture how they change over time. A central feature of DynamicNet is represented by the ability of supporting matching-based community evolution detection, by identifying several classes of community transitions. Experimental results clearly demonstrate the reliability and the efficiency of our proposal.

The roll calls of the Italian Parliament in the current legislature is studied by employing multidimensional scaling, hierarchical clustering, and network analysis. In order to detect changes in voting behavior, the roll calls have been divided in seven periods of six months each. All the methods employed pointed out an increasing fragmentation of the political parties endorsing the previous government that culminated in its downfall. By using the concept of modularity at different resolution levels, we identify the community structure of Parliament and its evolution in each of the time periods considered. The analysis performed revealed as a valuable tool in detecting trends and drifts of Parliamentarians. It showed its effectiveness at identifying political parties and at providing insights on the temporal evolution of groups and their cohesiveness, without having at disposal any knowledge about political membership of Representatives.

The detection of groups of proteins sharing common biological features is an important research issue, intensively investigated in the last few years, because of the insights it can give in understanding cell behavior. In this paper we present an extensive experimental evaluation campaign aiming at exploring the capability of Genetic Algorithms (GAs) to find clusters in protein-protein interaction networks, when different topological-based fitness functions are employed. A complete experimentation on the yeast protein-protein interaction network, along with a comparative evaluation of the effectiveness in detecting true complexes on the yeast and human networks, reveals GAs as a feasible and competitive computational technique to cope with this problem.

Several approaches have been presented in the literature to cluster Protein-Protein Interaction (PPI) networks. They can be grouped in two main categories: those allowing a protein to participate in different clusters and those generating only nonoverlapping clusters. In both cases, a challenging task is to find a suitable compromise between the biological relevance of the results and a comprehensive coverage of the analyzed networks. Indeed, methods returning high accurate results are often able to cover only small parts of the input PPI network, especially when low-characterized networks are considered. We present a coclustering-based technique able to generate both overlapping and nonoverlapping clusters. The density of the clusters to search for can also be set by the user. We tested our method on the two networks of yeast and human, and compared it to other five well-known techniques on the same interaction data sets. The results showed that, for all the examples considered, our approach always reaches a good compromise between accuracy and network coverage. Furthermore, the behavior of our algorithm is not influenced by the structure of the input network, different from all the techniques considered in the comparison, which returned very good results on the yeast network, while on the human network their outcomes are rather poor.

A multiobjective genetic algorithm to uncover community structure in complex network is proposed. The algorithm optimizes two objective functions able to identify densely connected groups of nodes having sparse inter-connections. The method generates a set of network divisions at different hierarchical levels in which solutions at deeper levels, consisting of a higher number of modules, are contained in solutions having a lower number of communities. The number of modules is automatically determined by the better tradeoff values of the objective functions. Experiments on synthetic and real life networks show that the algorithm successfully detects the network structure and it is competitive with state-of-the-art approaches.

The discovery of evolving communities in dynamic networks is an important research topic that poses challenging tasks. Previous evolutionary based clustering methods try to maximize cluster accuracy, with respect to incoming data of the current time step, and minimize clustering drift from one time step to the successive one. In order to optimize both these two competing objectives, an input parameter that controls the preference degree of a user towards either the snapshot quality or the temporal quality is needed. In this paper the detection of communities with temporal smoothness is formulated as a multiobjective problem and a method based on genetic algorithms is proposed. The main advantage of the algorithm is that it automatically provides a solution representing the best trade-off between the accuracy of the clustering obtained, and the deviation from one time step to the successive. Experiments on synthetic data sets show the very good performance of the method compared to state-of-the-art approaches.

A recommendation engine for disease prediction that combines clustering and association analysis techniques is proposed. The system produces local prediction models, specialized on subgroups of similar patients by using the past patient medical history, to determine the set of possible illnesses an individual could develop. Each model is generated by using the set of frequent diseases that contemporarily appear in the same patient. The illnesses a patient could likely be affected in the future are obtained by considering the items induced by high confidence rules generated by the frequent diseases. Experimental results show that the proposed approach is a feasible way to diagnose diseases.

A multiobjective genetic algorithm for detecting communities in dynamic networks, i.e., networks that evolve over time, is proposed. The approach leverages on the concept of evolutionary clustering, assuming that abrupt changes of community structure in short time periods are not desirable. The algorithm correctly detects communities and it is shown to be very competitive w.r.t. some state-of-the-art methods.

Extracting and understanding community structure in complex networks is one of the most intensively investigated problems in recent years. In this paper we propose a genetic based approach to discover overlapping communities. The algorithm optimizes a fitness function able to identify densely connected groups of nodes by employing it on the line graph corresponding to the graph modelling the network. The method generates a division of the network in a number of groups in an unsupervised way. This number is automatically determined by the optimal value of the fitness function. Experiments on synthetic and real life networks show the capability of the method to successfully detect the network structure.

Existing density-based data stream clustering algorithms use a two-phase scheme approach consisting of an online phase, in which raw data is processed to gather summary statistics, and an offline phase that generates the clusters by using the summary data. In this paper we propose a data stream clustering method based on a multi-agent system that uses a decentralized bottom-up self-organizing strategy to group similar data points. Data points are associated with agents and deployed onto a 2D space, to work simultaneously by applying a heuristic strategy based on a bio-inspired model, known as flocking model. Agents move onto the space for a fixed time and, when they encounter other agents into a predefined visibility range, they can decide to form a flock if they are similar. Flocks can join to form swarms of similar groups. This strategy allows to merge the two phases of density-based approaches and thus to avoid the offline cluster computation, since a swarm represents a cluster. Experimental results show the capability of the bio-inspired approach to obtain very good results on real and synthetic data sets.

A multiobjective genetic algorithm to uncover community structure in complex network is proposed. The algorithm optimizes two objective functions able to identify densely connected groups of nodes having sparse interconnections. The method generates a set of network divisions at different hierarchical levels in which solutions at deeper levels, consisting of a higher number of modules, are contained in solutions having a lower number of communities. The number of modules is automatically determined by the better tradeoff values of the objective functions. Experiments on synthetic and real life networks show the capability of the method to successfully detect the network structure.

A new genetic algorithm to detect communities in social networks is presented. The algorithm uses a fitness function able to identify groups of nodes in the network having dense intra-connections, and sparse inter-connections. The variation operators employed are suitably adapted to take into account the actual links among the nodes. These modified operators makes the method efficient because the space of possible solutions is sensibly reduced. Experiments on a real life network show the capability of the method to successfully identify the network structure.

A boosting algorithm based on cellular genetic programming (GP) to build an ensemble of predictors is proposed. The method evolves a population of trees for a fixed number of rounds and, after each round, it chooses the predictors to include in the ensemble by applying a clustering algorithm to the population of classifiers. Clustering the population allows the selection of the most diverse and fittest trees that best contribute to improve classification accuracy. The method proposed runs on a distributed hybrid environment that combines the island and cellular models of parallel GP. The combination of the two models provides an efficient implementation of distributed GP, and, at the same time, the generation of low sized and accurate decision trees. The large amount of memory required to store the ensemble affects the performance of the method. This paper shows that, by applying suitable pruning strategies, it is possible to select a subset of the classifiers without increasing misclassification errors; indeed for some data sets, for up to 30% of pruning, ensemble accuracy increases. Experimental results show that the combination of clustering and pruning enhances classification accuracy of the ensemble approach.

The paper presents an adaptive GP boosting ensemble method forthe classification of distributed homogeneous streaming data that comes from multiple locations. The approach is able to handle concept drift via change detection by employing a change detection strategy, based on self-similarity of the ensemble behavior, and measured by its fractal dimension. It is efficient since each nodeof the network works with its local streaming data, and communicate only the local model computed with the otherpeer-nodes. Furthermore, once the ensemble has been built, it isused to predict the class membership of new streams of data until concept drift is detected. Only in such a case the algorithm is executed to generate a new set of classifiers to update the current ensemble. Experimental results on a synthetic and reallife data set showed the validity of the approach in maintaining an accurate and up-to-date GP ensemble.

An adaptive boosting ensemble algorithm for classifying homogeneous distributed data streams is presented. The method builds an ensemble of classifiers by using Genetic Programming (GP) to inductively generate decision trees, each trained on different parts of the distributed training set. The approach adopts a co-evolutionary platform to support a cooperative model of GP. A change detection strategy, based on self-similarity of the ensemble behavior, and measured by its fractal dimension, permits to capture time- evolving trends and patterns in the stream, and to reveal changes in evolving data streams. The approach tracks online ensemble accuracy deviation over time and decides to recompute the ensemble if the deviation has exceeded a pre- specified threshold. This allows the maintenance of an accurate and up-to-date ensemble of classifiers for continuous flows of data with concept drifts. Experimental results on a real life data set show the validity of the approach.

A boosting algorithm based on cellular genetic programming to build an ensemble of predictors is proposed. The method evolves a population of trees for a fixed number of rounds and, after each round, it chooses the predictors to include into the ensemble by applying a clustering algorithm to the population of classifiers. The method proposed runs on a distributed hybrid multi-island environment that combines the island and cellular models of parallel genetic programming. The large amount of memory required to store the ensemble makes the method heavy to deploy. The paper shows that by applying suitable pruning strategies it is possible to select a subset of the classifiers without increasing misclassification errors; indeed, up to 20 of pruning, ensemble accuracy increases. Experiments on several data sets show that combining clustering and pruning enhances classification accuracy of the ensemble approach.

A co-clustering algorithm for large sparse binary data matrices, based on a greedy technique and enriched with a local search strategy to escape poor local maxima, is proposed. The algorithm starts with an initial random solution and searches for a locally optimal solution by successive transformations that improve a quality function which combines row and column means together with the size of the co-cluster. Experimental results on synthetic and real data sets show that the method is able to find significant co-clusters

An extension of cellular genetic programming for data classification (CGPC) to induce an ensemble of predictors is presented. Two algorithms implementing the bagging and boosting techniques are described and compared with CGPC. The approach is able to deal with large data sets that do not fit in main memory since each classifier is trained on a subset of the overall training data. The predictors are then combined to classify new tuples. Experiments on several data sets show that, by using a training set of reduced size, better classification accuracy can be obtained, but at a much lower computational cost

A distance-based outlier detection method that finds the top outliers in an unlabeled data set and provides a subset of it, called outlier detection solving set, that can be used to predict the outlierness of new unseen objects, is proposed. The solving set includes a sufficient number of points that permits the detection of the top outliers by considering only a subset of all the pairwise distances from the data set. The properties of the solving set are investigated, and algorithms for computing it, with subquadratic time requirements, are proposed. Experiments on synthetic and real data sets to evaluate the effectiveness of the approach are presented. A scaling analysis of the solving set size is performed, and the false positive rate, that is, the fraction of new objects misclassified as outliers using the solving set instead of the overall data set, is shown to be negligible. Finally, to investigate the accuracy in separating outliers from inliers, ROC analysis of the method is accomplished. Results obtained show that using the solving set instead of the data set guarantees a comparable quality of the prediction, but at a lower computational cost.

A new definition of distance-based outlier and an algorithm, called HilOut, designed to efficiently detect the top n outliers of a large and high-dimensional data set are proposed. Given an integer k, the weight of a point is defined as the sum of the distances separating it from its k nearest-neighbors. Outlier are those points scoring the largest values of weight. The algorithm HilOut makes use of the notion of space-filling curve to linearize the data set, and it consists of two phases. The first phase provides an approximate solution, within a rough factor, after the execution of at most d + 1 sorts and scans of the data set, with temporal cost quadratic in d and linear in N and in k, where d is the number of dimensions of the data set and N is the number of points in the data set. During this phase, the algorithm isolates points candidate to be outliers and reduces this set at each iteration. If the size of this set becomes n, then the algorithm stops reporting the exact solution. The second phase calculates the exact solution with a final scan examining further the candidate outliers that remained after the first phase. Experimental results show that the algorithm always stops, reporting the exact solution, during the first phase after much less than d + 1 steps. We present both an in-memory and disk-based implementation of the HilOut algorithm and a thorough scaling analysis for real and synthetic data sets showing that the algorithm scales well in both cases.

This paper presents a study that evaluates the influence of the parallel genetic programming (GP) models in maintaining diversity in a population. The parallel models used are the cellular and the multipopulation one. Several measures of diversity are considered to gain a deeper understanding of the conditions under which the evolution of both models is successful. Three standard test problems are used to illustrate the different diversity measures and analyze their correlation with performance. Results show that diversity is not necessarily synonym of good convergence.

A new parallel implementation of genetic programming (GP) based on the cellular model is presented and compared with both canonical GP and the island model approach. The method adopts a load-balancing policy that avoids the unequal utilization of the processors. Experimental results on benchmark problems of different complexity show the superiority of the cellular approach with respect to the canonical sequential implementation and the island model. A theoretical performance analysis reveals the high scalability of the implementation realized and allows to predict the size of the population when the number of processors and their efficiency are fixed.

Data clustering is an important task in the area of data mining. Clustering is the unsupervised classification of data items into homogeneous groups called clusters. Clustering methods partition a set of data items into clusters, such that items in the same cluster are more similar to each other than items in different clusters according to some defined criteria. Clustering algorithms are computationally intensive, particularly when they are used to analyze large amounts of data. A possible approach to reduce the processing time is based on the implementation of clustering algorithms on scalable parallel computers. This paper describes the design and implementation of P-AutoClass, a parallel version of the AutoClass system based upon the Bayesian model for determining optimal classes in large data sets. The P-AutoClass implementation divides the clustering task among the processors of a multicomputer so that each processor works on its own partition and exchanges intermediate results with the other processors. The system architecture, its implementation, and experimental performance results on different processor numbers and data sets are presented and compared with theoretical performance. In particular, experimental and predicted scalability and efficiency of P-AutoClass versus the sequential AutoClass system are evaluated and compared.

A parallel genetic programming approach to induce decision trees in large data sets is presented. A population of trees is evolved by employing the genetic operators and every individual is evaluated by using a fitness function based on the J-measure. The method is able to deal with large data sets since it uses a parallel implementation of genetic programming through the grid model and an out of core technique for those data sets that do not fit in main memory. Preliminary experiments on data sets from the UCI machine learning repository give good classification outcomes and assess the scalability of the method.

A parallel hybrid method for solving the satisfiability (SAT) problem that combines cellular genetic algorithms (GAs) and the random walk SAT (WSAT) strategy of greedy SAT (GSAT) is presented. The method, called cellular genetic WSAT (CGWSAT), uses a cellular GA to perform a global search from a random initial population of candidate solutions and a local selective generation of new strings. The global search is then specialized in local search by adopting the WSAT strategy. A main characteristic of the method is that it indirectly provides a parallel implementation of WSAT when the probability of crossover is set to zero. CGWSAT has been implemented on a Meiko CS-2 parallel machine using a 2D cellular automaton as a parallel computation model. The algorithm has been tested on randomly generated problems and some classes of problems from the DIMACS and SATLIB test set.

A new parallel hybrid method for solving the satisfiability problem that combines cellular genetic algorithms and the random walk (WSAT) strategy of GSAT is presented. The method, called CGWSAT, uses a cellular genetic algorithm to perform a global search on a random initial population of candidate solutions and a local selective generation of new strings. Global search is specialized in local search by adopting the WSAT strategy. CGWSAT has been implemented on a Meiko CS-2 parallel machine using a two-dimensional cellular automaton as a parallel computation model. The algorithm has been tested on randomly generated problems and some classes of problems from the DIMACS test set.

An enumerative approach for selective generation of prime implicants of a theory in conjunctive normal form is presented. The method is based on 0-1 programming. Optimal solutions of the integer linear program associated with the theory correspond to prime implicants. All prime implicants can be obtained by augmenting the integer program with new constraints which discard the already obtained solutions. The method allows to implement preference criteria in the choice of the prime implicants to find.