SkyGraph: an algorithm for important subgraph discovery in relational graphs
Data Mining and Knowledge Discovery, 17 (1):
57--76 (August 2008)Abstract
A significant number of applications require effective and efficient manipulation of relational graphs, towards discovering important patterns. Some example applications are: (i) analysis of microarray data in bioinformatics, (ii) pattern discoveryin a large graph representing a social network, (iii) analysis of transportation networks, (iv) community discovery in Webdata. The basic approach followed by existing methods is to apply mining techniques on graph data to discover important patterns,such as subgraphs that are likely to be useful. However, in some cases the number of mined patterns is large, posing difficultiesin selecting the most important ones. For example, applying frequent subgraph mining on a set of graphs the system returnsall connected subgraphs whose frequency is above a specified (usually user-defined) threshold. The number of discovered patternsmay be large, and this number depends on the data characteristics and the frequency threshold specified. It would be moreconvenient for the user if “goodness” criteria could be set to evaluate the usefulness of these patterns, and if the usercould provide preferences to the system regarding the characteristics of the discovered patterns. In this paper, we proposea methodology to support such preferences by applying subgraph discovery in relational graphs towards retrieving importantconnected subgraphs. The importance of a subgraph is determined by: (i) the order of the subgraph (the number of vertices)and (ii) the subgraph edge connectivity. The performance of the proposed technique is evaluated by using real-life as wellas synthetically generated data sets.
Description
SpringerLink - Zeitschriftenbeitrag
