  A key challenge within the social network literature is the problem of
network generation - that is, how can we create synthetic networks that match
characteristics traditionally found in most real world networks? Important
characteristics that are present in social networks include a power law degree
distribution, small diameter and large amounts of clustering; however, most
current network generators, such as the Chung Lu and Kronecker models, largely
ignore the clustering present in a graph and choose to focus on preserving
other network statistics, such as the power law distribution. Models such as
the exponential random graph model have a transitivity parameter, but are
computationally difficult to learn, making scaling to large real world networks
intractable. In this work, we propose an extension to the Chung Lu ran- dom
graph model, the Transitive Chung Lu (TCL) model, which incorporates the notion
of a random transitive edge. That is, with some probability it will choose to
connect to a node exactly two hops away, having been introduced to a 'friend of
a friend'. In all other cases it will follow the standard Chung Lu model,
selecting a 'random surfer' from anywhere in the graph according to the given
invariant distribution. We prove TCL's expected degree distribution is equal to
the degree distribution of the original graph, while being able to capture the
clustering present in the network. The single parameter required by our model
can be learned in seconds on graphs with millions of edges, while networks can
be generated in time that is linear in the number of edges. We demonstrate the
performance TCL on four real- world social networks, including an email dataset
with hundreds of thousands of nodes and millions of edges, showing TCL
generates graphs that match the degree distribution, clustering coefficients
and hop plots of the original networks.
