Statistical properties of community structure in large social and information 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

• 1: R. Z. Albert and A.-L. Barabási. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.
• 2: Christopher Allen. Life with alacrity: The Dunbar number as a limit to group sizes, http://www.lifewithalacrity.com/2004/03/the_dunbar_numb.html, 2004.
• 3: Reid Andersen , Fan Chung , Kevin Lang, Local Graph Partitioning using PageRank Vectors, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.475-486, October 21-24, 2006 [doi>10.1109/FOCS.2006.44]
• 4: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 5: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 6: F. R. K. Chung. Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics. AMS, 1997.
• 7: Fan Chung , Linyuan Lu, Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics), American Mathematical Society, Boston, MA, 2006
• 8: A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. arXiv:cond-mat/0408187, August 2004.
• 9: L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas. Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment, 29(09):P09008, 2005.
• 10: Inderjit S. Dhillon , Yuqiang Guan , Brian Kulis, Weighted Graph Cuts without Eigenvectors A Multilevel Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.11, p.1944-1957, November 2007 [doi>10.1109/TPAMI.2007.1115]
• 11: Robin Dunbar. Grooming, Gossip, and the Evolution of Language. Harvard Univ Press, October 1998.
• 12: A. D. Flaxman, A. M. Frieze, and J. Vera. A geometric preferential attachment model of networks. In WAW '04: Proceedings of the 3rd Workshop On Algorithms And Models For The Web-Graph, pages 44--55, 2004.
• 13: M. Gaertler. Clustering. In U. Brandes and T. Erlebach, editors, Network Analysis: Methodological Foundations, pages 178--215. Springer, 2005.
• 14: Johannes Gehrke , Paul Ginsparg , Jon Kleinberg, Overview of the 2003 KDD Cup, ACM SIGKDD Explorations Newsletter, v.5 n.2, December 2003 [doi>10.1145/980972.980992]
• 15: S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43:439--561, 2006.
• 16: Ravi Kannan , Santosh Vempala , Adrian Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM), v.51 n.3, p.497-515, May 2004 [doi>10.1145/990308.990313]
• 17: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 18: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 19: K. Lang and S. Rao. A flow-based method for improving the expansion or conductance of graph cuts. In IPCO '04: Proceedings of the 10th International Conf. on Integer Programming and Combinatorial Optimization, 2004.
• 20: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 21: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 22: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graph evolution: Densification and shrinking diameters, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.2-es, March 2007 [doi>10.1145/1217299.1217301]
• 23: J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Statistical properties of community structure in large social and information networks. Manuscript.
• 24: M. E. J. Newman. Detecting community structure in networks. The European Physical J. B, 38:321--330, 2004.
• 25: M. E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E, 74, 2006.
• 26: M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America, 103(23):8577--8582, 2006.
• 27: E. Ravasz and A.-L. Barabási. Hierarchical organization in complex networks. Physical Review E, 67:026112, 2003.
• 28: M. Richardson, R. Agrawal, and P. Domingos. Trust management for the semantic web. In ISWC ?03: Proceedings of the 2nd International Semantic Web Conference, pages 351--368, 2003.
• 29: Matei Ripeanu , Adriana Iamnitchi , Ian Foster, Mapping the Gnutella Network, IEEE Internet Computing, v.6 n.1, p.50-57, January 2002 [doi>10.1109/4236.978369]
• 30: S. E. Schaeffer. Graph clustering. Computer Science Review, 1(1):27--64, 2007.
• 31: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 32: D. A. Spielmat, Spectral partitioning works: planar graphs and finite element meshes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.96, October 14-16, 1996
• 33: S. L. Tauro, C. Palmer, G. Siganos, and M. Faloutsos. A simple conceptual model for the internet topology. In GLOBECOM ?01: Global Telecommunications Conference, pages 1667--1671, 2001.
• 34: D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature, 393:440--442, 1998.
• 35: W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33:452--473, 1977.
• 36: C. T. Zahn, Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters, IEEE Transactions on Computers, v.20 n.1, p.68-86, January 1971 [doi>10.1109/T-C.1971.223083]
• 37: Ying Zhao , George Karypis, Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering, Machine Learning, v.55 n.3, p.311-331, June 2004 [doi>10.1023/B:MACH.0000027785.44527.d6]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Experimentation, Measurement

Keywords:
community structure, conductance, graph partitioning, random walks, social networks