Graph Partitioning Using GirvanNewman Algorithm

From CLAIRlib

In this tutorial, you will use Clair::Network::GirvanNewman 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::GirvanNewman object

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

use Clair::Network::GirvanNewman;
$GN = new Clair::Network::GirvanNewman($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 = $GN->partition();

$graphPartition is a hash with "node id" as key and "partition number" as value. The hierarchy structure for each node is represented as (0|1|2|1|...). So the number between "|" is the partition the node belongs to in a specific hierarchy.

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|1|1|2|3|3|4|4|7|8|8|9|10|10|11|4|4|5|6|6|6|7|8|8|8|8|9|9|9|9|9|9|20|21',
         '32' => '0|1|1|2|1|1|2|2|5|6|6|7|8|8|9|3|3|4|4|4|4|5|6|6|6|6|7|7|7|7|7|7|6|7',
         . . .
         . . .
         '19' => '0|1|1|2|3|3|4|4|7|8|8|9|10|10|11|4|4|5|6|6|6|7|8|8|8|8|9|9|9|9|9|10|17|1',
         '5' => '0|0|0|0|4|4|5|6|3|1|1|2|2|2|2|7|8|11|12|8|8|9|16|17|17|19|11|11|4|13|10|30|0|0'
        };