Triadic Closures Are the New Black

DZone 's Guide to

Triadic Closures Are the New Black

Sometimes it's useful to explore theoretical concepts, if only in the hope that we may better understand the technologies we use and that, better still, we might be able to apply these concepts to our advantage. In this case, we take a look at triadic closures. Read on to find out more about a concept that is very widely applied.

· Database Zone ·
Free Resource

In the graph database world, we often eschew theory for the sake of expediency and concrete results ("Hey, that code isn't going to write itself; also, it's due yesterday.")  But in so doing, we miss important benefits that wouldn't otherwise be known to us.

One such theoretical concept in the graph world is that of the triadic closure.

The first time I had heard about triadic closures, I was in a graph theory course while doing my undergrad in math. It would be almost ten more years until I heard mention of triadic closures while I was attending an excellent talk by Neo Technology's Chief Scientist Jim Webber at GraphConnect 2013 in New York City.

So, what are these "triadic closures", and how can they benefit us in the real world?

Triangles Are Cool, Man

To simplify things, let's consider the "triadic" part of the concept: we can intuit that if something is triadic it will be comprised of three parts; in this case, three vertices or nodes.  

What about the "closure" side of things?

Of these three vertices, two of them (call them v1 and v2) will share a common, third vertex (call it v3) connected via separate edges or relationships.

Image title

"Booooring," I hear most of you yelling at your screen, "it's not really closed so it's not much of a closure, now, is it?"

Well, here's the cool part: Often times, those two unique vertices aren't themselves joined by a single edge; however, we can infer that there is an above-average probability that those two vertices will themselves become connected at some future point in time (we can thank Anatol Rapoport for his work on this), thus becoming "closed".

This may all seem rather abstract, but stay with me here.

Let's imagine that v1 and v2 represent two people (call them "Alice" and "Bob") who don't know each other.  Now, let's say that v3 represents a common friend, call him "Charlie").  Intuitively, we might assume that Alice and Bob will also become friends—if they aren't already!

Image title

This principle of transitivity is what gives triadic closures its power.  In fact, it is obvious to see the application in social networks, e.g. friend recommendations.

Think about how other networks such as Twitter or YouTube might (and do) make use of this concept.

And, it doesn't take much effort to imagine how this might be extended to, say, making quality recommendations that extend beyond simply establishing a relationship between two people/nodes.

Consider if, instead of the above, we had Alice and Bob having both bought the same product; we might then infer that there is a high degree of probability that Alice might also want to buy other items that Bob already has.

In Graph Databases

I realize that, for many, "triadic closure" is just a fancy way of saying "recommendations" and it may seem obvious in both its application and implementation; however, I would submit that there are a growing number of users who either are new to graph databases, are attempting to use them in "traditional" ways, or are aware of recommendations but don't know how to implement them to great effect.

At the risk of singling out a single vendor, Neo4j has made querying for triadic closures rather straight forward given their Cypher querying language (yes, I realize there are other methods of querying such as Pacer and Gremlin.)

For example, without diving into the specifics, the following Cypher query looks fairly intuitive:

// all labels left in for the sake of clarity
MATCH (a:Person {name:"Alice"})-[:FRIENDS_WITH]->(b:Person)-[:FRIENDS_WITH]->(c:Person)
WHERE a <> c

This query will return all people Alice might know through a common friend of someone else—or, put another way, it will return people that Alice would likely want to know, given her friendship with a common person.

In the case of Neo4j, as of the 2.3 release, the graph database has been optimized to recognize this pattern and has brought about some significant performance gains.

(For an excellent and detailed discussion about these gains, please visit here.)

For those wondering, the same link above mentions some important points on how the Cypher interpreter knows when to apply the optimizations.  

Taken from the link above:

"The key point of [a triadic pattern in Neo4j] is that the predicate pattern WHERE NOT (a)-[:FOLLOWS]->(c) needs to have the same direction, type, and labels as the first part of the MATCH pattern MATCH (a:User)-[:FOLLOWS]->(b).

"So b and c need to have the same labels. Triadic re-expresses the problem as find all (c) that are not in the set of (b)which is only a reasonable re-expression if the set of found (b) is a superset of possible (c)."


Far too often, we miss important concepts and even optimizations that our technologies can bring us.  In this case, it is my hope that this article has helped to spread some greater awareness of the awesomeness that is the triadic closure.

Being reminded of theoretical concepts as well as the benefits that they can bring is also a benefit in and of itself.  So be sure to keep your eyes open, and spend an hour here and there reading up on the more abstract and theoretical concepts out there!  You never know when inspiration may strike.

graph databases, graph theory, neo4j, recommendations, social network

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}