Name
Abstract | ||
|---|---|---|
Graphs are increasingly used to model a variety of loosely structured data such as biological or social networks and entity-relationships. Given this profusion of large-scale graph data, efficiently discovering interesting substructures buried within is essential. These substructures are typically used in determining subsequent actions, such as conducting visual analytics by humans or designing expensive biomedical experiments. In such settings, it is often desirable to constrain the size of the discovered results in order to directly control the associated costs. In this paper, we address the problem of finding cardinality-constrained connected sub trees in large node-weighted graphs that maximize the sum of weights of selected nodes. We provide an efficient constant-factor approximation algorithm for this strongly NP-hard problem. Our techniques can be applied in a wide variety of application settings, for example in differential analysis of graphs, a problem that frequently arises in bioinformatics but also has applications on the web. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/ICDM.2010.86 | ICDM |
Keywords | Field | DocType |
optimisation,visual analytics,expensive biomedical experiment,application setting,graph mining,approximation theory,associated cost,tree data structures,np-hard problem,wide variety,grpahs,differential analysis,subgraph discovery,data structure,cardinalty constrained subgraphs,large node-weighted graph,approximation algorithm,interesting substructure,efficient constant-factor approximation algorithm,large-scale graph data,bioinformatics,cardinality-constrained connected subtrees,interesting small trees,np hard problem,approximation algorithms,algorithm design and analysis,entity relationship,social network,clustering algorithms,structured data,steiner trees | Approximation algorithm,Data structure,Algorithm design,Steiner tree problem,Computer science,Tree (data structure),Visual analytics,Artificial intelligence,Cluster analysis,Data model,Machine learning | Conference |
ISSN | ISBN | Citations |
1550-4786 E-ISBN : 978-0-7695-4256-0 | 978-0-7695-4256-0 | 3 |
PageRank | References | Authors |
0.43 | 21 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephan Seufert | 1 | 279 | 10.69 |
| Srikanta Bedathur | 2 | 607 | 43.23 |
| Julian Mestre | 3 | 103 | 7.88 |
| Gerhard Weikum | 4 | 12710 | 2146.01 |