Fast Enumeration of Large k-Plexes

Overview

This page contains the software and data used in the paper "Fast Enumeration of Large k-Plexes" authored by Alessio Conte, Donatella Firmani, Caterina Mordente, Maurizio Patrignani, and Riccardo Torlone and published at the 23rd SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2017). The purpose of this work is the enumeration of large k-plexes in networks.

A k-plex is a set of nodes such that each of them has edges with all the others with the possible exception of k missing neighbours (including itself). So, for example, for k=1 k-plexes are cliques, for k=2, each node may miss one edge, etc.

Our software speeds up the search of several orders of magnitude with respect to traditional k-plex enumeration algorithm.

Software Instructions

General instructions

We provide two .sh files containing two examples of linux scripts to start the experiments
It is important that all files are placed into the same directory

To launch the computations two ways are possible:

Using the .sh script
- Open a shell and go in the main directory of the project
- Execute the following commands:
```
               chmod +x script_name.sh
               ./script_name.sh
      
```
Directly issuing the commands
- Open a shell and go in the main directory of the project
- Copy the content of the script file into the shell

Input file format

The input is a graph in NDE (Nodes-Degrees-Edges) format that has to be placed in the main project directory. A file specifying a graph in the NDE 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.

As our code does not require information on the input/output degrees (our graphs are undirected), some parts of the NDE format are intentionally left blank. An example (example.nde) can be found in the compressed files.

Finding all largest k-plexes

Example of command:

 
     java -jar max_kplex.jar example.nde 2

Parameters:

the jar file
the input .nde file containing the graph
the k specifying the maximum k-plex you are searching for

Output example:

      cliqueness time:0.115
      coreness time:0.007
      Launching Berlowitz...
      Building graph from file graph.txt...
      Graph is ready
      Starts enumerating connected k-plexes..
      Output will be found at output_file_connected
      time for enumerating 6 kplexes: 0.035848
      max:4 4,5,6,7
      Running time for enumerating 6 kplexes: 0.035997

Where "max:4" indicates that 4 is the size of the maximum k-plex found and "4,5,6,7" are the ids of the nodes composing the maximum k-plex

Finding all maximal k-plexes non-smaller than S

Example of command:

 
     java -jar all_kplex.jar example.nde 2 2

Parameters:

the jar file
the input .nde file containing the graph
the k specifying the maximum k-plexes you are searching for
the minimum size of the searched k-plexes

Output example:

      total time6.303
      13
      printing k-plexes:
      3,5,6
      1,3,5
      3,4,5
      2,4,7
      2,3,4
      5,6,7
      2,4,5
      4,6,7
      1,3
      1,2,3
      3,5
      5,6
      4,7
      final # of k-plexes found:13

Data Used in the Experiments

We tested the software on a mix of real-world networks with various sizes and characteristics. All our networks are taken from the LASAGNE repository.

Software Download

LargePlexes.rar (updated 2018-05-08) [22.2 MB]
LargePlexes.tgz (alternative format) (updated 2018-05-08) [33.0 MB]

Contacts

Ph.D Alessio Conte (conte@di.unipi.it)
Computer Science Department, University of Pisa,
Largo B. Pontecorvo, 3 -- 56127, Pisa, Italy.
Ph.D. Donatella Firmani (donatella.firmani@uniroma3.it)
Engineering Department, Roma Tre University,
Via della Vasca Navale, 79 - 00146, Rome, Italy.
Dr. Caterina Mordente (c.mordente@be-tse.it)
Be Think Solve Execute,
Viale dell'Esperanto, 71 -- 00144 Roma, Italy.
Prof. Maurizio Patrignani (patrigna@dia.uniroma3.it)
Engineering Department, Roma Tre University,
Via della Vasca Navale, 79 - 00146, Rome, Italy.
Prof. Riccardo Torlone (torlone@dia.uniroma3.it)
Engineering Department, Roma Tre University,
Via della Vasca Navale, 79 - 00146, Rome, Italy.

References

[Berlowitz et al.]

Devora Berlowitz, Sara Cohen, and Benny Kimelfeld. "Efficient enumeration of maximal k-plexes". In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD '15, pages 431-444, New York, NY, USA, 2015. ACM.

[Conte et al.]

Alessio Conte, Donatella Firmani, Caterina Mordente, Maurizio Patrignani, Riccardo Torlone. Fast Enumeration of Large k-Plexes. In, Tina Eliassi-Rad, Ravi Kumar, editors, 23rd SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2017), ACM, pages 115-124, 2017.

[LASAGNE]

LASAGNE Laboratory of Algorithms, modelS, and Analysis of Graphs and NEtworks. https://www.pilucrescenzi.it/wp/networks/

This page is maintained by Maurizio Patrignani (patrigna@dia.uniroma3.it).