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

DOI10.1007/978-3-319-42634-1_25MaRDI QIDQ2817872zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 5538644 (Why is no real title available?)
• 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)