Im almost certain I am not missing any k factor. I've been carefully checking for that. The algorithm would have fallen apart on any unweighted graph with hundreds of nodes with at least 2 connections each.

EDIT: PS I read the paper you linked before your ninja edit :)