Journal
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
Volume 24, Issue 7, Pages 1216-1230Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2010.271
Keywords
Dense subgraph; social network; community; matrix reordering; hierarchical clustering; partial clustering
Categories
Funding
- US National Science Foundation (NSF) [DMS-0810938]
- Minnesota Supercomputer Institute
- University of Minnesota
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available