2008 StatisticalPropertiesofCommunit

(Leskovec, Lang et al., 2008) ⇒ Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. (2008). “Statistical Properties of Community Structure in Large Social and Information Networks.” In: Proceedings of the 17th International Conference on World Wide Web. doi:10.1145/1367497.1367591

Subject Headings: Identifying Community Structure in Networks, Community Characterization.

Notes

Cited By

Quotes

Author Keywords

community structure; conductance; graph partitioning; random walks; social networks

Abstract

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.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2008 StatisticalPropertiesofCommunit	Jure Leskovec Anirban Dasgupta Michael W. Mahoney Kevin J. Lang			Statistical Properties of Community Structure in Large Social and Information Networks				10.1145/1367497.1367591		2008