Name
Abstract | ||
|---|---|---|
Graph support measures are functions measuring how frequently a given subgraph pattern occurs in a given database graph. An important class of support measures relies on overlap graphs. A major advantage of the overlap graph based approaches is that they combine anti-monotonicity with counting occurrences of a pattern which are independent according to certain criteria. However, existing overlap graph based support measures are expensive to compute. In this paper, we propose a new support measure which is based on a new notion of independence. We show that our measure is the solution to a linear program which is usually sparse, and using interior point methods can be computed efficiently. We show experimentally that for large networks, in contrast to earlier overlap graph based proposals, pattern mining based on our support measure is feasible. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-33460-3_29 | ECML/PKDD (1) |
Keywords | Field | DocType |
subgraph pattern,new support measure,interior point method,support measure,frequent subgraph pattern mining,graph support measure,certain criterion,important class,pattern mining,computable support measure,new notion,database graph,linear program | Strength of a graph,Data mining,Line graph,Forbidden graph characterization,Theoretical computer science,Distance-hereditary graph,Null graph,Universal graph,Subgraph isomorphism problem,Mathematics,Graph (abstract data type) | Conference |
Citations | PageRank | References |
3 | 0.39 | 14 |
Authors | ||
2 | ||