The Routing of Complex Contagion in Kleinberg’s Small-World Networks

DOI10.1007/978-3-319-42634-1_25zbMATH Open1394.94971arXiv1503.00448OpenAlexW2963485666MaRDI QIDQ2817872FDOQ2817872

Authors: Wei Chen, Xiaoming Sun, Jialin Zhang, Qiang Li 

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In Kleinberg's small-world network model, strong ties are modeled as deterministic edges in the underlying base grid and weak ties are modeled as random edges connecting remote nodes. The probability of connecting a node $u$ with node $v$ through a weak tie is proportional to $1/|uv{|}^{a}lpha$, where $|uv|$ is the grid distance between $u$ and $v$ and $alphage0$ is the parameter of the model. Complex contagion refers to the propagation mechanism in a network where each node is activated only after $kge2$ neighbors of the node are activated. In this paper, we propose the concept of routing of complex contagion (or complex routing), where we can activate one node at one time step with the goal of activating the targeted node in the end. We consider decentralized routing scheme where only the weak ties from the activated nodes are revealed. We study the routing time of complex contagion and compare the result with simple routing and complex diffusion (the diffusion of complex contagion, where all nodes that could be activated are activated immediately in the same step with the goal of activating all nodes in the end). We show that for decentralized complex routing, the routing time is lower bounded by a polynomial in $n$ (the number of nodes in the network) for all range of $alpha$ both in expectation and with high probability (in particular, $Omega(n^{frac1alpha+2})$ for $alphale2$ and $Omega(n^{fracalpha2(alpha+2)})$ for $alpha>2$ in expectation), while the routing time of simple contagion has polylogarithmic upper bound when $alpha=2$. Our results indicate that complex routing is harder than complex diffusion and the routing time of complex contagion differs exponentially compared to simple contagion at sweetspot.

Full work available at URL: https://arxiv.org/abs/1503.00448

Recommendations

• Complex contagions in Kleinberg's small world model
• Infection dynamics on small-world networks
• Contagion dynamics in complex networks
• Contagion spreading on complex networks with local deterministic dynamics
• STEADY STATES OF EPIDEMIC SPREADING IN SMALL-WORLD NETWORKS
• Modeling and analysis of epidemic diffusion within small-world network
• EPIDEMIOLOGY MODEL ON SHORTCUT AND SMALL WORLD NETWORKS
• Contagion in networks: stability and efficiency
• Cascades and myopic routing in nonhomogeneous Kleinberg's small world model

zbMATH Keywords

social networkscomputational social sciencediffusionsmall-world networksdecentralized routingcomplex contagion

Mathematics Subject Classification ID

Applications of graph theory to circuits and networks (94C15) Internet topics (68M11)

Cites Work

• Networks, crowds and markets. Reasoning about a highly connected world.
• Collective dynamics of `small-world' networks
• Networks. An introduction.
• Automata, Languages and Programming
• Title not available (Why is that?)
• Renormalization group analysis of the small-world network model
• Title not available (Why is that?)
• Title not available (Why is that?)
• The small-world phenomenon: an algorithmic perspective
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation on the random regular graph
• \(k\)-core organization in complex networks
• On the searchability of small-world networks with arbitrary underlying structure
• The Routing of Complex Contagion in Kleinberg’s Small-World Networks
• Complex contagions in Kleinberg's small world model
• The effect of power-law degrees on the navigability of small worlds (extended abstract)

Cited In (5)

• The Routing of Complex Contagion in Kleinberg’s Small-World Networks
• Effects of inspections in small world social networks with different contagion rules
• Complex contagions in Kleinberg's small world model
• Title not available (Why is that?)
• Cascades and myopic routing in nonhomogeneous Kleinberg's small world model

This page was built for publication: The Routing of Complex Contagion in Kleinberg’s Small-World Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817872)