Mining closed relational graphs with connectivity constraints

Xifeng Yan, X. Jasmine Zhou, Jiawei Han

Research output: Contribution to conferencePaper

Abstract

Relational graphs are widely used in modeling large scale networks such as biological networks and social networks. In this kind of graph, connectivity becomes critical in identifying highly associated groups and clusters. In this paper, we investigate the issues of mining closed frequent graphs with connectivity constraints in massive relational graphs where each graph has around 10K nodes and 1M edges. We adopt the concept of edge connectivity and apply the results from graph theory, to speed up the mining process. Two approaches are developed to handle different mining requests: CLOSECUT, a pattern-growth approach, and SPLAT, a pattern-reduction approach. We have applied these methods in biological datasets and found the discovered patterns interesting.

Original languageEnglish (US)
Pages324-333
Number of pages10
StatePublished - Dec 1 2005
EventKDD-2005: 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - Chicago, IL, United States
Duration: Aug 21 2005Aug 24 2005

Other

OtherKDD-2005: 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
CountryUnited States
CityChicago, IL
Period8/21/058/24/05

Keywords

  • Closed pattern
  • Connectivity
  • Graph

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'Mining closed relational graphs with connectivity constraints'. Together they form a unique fingerprint.

  • Cite this

    Yan, X., Zhou, X. J., & Han, J. (2005). Mining closed relational graphs with connectivity constraints. 324-333. Paper presented at KDD-2005: 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, IL, United States.