Hi,
Short answer: No, this dataset would not fit on one server.
100-1000 favorites per user would mean an expected value of 549.5 favorites per user (if random distribution is assumed). Multiplied with 100M users that's a total of 54.95 billion favorite-relationships. This is out of range of the current implementation (although a future version might support it). From a disk space point of view there are certainly server disk arrays that can store that many relationships, 54.96 billion relationships would consume just over 1.8TB of disk space. Then there are storage for the nodes, and the properties you might want to store with the nodes and relationships in addition to that 1.8TB.
As for the speediness of traversing out users with similar favorites:
First of all, your definition of "similar favorites" is vague, so I'll interpret it as users with the same favorites.
The problem with this query is the sheer number of such users:
If each user has on average F favorites, there are U users and B books in the system, then each book will on average be favorited by F' = F*U/B users. With your numbers (U=100M, B=1M, F=100-1000) this means each book is favorited by 10-100 thousand users. The expected number of users that favors a particular book would be 54950 users.
This means that when starting from one user, finding all users with the same favorites would need to traverse from that user to 100-1000 books, and from each book to 10'000-100'000 other users. This is a total of 1 million - 100 million users, with an expected size of the result set being just over 30 million. However these are likely to not be 1M-100M unique users, but since filtering out duplicates is an additional operation the fact that the dataset contains duplicated will not improve the traversal speed.
However, your question didn't state that you were interested in finding all such users. If you were satisfied with getting only five random such users you would simply do a depth first traversal and stop after finding as many (five) users as you wanted, and not pay any penalty for the fact that there are millions of other matching user nodes.
When traversing through the graph, Neo4j loads the nodes and relationships lazily as they are needed. This means that the speed of your traversal is constant over the structure you are traversing. In this case the structure is two relationships, one from the initial user to the book, and one from the book to another user. That is two relationships hops, a constant time operation. If you traverse a fixed number of these (five in the previous paragraph) you end up with a traversal time of the number of result elements multiplied with the traversal time for one. For finding all such users, the equation is similar, but the numbers of result elements is bigger. However the traversal time is only dependent on the number of elements you actually traverse. The total size of your graph does not effect the traversal time (as it would in a relational database). So if F and F' stayed constant while U increased you would still get the same traversal speed for your query.
Since my laptop does not have a 2TB disk (and since Neo4j currently does not handle that many relationships) I couldn't run simulations with a dataset distributed exactly according to your specifications. Instead I created two datasets, representing only the users and books seen in one traversal. One dataset where the starting user has 100 favorite books, and each book is the favorite of 10 thousand users (the number of expected users to have a random book as a favorite if each user has 100 favorites). And one dataset where the starting user has 1000 favorite books, and each book is the favorite of 100 thousand users.
The second dataset was too large for Neo4j to be able to fit it in the caches when running on my laptop, so I only have traversal figures for running with uncached data. The execution time in this case, for traversing over that entire graph (representing a worst case query according to your description) was just over 2000seconds. That is a traversal speed of 50'000 relationships / second. This is with a pretty cheap mechanical (spinning) disk, an SSD would probably increase the speed at least five times.
The first dataset was much more cache friendly. With cold caches I had a traversal speed of slightly less than 9 seconds (ca 115'000 relationships traversed/second), and 0.9 seconds with warm caches (ca 1'150'000 relationships traversed/second). The first improvement (over the cold cache case of the large dataset) in traversal speed here is due to the fact that the dataset fits in the filesystem cache. Then the Neo4j caches gives an additional 10x performance improvement over that, which is what we see in the case with warm caches.
Cheers,
Tobias