Performance

The key constraint on the DPP algorithm is the identification of k-plexes. In an attempt to circumvent this limitation, the algorithm first identifies cliques (fully connected sets of vertices) using the Bron-Kerbosch algorithm. All cliques are inherently k-plexes as well, so these cliques are set aside. Then, k-plexes are identified in a subgraph of the remaining vertices. This strategy makes the k-plex search much more efficient, but it still remains the primary limitation on the algorithm.

Currently, the k-plex search is performed using a variation on the Bron-Kerbosch algorithm, although more efficient algorithms.

Performance will vary greatly depending on the connectivity and other details. But while optimizing the implementation, we ran rough benchmarks on a MacBookPro with a 2.6 GHz Intel Core i7 processor and 16GB RAM. The current implementation of the algorithm takes approximately:

• 80 seconds for a 100-vertex functional network with 500 time steps

Potential further optimizations include:

• Implementing a lower level k-plex search algorithm.
• Refining the stitching of communities across time.
• Reducing RAM usage by storing the algorithm output in structured arrays rather than cell arrays.
• Utilizing the parallel toolbox.