That is a fascinating paper, and engagingly written. I think the most surprising thing from it was that this weird almost-a-spanning-tree structure arises from two simple, local rules:

1. People tend to date other people with a similar amount of past sexual experience.

2. People avoid dating the exes of other people who are close to them in the relationship graph, since this makes them look bad to their friends, exes, and so on. This accounts for the lack of short cycles.

When the authors applied these rules in a computer simulation, they ended up with results almost indistinguishable from the empirically-observed sex-graphs.