This folder contains the source code of the algorithm in 

[Conte et al.] Fast Enumeration of Large k-Plexes - KDD 2017

And an explaination on how to run the code.


Credits:
Ph.D. Alessio Conte, University of Pisa (conte@di.unipi.it)
Ph.D. Donatella Firmani, Roma Tre University (donatella.firmani@uniroma3.it)
Dr. Caterina Mordente, Be Think Solve Execute (c.mordente@be-tse.it)
Prof. Maurizio Patrignani, Roma Tre University (patrigna@dia.uniroma3.it)
Prof. Riccardo Torlone, Roma Tre University (torlone@dia.uniroma3.it)


The code includes that of the algorithm in:
[Berlowitz et al.] Effcient enumeration of maximal k-plexes - SIGMOD 2015
Kindly provided by the authors Devora Berlowitz, Sara Cohen and Benny Kimelfeld, which is used as a blackbox by our algorithm.

It can be found in the folders "kplex_without_improvments_enum" and "kplex_without_improvments_max", and received minimal modifications (mainly, some print instruction have been removed and some input parameters have been modified to better conform to our code).


Our algorithm can be run as follows:

FOR LISTING ALL LARGE K-PLEXES: 

------------------
java -jar all_kplex.jar graph.nde k minSize
------------------

(graph file must be in this folder)


EXAMPLE:
The command  "java -jar all_kplex.jar example.nde 2 3" finds all 2-plexes of size at least 3.

The last lines of the output contain, in this order:
- total running time (seconds)
- the list of k-plexes found
- their number (on the last line)


FOR FINDING ONLY THE MAXIMUM K-PLEX:

------------------
java -jar max_kplex.jar graph.nde k
------------------

The output contains in the last lines the running time and the largest k-plex (as well as its size)


GRAPH FORMAT:

The input is a graph in NDE format that has to in the main project directory. A file specifying a graph in the NDE (Nodes-Degrees-Edges) format should contain the following information

-One line containing the number of nodes

-For each node, one line containing the index of the node and its degree.

-For each edge, one line containing the indices of its extremes.

An example can be found as example.nde (as our code does not require information on the degrees, those lines are intentionally left blank)