По номеру телефона. Вконтакте в настройках профиля есть пункт, типа «синхронизировать с контактами» или что-то в этом духе. Если нажать там галку, ВК проходит по всем контактам из адресной книги и проверяет, зарегистрированы ли они в ВК. И предлагает дружить))