LINEは登録時にあなたの電話帳の内容を送信するか聞いてきているでしょう。普通の人は自分の個人情報の電話帳の登録をサーバーに送るのでLINE側は受け取った電話帳の登録を比較して友達だろうといえますよ。他にもロジックがあるでしょうけど