Finding large dense subgraphs in relational graphs

This paper considers the problem of finding large dense subgraphs in relational graphs, i.e., a set of graphs which share a common vertex set. We present an approximation algorithm for finding the densest common subgraph in a relational graph setbased on an extension of Charikar's linear programming basedapproach for finding the densest subgraph in a single graph. We also present a simple greedyheuristic which can be implemented efficiently foranalysis of larger graphs. We give graph dependent bounds on thequality of the solutions returned by our methods. Lastly,we show by empirical evaluation on severalbenchmark datasets that our method out-performs existing approaches.
Authors Name: 
Vinay Jethava
Niko Beerenwinkel
S.I. 2014: 
Tuesday, September 8, 2015 - 16:15 to 16:40