Mining Density Contrast Subgraphs

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

5 Scopus Citations
View graph of relations

Author(s)

  • Lingyang Chu
  • Yanyan Zhang
  • Zhefeng Wang
  • Jian Pei
  • Enhong Chen

Detail(s)

Original languageEnglish
Title of host publicationProceedings IEEE 34th International Conference on Data Engineering (ICDE 2018)
PublisherIEEE
Pages221-232
ISBN (Electronic)9781538655207
ISBN (Print)9781538655214
Publication statusPublished - Apr 2018
Externally publishedYes

Publication series

NameProceedings - IEEE International Conference on Data Engineering (ICDE)
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X

Conference

Title34th IEEE International Conference on Data Engineering (ICDE 2018)
PlaceFrance
CityParis
Period16 - 19 April 2018

Abstract

Dense subgraph discovery is a key primitive in many graph mining applications, such as detecting communities in social networks and mining gene correlation from biological data. Most studies on dense subgraph mining only deal with one graph. However, in many applications, we have more than one graph describing relations among a same group of entities. In this paper, given two graphs sharing the same set of vertices, we investigate the problem of detecting subgraphs that contrast the most with respect to density. We call such subgraphs Density Contrast Subgraphs, or DCS in short. Two widely used graph density measures, average degree and graph affinity, are considered. For both density measures, mining DCS is equivalent to mining the densest subgraph from a 'difference' graph, which may have both positive and negative edge weights. Due to the existence of negative edge weights, existing dense subgraph detection algorithms cannot identify the subgraph we need. We prove the computational hardness of mining DCS under the two graph density measures and develop efficient algorithms to find DCS. We also conduct extensive experiments on several real-world datasets to evaluate our algorithms. The experimental results show that our algorithms are both effective and efficient.

Research Area(s)

  • Dense Subgraph, Average Degree, Graph Affinity, Contrast Mining

Citation Format(s)

Mining Density Contrast Subgraphs. / Yang, Yu; Chu, Lingyang; Zhang, Yanyan et al.

Proceedings IEEE 34th International Conference on Data Engineering (ICDE 2018). IEEE, 2018. p. 221-232 8509250 (Proceedings - IEEE International Conference on Data Engineering (ICDE)).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review