惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

N
Netflix TechBlog - Medium
Blog — PlanetScale
Blog — PlanetScale
Google DeepMind News
Google DeepMind News
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
F
Fortinet All Blogs
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
Stack Overflow Blog
Stack Overflow Blog
人人都是产品经理
人人都是产品经理
H
Hackread – Cybersecurity News, Data Breaches, AI and More
L
LangChain Blog
Microsoft Security Blog
Microsoft Security Blog
Apple Machine Learning Research
Apple Machine Learning Research
Y
Y Combinator Blog
阮一峰的网络日志
阮一峰的网络日志
博客园_首页
IT之家
IT之家
V
V2EX
C
Check Point Blog
MongoDB | Blog
MongoDB | Blog
Last Week in AI
Last Week in AI
B
Blog
J
Java Code Geeks
大猫的无限游戏
大猫的无限游戏
雷峰网
雷峰网

cs.SI updates on arXiv.org

Hiding in Plain Sight: Finding MAHA on Reddit Prism: Structural Symmetry Scanning via Duality-Constrained Laplacian Projection MV-Gate: Insider Threat Detection via Multi-View Behavioral Statistics and Semantic Modeling Algorithmic Cultivation: How Social Media Feeds Shape User Language Universal Dynamics of Punctuated Progress AI-Mediated Communication Can Steer Collective Opinion CitePrism: Human-in-the-Loop AI for Citation Auditing and Editorial Integrity Explainable Detection of Depression Status Shifts from User Digital Traces Can Visual Mamba Improve AI-Generated Image Detection? An In-Depth Investigation ScioMind: Cognitively Grounded Multi-Agent Social Simulation with Anchoring-Based Belief Dynamics and Dynamic Profiles Humanwashing -- It Should Leave You Feeling Dirty When Do LLMs Generate Realistic Social Networks? A Multi-Dimensional Study of Culture, Language, Scale, and Method Moltbook Moderation: Uncovering Hidden Intent Through Multi-Turn Dialogue Linking Extreme Discourse to Structural Polarization in Signed Interaction Networks Predicting Channel Closures in the Lightning Network with Machine Learning Latent Causal Void: Explicit Missing-Context Reconstruction for Misinformation Detection Predictive Maps of Multi-Agent Reasoning: A Successor-Representation Spectrum for LLM Communication Topologies Large Language Models for Causal Relations Extraction in Social Media: A Validation Framework for Disaster Intelligence When Can Digital Personas Reliably Approximate Human Survey Findings? RAwR: Role-Aware Rewiring via Approximate Equitable Partition GravityGraphSAGE: Link Prediction in Directed Attributed Graphs Structure-Centric Graph Foundation Model via Geometric Bases Attention-based graph neural networks: a survey When AI Meets Science: Research Diversity, Interdisciplinarity, Visibility, and Retractions across Disciplines in a Global Surge Scalable inference of spatial regions and temporal signatures from time series Can LLMs Emulate Human Belief Dynamics? Predicting Post Virality with Temporal Cross-Attention over Trend Signals H3: A Healthcare Three-Hop Index for Physician Referral Network Prediction Dynamic Graph with Similarity-Aware Attention Graph Neural Network for Recommender Systems Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks
The Routing of Complex Contagion in Kleinberg's Small-Wor...
Wei Chen, Qiang Li, Xiaoming Sun, Jialin Zhang · 2015-03-02 · via cs.SI updates on arXiv.org

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|^α$, where $|uv|$ is the grid distance between $u$ and $v$ and $α\ge 0$ is the parameter of the model. Complex contagion refers to the propagation mechanism in a network where each node is activated only after $k \ge 2$ 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 $α$ both in expectation and with high probability (in particular, $Ω(n^{\frac{1}{α+2}})$ for $α\le 2$ and $Ω(n^{\fracα{2(α+2)}})$ for $α> 2$ in expectation), while the routing time of simple contagion has polylogarithmic upper bound when $α= 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.