Name
Abstract | ||
|---|---|---|
The identification and enumeration of small, non-isomorphic graphs, called graphlets, within larger graphs is an analytic tool used for graph analytics. The problem of identifying graphlets embedded within a larger graph is a larger implementation of the graph isomorphism problem, with no known polynomial time algorithmic solution. One common method to identify the class of a given subgraph embedded within a supergraph is to make a degree list, called a signature, of it, and compare it to a list of known signatures and their corresponding graphlets. However, some graphlets have the same signature. Extra processing is needed to differentiate between them, and the existing method for determining how to differentiate them is by inspection and on a case by case basis. This paper proposes an algorithm to differentiate graphlets with identical signatures which significantly outperforms the existing method. A search space reduction technique is also proposed to reduce the computation cost. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/CIC.2016.053 | 2016 IEEE 2nd International Conference on Collaboration and Internet Computing (CIC) |
Keywords | Field | DocType |
Graph analytics,Graphlet,Subgraph isomorphism,Embedded graphs | Computer science,Enumeration,Induced subgraph isomorphism problem,Theoretical computer science,Isomorphism,Epigraph,Time complexity,Subgraph isomorphism problem,Graph isomorphism problem,Computation | Conference |
ISBN | Citations | PageRank |
978-1-5090-4608-9 | 0 | 0.34 |
References | Authors | |
3 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Calvin Alumbaugh | 1 | 0 | 0.34 |
| Li Qinghua | 2 | 10 | 7.79 |
| Vincent C. Hu | 3 | 143 | 12.86 |