A growing set of on-line applications are generating data that can be viewed
as very large collections of small, dense social graphs -- these range from
sets of social groups, events, or collaboration projects to the vast collection
of graph neighborhoods in large social networks. A natural question is how to
usefully define a domain-independent coordinate system for such a collection of
graphs, so that the set of possible structures can be compactly represented and
understood within a common space. In this work, we draw on the theory of graph
homomorphisms to formulate and analyze such a representation, based on
computing the frequencies of small induced subgraphs within each graph. We find
that the space of subgraph frequencies is governed both by its combinatorial
properties, based on extremal results that constrain all graphs, as well as by
its empirical properties, manifested in the way that real social graphs appear
to lie near a simple one-dimensional curve through this space.
We develop flexible frameworks for studying each of these aspects. For
capturing empirical properties, we characterize a simple stochastic generative
model, a single-parameter extension of Erdos-Renyi random graphs, whose
stationary distribution over subgraphs closely tracks the concentration of the
real social graph families. For the extremal properties, we develop a tractable
linear program for bounding the feasible space of subgraph frequencies by
harnessing a toolkit of known extremal graph theory. Together, these two
complementary frameworks shed light on a fundamental question pertaining to
social graphs: what properties of social graphs are 'social' properties and
what properties are 'graph' properties?
We conclude with a brief demonstration of how the coordinate system we
examine can also be used to perform classification tasks, distinguishing
between social graphs of different origins.

本研究通过计算每个图中的小诱导子图的频率来制定和分析这种表示，发现子图频率空间不仅受其组合属性的制约，还受其实证属性以及社会图在空间中实际位置的影响，并提供了灵活的框架和分类算法，以研究这些方面。