document: Statistical properties of community structure in large social and information networks A large body of work has been devoted to identifying community structure in networks . A community is often though of as a set of nodes that has more connections between its members than to the remainder of the network . In this paper , we characterize as a function of size the statistical and structural properties of such sets of nodes . We define the network community profile plot , which characterizes the `` best '' possible community - according to the conductance measure - over a wide range of size scales , and we study over 70 large sparse real-world networks taken from a wide range of application domains . Our results suggest a significantly more refined picture of community structure in large real-world networks than has been appreciated previously . Our most striking finding is that in nearly every network dataset we examined , we observe tight but almost trivial communities at very small scales , and at larger size scales , the best possible communities gradually `` blend in '' with the rest of the network and thus become less `` community-like . '' This behavior is not explained , even at a qualitative level , by any of the commonly-used network generation models . Moreover , this behavior is exactly the opposite of what one would expect based on experience with and intuition from expander graphs , from graphs that are well-embeddable in a low-dimensional structure , and from small social networks that have served as testbeds of community detection algorithms . We have found , however , that a generative model , in which new edges are added via an iterative `` forest fire '' burning process , is able to produce graphs exhibiting a network community structure similar to our observations .
doc_bio_tags: O O O B I O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O