Focusing on 1): if "most popular follower" means "follower with the most followers", you could try one of three strategies.
First, just check which of the the top 100 (1000) most-followed users follow the celebrity - this will likely eliminate the heaviest hitters immediately.
For accounts with normal amount of followers, do as you already do.
For the in-betweeners,
Pick your celebrity.
For a random 1% (.1%) of his/her followers:
Retrieve list of people followed by this follower
For each user followed by a follower of the celebrity:
Increase number of people following this user by 1
For each user in the top 1% (10%, .1%) of the above table of users:
Retrieve number of followers
Report user with highest number of followers from the above
This is, of course, based on the idea that often-followed users who follow a celebrity will also have many followers among the followers of the celebrity. Results will become more accurate as you poll more followers, of course.
(I don't use Twitter or their API, and the above may be completely wrong.)
see, this is what I came for. I believe there's room for optimization within the limits I have to adhere to right now. your approach seems like a stab at it and I'll think this through again in a bit if it makes sense. but you're hitting the nail on the head in terms of where my problem is, i can't change what twitter does, i can display partial results but it's suboptimal in many ways, so how can i make these partial results the best possible quality? this is where you answer seems to make sense - thanks. i'll think about this one for sure.
First, just check which of the the top 100 (1000) most-followed users follow the celebrity - this will likely eliminate the heaviest hitters immediately.
For accounts with normal amount of followers, do as you already do.
For the in-betweeners,
This is, of course, based on the idea that often-followed users who follow a celebrity will also have many followers among the followers of the celebrity. Results will become more accurate as you poll more followers, of course.(I don't use Twitter or their API, and the above may be completely wrong.)