Databases Reference
In-Depth Information
algorithms from graph theory that yield predictive insight into the behavior of connec‐
ted data.
Graph Theory and Predictive Modeling
Graph theory
is a mature and well-understood field of study concerning the nature of
networks (or from our point of view, connected data). The analytic techniques that have
been developed by graph theoreticians can be brought to bear on a range of interesting
problems. Now that we understand the low-level traversal mechanisms, such as breadth-
first search, we can start to consider higher-order analyses.
Graph theory techniques are broadly applicable to a wide range of problems. They are
especially useful when we first want to gain some insight into a new domain—or even
understand what kind of insight it's possible to extract from a domain. In such cases
there are a range of techniques from graph theory and social sciences that we can
straightforwardly apply to gain insight.
In the next few sections we'll introduce some of the key concepts in social graph theory.
We'll introduce these concepts in the context of a social domain based on the works of
sociologists Mark Granovetter, and Easley and Kleinberg.
1
Property Graphs and Graph Theory
Much of the work on graph theory assumes a slightly different model to the property
graphs we've been using throughout this topic. This work tends to ignore direction and
labeling of graphs, instead assuming undirected relationships with a single label derived
from the domain (e.g.,
friend
or
colleague
).
We're going to take a hybrid approach here. We'll add names to relationships where it
helps add domain-specific meaning. In many cases, however, we will ignore relationship
direction. This won't impact the analysis, however: the graph structure upholds the same
principles irrespective of its construction.
Triadic Closures
A
triadic closure
is a common property of social graphs, where we observe that if two
nodes are connected via a path involving a third node, there is an increased likelihood
that the two nodes will become directly connected at some point in the future. This is
a familiar social occurrence: if we happen to be friends with two people, there's an
increased chance that those people will become direct friends too. The very fact of their
1. In particular, see Granovetter's pivotal work on the strength of weak ties in social communities:
http://stan
