11563 research outputs found
Sort by
Tab-Shapley: identifying top-k tabular data quality insights
No full textWe present an unsupervised method for aggregating anomalies in tabular datasets by identifying the top-k tabular data quality insights. Each insight consists of a set of anomalous attributes and the corresponding subsets of records that serve as evidence to the user. The process of identifying these insight blocks is challenging due to (i) the absence of labeled anomalies, (ii) the exponential size of the subset search space, and (iii) the complex dependencies among attributes, which obscure the true sources of anomalies. Simple frequency-based methods fail to capture these dependencies, leading to inaccurate results. To address this, we introduce Tab-Shapley, a cooperative game theory based framework that uses Shapley values to quantify the contribution of each attribute to the data's anomalous nature. While calculating Shapley values typically requires exponential time, we show that our game admits a closed-form solution, making the computation efficient. We validate the effectiveness of our approach through empirical analysis on real-world tabular datasets with ground-truth anomaly labels
Revisiting token sliding on chordal graphs
No full textIn this article, we revisit the complexity of the reconfiguration of independent sets under the token sliding rule on chordal graphs. In the \textsc{Token Sliding-Connectivity} problem, the input is a graph G and an integer k, and the objective is to determine whether the reconfiguration graph TSk(G) of G is connected. The vertices of TSk(G) are k-independent sets of G, and two vertices are adjacent if and only if one can transform one of the two corresponding independent sets into the other by sliding a vertex (also called a \emph{token}) along an edge. Bonamy and Bousquet [WG'17] proved that the \textsc{Token Sliding-Connectivity} problem is polynomial-time solvable on interval graphs but \NP-hard on split graphs. In light of these two results, the authors asked: can we decide the connectivity of TSk(G) in polynomial time for chordal graphs with \emph{maximum clique-tree degree} d? We answer this question in the negative and prove that the problem is \para-\NP-hard when parameterized by d. More precisely, the problem is \NP-hard even when d=4. We then study the parameterized complexity of the problem for a larger parameter called \emph{leafage} and prove that the problem is \co-\W[1]-hard. We prove similar results for a closely related problem called \textsc{Token Sliding-Reachability}. In this problem, the input is a graph G with two of its k-independent sets I and J, and the objective is to determine whether there is a sequence of valid token sliding moves that transform I into J
A STUDY ON THE FLOW PHYSICS OF ALTITUDE ADAPTIVE NOZZLES
No full textClass of rocket nozzles which are capable of changing the effective flow area ratio with change in ambient pressure as it ascends through atmosphere are called altitude adaptive nozzles. Aerospike nozzles, expansion deflection nozzles, dual bell and double divergent nozzles are types of altitude adaptive nozzles. These nozzles are able to adapt to ambient conditions on account of the complex flow phenomena within. This paper discusses the topical problem of fluid flow physics in altitude adaptive nozzles such as annular aerospike, linear plug, expansion deflection and dual bell nozzles as the nozzle operates from low to high nozzle pressure ratios. The strategy to numerically model the flow within these nozzles is also discussed
Making Knowledge Visible: Artisans, Craftsmen, Printmakers, and the Knowledge Sharing Practices of 19th-Century Bengal
No full textAnalysis of reference and citation copying in evolving bibliographic networks
No full textExtensive literature demonstrates how the copying of references (links) can lead to the emergence of various structural properties (e.g., power-law degree distribution and bipartite cores) in bibliographic and other similar directed networks. However, it is also well known that the copying process is incapable of mimicking the number of directed triangles in such networks; neither does it have the power to explain the obsolescence of older papers. In this paper, we propose RefOrCite, a new model that allows for copying of both the references from (i.e., out-neighbors of) as well as the citations to (i.e., in-neighbors of) an existing node. In contrast, the standard copying model (CP) only copies references. While retaining its spirit, RefOrCite differs from the Forest Fire (FF) model in ways that makes RefOrCite amenable to mean-field analysis for degree distribution, triangle count, and densification. Empirically, RefOrCite gives the best overall agreement with observed degree distribution, triangle count, diameter, h-index, and the growth of citations to newer papers. � 2020 Elsevier B.V., All rights reserved
