62 research outputs found
Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
No full textIn this paper we propose a simple algorithm called CliqueMinTriang for computing a minimal triangulation of a graph. If F is the set of edges that is added to G to make it a complete graph Kn then the asymptotic complexity of CliqueMinTriang is O(|F|(δ2+|F|)) where δ is the degree of the subgraph of Kn induced by F. Therefore our algorithm performs well when G is a dense graph. We also show how to exploit the existing minimal triangulation techniques in conjunction with CliqueMinTriang to efficiently find a minimal triangulation of nondense graphs. Finally we show how the algorithm can be adapted to perform a backward stepwise selection of decomposable Markov networks; the resulting procedure has the same time complexity as that of existing similar algorithms
Auditing Sum Queries
No full textLecture Notes in Computer Science 2572 (G. Goos, J. Hartmanis, J. Van Leeuwen, eds.
Equivalence between hypergraph convexities
No full textLet G be a connected graph on V. A subset X of V is all-paths convex or ap-convex if X contains
each vertex on every path joining two vertices in X and ismonophonically convex orm-convex if
X contains each vertex on every chordless path joining two vertices in X. First of all, we prove that
ap-convexity and m-convexity coincide in G if and only if G is a tree. Next, in order to generalize
this result to a connected hypergraph H, in addition to the hypergraph versions of ap-convexity
and m-convexity, we consider canonical convexity or c-convexity and simple-path convexity
or sp-convexity for which it is well known that m-convexity is finer than both c-convexity and
sp-convexity and sp-convexity is finer than ap-convexity. After proving sp-convexity is coarser
than c-convexity, we characterize the hypergraphs in which each pair of the four convexities
above is equivalent. As a result, we obtain a convexity-theoretic characterization of Berge-acyclic
hypergraphs and of γ-acyclic hypergraphs
Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent
No full textLet G be a connected graph. A subset X of V(G) is g-convex (mconvex)
if it contains all vertices on shortest (induced) paths between
vertices in X. We state characteristic properties of graphs in which every
g-convex set is m-convex, based on which we show that such graphs can
be recognized in polynomial time. Moreover, we state a new convexity - theoretic
characterization of Ptolemaic graphs
Mycoplasma genitalium: prevalence in men presenting with urethritis to a South Australian public sexual health clinic
No full textAbstract not availableT. M. Mezzini, R. G. Waddell, R. J. Douglas and T. A. Sadlo
Privacy Preserving and Data Mining in an On-Line Statistical Database of Additive Type
No full textIn an on-line statistical database, the query-answering system should prevent answers to statistical queries from leading to disclosure of confidential data. On the other hand, a statistical user is inclined to data mining, that is, to disclose pieces of information that are implicit in the (explicit) answers to his queries. A key task for both is to find data that is derivable from given summary statistics. We show that this task is easy if data is additive and the set of given summary statistics can be modelled by a graph
University dropout prediction through educational data mining techniques: A systematic review
No full textThe dropout rates in the European countries is one of the major issues to be faced in a near future as stated in the Europe 2020 strategy. In 2017, an average of 10.6% of young people (aged 18-24) in the EU-28 were early leavers from education and training according to Eurostat’s statistics. The main aim of this review is to identify studies which uses educational data mining techniques to predict university dropout in traditional courses. In Scopus and Web of Science (WoS) catalogues, we identified 241 studies related to this topic from which we selected 73, focusing on what data mining techniques are used for predicting university dropout. We identified 6 data mining classification techniques, 53 data mining algorithms and 14 data mining tools
The contour of a bridged graph is geodetic
No full textThe eccentricity of a vertex vv in a graph GG is the maximum distance of vv from any other vertex of GG and vv is a contour vertex of GG if each vertex adjacent to vv has eccentricity not greater than the eccentricity of vv. The set of contour vertices of GG is geodetic if every vertex of GG lies on a shortest path between a pair of contour vertices. An induced connected subgraph HH of GG is isometric if, every two vertices of HH, have in HH the same distance as in GG. A graph is bridged if it does not contains an isometric cycle with length greater than 3. In this note, we show that the contour of a bridged graph is geodetic
On the geodeticity of the contour of a graph
No full textThe eccentricity of a vertex vv in a graph GG is the maximum distance of vv from any other vertex of GG and vv is a contour vertex of GG if each vertex adjacent to vv has eccentricity not greater than the eccentricity of vv. The set of contour vertices of GG is geodetic if every vertex of GG lies on a shortest path between a pair of contour vertices. In this paper, we firstly investigate the existence of operations on graphs that allow to construct graphs in which the contour is geodetic. Then, after providing an alternative proof of the fact that the contour is geodetic in every HHD-free graph, we show that the contour is geodetic in every cactus and in every graph whose blocks are HHD-free or cycles or cographs. Finally, we generalize the above result by introducing the concept of geodetic-contour-preserving class of graphs and by proving that, if each block BB in a graph GG belongs to a class GBGB of graphs which is geodetic-contour-preserving, then the contour of GG is geodetic
Deep learning approach for predicting university dropout: A case study at roma tre university
No full textBased on current trends in graduation rates, 39% of today young adults on average across OECD countries are expected to complete tertiary-type A (university level) education during their lifetime. In 2017, an average of 10.6% of young people (aged 1824) in the EU-28 were early leavers from education and training. Therefore the level of dropout in the scenery of European education is one of the major issue to be faced in a near future. The main aim of the research is to predict, as early as possible, which student will dropout in the Higher Education (HE) context. The accurate knowledge of this information would allow one to effectively carry out targeted actions in order to limit the incidence of the phenomenon. The recent breakthrough on Neural Networks with the use of Convolutional Neural Networks (CNN) architectures has become disruptive in AI. By stacking together tens or hundreds of convolutional neural layers, a “deep” network structure is obtained, which has been proved very effective in producing high accuracy models. In this research the administrative data of about 6000 students enrolled from 2009 in the Department of Education at Roma Tre University had been used to train a Convolutional Neural Network based. Then, the trained network provides a predictive model that predicts whether the student will dropout. Furthermore, we compared the results obtained using deep learning models to the ones using Bayesian networks. The accuracy of the obtained deep learning models ranged from 67.1% for the first-year students up to 94.3% for the third-year students
- …
