Hard to find information on the English-speaking internet, but looks like Yandex began to focus on link analysis only in 2004: https://yandex.ru/company/press_releases/2004/0326/