Fundamenta Informaticae - Volume 129, issue 3

Authors: Appice, Annalisa | Ceci, Michelangelo | Malerba, Donato

Article Type: Research Article

Abstract: Multi-Relational Data Mining (MRDM) refers to the process of discovering implicit, previously unknown and potentially useful information from data scattered in multiple tables of a relational database. Following the mainstream of MRDM research, we tackle the regression where the goal is to examine samples of past experience with known continuous answers (response) and generalize future cases through an inductive process. Mr-SMOTI, the solution we propose, resorts to the structural approach in order to recursively partition data stored into a tightly-coupled database and build a multi-relational model tree which captures the linear dependence between the response variable and one or more …explanatory variables. The model tree is top-down induced by choosing, at each step, either to partition the training space or to introduce a regression variable in the linear models with the leaves. The tight-coupling with the database makes the knowledge on data structures (foreign keys) available free of charge to guide the search in the multi-relational pattern space. Experiments on artificial and real databases demonstrate that in general Mr-SMOTI outperforms both SMOTI and M5' which are two propositional model tree induction systems, and TILDE-RT which is a state-of-art structural model tree induction system. Show more

Keywords: Data mining, Mining methods and algorithms, Regression, Relational Model Trees, Relational DBMS coupling, Lookahead in Model Tree Induction

DOI: 10.3233/FI-2014-969

Citation: Fundamenta Informaticae, vol. 129, no. 3, pp. 193-224, 2014

Authors: Apt, Krzysztof R. | Markakis, Evangelos

Article Type: Research Article

Abstract: We introduce a new threshold model of social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives. We characterize social networks for which adoption of a product by the whole network is possible (respectively necessary) and the ones for which a unique outcome is guaranteed. These characterizations directly yield polynomial time algorithms that allow us to determine whether a given social network satisfies one of the above properties. We also study algorithmic questions for networks without unique outcomes. We show that the problem of determining whether a final network exists in which all …nodes adopted some product is NP-complete. In turn, we also resolve the complexity of the problems of determining whether a given node adopts some (respectively, a given) product in some (respectively, all) network(s). Further, we show that the problem of computing the minimum possible spread of a product is NP-hard to approximate with an approximation ratio better than Ω(n), in contrast to the maximum spread, which is efficiently computable. Finally, we clarify that some of the above problems can be solved in polynomial time when there are only two products. Show more

DOI: 10.3233/FI-2014-970

Citation: Fundamenta Informaticae, vol. 129, no. 3, pp. 225-250, 2014

Authors: Di Mauro, Nicola | Basile, Teresa M.A. | Ferilli, Stefano | Esposito, Floriana

Article Type: Research Article

Abstract: In Artificial Intelligence with Coalition Structure Generation (CSG) one refers to those cooperative complex problems that require to find an optimal partition (maximizing a social welfare) of a set of entities involved in a system. The solution of the CSG problem finds applications in many fields such as Machine Learning (set covering machines, clustering), Data Mining (decision tree, discretization), Graph Theory, Natural Language Processing (aggregation), Semantic Web (service composition), and Bioinformatics. The problem of finding the optimal coalition structure is NP-complete. In this paper we present a greedy adaptive search procedure (GRASP) with path-relinking to efficiently search the space of …coalition structures. Experiments and comparisons to other algorithms prove the validity of the proposed method in solving this hard combinatorial problem. Show more

Keywords: Coalition Structure Generation, Stochastic-Local-Search, GRASP procedure, Path-Relinking

DOI: 10.3233/FI-2014-971

Citation: Fundamenta Informaticae, vol. 129, no. 3, pp. 251-277, 2014

Authors: Németh, Gábor Árpád | Pap, Zoltán

Article Type: Research Article

Abstract: While evolutionary development methodologies have become increasingly prevalent, incremental testing methods are lagging behind. Most traditional test generation algorithms – including the Transition Tour method – rebuild test sequences from scratch even if minimal changes to the system have been made. In the current paper we propose two incremental algorithms to update a Transition Tour test sequence after changes in a deterministic finite state machine model. Our solution uses existing information – the Eulerian graph of a previous version of the system and an Euler tour in it – to update the test cases of the system in response to …modification. The first algorithm keeps an Eulerian graph up to date, while the second algorithm maintains an Euler tour in the augmented graph. Analytical and practical analyses show that our algorithms are very efficient in the case of changing specifications. We also demonstrate our methods through an example. Show more

Keywords: finite state machine, test generation algorithms, incremental algorithms, incremental test generation

DOI: 10.3233/FI-2014-972

Citation: Fundamenta Informaticae, vol. 129, no. 3, pp. 279-300, 2014