PaperlayerView exact revision on arXiv

Source-linked AI summary

Maximizing Entropy Yields Spatial Scaling in Social Networks

Yanqing Hu, Yougui Wang, Daqing Li, Shlomo Havlin, Zengru Di

arXiv:1002.1802v1physics.soc-ph

TL;DR

The paper asks why social networks exhibit the spatial law P(r) ∝ r^-1 and how that law benefits individuals. It proposes maximizing information entropy as the underlying principle and concludes that this distribution forms an optimal network for collecting maximal information.

  • Problem

    The origin of the observed P(r) ∝ r^-1 spatial scaling in social networks, and its benefit to individuals, remains unresolved.

    Source: §2 · pp. 2–3

  • Method

    The paper models friendship formation as information collection and explains the scaling through maximization of information entropy.

    Source: §2 · p. 3

  • Results

    The P(r) ∝ r^-1 spatial distribution can result from entropy maximization and is associated with an optimal network for collecting maximal information.

    Source: §2 · pp. 2–3

  • Takeaways & Limitations

    The proposed spatial distribution can benefit individuals by enabling efficient message delivery and maximal information collection.

    Source: §2 · pp. 2–3

    The explanation assumes that human social behavior is based on gathering maximum information through different activities.

    Source: §2 · p. 3

Abstract

from arXiv · show

In addition to the well known common properties such as small world and community structures, recent empirical investigations suggest a universal scaling law for the spatial structure of social networks. It is found that the probability density distribution of an individual to have a friend at distance $r$ scales as $P(r)\propto r^{-1}$. The basic principle that yields this spatial scaling property is not yet understood. Here we propose a fundamental origin for this law based on the concept of entropy. We show that this spatial scaling law can result from maximization of information entropy, which means individuals seek to maximize the diversity of their friendships. Such spatial distribution can benefit individuals significantly in optimally collecting information in a social network.

2. Department of Physics, Bar-Ilan University, Ramat-Gan 52900, Israel

Empirical studies report a spatial friendship distribution scaling as P(r) ∝ r^-1, but the principle producing this law remains unresolved. The paper proposes that maximizing information entropy explains the scaling and supports efficient information collection.

  • P(r) ∝ r^-1 is reported for an individual’s friend-distance distribution, the Hewlett-Packard Labs email network, and a large mobile-phone communication network.The mobile-phone network consisted of 2.5 million customers.Source: §2 · p. 2
  • The unresolved question is why social networks possess this spatial scaling and how it benefits individuals.Source: §2 · pp. 2–3
  • In d-dimensional space, optimal navigability uses connection probability proportional to r^-d, which yields P(r) ∝ r^-1 because the number of nodes at distance r scales as r^(d-1).The paper links this scaling to efficient message delivery in a minimal number of hops.Source: §2 · p. 2
  • The paper proposes entropy as the fundamental origin of the spatial scaling law.It hypothesizes that people seek information through diverse activities and that friendship formation can collect information.Source: §2 · p. 3
  • A network based on Eq. (1) is presented as optimal for helping people collect maximal information.Source: §2 · p. 3

I. MODEL

The model places individuals on a toroidal lattice and assigns each a finite distance budget for selecting long-range acquaintances. It measures collected information through the entropy of a sequence containing selected nodes and their neighbors.

I. MODEL

  • Each node represents an individual on a toroidal lattice, with a finite energy w represented by the sum of distances to its friends.The lattice is used to represent the world in which nodes interact.Source: §I · p. 3
  • Nodes select long-range acquaintances one by one until the total distance reaches w.Source: §I · p. 3
  • The information brought by a node is represented by that node and all its neighbors, and the resulting node sequence measures collected information through entropy.The entropy is determined by the sequence of friends and friends of friends.Source: §I · p. 3

II. RESULTS

The optimization and evolutionary models identify P(r) ∝ r^-1 as the entropy-maximizing spatial distribution of friendships, under finite energy constraints and across power-law alternatives. Simulations show this distribution supports maximal diversity of friend locations and efficient information collection.

Optimization model

  • When α ≈ 1, information entropy remains near its maximum across a broad range of energy values, with α = 1 ± 0.05 for w ∈ (5 × 10^4, 10^6) and f ∈ (50, 1000).The optimization model links the energy constraint w to the average number of friends f at the optimum.Source: §II · p. 5
  • For f = 300, the optimal exponent is α = −0.99 ± 0.03, matching the empirically relevant average number of yearly contacts.This result is reported from the optimization model and corresponds to the observed inverse-distance scaling.Source: §II · p. 5

Optimization and evolutionary results

  • P(r) ∝ r^-1 is the optimal friendship-distance distribution for collecting maximal information among power-law distributions.The paper also concludes that it remains optimal among all tested distribution types through the evolutionary model.Source: §II · pp. 5, 7

Analytical scope and implementation

  • The evolutionary simulations are constrained to L = 100 because recording every node’s friends makes a lattice with L = 10000 too large to simulate.The reduced-size model assumes energy scales linearly with distance and uses w = 1086, corresponding to f = 50.Source: §II · p. 6

Evolutionary model

  • The evolutionary system converges from a uniform initial distribution to a steady state whose distance distribution is very close to P(r) ∝ r^-1.The entropy difference decays exponentially during evolution, and the stationary entropy is fixed after sufficiently long evolution.Source: §II · p. 7
  • The evolutionary model on a 100 × 100 toroidal lattice reaches maximum entropy 7.15 and produces a friendship-distance PDF scaling as P(r) ∝ r^-1.Its result is close to the optimization-model maximum entropy of 7.18 and corresponding α = 0.95 ± 0.05.Source: §II · pp. 6–7

Analytical scope and implementation

  • Analytically, when energy scales linearly with system size as w = cL for L → +∞, P(r) ∝ r^-1 maximizes entropy among power-law distributions.The models use lattice distance and avoid explicitly constructing the full network, enabling simulations on large lattices.Source: §II · pp. 4, 7, 8

III. CONCLUSION

Empirical evidence supports P(r) ∝r−1 as a universal spatial property of social networks, while the paper proposes entropy maximization as its origin and links it to information collection.

  • P(r) ∝r−1 is identified as a universal spatial property for social networks.Source: §III · p. 8
  • The paper proposes that this spatial scaling law may result from maximization of entropy.Source: §III · p. 8
  • The resulting spatial distribution can benefit individuals for optimally collecting information.Source: §III · p. 8

IV. EXPLANATION FOR SPATIAL SCALING OF LIVEJOURNAL

The LiveJournal analysis explains the near-r−1 scaling through the network’s fractal dimension and the distance-dependent number of node pairs.

IV. EXPLANATION FOR SPATIAL SCALING OF LIVEJOURNAL

  • Q(r) is the fraction of friendships among user pairs at distance r, computed as F(r)/S(r).F(r) counts friendships at distance r, while S(r) counts node pairs at that distance.Source: §IV · p. 11
  • LiveJournal’s fractal dimension is about 0.8, defined through the exponent of ranku(v) = c · r(u, v)^d.Source: §IV · p. 11
  • For a d-dimensional lattice, the number of nodes at distance r scales as r^(d−1), including in fractal networks.Source: §IV · p. 11
  • The LiveJournal distance distribution is about r^0.8−1 · r−1 = r−1.2, close to r−1.Source: §IV · p. 11

A. Why We Only Consider Friends and Next Nearest Friends?

The model focuses on up to three degrees of influence because friends and next-nearest friends are treated as important, while broader influence is computationally difficult to simulate.

A. Why We Only Consider Friends and Next Nearest Friends?

B. Algorithm of OM

The OM algorithm constructs a spatial network by indexing lattice nodes, sampling friendship distances from a power-law distribution, and repeatedly adding directed links until the energy constraint is reached.

B. Algorithm of OM

  • A 10000 × 10000 lattice makes recording all node-link information difficult.Source: B. Algorithm of OM · p. 12
  • Nodes are indexed from 1 to 10^8, and r(u, v) calculates lattice distance between node pairs.Source: B. Algorithm of OM · p. 12
  • Because all OM nodes are equivalent, any node can be set as u = 1 without loss of generality.Source: B. Algorithm of OM · p. 12
  • The algorithm samples r from P(r) ∝r−α, randomly selects a node at that distance, and creates a directed friendship link.Source: B. Algorithm of OM · p. 12
  • The process repeats until the energy reaches its limit constraint, yielding the friends of node 1 and, analogously, other nodes’ friends.Source: B. Algorithm of OM · p. 12

C. Analysis on OM

The analysis examines entropy optimization under w = cL and compares power-law distance distributions across α < 1. It identifies the relevant symbols and reports monotonic behavior in this regime.

1. Symbol and Expression Descriptions

  • Rα denotes the expected number of friends, while L is the lattice edge length and f denotes the number of friends.Source: §1 · p. 13
  • The connection probability between nodes i and j is defined for a given α, with friend sets and selection probabilities specified for node 1.Source: §1 · p. 13

C. Analysis on OM

  • For w = cL, the analysis considers the entropy objective for distance distributions P(r) ∝ r^-α.The section frames the optimization using lattice size L, friend count, and connection probabilities.Source: C. Analysis on OM · pp. 12–13, §2 · p. 13

2. Case 1: α < 1

  • The analyzed expression is a monotonic increasing function when α < 1.Source: §2 · p. 14

3. Case 2: α > 1

For α > 1, the analysis uses large-system approximations to establish monotonicity and concludes that exponent −1 is optimal for fixed c. It motivates next-nearest-neighbor selection through social experience and global optimality of EM.

3. Case 2: α > 1

  • For sufficiently large z, the normal distribution approximates the binomial distribution with μ = zq and σ^2 = zq(1 − q).Source: §3 · p. 14
  • The proof analyzes g(z) as a monotonic increasing function, supported by the plotted relation y = −q log q − g(z).The figure is used to verify the lemma and the small-z inequality g(z) > −q log q.Source: §3 · p. 15, Figure 5 · p. 15
  • For any fixed c, exponent −1 is the optimal exponent.This conclusion follows from the monotonicity analysis in the α > 1 case.Source: §3 · pp. 15–16

A. Why we chose new friend only from the next nearest neighbors?

  • The next-nearest-neighbor rule reflects the observation that people often make friends through friends of friends.The section also states that EM is globally optimal, so choosing any node gives the same theoretical result.Source: A. Why we chose new friend only from… · p. 16

B. How to Measure the Power Law Exponent in EM?

The paper notes that estimating a power-law exponent is difficult, especially near −1. It therefore uses least squares and an accumulated-curve log-linear plot, which appears consistent with P(r) ∝ r^-1.

B. How to Measure the Power Law Exponent in EM?

Loading 1002.1802v1…