Dimensionality of social networks using motifs and eigenvalues

Anthony Bonato; David F Gleich; Myunghwan Kim; Dieter Mitsche; Paweł Prałat; Yanhua Tian; Stephen J Young

doi:10.1371/journal.pone.0106052

Dimensionality of social networks using motifs and eigenvalues

PLoS One. 2014 Sep 4;9(9):e106052. doi: 10.1371/journal.pone.0106052. eCollection 2014.

Authors

Anthony Bonato¹, David F Gleich², Myunghwan Kim³, Dieter Mitsche⁴, Paweł Prałat¹, Yanhua Tian⁵, Stephen J Young⁶

Affiliations

¹ Department of Mathematics, Ryerson University, Toronto, Ontario, Canada.
² Computer Science Department, Purdue University, West Lafayette, Indiana, United States of America.
³ Electrical Engineering Department, Stanford University, Stanford, California, United States of America.
⁴ Laboratoire J.A. Dieudonné, Université de Nice Sophia-Antipolis, Nice, France.
⁵ Department of Mathematics and Statistics, York University, Toronto, Ontario, Canada.
⁶ Mathematics Department, University of Louisville, Louisville, Kentucky, United States of America.

Abstract

We consider the dimensionality of social networks, and develop experiments aimed at predicting that dimension. We find that a social network model with nodes and links sampled from an m-dimensional metric space with power-law distributed influence regions best fits samples from real-world networks when m scales logarithmically with the number of nodes of the network. This supports a logarithmic dimension hypothesis, and we provide evidence with two different social networks, Facebook and LinkedIn. Further, we employ two different methods for confirming the hypothesis: the first uses the distribution of motif counts, and the second exploits the eigenvalue distribution.

Publication types

Research Support, Non-U.S. Gov't
Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

Computer Graphics
Humans
Mathematical Concepts
Models, Theoretical
Social Networking*
Support Vector Machine

Grants and funding

NSERC DG grants; NSF CAREER award CCF-1149756; MITACS for hosting the authors' research team at the Advances in Network Analysis and its Applications Workshop held at the University of British Colombia in July 2012. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.