Thread by @demivasques

New preprint out!

Transitivity and degree assortativity explained: The bipartite structure of social networks
arxiv.org/abs/1912.03211

A thread on #affiliationnetworks (#bipartitenetworks #twomodenetworks) and their importance to social systems.

Social networks tend to present higher levels of transitivity (friend of my friend is my friend too) and degree assortativity (popular people are likely to connect to other popular people and unpopular to unpopular) than others.

Why?

In their article (arxiv.org/abs/cond-mat/0…), Newman and Park said: "if social networks are divided into groups or communities, this division alone can produce both degree correlations and clustering".

What they meant is: social systems have an underlying bipartite structure!

In a network with a bipartite structure we have two sets of nodes. And links connect nodes of different sets.

That's the case of affiliation networks: sets of actors and groups (events, clubs, church, etc). They are connected if an actor belongs to one of these groups.

As we are mostly interested in the relations between actors, we create another network from the bipartite one, with only the set of actors. This is a so-called projection (or projected network).

The projection is a traditional one-mode network with actors that are now connected to each other if they belong to the same group (coattend an event, co-author a paper, and so on).

Considering that humans evolved to live in groups and as part of collectives (see for example "The Evolution of Human Ultra-sociality" by Richerson and Boyd tinyurl.com/ret8p4b), Newman and Park's assumption makes a lot of sense.

Also, more recently, @DanLarremore @aaronclauset @az_jacobs (ncbi.nlm.nih.gov/pmc/articles/P…) also raised the question of "whether assortativity is due to properties of social networks or due to implicitly projecting from bipartite data"

Newman and Park are right in saying "this division alone can produce". It can, but not necessarily it does.

And the answer to Larremore et al. is: assortativity is due to properties of social networks.

Let's start with what they had in mind: degree distributions. Each group creates a clique (complete subgraph), in the projected network, of the size of its degree (i.e. the size of the group). A complete subgraph is full of triangles and has transitivity = 1.

Then we have the actors. The higher the degree of an actor in the bipartite network (i.e. the higher the number of groups to which one belongs) the more groups are connected together in the projection.

Groups create cliques of actors and actors connect these groups together.

When connecting groups together, actors create open triplets (I don't know some friends of my friends). The more groups an actor connects together, the more open triplets one creates. That decreases the transitivity of the projected network.

For degree assortativity, this is a little more complicated. @eestradalab showed that this property depends on three things: transitivity, relative branching, and intermodular connectivity (journals.aps.org/pre/pdf/10.110…)

Roughly, relative branching measures how "branched" a network is and intermodular connectivity measures how network modules (cliques in our case) are connected.

While transitivity and intermodular connectivity increase assortativity, relative branching decreases it.

Then again, likewise for transitivity, a combination of the distribution of the degrees of actors and groups will tell if a projected network is more or less degree assortative.

Not so simple but, in general, if the degree distribution of groups is more right-skewed than the degree distribution of actors, the projection tends to be assortative.

Otherwise, if the degree distribution of actors is more right-skewed, the projection tends to be dissortative.

But we are not done! Newman and Park said "the presence of groups in the network can explain about 40% of the assortativity we observe in this case, but not all of it." The case is the network of boards of directors they studied.

They continued "There is some further assortativity in addition to the purely topological effect of the groups, and we conjecture that this is due to true sociological or psychological effects in the way in which acquaintanceships are formed."

"One possibility is...", they wrote, "...that directors who sit on many boards tend to sit on them with others who sit on many boards."

Well, this is great! When that happens, cycles of size four are created in the bipartite network.

We have observed that cycles of size four (four-cycles), and also of size six (six-cycles), are much more frequent in (bipartite) empirical networks than in random networks

arxiv.org/abs/1909.10977
researchspace.auckland.ac.nz/handle/2292/46…

We claim that four and six-cycles are the representation of the sociological or psychological effects that Newman and Park were talking about.

While four-cycles are repeated interactions between a pair of actors (for instance based on trust, respect, empathy, and so on), six-cycles represent triadic closure (again, a friend of my friend is also my friend).

How these small cycles affect transitivity and assortativity?

The first, simple thing, is that six-cycles of bipartite networks help in creating more triangles in the projection as proposed by @toreopsahl (arxiv.org/abs/1006.0887)

The second is that these small cycles are suppressing the number of open triplets, for the case of transitivity, and relative branching, for degree assortativity.

That is, small cycles play in favor of higher levels of these properties in social networks!

In short, the structure of social networks is different because of the:

-underlying bipartite structure.
-distribution of groups size, often more skewed than that of the number of groups to which actors belong.
-repeated interactions and triadic closure among actors.