File Coverage

lib/Graph/Algorithm/HITS.pm

Criterion	Covered	Total	%
statement	13	15	86.6
branch			n/a
condition			n/a
subroutine	5	5	100.0
pod			n/a
total	18	20	90.0

package Graph::Algorithm::HITS;

use strict;
use 5.008_005;
our $VERSION = '0.02';

use Moo;
use Graph;
use PDL;
use Carp;

has graph => (is => 'ro', required => 1);
has adj_matrix => (is => 'ro', lazy => 1, builder => '_adj_matrix_builder');
has trans_adj => (is => 'ro', lazy => 1, builder => '_trans_adj_builder');
has trans_x_adj => (
    is => 'ro',
    lazy => 1,
    default => sub {
        my $self = shift;
        $self->trans_adj x $self->adj_matrix;
    }
);

has hub_matrix => (
    is => 'rw',
    lazy => 1,
    default => sub {
        my $self = shift;
        my $size = $self->graph->vertices;
        ones 1,$size;
    }
);

has auth_matrix => (
    is => 'rw',
    lazy => 1,
    default => sub {
        my $self = shift;
        my $size = $self->graph->vertices;
        ones 1,$size;
    },
);

sub BUILD {
    my $self = shift;
    # make sure it's directed graph
    unless ($self->graph->is_directed) {
        croak 'Graph needs to be directed';
    }
}

#Create adjacency matrix from graph
sub _adj_matrix_builder {
    my $self = shift;
    my $matrix = [];
    for my $v1 (sort $self->graph->vertices ) {
        my @row = ();
        for my $v2 (sort $self->graph->vertices ){
            if ($v1 eq $v2) {
                push @row, 0;
            }else {
                if ($self->graph->has_edge($v1, $v2)){
                    push @row, 1;
                }else {
                    push @row, 0;
                }
            }
        }
        push @$matrix, \@row;
    }
    return pdl $matrix;
}

#Create transpose adjacency matrix
sub _trans_adj_builder {
    my $self = shift;
    return transpose $self->adj_matrix;
}

sub iterate {
    my ($self, $itr) = @_;
    for (1..$itr) {
        my $m =  $self->trans_x_adj x $self->auth_matrix;
        $self->auth_matrix($m/$self->_get_sum($m));
    }
    my $m = $self->adj_matrix x $self->auth_matrix;
    $self->hub_matrix($m/$self->_get_sum($m));
}

sub _get_sum {
    my ($self, $m) = @_;
    my $result = unpdl $m;
    my $sum=0;
    $sum += shift @$_ for (@$result);
    return $sum;
}

sub get_authority {
    my $self = shift;
    my $ref = unpdl $self->auth_matrix;
    my %result;
    for my $v (sort $self->graph->vertices) {
        $result{$v} = shift @{ shift @$ref };
    }
    return \%result;
}

sub get_hub {
    my $self = shift;
    my $ref = unpdl $self->hub_matrix;
    my %result;
    for my $v (sort $self->graph->vertices) {
        $result{$v} = shift @{ shift @$ref };
    }
    return \%result;
}

1;
__END__