Source-linked AI summary
A comparative study of social network models: network evolution models and nodal attribute models
Riitta Toivonen, Lauri Kovanen, Mikko Kivelä, Jukka-Pekka Onnela, Jari Saramäki, Kimmo Kaski
TL;DR
How social-network structures arise from network-dependent processes or nodal attributes remains an open modeling question. This paper compares these model classes and an ERGM against empirical acquaintance networks, finding that network evolution models more closely reproduce key structural patterns than nodal attribute models.
Problem
The paper asks whether structures observed in social networks can be explained by network-dependent mechanisms.
Method
The study compares dynamic network evolution models with nodal attribute models and an ERGM using empirical acquaintance networks.
Results
Network evolution models produce broader degree distributions and decreasing clustering spectra that agree more closely with empirical data.
Takeaways & Limitations
Network evolution models provide a closer match to empirical social-network structure than models based only on nodal attributes.
Takeaways & Limitations
Differences among model choices make it difficult to isolate their individual effects.
Abstract
from arXiv · showhide
This paper reviews, classifies and compares recent models for social networks that have mainly been published within the physics-oriented complex networks literature. The models fall into two categories: those in which the addition of new links is dependent on the (typically local) network structure (network evolution models, NEMs), and those in which links are generated based only on nodal attributes (nodal attribute models, NAMs). An exponential random graph model (ERGM) with structural dependencies is included for comparison. We fit models from each of these categories to two empirical acquaintance networks with respect to basic network properties. We compare higher order structures in the resulting networks with those in the data, with the aim of determining which models produce the most realistic network structure with respect to degree distributions, assortativity, clustering spectra, geodesic path distributions, and community structure (subgroups with dense internal connections). We find that the nodal attribute models successfully produce assortative networks and very clear community structure. However, they generate unrealistic clustering spectra and peaked degree distributions that do not match empirical data on large social networks. On the other hand, many of the network evolution models produce degree distributions and clustering spectra that agree more closely with data. They also generate assortative networks and community structure, although often not to the same extent as in the data. The ERG model turns out to produce the weakest community structure.
1. In tro du tion
The paper reviews and compares social-network models from the complex-networks literature, classifying them by whether link formation depends on network structure or nodal attributes. It evaluates these categories and structurally dependent ERGMs on empirical acquaintance networks using basic and higher-order network properties.
- Model classification: The study classifies models into network evolution models (NEMs), whose link additions depend on local network structure, and nodal attribute models (NAMs), whose link probabilities depend only on nodal attributes.It also includes ERGMs with nodal-attribute or structural dependencies for comparison.
- Evaluation framework: The models are fitted to two empirical acquaintance networks and compared with data on degree distributions, assortativity, clustering spectra, geodesic path lengths, and community structure.Communities are defined as groups whose nodes are more densely connected within the same community than across communities.
- Study assumptions: The comparison treats generated networks as undirected and unweighted, without multiple links or self-links, and assesses models designed to reproduce several typical social-network features.Tie strengths are not taken into account.
- Network evolution models (NEMs): NEMs are iterative models with explicit stochastic rules that add or delete nodes and links according to network structure, typically stopping at a target size or stabilized statistics.Growing NEMs use a predetermined network size, whereas dynamical NEMs use a heuristic stabilization criterion.
- Nodal attribute models (NAMs): NAMs generate edges from node attributes alone, excluding an evolutionary aspect, and are often motivated by homophily—the tendency for similar individuals to interact.The models are also described as spatial models because node attributes determine social or geographical locations.
2. Des ription of the mo dels
This section classifies social-network models by their mechanisms for generating ties, emphasizing network evolution through triadic closure and global connections. It describes dynamic and growing evolution models, including their link-formation and deletion mechanisms, and introduces nodal attribute models based on distance-dependent link probabilities.
- Dynamical network evolution models: Dynamic network evolution models combine triadic closure and global connections to create new links, using DEB, MVS, and KOSKK as representative models.These mechanisms form the basis of the network evolution models studied in the paper.
- Dynamical network evolution models: KOSKK accounts for interaction strength, preferentially creating links through strong ties and strengthening ties after interactions, which produces clear community structure.The paper confirms this community-structure effect in its Section 4 analysis.
- Growing network evolution models: The study includes two growing network evolution models, Váz and TOSHK, designed to generate broad or power-law degree distributions, high clustering, and, for TOSHK, community structure.TOSHK introduces newcomers through initial contacts and their neighbors, whereas Váz begins with a random node and potential edges to its neighbors.
- Nodal attribute models: The nodal attribute models BPD A and WPR differ in how link probability depends on distance and in the distance measure they use, with studied cases in 1D and 2D.The authors allow social spaces of any dimension but analyze one- and two-dimensional cases.
3. Fitting the mo dels
The study fits diverse social-network models to two empirical networks by tuning parameters against key structural features. It targets network size, degree, clustering, and additional measures such as assortativity or geodesic path length, while averaging results across stochastic realizations.
- Fitting procedure: Models are fitted to two real-world networks by simulating realizations and selecting parameter values that best match relevant network statistics.The fitting procedure aims to unify model properties while allowing each model’s parameters to determine the targeted features.
- Targeted features: The primary fitting targets are the largest connected component, average degree, and average clustering coefficient.These features are measured within the largest connected component, consistent with both empirical datasets being connected components of larger networks.
- Evaluation and limitations: Reported model-network properties are averaged over 100 realizations because stochastic models with identical parameters produce different network outcomes.Fitting only a limited number of datasets does not permit a full assessment of model adaptability.
4. Comparison of higher order statisti s
Higher-order comparisons show that NEMs generally match empirical degree distributions and clustering spectra better than NAMs, while NAMs produce clearer but overly fragmented community structure. Path-length distributions are broadly reasonable across models, although some NEMs are too compact and the Váz model remains comparatively long-path despite its broad degree distribution.
- Degree distributions: NEMs match empirical degree distributions better than NAMs, whose skewed, rapidly decaying distributions imply too few very high-degree nodes.Empirical distributions decay exponentially in email and more slowly in lastfm, whereas many NEMs decay more slowly than Poisson but faster than a power law.
- Clustering spectrum: NAM homophily produces a flat clustering spectrum c(k) = const, unlike empirical networks where clustering decreases with node degree.This indicates that attribute-based homophily alone does not explain the observed network structures.
- Geodesic paths: All models display reasonable geodesic path-length distributions, but dynamical NEMs and TOSHK are slightly too compact relative to the data.The Váz model instead has rather long geodesic paths despite its broad degree distribution, apparently because its high assortativity counteracts the shortening effect of high-degree nodes.
- Community structure: NAMs form very clear communities that are loosely interconnected, whereas other NEMs and ERGM1 contain a core less characterized by loosely connected clusters.NAMs and KOSKK break down into small clusters, while low-overlap links act as bridges between clusters in these models.
- Community structure: After removing 50 percent of ERGM1 links beginning with the lowest-overlap links, a core containing 93.6 percent of nodes remains intact.This supports the finding that ERGM1 networks contain few dense substructures such as cliques or k-clusters.
5. Summary and dis ussion
The study systematically compares network evolution models, nodal attribute models, and a structurally dependent ERGM against empirical social-network structure. NAMs reproduce assortativity and strong communities but misrepresent clustering and degree distributions, whereas many NEMs better match these features without reproducing every important property.
- Study scope: The paper presents the first systematic comparison of models from the network evolution and nodal attribute families, including structural features and their underlying modeling philosophies.The models were fitted to empirical data and compared with an exponential random graph model incorporating recently proposed structural dependencies.
- Empirical benchmarks: Empirical social networks typically exhibit highly skewed degree distributions, high average clustering coefficients, decreasing clustering spectra c(k), and positive degree-degree correlations r.These characteristics motivate evaluating both average values and distributions rather than isolated summary statistics.
- Nodal attribute models: NAMs based solely on homophily generate strong assortativity and pronounced communities, but their clustering spectra differ markedly from observed data and their degree distributions are peaked.They produce many cliques and loosely connected dense clusters, with clustered structure more pronounced than in the data.
- Network evolution models: Many NEMs produce broader degree distributions and decreasing clustering spectra that agree more closely with empirical data, while also generating assortative networks and many large cliques and k-clusters.Their assortativity is typically weaker than in the data, and dynamic NEMs show stronger assortativity with node deletion than with link deletion.
A kno wledgemen ts
The authors acknowledge support from the Academy of Finland, the Finnish Centre of Excellence Programme 2006–2011, Project No. 213470, and the MIT graduate school.
- The authors acknowledge the Academy of Finland and the Finnish Centre of Excellence Programme 2006–2011.
- Project No. 213470 is identified among the acknowledged sources of support.
- R.T. is supported by the MIT graduate school.
A. App endix
The appendix defines the network representation and notation used to evaluate social-contact networks. It introduces measures of degree, clustering, assortativity, and geodesic path length, including clustering spectra and average path length.
- A.1. Basic network measures: Social-contact networks represent individuals as nodes and ties between them as links, with overlines denoting averages across nodes, links, or networks.N denotes network size, while LC and NLC denote the largest connected component and its size.
- A.1. Basic network measures: A node’s degree k is its number of network neighbors, and isolated nodes have degree zero.A component is a connected subset of nodes; the study focuses on each network’s largest component LC.
- A.1. Basic network measures: The clustering coefficient c_i measures how extensively node i’s neighbors know one another, while c(k) forms the clustering spectrum across degree classes.c_i equals zero when no neighbors are acquainted and one when all are acquainted; it is undefined for k < 2.
- A.1. Basic network measures: Assortativity describes degree correlation between connected nodes, with r and k_nn(k) indicating whether high- and low-degree nodes tend to connect to similar-degree neighbors.A positive k_nn(k) trend indicates that high-degree nodes typically have high-degree neighbors.
- A.1. Basic network measures: The geodesic path length l_ij is the minimum number of links between nodes i and j, while average path length l̄ describes network compactness.Path-length distributions and averages quantify distances between nodes and the network’s compactness.
A.2. Determining optimal network p ar ameters
Parameters were fitted by simulating networks and minimizing relative errors in average degree, clustering coefficient, and geodesic path length, with greatest emphasis on matching nodes and links. Most models were relatively insensitive to feature weights, whereas ERGM1 lacked an exact fit and showed unstable, multimodal optimization behavior.
- Fitting procedure: The error weighting emphasized matching the number of nodes and links, assigned less weight to clustering, and assigned least weight to average geodesic path length.The error function used as many components as the model had network parameters.
- Optimization results: For nearly all models, fitted results were insensitive to the weights because the models closely matched target values up to the number of model parameters.This applied to DEB, MVS, KOSKK, Váz, BPDA, and the email fit of WPR.
- Optimization results: ERGM1 had no exact fit, and optimization attempts failed likely because its probability distribution was multimodal.When fitting ERGM1 to email data, a sudden transition occurred around θL = −6.961 toward a denser, less clustered network.
Referen es
The references section compiles prior work on social-network models, network structure, and empirical or dynamical analyses of social networks.
- Network models: The bibliography includes studies of social-network models involving clustering, correlations, communities, local interaction, and network growth.Examples include models of acquaintance networks, community structure, and networks grown with local rules.
- Exponential random graph models: Several references address exponential random graph models, their statistical estimation, specifications, degeneracy, and goodness of fit.The cited works cover p* models, curved exponential-family models, and methodological developments for social networks.
- Network dynamics: Additional citations concern social-network dynamics and applications, including rumor spreading, epidemics, cooperation, opinions, and networked societies.The cited studies connect network structure with spreading processes, social dynamics, and collective behavior.
- Empirical network structure: The references also cover empirical social-network phenomena including homophily, assortative mixing, communication networks, small-world structure, and overlapping communities.These works examine human interaction, mobile communication, instant messaging, and community structure in social or complex networks.