Spectral Partitioning Using Fiedler Vector

From Clairlib
Jump to: navigation, search

In this tutorial you will use Clairlib module Clair::Network::Spectral to partition the Karate Club network into two subgraphs. Clair::Network::Spectral implements Spectral Partitioning using Fiedler Vector (i.e. the second smallest eigenvector).

Contents

Dataset

The dataset used in this tutorial is the Karate Club network, a network of friendships between the 34 members of a karate club at a US university, as described by Wayne Zachary in 1977. The network file is in GML format:

Creator "Mark Newman on Fri Jul 21 12:39:27 2006"
graph
[
  node
  [
    id 1
  ]
  .
  .
  node
  [
    id 34
  ]
  edge
  [
    source 2
    target 1
  ]
  .
  .
  edge
  [
    source 34
    target 33
  ]
]

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::Spectral object

Create a new Clair::Network::Spectral by calling the constructor and passing the following parameters:

  • Network: a Clair::Network object.
  • Splitting Method (optional): to specify the method used to choose the splitting value. This can take one of the following options:
    • Bisection: The splitting value is the median of the Fiedler Vector components.
    • Gap: The splitting value is in the middle of largest gap within the Fiedler Vector components.
    • Sign (Default): The splitting value is 0.

The splitting value is used to partition the network into two parts by choosing all nodes whose corresponding Fiedler Vector component is larger than splitting value to be in one partition and the remaining nodes to be in the other partition. For the purpose of this tutorial we will use the "bisection" method.

use Clair::Network::Spectral;
$spectral = new Clair::Network::Spectral($net,"sign");

Partition the network

To partition the network, simply call get_partitions subroutine via $spectral object. get_partitions returns the nodes of each of the partitions in an array.

my(@parta,@partb) = $spectral->get_partitions();

You can print the result of partitioning the Karate Club network in by looping through the two resulting arrays or simply by using the dumper.

use Data::Dumper 
print "PartA = ",Dumper(@parta),"\n";
print "PartB = ",Dumper(@partb),"\n";

The output should be as follows:

PartA = [
         '25',
         '15',
          .
          .
         '31',
         '30'
        ];
PartB = [
         '13',
         '8',
          .
          .
         '18',
         '12'
       ];


You can get the splitting value that was used to do the partitioning by calling get_splitting_value().

my $splitting_value = $spectral->get_splitting_value();

The result should be 0.0625504557748447. You can also get the Fiedler Vector by

 my $splitting_value = $spectral->get_fiedler_vector();

You can change the splitting method anytime and then redo the partitioning using the new method.

 $spectral->set_splitting_method("gap");
Personal tools
Namespaces

Variants
Actions
Main Menu
Documentation
Clairlib Lab
Community
Development
Toolbox