ODES: Overlapping DEnse Sub-graphs

Download ver 0.4

News: A paper on ODES has been accepted, Bioinformatics, Vol. 26, No. 21. (1 November 2010), pp. 2788-2789; doi: 10.1093/bioinformatics/btq514


ODES is a pthreads parallelized exact algorithm to enumerate all maximal sub-graphs of a graph that exceed a specified cutoff density of at least 1/2, even if they overlap. The following is proved in our paper:

Theorem
A connected graph G, with density den(G) >= 0.5, and number of verticies n >= 3, has at least one non-cut vertex w where degree d(w) <= the average degree of vertices in G. Removal of w from G does not decrease the density of G.

The theorem says that vertices can iteratively be removed from a sufficiently dense graph, without decreasing its density or cutting it into disconnected pieces, until all that remains is a single pair of connected vertices. The algorithm goes the other way: Starting with the set S of all connected pairs of vertices (single-edge sub-graphs), an iteration consists of looking for adjacent vertices that can be added to each member of S consistent with the theorem. A member m of S to which a vertex can be added is placed with the added vertex into a new set S' for the next iteration, one for each new vertex that can be added to m. The brute-force search space of a non-clique graph G is thus confined to the actual dense sub-graphs of G, and since each iteration is independent, it can be handled by its own thread. During any iteration, a dense subgraph is saved for output if it is of sufficient size, and no more vertices can be added.

Features yet to implement (see paper):

  • run algorithm within a series of density bins that span the interval 0.5 to 1.0
  • replace binary search with a fast hash function
  • output some indication of overlaps

    • Due to its high complexity, ODES does not scale well to very large dense sub-graphs. This can be ameliorated, however, by using ODES in conjunction with a heuristic method. If heuristically determined edges from large dense sub-graphs H are excluded from the initial single-edge sub-graph list S for ODES, but retained in the subsequent search space, ODES will find all other overlapping dense sub-graphs outside of H, along with those dense sub-graphs that overlap H containing at least one edge E outside of H that can be the last one chosen according to our theorem. Dense sub-graphs overlapping H that have no such edge E outside of H will not be found. See the README file for details to turn this feature on.

    SourceForge.net Logo

    James Long
    International Arctic Research Center
    University of Alaska Fairbanks
    PO Box 757340
    Fairbanks, AK 99775-7340
    USA
    Voice: (907) 474-2440

    jlong@alaska.edu
    International Arctic Research Center


    Chris Hartman
    Department of Computer Science
    University of Alaska Fairbanks
    PO Box 756670
    Fairbanks, AK 99775-6670
    USA