Where can I get Twitter dataset with 125K nodes and 2M edges that show relationships between users? An edge from user i to user j means user j follows user i.
Does it have to be a follower-following relationship specifically? If not, you might have more options. Specifically, you could use the Twitter StreamingAPI to collect your own data and process into a user-mention network (one could infer a follower-following relationship this way). There are also many other datasets available from which you can process in the same manner:
As per request from Twitter the data is no longer available.
Unfortunately it is no longer officially online. You could try to contact them, or ...
Also, the graph itself is available (link).
You could try their other datasets, in particular the Higgs Twitter:
UPDATE: I found a potential source on academic torrents. Use at your own peril.