Name
Abstract | ||
|---|---|---|
Given a sequence G= of simple graphs over uniquely labeled vertices from a set V, the periodic subgraph mining problem consists in discovering maximal subgraphs that recur at regular intervals in G. For a periodic subgraph to be maximal, it is intended here that it cannot be enriched by adding edges nor can its temporal span be expanded in any direction. We give algorithms that improve the theoretical complexity of solutions previously available for this problem. In particular, we show an optimal solution based on an implicit description of the output subgraphs that takes time O(|V|+|E@?|xT^2/@s)-where |E@?| is the average number of edges over the entire sequence G-to publish all maximal periodic subgraphs that meet or exceed a minimum occurrence threshold @s. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jda.2012.05.002 | J. Discrete Algorithms |
Keywords | Field | DocType |
output subgraphs,maximal periodic subgraphs,implicit description,entire sequence,periodic subgraph,sequence g,average number,periodic subgraphs mining problem,efficient algorithm,minimum occurrence threshold,maximal subgraphs,periodic subgraph mining problem,interactions,social networks | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Algorithm,Periodic graph (geometry),Mathematics | Journal |
Volume | ISSN | Citations |
17, | 1570-8667 | 0 |
PageRank | References | Authors |
0.34 | 6 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alberto Apostolico | 1 | 1441 | 182.20 |
| Péter L. Erds | 2 | 23 | 2.21 |
| Ervin Gyri | 3 | 4 | 1.90 |
| Zsuzsanna Lipták | 4 | 212 | 24.03 |
| Cinzia Pizzi | 5 | 139 | 15.73 |