Please use this identifier to cite or link to this item: https://doi.org/10.1145/1376616.1376663
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
Visualization
Issue Date: 2008
Source: 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. https://doi.org/10.1145/1376616.1376663
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40425
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.

SCOPUSTM   
Citations

42
checked on Jan 9, 2018

Page view(s)

69
checked on Jan 19, 2018

Google ScholarTM

Check

Altmetric


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