#
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.

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