Search

Inspired by the split decomposition of graphs and rank-width, we introduce the notion of r-splits. We focus on the family of r-splits of a graph of order n, and we prove that it forms a hypergraph with several properties. We prove that such hypergraphs can be represented using only O(nr+1) of its hyperedges, despite its potentially exponential number of hyperedges. We also prove that there exist hypergraphs that need at least (nr) hyperedges to be represented, using a generalization of set orthogonality. [ABSTRACT FROM AUTHOR]

Dense subgraphs convey important information and insights about a graph structure. Several applications, such as graph visualization, graph summarization, and complex network analysis rely on discovering the dense subgraphs available within the target graph. This enumeration problem has been intensively addressed by several research communities but remains a challenging problem because of its importance and use. This problem generalizes the clique problem and is thus NP-hard and not approximable in polynomial time in general graphs. In this paper, we propose to deal with this problem in a specific application case where the type of the discovered dense subgraphs is important. This is the case of graph summarization for example. However, existing dense subgraph discovery algorithms are either dedicated to specific kind of structures such as cliques and bicliques or are too general and list the dense subgraphs without giving their types. To deal with this issue, we provide a unified approach that lists dense subgraphs and provides their types. Our approach relies on deep learning. More precisely, we enrich exiting structural node embedding with extra information, computed on node neighborhoods, to effectively capture their belonging to dense subgraphs. We evaluate our approach on several datasets to attest its efficiency and its effectiveness on two main applications: graph summarization and graph clustering. Our results show that our method significantly improves the compression rate in graph summarization, achieving up to 30% size reduction for the largest graphs tested and exceeding 80% for sparse graphs. Additionally, even for highly dense graphs, our method consistently achieves a non-zero AMI score, outperforming other approaches on the clustering application. • We propose a deep learning approach to dense subgraph mining. • We aim to simply give insights about a graph structure. • We compute a node parameter that reveals how much dense the graph is around it. • We apply this approach successfully in graph summarization and clustering. [ABSTRACT FROM AUTHOR]

Self-monitoring is a simple and effective mechanism for surveilling wireless sensor networks, especially to cope against faulty or compromised nodes. A node v can monitor the communication over a link e if both end-nodes of e are neighbors of v . Finding a set of monitoring nodes satisfying all monitoring constraints is called the edge-monitoring problem . The minimum edge-monitoring problem is known to be NP-complete. In this paper, we present a novel self-stabilizing algorithm for computing a minimal edge-monitoring set under the unfair distributed scheduler. For sparse networks the time complexity of this new algorithm is much lower than the currently best known algorithm. [ABSTRACT FROM AUTHOR]

Let k be a positive integer, Sk and Ck denote, respectively, a star and a cycle of k edges. Kn is the usual notation for the complete multigraph on n vertices and in which every edge is taken times. In this paper, we investigate necessary and sufficient conditions for the existence of the decomposition of Kn into edges disjoint of stars Sk's and cycles Cu's. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in four proper vertex colorings of graphs, with additional domination property. In the dominator colorings , strong colorings and strict strong colorings of a graph G , every vertex has to dominate at least one color class. Conversely, in the dominated colorings of G , every color class has to be dominated by at least one vertex. We study arbitrary graphs as well as P 4 -sparse graphs, P 5 -free graphs, bounded treewidth graphs and claw-free graphs. [ABSTRACT FROM AUTHOR]

Drug design is a research process with a goal of creating a chemical drug to produce the desired biological effect. Because of the long time and the high cost issues associated with traditional drug discovery, there is a need to develop new techniques and strategies to increase the diminishing effectiveness of traditional approaches. Ligand-Based Virtual Screening (LBVS) plays a vital role in the early stage of the drug discovery. It could constitute a possible solution to solve the time and cost problems. Subsequently, the researchers are looking for new methods to find new active compounds and bring them to market in a short time. LBVS can be enhanced by different methods and strategies such as Machine Learning and Deep Learning. In this paper, a Deep Convolutional Neural Network method is proposed to enhance the performances of Ligand-Based Virtual Screening process (DCNNLB). Two main contributions are presented in this paper, The first contribution consists of designing a model based on Deep Convolutional Neural Network (DCNN) for LBVS. We propose several topological network models to find the one that gives the best performance such as accuracy and recall. For this, many network topology configurations have been proposed, and a variety of parameters have been taken into account. Furthermore, our proposed model is trained on all compounds of all activity classes of the Drug Data Report Database (MDDR). Thus, it presented a mean accuracy of 0.98 for all three MDDR Datasets. The second contribution is to generate a new learning representation in order to better represent chemical compound. This representation is based on the extraction of the automatic features learning from the weights of our proposed model. Consequently, it is very efficient in calculating molecular similarity and performances of the LBVS process. The obtained results with the three different datasets drawn from the MDDR and the performance evaluation with ANOVA test, have proved the superiority in performance of our proposed method compared to the different conventional methods. [Display omitted] • New molecular representations obtained by the proposed deep convolutional model. • Enhancement in effectiveness of similarity searching with DCNNLB method in LBVS. • Decreasing in training time by using the molecular learning representation. • The proposed DCNNLB method significantly outperforms the conventional TAN method. [ABSTRACT FROM AUTHOR]