File Coverage

blib/lib/Graph/Similarity/SimRank.pm

Criterion	Covered	Total	%
statement	7	9	77.7
branch			n/a
condition			n/a
subroutine	3	3	100.0
pod			n/a
total	10	12	83.3

package Graph::Similarity::SimRank;

use strict;
use warnings;
use Moose;
use Graph;

with 'Graph::Similarity::Method';

our $VERSION = '0.02';

has 'graph'     => (is => 'rw', isa => 'Graph', required => 1);
has 'constant'  => (is => 'rw', isa => 'Num', default => 0.6);

__PACKAGE__->meta->make_immutable;
no Moose;

# Set constant value. In the paper, it's 0.8
sub setConst {
    my ($self, $value) = @_;
    $self->constant($value);
}

sub calculate {
    my $self = shift;

    my $g = $self->graph;
    my $c = $self->constant;
    my $itr = $self->num_of_iteration;

    # Initialize
    my @all = $g->vertices;
    my %R;
    for my $v1 (@all) {
        for my $v2 (@all) {
            if ($v1 eq $v2){
                $R{$v1}{$v2} = 1;
            }
            else {
                $R{$v1}{$v2} = 0;
            }
        }
    }

    for(my $i=0; $i<$itr; $i++){
        for my $v1 (@all) {
            for my $v2 (@all) {
                if ($v1 eq $v2){
                    $R{$v1}{$v2} = 1;
                }
                else {
                    my @p1 = $g->predecessors($v1);
                    my @p2 = $g->predecessors($v2);

                    if (scalar(@p1) == 0 || scalar(@p2) == 0){
                        $R{$v1}{$v2} = 0;
                    }
                    else {
                        my $sum = 0;
                        for my $p1 (@p1){
                            for my $p2 (@p2) {
                                $sum += $R{$p1}{$p2};
                            }
                        }
                            $R{$v1}{$v2} = ( $c / (scalar(@p1) * scalar(@p2)) ) * $sum;
                    }
                }
            }
        }
    }
    $self->_setSimilarity(\%R);
    return \%R;
}


=head1 NAME

Graph::Similarity::SimRank - SimRank implementation

=head1 VERSION

Version 0.02

=head1 SYNOPSIS

Please see L<Graph::Similarity>

=head1 DESCRIPTION

This is the implementation of the below paper.

B<Glen Jeh, Jennifer Widon, "SimRank: A Measure of Structural-Context Similarity">

=head1 METHODS

=head2 setConst($const)

The const value is 0.6 by default becasue wikipedia mentions this is more acturate value,
whereas the paper uses 0.8.
You can change this to what you want. The value should be between 0 and 1.

=head2 calculate()

This calculates SimRank. The algorithm is Naive Method in section 4.4.1 in the paper.

=head1 AUTHOR

Shohei Kameda, C<< <shoheik at cpan.org> >>

=head1 LICENSE AND COPYRIGHT

Copyright 2012 Shohei Kameda.

This program is free software; you can redistribute it and/or modify it
under the terms of either: the GNU General Public License as published
by the Free Software Foundation; or the Artistic License.

See http://dev.perl.org/licenses/ for more information.


=cut

1; # End of Graph::Similarity::SimRank