PaperlayerView exact revision on arXiv

Source-linked AI summary

Conjoining Speeds up Information Diffusion in Overlaying Social-Physical Networks

Osman Yagan, Dajun Qian, Junshan Zhang, Douglas Cochran

arXiv:1112.4002v2cs.SIphysics.soc-ph

TL;DR

Information diffusion across physical and online social networks is studied as an epidemic process on an overlay network. Using an SIR-based model and percolation analysis, the paper characterizes epidemic thresholds and sizes, finding that conjoining networks can enable epidemics and substantially increase their reach.

  • Problem

    The paper studies how information epidemics spread across an overlay of a physical information network and online social networks.

  • Method

    It models transmission with the SIR framework and analyzes the resulting coupled random graph using percolation and generating-function methods.

  • Results

    Conjoining networks enables epidemics at λf ≥0.77 in one ER example and raises epidemic probability from 0.58 to 0.82 in another.

  • Takeaways & Limitations

    Overlaying physical and online networks can significantly increase the scale and speed of information diffusion, including when individual networks lack percolation.

Abstract

from arXiv · show

We study the diffusion of information in an overlaying social-physical network. Specifically, we consider the following set-up: There is a physical information network where information spreads amongst people through conventional communication media (e.g., face-to-face communication, phone calls), and conjoint to this physical network, there are online social networks where information spreads via web sites such as Facebook, Twitter, FriendFeed, YouTube, etc. We quantify the size and the critical threshold of information epidemics in this conjoint social-physical network by assuming that information diffuses according to the SIR epidemic model. One interesting finding is that even if there is no percolation in the individual networks, percolation (i.e., information epidemics) can take place in the conjoint social-physical network. We also show, both analytically and experimentally, that the fraction of individuals who receive an item of information (started from an arbitrary node) is significantly larger in the conjoint social-physical network case, as compared to the case where the networks are disjoint. These findings reveal that conjoining the physical network with online social networks can have a dramatic impact on the speed and scale of information diffusion.

I. INTRODUCTION

The paper develops a theoretical framework for information diffusion across coupled physical and online social networks. It characterizes epidemic thresholds and sizes, and shows that conjoining networks can enable and enlarge information epidemics.

  • Motivation: The framework addresses a gap in prior work, which largely studied information propagation within single networks or coupled networks with identical or disjoint vertex sets.The paper focuses on overlay networks whose vertex sets are neither identical nor disjoint.
  • Motivation: The model overlays a physical information network with an online social network whose members are a subset of the population.Information can cross through conventional communication channels and online platforms such as Facebook, Twitter, and YouTube.
  • Contributions: The analysis characterizes the critical point, epidemic probability, epidemic size, and expected outbreak size in the overlaying network.Above the critical point, a single information source can reach a positive asymptotic fraction of individuals; below it, the informed fraction tends to zero.
  • Results: For an ER physical network with λw = 0.6 and α = 0.2, epidemics are possible when λf ≥0.77, whereas disjoint networks require λw > 1 or λf > 1.The comparison illustrates that conjoining networks can permit epidemics even when the individual networks do not percolate.
  • Results: The epidemic probability rises from 0.58 in a single ER network with λw = 1.5 to 0.82 after conjoining an ER network with α = 0.5 and λf = 1.5.The paper reports that the conjoint network can spread information to a significantly larger population fraction than disjoint networks.
  • Scope: The main conclusions assume that the online network contains a positive fraction of the population.When the online network has only ⌊nγ⌋ nodes with γ < 1, conjoining it does not change the threshold or expected epidemic size.

E. Organization of the Paper

The paper organizes its analysis around a random-graph model for an overlay network formed by combining a physical network and an online social network. Nodes join the online network independently, and same-type stubs are randomly paired to construct the colored overlay graph.

  • A. Overlay Network Model: The overlay network consists of a physical network W on n nodes and an online network F whose membership is independently assigned with probability α.The online vertex set is denoted NF; the sublinear case |NF| = o(n) is treated separately.
  • A. Overlay Network Model: The physical and online networks are specified through degree distributions, with node degrees independently drawn from the corresponding distributions.The model uses distributions {pw_k} and {pf_k}, and assumes finite moments of arbitrary order.
  • A. Overlay Network Model: The overlay H = W ∪ F contains an edge whenever two nodes are adjacent in either the physical or online network.Online transmission requires both endpoints to be members of the online network.
  • A. Overlay Network Model: Edges in H are assigned two types: online social edges are type 1 and physical connections are type 2.The resulting colored degree records the numbers of incident edges of each type.
  • A. Overlay Network Model: The graph is constructed by assigning each node same-type stubs and randomly pairing stubs of each type until none remain.This produces the colored degree-driven random graph used for the analysis.

B. Information Propagation Model

The model treats information diffusion as SIR spreading across an overlay of physical and online networks, then characterizes epidemic thresholds, outbreak sizes, and giant-component structure through coupled random-graph analysis.

  • Information diffusion model: Information spreads according to the SIR model, with individuals transitioning among susceptible, infectious, and recovered states.Transmission probabilities differ between physical and online-network links through transmissibilities T_w and T_f.
  • Information diffusion model: Information diffusion is equivalent to bond percolation on the occupied edges of the conjoint network H = W ∪ F.An outbreak equals the set of nodes reachable from its source through occupied links.
  • Arbitrary degree distributions: The fractional giant-component size gives both the probability that an arbitrary node triggers an epidemic and the corresponding epidemic fraction.This follows because an epidemic occurs precisely when the source belongs to a giant component containing a positive fraction of nodes.
  • Arbitrary degree distributions: Theorem 3.1 determines the epidemic threshold and asymptotic epidemic fraction for coupled networks with arbitrary degree distributions.The epidemic fraction is obtained by solving recursive equations for the smallest h1 and h2 and then evaluating the resulting expression.
  • Arbitrary degree distributions: σ⋆_fw > 1 marks the supercritical regime, where an information item has positive probability of reaching a linear fraction of individuals.For σ⋆_fw ≤ 1, all outbreaks are non-epidemic and reach o(n) individuals with high probability.
  • Arbitrary degree distributions: The exact coupled-network threshold can differ substantially from the classical single-network approximation.For α = 0.2, T_wλ_w = 0.6, and T_fλ_f = 0.8, σ⋆_fw = 1.03 while the approximation gives 0.89.

B. Special Case: Information Diffusion in coupled ER graphs

For coupled Erdős–Rényi physical and social networks, the paper derives sharper giant-component thresholds and sizes, showing how both networks jointly determine the phase transition.

  • ER overlay model: The coupled ER overlay is H(n; α, T_wλ_w, T_fλ_f) = W(n; T_wλ_w/n) ∪ F(n; α, T_fλ_f/(αn)).The physical network spans all vertices, while the social network includes each vertex independently with probability α.
  • Phase transition: λ⋆_fw ≤ 1 yields a largest component of O(log n) with high probability, whereas λ⋆_fw > 1 yields a giant component of Θ(n).In the supercritical regime, the second-largest component is O(log n).
  • Phase transition: The phase-transition boundary is plotted as the minimum T_fλ_f required for a giant component versus T_wλ_w for different α values.Above each curve a giant component exists; below it all components have O(log n) nodes.
  • Phase transition: The ER analysis provides sharper component-size bounds than Theorem 3.1, although its asymptotic giant-component size agrees numerically with that theorem.The sharper bounds include O(log n) for the largest subcritical component and the second-largest supercritical component.
  • Phase transition: The threshold is symmetric in T_fλ_f and T_wλ_w, so both networks have identical roles in reaching the supercritical regime.When one network is absent, the condition reduces to the usual ER requirement that the remaining occupied mean degree exceed one.
  • Limiting cases: For α = 1, the overlay reduces to an ER graph with asymptotic mean degree T_fλ_f + T_wλ_w.Thus the coupled-network result recovers the classical ER giant-component condition in this limiting case.

A. ER Networks

The paper analyzes Erdős–Rényi physical and online networks, quantifying giant-component thresholds, sizes, and outbreak sizes through theory and experiments. Conjoining the networks lowers epidemic thresholds and produces strong agreement between analytical and experimental results.

  • Model: The conjoint network is modeled as the union of an ER physical graph and an ER online graph with transmissibilities T_w and T_f.The online graph includes each population node independently with probability α.
  • Validation: Analytical giant-component and average-outbreak-size results closely match experiments using n = 2 × 10^5 nodes and 200 trials per point.The giant-component curves come from Theorem 3.3, while outbreak-size curves come from Theorem 3.2.
  • Thresholds: 0.760, 0.586, and 0.514 are the critical values of T_fλ_f = T_wλ_w for α = 0.1, 0.5, and 0.9, respectively.These thresholds mark the onset of a giant component, interpreted as an information epidemic.
  • Outbreaks: Average outbreak size grows unboundedly as T_fλ_f = T_wλ_w approaches the corresponding epidemic threshold.This behavior is shown in the inset associated with the ER-network experiments.
  • Power-law networks: For power-law degree distributions with exponential cutoff, the paper computes thresholds and giant-component sizes using Theorem 3.1 and compares them with simulations.The distributions use γ_f = γ_w = 2.5 and Γ_f = Γ_w = 10, with β_f = β_w = 1.545 for fair comparison with disjoint networks.
  • Power-law validation: Power-law-network experiments also show excellent agreement between analytical giant-component predictions and simulations.Experiments use n = 2 × 10^5 nodes and average 200 trials per parameter set; outbreak-size fits use n = 30 × 10^6 near threshold.

V. ONLINE SOCIAL NETWORKS WITH o(n) NODES

When the online network has only o(n) members, it cannot materially change whether a giant information component exists or its asymptotic fractional size. The conjoint network therefore inherits these properties from the physical network.

  • Setting: An online network with n^γ members, where 0 < γ < 1, has a sublinear vertex set relative to the physical network’s n nodes.The online members are selected independently with probability n^(γ−1).
  • General degree distributions: For arbitrary degree distributions, the same asymptotic conclusion holds under the stated degree-sequence conditions, including (22) and γ ≤ 3.The largest component remains asymptotically controlled by the physical network.
  • Subcritical regime: If the physical network is subcritical with C_1(W) = o(n), then the conjoint network satisfies C_1(H) = o(n) with high probability.Thus, the online network does not create a linear-sized component in this regime.
  • Supercritical regime: If C_1(W) = Θ(n), then C_1(H) = (1 + o(1))C_1(W).The conjoint network’s largest component is asymptotically the same size as the physical network’s largest component.
  • Consequence: Consequently, with n^γ online members for 0 ≤ γ < 1, a positive-fraction epidemic occurs if and only if it already occurs in the physical network.The fractional epidemic size is also the same as in the physical network alone.
  • Power-law specialization: For power-law degrees with exponential cutoff, the corollary preserves the subcritical and supercritical conclusions for sublinear online networks.The proof uses conditions satisfied with w_n = O(log n).

VI. PROOFS OF THEOREM 3.1 AND THEOREM 3.2

The proofs map information diffusion to a two-type branching process represented by generating functions. Linear stability of its fixed point yields the epidemic threshold, while the nontrivial solution determines giant-component size and outbreak statistics.

  • Branching-process construction: The branching process distinguishes type-1 online edges and type-2 physical edges, with information transmitted independently using T_f and T_w.It starts from an arbitrary node and recursively explores informed neighbors.
  • Generating functions: The generating functions h_1(x) and h_2(x) encode finite informed-component sizes reached through type-1 and type-2 edges.They are solved through self-consistency equations for the two edge types.
  • Threshold criterion: The fixed point h_1(1) = h_2(1) = 1 is physically valid in the subcritical regime when the Jacobian’s spectral radius satisfies σ(J) ≤ 1.In that case H(1) = 1 and informed components remain finite.
  • Supercritical regime: When the spectral radius exceeds one, the branching process is supercritical and a nontrivial fixed point with h_1(1), h_2(1) < 1 emerges.This implies a positive probability of producing an infinite tree and a giant component.
  • Giant-component size: The fractional giant-component size is 1 − H(1), obtained from the stable nontrivial solution of the recursive equations.This quantity equals the asymptotic fraction of informed nodes.
  • Outbreak size: In the subcritical regime, the mean outbreak size is obtained from the first derivative of H(x) at x = 1.The derivatives of h_1 and h_2 are computed recursively to derive the stated outbreak-size expressions.

VII. PROOF OF THEOREM 3.3

The section introduces the proof of Theorem 3.3 and identifies the technical tools used to establish it.

  • Proof scope: The section proves Theorem 3.3.
  • Proof setup: The proof begins by summarizing the technical tools required for the theorem.
  • Organization: The section serves as the transition into the theorem’s technical proof.

A. Inhomogeneous Random Graphs

The paper models typed inhomogeneous random graphs through kernels and branching processes, using spectral radius to characterize giant-component phase transitions. Subcritical graphs lack giant components, while supercritical graphs contain one occupying a positive vertex fraction.

  • Model construction: Vertices are assigned points in a measured metric space, and edges appear independently with probability κ(x_i, x_j)/n.The resulting graph is denoted G_V(n, κ).
  • Model construction: For finitely many vertex types, the kernel becomes an r×r matrix describing connection rates among types.Examples include vertices with and without Facebook membership.
  • Branching-process analysis: Branching-process survival probabilities ρ(κ; i) are defined by recursively exploring neighbors from a node of type i.The overall survival probability ρ(κ) is obtained from the type-specific probabilities.
  • Phase transition: σ(M) > 1 is equivalent to a non-trivial stable fixed point of the recursive map and marks the supercritical regime.Here M(i, j) = κ(i, j) · µ_j.
  • Phase transition: When σ(M) ≤ 1, the graph has no giant component and C1(GV(n, κ)) = o(n) whp.With bounded kernels, the stronger bound C1(GV(n, κ)) = O(log n) whp holds.
  • Phase transition: When σ(M) > 1, an arbitrary node belongs to the giant component with probability ρ(κ), which asymptotically contains fraction ρ(κ) of vertices.The giant component has size C1(GV(n, κ)) = Ω(n) whp.

B. A Proof of Theorem 3.3

Theorem 3.3 applies the typed random-graph framework to a physical network overlaid with an online network. Its critical condition and epidemic size follow from the spectral radius and transmissibility-adjusted mean degrees.

  • Network representation: The overlay H combines a physical network W with an online network F, using Facebook membership to define vertex types.Type 1 denotes Facebook members and type 2 denotes non-members.
  • Network representation: The kernel assigns λw to physical-network connections and distinguishes Facebook-member connections through the online-network parameter λf.The type probabilities are µ1 = α and µ2 = 1 − α.
  • Critical threshold: The matrix M is computed from the kernel and type probabilities, and its spectral radius determines whether H has a giant component.The matrix is defined by M(i, j) = κ(i, j)µ_j.
  • Component sizes: If condition (36) fails, C1(H(n; α, λw, λf)) = O(log n); when it holds, the second-largest component is also O(log n).The latter bound follows because the kernel is bounded.
  • Epidemic size: The asymptotic epidemic size is obtained from the stable solution for the type-specific probabilities ρ1 and ρ2.These probabilities satisfy the coupled equations in (38).
  • Transmissibility: Transmissibilities enter by replacing λf with Tfλf and λw with Twλw in the threshold and epidemic-size relations.This establishes Theorem 3.3 for unrestricted transmissibilities.

VIII. CONCLUSION

The paper precisely characterizes information-epidemic thresholds and asymptotic sizes in social-physical networks under the SIR model. It presents this as the first phase-transition analysis for conjoint networks with partially overlapping, non-identical vertex sets.

  • Contributions: The study characterizes the critical threshold and asymptotic size of information epidemics in an overlaying social-physical network.The network combines face-to-face interactions with online networks such as Facebook and Twitter.
  • Contributions: Under the SIR model, the critical point and epidemic size can be precisely determined for the overlaying network.The result applies to information transmitted among individuals across the combined networks.
  • Novelty: The study is presented as the first work on phase transitions in conjoint networks whose vertex sets are neither identical nor disjoint.The authors identify this setting as distinct from previously studied network couplings.

APPENDIX INFORMATION DIFFUSION WITH MULTIPLE ONLINE

The appendix extends the model from one online network to multiple online networks, illustrated with Facebook and Twitter overlaid on a physical network. The same spectral-radius criterion determines whether a positive-fraction information epidemic exists.

  • Multiple-network model: A third network T is added to the physical network W and online network F, yielding H = W ∪ F ∪ T.Twitter membership is sampled independently with probability αt.
  • Network parameters: The combined network uses ER layers with asymptotic mean degrees λw, λf, and λt for the physical, Facebook, and Twitter networks.The displayed kernel encodes connection rates among the four membership types.
  • Vertex types: The three-network model represents four vertex types based on Facebook and Twitter membership combinations.The type probabilities are µ1 = αfαt, µ2 = αf(1 − αt), µ3 = (1 − αf)αt, and µ4 = (1 − αf)(1 − αt).
  • Epidemic threshold: σ(M) > 1 is necessary for an item from one node to reach a positive fraction of individuals; otherwise all outbreaks have size O(log n).The criterion applies to the spectral-radius matrix of the combined network.
  • Transmissibility: With unrestricted transmissibilities, the results remain valid after substituting Twλw, Tfλf, and Ttλt for the corresponding mean-degree parameters.This extends the threshold and size conclusions to all three network layers.
Loading 1112.4002v2…