Please use this identifier to cite or link to this item:
Title: CSV: Visualizing and mining cohesive subgraphs
Authors: Wangt, N.
Parthasarathy, S.
Tan, K.-L. 
Tung, A.K.H. 
Keywords: Clique
Data mining
Graph density
Graph mining
Issue Date: 2008
Citation: Wangt, N.,Parthasarathy, S.,Tan, K.-L.,Tung, A.K.H. (2008). CSV: Visualizing and mining cohesive subgraphs. Proceedings of the ACM SIGMOD International Conference on Management of Data : 445-457. ScholarBank@NUS Repository.
Abstract: Extracting dense sub-components from graphs efficiently is an important objective in a wide range of application domains ranging from social network analysis to biological network analysis, from the World Wide Web to stock market analysis. Motivated by this need recently we have seen several new algorithms to tackle this problem based on the (frequent) pattern mining paradigm. A limitation of most of these methods is that they are highly sensitive to parameter settings, rely on exhaustive enumeration with exponential time complexity, and often fail to help the users understand the underlying distribution of components embedded within the host graph. In this article we propose an approximate algorithm, to mine and visualize cohesive subgraphs (dense sub components) within a large graph. The approach, refereed to as Cohesive Subgraph Visualization (CSV) relies on a novel mapping strategy that maps edges and nodes to a multi-dimensional space wherein dense areas in the mapped space correspond to cohesive subgraphs. The algorithm then walks through the dense regions in the mapped space to output a visual plot that effectively captures the overall dense sub-component distribution of the graph. Unlike extant algorithms with exponential complexity, CSV has a complexity of O(V 2logV) when fixing the parameter mapping dimension, where V corresponds to the number of vertices in the graph, although for many real datasets the performance is typically sub-quadratic. We demonstrate the utility of CSV as a stand-alone tool for visual graph exploration and as a pre-filtering step to significantly scale up exact subgraph mining algorithms such as CLAN [33]. Copyright 2008 ACM.
Source Title: Proceedings of the ACM SIGMOD International Conference on Management of Data
ISBN: 9781605581026
ISSN: 07308078
DOI: 10.1145/1376616.1376663
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 11, 2019

Page view(s)

checked on Feb 9, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.