Dense subgraph extraction with application to community detection

Jie Chen, Yousef Saad

Research output: Contribution to journalArticle

107 Citations (Scopus)

Abstract

This paper presents a method for identifying a set of dense subgraphs of a given sparse graph. Within the main applications of this dense subgraph problem, the dense subgraphs are interpreted as communities, as in, e.g., social networks. The problem of identifying dense subgraphs helps analyze graph structures and complex networks and it is known to be challenging. It bears some similarities with the problem of reordering/blocking matrices in sparse matrix techniques. We exploit this link and adapt the idea of recognizing matrix column similarities, in order to compute a partial clustering of the vertices in a graph, where each cluster represents a dense subgraph. In contrast to existing subgraph extraction techniques which are based on a complete clustering of the graph nodes, the proposed algorithm takes into account the fact that not every participating node in the network needs to belong to a community. Another advantage is that the method does not require to specify the number of clusters; this number is usually not known in advance and is difficult to estimate. The computational process is very efficient, and the effectiveness of the proposed method is demonstrated in a few real-life examples.

Original languageEnglish (US)
Article number5677532
Pages (from-to)1216-1230
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume24
Issue number7
DOIs
StatePublished - Jun 6 2012

Fingerprint

Complex networks

Keywords

  • Dense subgraph
  • community
  • hierarchical clustering
  • matrix reordering
  • partial clustering
  • social network

Cite this

Dense subgraph extraction with application to community detection. / Chen, Jie; Saad, Yousef.

In: IEEE Transactions on Knowledge and Data Engineering, Vol. 24, No. 7, 5677532, 06.06.2012, p. 1216-1230.

Research output: Contribution to journalArticle

@article{ca869c40da4d4267bdb415e6582df995,
title = "Dense subgraph extraction with application to community detection",
abstract = "This paper presents a method for identifying a set of dense subgraphs of a given sparse graph. Within the main applications of this dense subgraph problem, the dense subgraphs are interpreted as communities, as in, e.g., social networks. The problem of identifying dense subgraphs helps analyze graph structures and complex networks and it is known to be challenging. It bears some similarities with the problem of reordering/blocking matrices in sparse matrix techniques. We exploit this link and adapt the idea of recognizing matrix column similarities, in order to compute a partial clustering of the vertices in a graph, where each cluster represents a dense subgraph. In contrast to existing subgraph extraction techniques which are based on a complete clustering of the graph nodes, the proposed algorithm takes into account the fact that not every participating node in the network needs to belong to a community. Another advantage is that the method does not require to specify the number of clusters; this number is usually not known in advance and is difficult to estimate. The computational process is very efficient, and the effectiveness of the proposed method is demonstrated in a few real-life examples.",
keywords = "Dense subgraph, community, hierarchical clustering, matrix reordering, partial clustering, social network",
author = "Jie Chen and Yousef Saad",
year = "2012",
month = "6",
day = "6",
doi = "10.1109/TKDE.2010.271",
language = "English (US)",
volume = "24",
pages = "1216--1230",
journal = "IEEE Transactions on Knowledge and Data Engineering",
issn = "1041-4347",
publisher = "IEEE Computer Society",
number = "7",

}

TY - JOUR

T1 - Dense subgraph extraction with application to community detection

AU - Chen, Jie

AU - Saad, Yousef

PY - 2012/6/6

Y1 - 2012/6/6

N2 - This paper presents a method for identifying a set of dense subgraphs of a given sparse graph. Within the main applications of this dense subgraph problem, the dense subgraphs are interpreted as communities, as in, e.g., social networks. The problem of identifying dense subgraphs helps analyze graph structures and complex networks and it is known to be challenging. It bears some similarities with the problem of reordering/blocking matrices in sparse matrix techniques. We exploit this link and adapt the idea of recognizing matrix column similarities, in order to compute a partial clustering of the vertices in a graph, where each cluster represents a dense subgraph. In contrast to existing subgraph extraction techniques which are based on a complete clustering of the graph nodes, the proposed algorithm takes into account the fact that not every participating node in the network needs to belong to a community. Another advantage is that the method does not require to specify the number of clusters; this number is usually not known in advance and is difficult to estimate. The computational process is very efficient, and the effectiveness of the proposed method is demonstrated in a few real-life examples.

AB - This paper presents a method for identifying a set of dense subgraphs of a given sparse graph. Within the main applications of this dense subgraph problem, the dense subgraphs are interpreted as communities, as in, e.g., social networks. The problem of identifying dense subgraphs helps analyze graph structures and complex networks and it is known to be challenging. It bears some similarities with the problem of reordering/blocking matrices in sparse matrix techniques. We exploit this link and adapt the idea of recognizing matrix column similarities, in order to compute a partial clustering of the vertices in a graph, where each cluster represents a dense subgraph. In contrast to existing subgraph extraction techniques which are based on a complete clustering of the graph nodes, the proposed algorithm takes into account the fact that not every participating node in the network needs to belong to a community. Another advantage is that the method does not require to specify the number of clusters; this number is usually not known in advance and is difficult to estimate. The computational process is very efficient, and the effectiveness of the proposed method is demonstrated in a few real-life examples.

KW - Dense subgraph

KW - community

KW - hierarchical clustering

KW - matrix reordering

KW - partial clustering

KW - social network

UR - http://www.scopus.com/inward/record.url?scp=84861732705&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84861732705&partnerID=8YFLogxK

U2 - 10.1109/TKDE.2010.271

DO - 10.1109/TKDE.2010.271

M3 - Article

VL - 24

SP - 1216

EP - 1230

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

SN - 1041-4347

IS - 7

M1 - 5677532

ER -