In this paper, we define a sound and complete inference system for triadic implications generated from a formal triadic context , where G, M, and B are object, attribute, and condition sets, respectively, and I is a ternary relation . The inference system is expressed as a set of axioms “à la Armstrong.” The type of triadic implications we are considering in this paper is called conditional attribute implication (CAI) and has the following form: , where X and Y are subsets of M, and is a subset of B. Such implication states that Ximplies Y under all conditions in and any subset of it. Moreover, we propose a method to compute CAIs from Biedermann's implications. We also introduce an algorithm to compute the closure of an attribute set X w.r.t. a set Σ of CAIs given a set of conditions.

The search for cohesive groups inside a social network is a topic commonly known as community detection and has attracted many researchers. However, the identification of groups with competitive features using blockmodeling, biclustering and structural or regular equivalences has benefited from a less important interest within the research community. In this paper we define a generic biclustering method called BiP that computes semantically meaningful coclusters (or biclusters) from a two-mode data network. The method has the following features: (i) it allows the processing of adjacency matrices whose data type can be either binary, discrete or categorical without any need for prior data codification, and (ii) each generated block may either represent a cluster of objects with the properties they own (or not), or a juxtaposition of subgroups with distinct profiles (and sometimes purely opposed ones) for a subset of attributes.

Several approaches have been proposed to solve the well-studied problem of detecting community structure in networks. However, many existing algorithms encounter difficulties when the proportion of inter-community links is higher than the proportion of intra-community links. To overcome this situation, we propose a novel algorithm which performs community detection in two phases. The first phase exploits the covariance of links between nodes and the interclass inertia in order to perform an initial partitioning of the network. The objective is to generate small disconnected groups of nodes mostly from the same community. Then, in the second phase, we propose an iterative process that repeatedly merges these initial groups to identify the final community structure that maximizes the modularity. We illustrate the suitability of our proposal through an empirical study that uses both generated and real-life networks.

Social networks are dynamic structures that contain a set of entities and links. In such a dynamic environment, a specific node or a group of nodes can play an important role in the information flow transmission within the network and therefore, its disappearance may lead to a disconnected network or a breakdown in the information flow. The objective of this paper is to extend our previous work on managing a node disappearance to handling the disappearance of a group of nodes. The proposed approach relies on the role played by a group of nodes to conduct network changes and maintain the network connected while restoring the information flow with a similar quality as before the group disappearance. We consider two situations (only one versus many communities) and categorize groups of nodes into three classes (scattered, contiguous and hybrid). Hence, we manage a group disappearance with respect to its class and the network topology by adding new links in a parsimonious way and finding a substitute for a leaving group. Our approach differs from existing link prediction solutions by the fact that it uses the information flow quality as a key performance indicator to identify the potential links to add and/or the possible substitute to a disappearing group. We implement a prototype by using an open source social network analysis library (NetworkX) and we validate our solution through experiments. The results show the benefits of our solution in terms of response time and the number of added links.

One of the problems in analyzing large multidimensional databases through OLAP sessions is that decision makers can be overwhelmed by the size of query answers, while they need a concise summary of data. Intensional query answering can help by providing a concise description of extensional answers (i.e., the sets of retrieved facts), generally relying on knowledge like integrity constraints, taxonomies, or patterns discovered from data. This paper proposes a framework for computing an intensional answer to an OLAP query by leveraging on the previous queries in the current session. Such intensional answer is concise and semantically rich, and allows the size of the extensional answers returned to be reduced, so as to achieve an effective trade-off between conciseness and informational content. After describing the general framework, we propose a specific instantiation that relies on previous contributions in cube modeling and intensional query answering.

The objective of this article is to define an approach towards generating implications with (or without) negation when only a formal context K = (G, M, I) is provided. To that end, we define a two-step procedure which first (i) computes implications

Social networks are dynamic structures in which entities and links appear and disappear for different reasons. Starting from the observation that each entity has a more or less important role within the network, the objective of this article is to propose a method which exploits the role played by nodes to predict the new structure of a social network once one entity disappears. The role of a node in the network is expressed in terms of the number of interactions it has with the rest of the network. Two roles are considered: the leader and the mediator with their corresponding measure: the degree centrality and the betweenness centrality.

Databases and data warehouses contain an overwhelming volume of information that users must wade through in order to extract valuable and actionable knowledge to supportthe decision-making process. This contribution addresses the problem of automatically analyzing large multidimensional tables to get a concise representation of data, identify patterns and provide approximate answers to queries.

On-line analytical processing (OLAP) provides tools to explore and navigate into data cubes in order to extract interesting information. Nevertheless, OLAP is not capable of explaining relationships that could exist in a data cube. Association rules are one kind of data mining techniques which finds associations among data. In this paper, we propose a framework for mining inter-dimensional association rules from data cubes according to a sum-based aggregate measure more general than simple frequencies provided by the traditional COUNT measure. Our mining process is guided by a meta-rule context driven by analysis objectives and exploits aggregate measures to revisit the definition of support and confidence. We also evaluate the interestingness of mined association rules according to Lift and Loevinger criteria and propose an efficient algorithm for mining inter-dimensional association rules directly from a multidimensional data.

Whereas the early frequent pattern mining methods admitted only relatively simple data and pattern formats (e.g., sets, sequences, etc.), there is nowadays a clear push towards the integration of ever larger portions of domain knowledge in the mining process in order to increase the precision and the abstraction level of the retrieved patterns and hence ease their interpretation. We present here a practically motivated study of a frequent pattern extraction from sequences of data objects that are described within a domain ontology. As the complexity of the descriptive structures is high, an entire framework for the pattern extraction process had to be defined. The key elements thereof are a pair of descriptive languages, one for individual data and another one for generic patterns, a generality relation between patterns, and an Apriori-like method for pattern mining.

Galois (concept) lattice theory has been successfully applied in data mining for the resolution of the association rule problem. In particular, structural results about lattices have been used in the design of efficient procedures for mining the frequent patterns (itemsets) in transaction databases. Since such databases are often dynamic, we propose a detailed study of the incremental aspects in lattice construction to support effective procedures for incremental mining of frequent closed itemsets (FCIs). Based on a set of descriptive results about lattice substructures involved in incremental updates, the paper presents a novel algorithm for lattice construction that explores only limited parts of a lattice for updating. Two new methods for incremental FCI mining are studied: the first inherits its extensive search strategy from a classical lattice method, whereas the second applies the new lattice construction strategy to the itemset mining context. Unlike batch techniques based on FCIs, both methods avoid rebuilding the FCI family from scratch whenever new transactions are added to the database and/or when the minimal support is changed.

Learning concepts and rules from structured (complex) objects is a quite challenging but very relevant problem in the area of machine learning and knowledge discovery. In order to take into account and exploit the semantic relationships that hold between atomic components of structured objects, we propose a knowledge discovery process, which starts from a set of complex objects to produce a set of related atomic objects (called contexts). The second step of the process makes use of the concatenation product to get a global context in which binary relations of individual contexts coexist with relations produced by the application of some operators to individual contexts. The last step permits the discovery of concepts and implication rules using the concept lattice as a framework in order to discover and interpret nontrivial concepts and rules that may relate different components of complex objects. This paper focuses on two main steps of the knowledge discovery process, namely data mining and interpretation.

We consider a class of linear query programs and integrity constraints and develop methods for (i) computing the residues and (ii) pushing them inside the recursive programs, minimizing redundant computation and run-time overhead. We also discuss applications of our strategy to intelligent query answering.>

The Galois (or concept) lattice produced from a binary relation has proved useful for many applications. Building the Galois lattice can be considered a conceptual clustering method because it results in a concept hierarchy. This article presents incremental algorithms for updating the Galois lattice and corresponding graph, resulting in an incremental concept formation method. Different strategies are considered based on a characterization of the modifications implied by such an update. Results of empirical tests are given in order to compare the performance of the incremental algorithms to three other batch algorithms. Surprisingly, when the total time for incremental generation is used, the simplest and less efficient variant of the incremental algorithms outperforms the batch algorithms in most cases. When only the incremental update time is used, the incremental algorithm outperforms all the batch algorithms. Empirical evidence shows that, on the average, the incremental update is done in time proportional to the number of instances previously treated. Although the worst case is exponential, when there is a fixed upper bound on the number of features related to an instance, which is usually the case in practical applications, the worst‐case analysis of the algorithm also shows linear growth with respect to the number of instances.

This paper describes an approach to software reuse that involves generating and retrieving abstractions from existing software systems using concept formation methods. The potential of the approach is illustrated through two important activities of the reuse process. First, the concept hierarchy generated by the concept formation methods is used for organizing and retrieving the artifacts inside a repository. Second, the generated concepts are used in identifying new abstractions that may be converted into new, more generic artifacts with better reuse potential. These experiments are part of a major software engineering research project involving many business and academic partners.

The focus is semantic query optimization in the presence of integrity constraints such as inclusion dependencies and context dependencies (CDs). The authors provide the motivation for the type of integrity constraints considered and for the work at large. They introduce CDs formally and illustrate their power in capturing semantics with an example. An inference mechanism is described for reasoning with these constraints. Sufficient conditions for testing redundancy of atoms in rules and rules in programs are described, and polynomial time algorithms are provided for detecting and eliminating such redundancies. The technique uniformly applies to recursive as well as nonrecursive queries. The approach is illustrated with examples. The discussion and examples are presented in terms of recursive rules only.>

An incremental algorithm for updating the Galois lattice is proposed where new objects may be dynamically added by modifying the existing lattice. A large experimental application reveals that adding a new object may be done in time proportional to the number of objects on the average. When there is a fixed upper bound on the number of properties related to an object, which is the case in practical applications, the worst case analysis of the algorithm confirms the experimental observations of linear growth with respect to the number of objects. Algorithms for generating rules from the lattice are also given.>