Каким образом написать скрипт для автоматического построения реф-дерева?

Идея раз: подсчитываем, на кого больше ссылок parent, его ставим во главе иерархии.

Не) Тут бинар, на каждого всегда двое максимум.

По поводу главы иерархии, в принципе можно и ручками вбить, так как известен логин. А вот дальше как от него отталкиваться, если честно в замешательстве. Сейчас копаю nested sets, но что-то мне подсказывает что либо можно это сделать проще, либо я слишком туплю. Мне бы хотя бы набросочек, чтобы дальше от него отталкиваться.

Насколько я помню, при такой структуре базы, т.е. когда только родитель хранится - только перебором.

Кроме nested sets есть еще materialized path и Adjacency List ну и гуглите по этим терминам или http://habrahabr.ru/post/46659/ например