Graph Partitioning Using Krenighan-Lin Algorithm

From CLAIRlib

In this tutorial, you will use Clair::Network::KrenighanLin to partition Karate Club network. For more information about Karate Club network, see Spectral Partitioning Using Fiedler Vector tutorial.

Read in the network file and create a Clair::Network object

First you need to create a Clair::Network::Reader::GML object

use Clair::Network::Reader::GML;
my $reader=new Clair::Network::Reader::GML();

Then, pass the network filename to the read_network subroutine via the $reader object. This will return a Clair::Network object.

use Clair::Network;
my $filename = "karate.gml";
my $net = $reader->read_network($filename);

Create a Clair::Network::KrenighanLin object

Create a new Clair::Network::KrenighanLin by calling its constructor

use Clair::Network::KrenighanLin;
$KL = new Clair::Network::KrenighanLin($net);

Partition the graph

To partition the graph, simply call partition() subroutine via the $GN object. partition() returns the result as a hash.

my $graphPartition = $KL->generatePartition();

$graphPartition is a hash with "node id" as key and "partition number (0/1)" as value.

You can use the dumper to print the contents of $graphPartition

use Data::Dumper
print Dumper($graphPartition);

The output will be something like

$VAR1 = {
         '33' => 0,
         '32' => 0,
         '21' => 0,
         '7' => 1,
         '26' => 0,
         '17' => 1,
         '2' => 1,
         '1' => 1,
         '18' => 1,
         '30' => 0,
         '16' => 0,
         '27' => 0,
         '25' => 0,
         '28' => 0,
         '14' => 1,
         '20' => 1,
         '24' => 0,
         '10' => 1,
         '31' => 0,
         '11' => 1,
         '22' => 1,
         '13' => 1,
         '23' => 0,
         '29' => 0,
         '6' => 1,
         '3' => 1,
         '9' => 0,
         '12' => 1,
         '15' => 0,
         '8' => 1,
         '4' => 1,
         '34' => 0,
         '19' => 0,
         '5' => 1
       };