Axioms of Density: How to Define and Detect the Densest Subgraph

Detecting the densest subgraph is one of the most important problems in graph mining and has a variety of applications. Although there are many possible metrics for subgraph density, there is no consensus on which density metric we should use. In this paper, we provide formal guidelines to choose an appropriate density metric using four axioms. These axioms capture the necessary conditions any density metric should satisfy to conform with our intuition. We investigate the existing density metrics to see whether or not they satisfy these four axioms and determine which ones violate at least one of the four. In addition, we suggest a new density metric, the discounted average degree, which is an extension of the average degree metric and which satisfies all four axioms. We also show how to obtain an optimum densest subgraph for small graphs using typical density metrics, including our new density metric, by using mixed integer quadratic programming. Finally, we develop a new heuristic algorithm to quickly obtain a good approximate solution for large graphs. Our computational experiments on real-world graphs showed that our new heuristic algorithm performs best in terms of the quality of the solutions.

By: Hiroki Yanagisawa and Satoshi Hara

Published in: RT0972 in 2016

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

RT0972.pdf

Questions about this service can be mailed to reports@us.ibm.com .