Dimensionality of Social Networks Using Motifs and Eigenvalues

Anthony Bonato, David F. Gleich, Myung‐Hwan Kim, Dieter Mitsche, Paweł Prałat, Yanhua Tian, Stephen J. Young2021 · DOI

TL;DR

This paper investigates the intrinsic dimensionality of real-world social networks like Facebook and LinkedIn. They propose and validate a "logarithmic dimension hypothesis," suggesting that the effective dimension of the underlying metric space used to model these networks scales logarithmically with the number of nodes. This finding has implications for understanding network structure and developing more accurate generative models.

What Problem Does This Paper Address?

Online social networks exhibit complex properties like skewed degree distributions and shrinking diameters. Existing network models often struggle to capture all these characteristics simultaneously. The authors focus on geometric models, specifically the Geometric Protean Model (GEO-P) and its memoryless variant (MGEO-P), which posit that network connections arise from an underlying metric space. A key question is: what is the dimension of this underlying space for real-world social networks, and how does it relate to the network's size? Previous theoretical work hinted at a logarithmic relationship between dimension and network size for certain models, but this had not been empirically tested on large-scale social networks.

Methods

The researchers employed two primary methods to estimate the dimensionality of social networks:

  1. Graphlet Counts and Support Vector Machines (SVMs): They computed the frequency of small subgraphs (graphlets) within real-world networks and simulated MGEO-P networks of varying dimensions. An SVM classifier was trained to predict the dimension of an MGEO-P network based on its graphlet counts. This classifier was then used to predict the dimension of the real-world networks.
  2. Spectral Densities and KL-Divergence: They analyzed the distribution of eigenvalues of the normalized Laplacian matrix for both real-world and simulated networks. The similarity between these spectral densities was measured using Kullback-Leibler (KL) divergence. The dimension of the MGEO-P network that minimized this divergence was considered the best fit.

Datasets

The study utilized two large-scale social network datasets:

  • Facebook Samples: 100 samples of social networks from universities, ranging in size from 700 to 42,000 nodes, collected in September 2005.
  • LinkedIn Samples: Snapshots of the LinkedIn connection network, created from May 2003 to October 2006. These were processed to represent networks of varying sizes, using the 5-core of the graph to ensure a dense, representative subset.

Key Insights and Ideas

  • Logarithmic Dimension Hypothesis: The most significant finding is the empirical support for the idea that the dimension of the underlying metric space in social networks scales logarithmically with the number of nodes. This suggests that while networks can be very large, the "space" they inhabit is relatively low-dimensional.
  • Geometric Structure in Social Networks: The results reinforce the notion that social networks possess an underlying geometric structure, moving beyond purely random or abstract connection models.
  • Model Sensitivity: The graphlet-based method showed sensitivity to clearly erroneous graph structures (Erdős-Rényi graphs) and was somewhat influenced by degree distribution, highlighting the importance of robust feature selection.
  • Robustness to Perturbations: The predicted dimension was found to be relatively stable even when a significant fraction (up to 15%) of network edges were randomly altered, suggesting the underlying dimensional property is not overly sensitive to minor structural changes.

Key Results

  • Facebook Data:
    • Graphlet method: Predicted dimension $m \approx 2.06 \log_{10}(n) - 3.00$.
  • Spectral density method: Predicted dimension $m \approx 1.21 \log_{10}(n) + 1.65$.
  • LinkedIn Data:
    • Graphlet method: Predicted dimension $m \approx 0.98 \log_{10}(n) + 1.01$.
  • Spectral density method: Predicted dimension $m \approx 0.77 \log_{10}(n) + 1.1$.
  • In both datasets and with both methods, the fitted dimension showed a clear logarithmic trend with the number of nodes ($n$), aligning with the theoretical prediction $m \approx \log(n)/\log(D)$ where $D$ is the diameter.
  • The MGEO-P model, while not perfectly capturing all network properties (e.g., tail of eigenvalue distribution), provided a good fit for the overall dimensional scaling.

Limitations and Future Work

  • Model Accuracy: The authors acknowledge that the MGEO-P model does not perfectly capture all aspects of real-world social networks, citing differences in spectral histograms and graphlet counts.
  • Sensitivity to Degree Distribution: The graphlet fitting method showed higher variance when applied to random graphs with the same degree distribution, suggesting a potential bias that needs further investigation.
  • Erdős-Rényi Graphs: Erdős-Rényi random graphs did not exhibit a discernible dimension using the graphlet methodology, indicating the method's ability to distinguish between different network generation processes.
  • Future Work: The paper suggests further exploration into the geometric structure of networks and the implications of this logarithmic dimension for network analysis and modeling. Investigating other network types and refining the MGEO-P model to better capture specific network properties are also potential avenues.

Summary updated

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.
BibTeX
@misc{bonato2021dimensionality,
  author = {Anthony Bonato and David F. Gleich and Myung‐Hwan Kim and Dieter Mitsche and Paweł Prałat and Yanhua Tian and Stephen J. Young},
  title = {{Dimensionality of Social Networks Using Motifs and Eigenvalues}},
  year = {2021},
  doi = {10.32920/14668887},
}

Loading related content...

Figure