Estimating entity importance via counting set covers
- 12 August 2012
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 687-695
- https://doi.org/10.1145/2339530.2339640
Abstract
The data-mining literature is rich in problems asking to assess the importance of entities in a given dataset. At a high level, existing work identifies important entities either by ranking or by selection. Ranking methods assign a score to every entity in the population, and then use the assigned scores to create a ranked list. The major shortcoming of such approaches is that they ignore the redundancy between high-ranked entities, which may in fact be very similar or even identical. Therefore, in scenarios where diversity is desirable, such methods perform poorly. Selection methods overcome this drawback by evaluating the importance of a group of entities collectively. To achieve this, they typically adopt a set-cover formulation, which identifies the entities in the minimum set cover as the important ones. However, this dichotomy of entities conceals the fact that, even though an entity may not be in the reported cover, it may still participate in many other optimal or near-optimal solutions. In this paper, we propose a framework that overcomes the above drawbacks by integrating the ranking and selection paradigms. Our approach assigns importance scores to entities based on both the number and the quality of set-cover solutions that they participate. Our algorithmic contribution lies with the design of an efficient algorithm for approximating the number of high-quality set covers that each entity participates. Our methodology applies to a wide range of applications. In a user study and an experimental evaluation on real data, we demonstrate that our framework is efficient and provides useful and intuitive results.Keywords
This publication has 17 references indexed in Scilit:
- The union of minimal hitting sets: Parameterized combinatorial bounds and countingJournal of Discrete Algorithms, 2009
- A team formation model based on knowledge and collaborationExpert Systems with Applications, 2009
- Parameterized enumeration, transversals, and imperfect phylogeny reconstructionTheoretical Computer Science, 2006
- Counting models for 2SAT and 3SAT formulaeTheoretical Computer Science, 2005
- Modeling Team Member Characteristics for the Formation of a Multifunctional Team in Concurrent EngineeringIEEE Transactions on Engineering Management, 2004
- The Parameterized Complexity of Counting ProblemsSIAM Journal on Computing, 2004
- The Pattern Ordering ProblemLecture Notes in Computer Science, 2003
- Identifying the Minimal Transversals of a Hypergraph and Related ProblemsSIAM Journal on Computing, 1995
- Monte Carlo sampling methods using Markov chains and their applicationsBiometrika, 1970
- A New Measure of Rank CorrelationBiometrika, 1938