Love is a Battlefield Spanning-Tree Network with no 4-Cycles

by Kieran Healy on August 13, 2004

Quick, in high school were you ever told not to date your old girlfriend’s current boyfriend’s old girlfriend? Or your old boyfriend’s current girlfriend’s old boyfriend? Probably not. But I bet you never did, either. This month’s “American Journal of Sociology”: has a very nice “paper”: (subscription only, alas) by “Peter Bearman”:, “Jim Moody”: and “Katherine Stovel”: about the structure of the romantic and sexual network in a population of over 800 adolescents at “Jefferson High” in a midsized town in the midwestern United States. They got a pretty well-bounded population (a high school included in the “AddHealth”: study) and mapped out all the connections between the students. Read on for the lurid details.

The authors found that the observed network isn’t well-represented by existing models, which are mainly concerned with predicting how STDs propagate through populations and have often been based on ego-centered network data. These are surveys where you ask the respondents about their sexual networks, but the respondents aren’t necessarily in the same network. Here’s a picture of four kinds of network:

Core models posit a small group of very sexually-active individuals who occasionally come into contact with (and infect) those outside the core. Bridge models think in terms of an infected component and an uninfected component which join at some point. The biggest network component observed at Jefferson High turned out to be the fourth type, however: a “spanning tree” structure. This is “a long chain of interconnections that stretches across a population, like rural phone wires running from a long trunk line to individual houses … characterized by a graph with few cycles, low redundancy, and consequently very sparse overall density.” When they tried to simulate this bit of the graph structure, the authors found they could get _most_ of the way there using a simple model where the probability of a tie depended on individuals having a preference for others with the same amount of sexual experience as themselves.[1] But simulated networks based on this model didn’t quite match the properties of the observed network. In particular, while the simulations had “cycles”: of length 4, the Jefferson High network did not.

What’s a cycle? If you start at Crooked Timber and click over to “Dan Drezner”: and then click Dan’s link to “Mark Kleiman”: and then return to Crooked Timber via Mark’s link to us, you’ve completed a cycle of length 3: a walk through the network that starts and ends with the same actor and where all the other actors are different and not repeated along the way. Cycles of length 3 are the smallest possible cycles. When it comes to tracing paths through heterosexual relationships, though, the smallest possible cycles are of length 4. In order to make a cycle beginning and ending with yourself, you need two members of the opposite sex plus one intervening individual the same sex as you. It turns out that this kind of cycle is just not found in the Jefferson High network. Although there’s no explicit taboo or social norm against that kind of pattern, nevertheless people just don’t date their old partner’s current partner’s old partner.

bq. From the perspective of males or females (and independent of the pattern of “rejection”), a relationship that completes a cycle of length 4 can be thought of as a “seconds partnership,” and therefore involves a public loss of status. Most adolescents would probably stare blankly at the researcher who asked boys: Is there a prohibition in your school against being in a relationship with your old girlfriend’s current boyfriend’s old girlfriend? It is a mouthful, but it makes intuitive sense. … For adolescents, the consequence of this prohibition is of little interest: what concerns them is avoiding status loss. But from the perspective of those interested in understanding the determinants of disease diffusion, the significance of a norm against relationships that complete short cycles is profound. The structural impact of the norm is that it induces a spanning tree, as versus a structure characterized by many densely connected pockets of activity (i.e., a core structure).

Individuals constitute social structures, yet those structures have properties that the members do not know about and can’t easily grasp — our vast amount of folk knowledge about our social relations notwithstanding. These properties can have all kinds of serious consequences. The “No 4-cycles” rule is interesting because on the one hand it reflects a very simple bit of structure and it’s not something that’s prohibited in any strong normative sense. I’m not sure I buy the authors’ status-based explanation for it, though. They suggest some alternatives — “‘jealousy’ or the avoidance of too much ‘closeness,’ a sentiment perhaps best described unscientifically as the ‘yuck factor.'” I find the yuck-factor idea more intriquing: I wonder whether it’s more likely to show up at the limits of easily-described network structures. Bigger cycles defy easy verbal description altogether and are also subject to lack of information because some of the ties will be in the past or far away, so they’re not subject to avoidance. Dyadic ties are easy to keep track of. Short cycles are still tricky to grasp, but it’s not that hard, so being able to trace them triggers the taboo-like “yuck” response.

As for consequences, the spanning-tree structures created by experience homophily plus the 4-cycle rule are very effective at propagating diseases along their chains. But they are also easy to break in a way that core-type networks are not:

bq. Under core and inverse core structures, it matters enormously _which_ actors are reached, while under a spanning tree structure the key is not so much which actors are reached, just that some are. This is because given the dynamic tendency for unconnected dyads and triads to attach to the main component, the structure is equally sensitive to a break (failure to transmit disease) at any site in the graph. In this way, relatively low levels of behavior changeeven by low-risk actors, who are perhaps the easiest to influence can easily break a spanning tree network into small disconnected components, thereby fragmenting the epidemic and radically limiting its scope.

fn1. “Homophily”:, or the tendency do associate with others with similar traits to oneself, is a powerful social force that explains a great deal about the structure of social networks — in this case, homophily on experience.



Sebastian Holsclaw 08.13.04 at 10:04 pm

You won’t date in a 4-cycle, but you might be willing to have sex with your ex’s current partner’s ex.


Ken Houghton 08.13.04 at 10:06 pm

Uh, the graphic needs to be integrated better to make the text around it readable.

I gather the authors confirmed what we already knew: social mobility doesn’t happen.


luckyman 08.13.04 at 10:26 pm

interesting! if one of the points of the study is to help track things like STD transmission, it’s worth noting that in the gay community the potential length of a cycle is shortened by one–and that cycles of 3 and 4 are very common because the community is small. this might help to explain different patterns of transmission in the gay and straight communities.


George 08.13.04 at 10:48 pm

Cool analysis, but I think a better model for high school sex is the 90-10 rule.


Jeff R. 08.13.04 at 10:49 pm

Hm. I’m thinking about, in this context, the standard Sitcom/Romantic-Comedy behavior pattern in which the respective blind dates of the two characters who are Obviously Meant For One Another [and may or may not have history together] fall immediately in love with one another.

Does this provide enough evidence to bury this cliche once and for all?


PG 08.13.04 at 11:35 pm

And I thought the blogcrush posting was as highschool-ish as we’d get here at CT… ;-)

It turns out that this kind of cycle is just not found in the Jefferson High network. Although there’s no explicit taboo or social norm against that kind of pattern, nevertheless people just don’t date their old partner’s current partner’s old partner.

Hm. Possibly this is only true of the sexually active kids. I know that at my high school, several students in the “popular white kids” clique, which my school was too conservative to include much sexual activity (really… Christians in Action was not ironic), dated each other’s exes current’s exes. The circle of approved dates was just too small not to do so.


The Mighty Reason Man 08.13.04 at 11:43 pm

I wonder, did the authors factor who dumped who (when sex was the result of dating, not just random hookups) into the study? Because it seems to me that, especially when talking high school, that the dumper would be much freer to date his ex’s current flame’s ex, if the determining factor really is potential loss of status.

Sorting by dumper/dumpee might be a decent way of learning whether fear of loss of status is the prohibiting factor.


dsquared 08.13.04 at 11:45 pm

The point being, to drag it down to my own level, that an ex’s current boyfriend is presumably, someone you don’t like and would therefore be unwilling to become “porridge brothers” with.

I seem to remember that one regular of the CT comments section used to maintain a graph of this sort on a termly basis for the college we both attended, for his satirical magazine. I also seem to remember that I was an unconnected node on that graph :-(


marek 08.14.04 at 12:06 am

It’s not clear how significant the word “currrent” is in the “old girlfriend’s current boyfriend’s old girlfriend” sequences.

Is it any different for “former girlfriend’s former boyfriend’s former girlfriend”? And if so, how large a time value does each “former” need to take to produce a different answer?


Matt McGrattan 08.14.04 at 1:07 am

I don’t think cycles of 4 are really all that unusual. Especially if, as Marek suggests, there are relatively large gaps in time.

Small social circles can quickly become incestuous. I’ll bet if they had done this survey among members of some social out-group – eyeliner wearing habitués of the only goth or rock club in a small socially conservative town, or whatever – then the figures would have been different. I’ll bet that in that sort of social scene the ‘core infection’ model looks a lot more apt.

High school, in contrast, is a relatively short period in terms of sexual activity. You’re in a high school for 4 or 5 years and for most people at least half of those years will be sexually inactive. [Where I went to school people started high school at 11 or 12 and left at 16 or 17.]

Measuring among a relatively large pool of available partners for a relatively short period — as in the high school case — may give results that other samples would not.


Kimmitt 08.14.04 at 2:59 am

For anecdotal reasons, I’d definitely think that the size of the high school would be important – that larger populations would have fewer 4-cycles than smaller ones. I doubt, however, that there is a lot of 4-cycling within subgroups of large populations – if so, wouldn’t the authors have seen more Panel C behavior (which is what I would have expected, based on my experience)?


novalis 08.14.04 at 4:00 am


Eric S. 08.14.04 at 6:40 am

To follow up with Sebastian… when Justin and Britany split and Justin hooked up with Cameron Diaz, didn’t Britany have a fling with Cameron Diaz’ ex? Sure seems like a loss of status for her and violation of a strong Yuck-factor norm. Sometimes the lines in our supermarket are REALLY long…


Jason Kuznicki 08.14.04 at 12:56 pm

Back when I was in high school (also with about 800 others), I’d say this probably happened more or less according to the model–with one exception:

The Band.

Yes, that’s right, just like in _American Pie_, and I went to high school well before that film came out. The marching band was isolated from the rest of the school because they took a lot of classes together: not just music, but separate schedules for a good deal of the week. They all dated one another in some VERY close loops, so much so that even at the time we called them the Incest Family.

It would be interesting to do a study on a much smaller high school and see what happened there.


Pedant 08.14.04 at 2:24 pm

Not to be pedantic, but I did a double take when I read the title, Spanning-Tree Network with No 4-Cycles.

I mean, by definition, a “tree” doesn’t have any cycles. A spanning-tree is a tree which touches all nodes in the network.

So it’s… redundant to say “a tree with no cycles.” And if there are any cycles, it’s not a tree. And it doesn’t seem like the “spanning” concept is doing much work for you here, either.

It seems like a better description of these networks would be Sparse, connected graphs that (locally) look like trees. Or maybe something that gets at the difference in connectivity-distributions between these observed networks, and the (posited) “core” networks.

(That is, on the small scale, you don’t see any “small” cycles).


Matt Weiner 08.14.04 at 4:43 pm

Porridge brothers, eh? A fellow-philosopher recently introduced me to the term “stomach buddy,” which I was told was an Icelandic term; I can’t remember whether it referred to people who were linked by two degrees or by three. The claim was that Iceland is so small that it becomes important to have terms for these relationships. I can’t find either porridge brother or stomach buddy by Google, although I suppose I will be able to soon. So I guess the norm could be something like “Don’t date your stomach buddy” or “Don’t be stomach buddies with someone two ways,” depending on which definition is right.

[Disclosure: The person who introduced me to this term was not Icelandic, or my stomach buddy, or my porridge brother. In fact I am a disembodied AI program and have no sort of personal life that would be of interest to anyone, so don’t ask.]


James 08.14.04 at 7:47 pm

The paper is freely available online, linked from the Gallery of Network Graphs (which I originally saw on Hot Links about 6 months ago.)
It contains details on the methodology – there were 800 students at the school, in a fairly isolated town (although it does account for relationships where one partner was not at school,) over a period of 18 months. And no, the network isn’t a spanning tree, just “has the appearance of a spanning tree. … [G]lobal structure is defined by a graph with few cycles, low redundancy, and consequently very sparse overall density.”
The actual graph of the dating network (from the gallery above, the paper I linked to is missing all the figures) shows two 4-cycles (with 3 common nodes between them), one 6-cycle, one large cycle of 38, and 283 nodes.


dsquared 08.14.04 at 7:58 pm

Just out of interest, were there really absolutely no homosexual relationships at that school?


Keith M Ellis 08.15.04 at 6:27 am

Just out of interest, were there really absolutely no homosexual relationships at that school?—D²

Yeah, that seems to me to be a big flaw in this study. (Not that I read the linked page.) Someone do the math: if you assume that 10% of the population is gay, then the 4-cycle rule won’t apply (as well as many other things). How would that change the structure? Wouldn’t it? Perhaps dramatically, given how these results demonstrate how sensitive such things are to small changes?


Jason Kuznicki 08.15.04 at 2:11 pm

I wouldn’t be surprised to find high schoolers concealing gay relationships from researchers, for fear of being discovered by their parents or peers. It’s likely to be a flaw of any study.


Zizka 08.15.04 at 6:05 pm

I think that the sex-neutral language creates a blindspot too. It’s still more permissible for boys to be promiscuous than girls even on the West Coast. (Actually, in 1991 it still was — even my son is old now. However, I suspect that in the Midwest it still is).

And boys are more into the conquest thing. A dumped girl won’t be a conquest any more, and will also in most cases be warier unless she wants to go all the way into being a doormat or slut. And even if she chooses that path, she will be very likely to go outside the gossipy, vicious HS environment.

I think that the rule can be stated idiomatically with overlapping principles of not wanting to get into a double-reject relationship (C and D getting together after having been rejected respectively by A and B, the new couple) with some attention to the fact that girls are supposed to be less available and less aggressive.

I think that a similiar study of a bar scene would come up with different results.


cbl 08.16.04 at 12:41 am


It seems like there is one homosexual relationship, located on the periphery of the upper-left quadrant of the graph. (Un)-luckily, his partner was bisexual, linking him to the rest of the dating scene.


nobody 08.17.04 at 3:53 am

novalis —

I’m on that chart. I know of at least one person with a parser for it, though I don’t know if it’s 100%. If not, it’s pretty close.


Peter Bearman 08.18.04 at 3:08 pm

Some comments on the discussion to this point — which has been extremely interesting and generally at higher level than at talks, etc. The scope conditions for the structural findings are pretty strong. That is, one would not expect such structures in adult populations where individuals have the capacity to segregate domains. For an unstated negative prohibition to obtain, people have to have the capacity to watch and enforce violations. Nor will it obtain in heterodox and isolated small groups.

The generally accepted 10% homosexual preference number is probably without too much empirical foundation – certainly not for this age population, where it is close to 2%. That said, the model here is a model for heterosexual relationships, since a cycle of length 4 makes sense only in that context. There are some homosexual relationships in the school, more than the single one identified so far. For Add Health as a whole, 2% rather than 10% is what is observed.

It is interesting that girls are as likely to be predators as boys, in the sense that if girls are going to have a lot of partners, their partners will tend to be less experienced. This is the same for boys. In adults, there tends to be homophily on number of partners beyond just one or two. This is not true for adolescents.

It is true that there are cycles and that spanning trees have no cycles, but the proportion of cycles is far less than one would expect by chance. The pedant is therefore right, but substantively wrong.

The implications of the paper are that most of the received models for estimating STD risk are wrong because they have the wrong underlying network structure in mind – at least for adolescents. This may strike some as important. For me, the most interesting thing is the fact that people follow normative rules that they cannot and do not articulate; this is not simply a modern phenomenon; similar dynamics can be seen in many other contexts – for example, Australian classificatory kinship systems. This suggests that those of us interested in understanding social behavior have to focus on the ways in which structure reveals grammars for action that are cognitively inaccessible to actors.

Hope I did not violate some unstated norm by posting to this discussion, my first such post – ever.

Peter Bearman


SHock 08.20.04 at 2:28 pm

Does the analysis include faculty?


Alan Bostick 08.20.04 at 6:21 pm

If a social force acts against four-cycles, it’s not a very strong force. In my own (het male) adult life I can pick out many four-cycles of which I am a member, and at least one three-cycle.


Anonymous Coward 08.21.04 at 7:20 am

This is so fucking cool.

Comments on this entry are closed.