%0 Conference Paper %1 Ugander2013Subgraph %A Ugander, Johan %A Backstrom, Lars %A Kleinberg, Jon %B Proceedings of the 22Nd International Conference on World Wide Web %C Republic and Canton of Geneva, Switzerland %D 2013 %I International World Wide Web Conferences Steering Committee %K motifs, subnets, topology social-networks %P 1307--1318 %T Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections %U http://portal.acm.org/citation.cfm?id=2488502 %X 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 one-dimensional 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 structures arising from different types of social graphs. %@ 978-1-4503-2035-1

@inproceedings{Ugander2013Subgraph, abstract = {{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 one-dimensional 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 structures arising from different types of social graphs.}}, added-at = {2019-06-10T14:53:09.000+0200}, address = {Republic and Canton of Geneva, Switzerland}, author = {Ugander, Johan and Backstrom, Lars and Kleinberg, Jon}, biburl = {https://www.bibsonomy.org/bibtex/247718b6926acd6ae4a1488fe69151609/nonancourt}, booktitle = {Proceedings of the 22Nd International Conference on World Wide Web}, citeulike-article-id = {13673824}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=2488502}, interhash = {898c78b58238a3015abf72a2aa13329d}, intrahash = {47718b6926acd6ae4a1488fe69151609}, isbn = {978-1-4503-2035-1}, keywords = {motifs, subnets, topology social-networks}, location = {Rio de Janeiro, Brazil}, pages = {1307--1318}, posted-at = {2015-07-15 15:41:46}, priority = {2}, publisher = {International World Wide Web Conferences Steering Committee}, series = {WWW '13}, timestamp = {2019-07-31T12:32:03.000+0200}, title = {{Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections}}, url = {http://portal.acm.org/citation.cfm?id=2488502}, year = 2013 }