Name
Abstract | ||
|---|---|---|
Existing studies on graph mining focus on exact graphs that are precise and complete. However, graph data tends to be uncertain in practice due to noise, incompleteness and inaccuracy. This paper investigates the problem of finding top-k maximal cliques in an uncertain graph. A new model of uncertain graphs is presented, and an intuitive measure is introduced to evaluate the significance of vertex sets. An optimized branch-and-bound algorithm is developed to find top-k maximal cliques, which adopts efficient pruning rules, a new searching strategy and effective preprocessing methods. The extensive experimental results show that the proposed algorithm is very efficient on real uncertain graphs, and the top-k maximal cliques are very useful for real applications, e.g. protein complex prediction. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/ICDE.2010.5447891 | ICDE |
Keywords | Field | DocType |
uncertain graph,optimisation,pruning rules,tree searching,top-k maximal cliques,searching strategy,graph mining,data mining,graph theory,optimized branch-and-bound algorithm,bioinformatics,uncertainty,computer science,polynomials,proteins,branch and bound algorithm,probability distribution,databases,pediatrics,prediction algorithms,g protein | Data mining,Mathematical optimization,Line graph,Computer science,K-tree,Chordal graph,Theoretical computer science,Trivially perfect graph,Pathwidth,Intersection number (graph theory),Clique (graph theory),Maximal independent set | Conference |
ISSN | ISBN | Citations |
1084-4627 | 978-1-4244-5444-0 | 48 |
PageRank | References | Authors |
1.33 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhaonian Zou | 1 | 331 | 15.78 |
| Jianzhong Li | 2 | 3196 | 304.46 |
| Hong Gao | 3 | 1086 | 120.07 |
| Shuo Zhang | 4 | 211 | 9.44 |