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

推荐订阅源

Vercel News
Vercel News
N
Netflix TechBlog - Medium
C
Check Point Blog
MyScale Blog
MyScale Blog
The GitHub Blog
The GitHub Blog
Blog — PlanetScale
Blog — PlanetScale
B
Blog RSS Feed
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
WordPress大学
WordPress大学
博客园 - Franky
MongoDB | Blog
MongoDB | Blog
I
InfoQ
Hugging Face - Blog
Hugging Face - Blog
Recent Announcements
Recent Announcements
人人都是产品经理
人人都是产品经理
腾讯CDC
V
Visual Studio Blog
Engineering at Meta
Engineering at Meta
T
The Blog of Author Tim Ferriss
V
V2EX
云风的 BLOG
云风的 BLOG
Microsoft Azure Blog
Microsoft Azure Blog
U
Unit 42
B
Blog

cs.IT updates on arXiv.org

Theoretical Limits of Language Model Alignment $f$-Divergence Regularized RLHF: Two Tales of Sampling and Unified Analyses A Unified Measure-Theoretic View of Diffusion, Score-Based, and Flow Matching Generative Models When Can Voting Help, Hurt, or Change Course? Exact Structure of Binary Test-Time Aggregation When Semantic Communication Meets Queueing: Cross-Layer Latency and Task Fidelity Optimization Convexity in Disguise: A Theoretical Framework for Nonconvex Low-Rank Matrix Estimation Conditional Diffusion Under Linear Constraints: Langevin Mixing and Information-Theoretic Guarantees Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval Expert Routing for Communication-Efficient MoE via Finite Expert Banks Contextual Memory-Enhanced Source Coding for Low-SNR Communications Realizable Bayes-Consistency for General Metric Losses Leveraging Code Automorphisms for Improved Syndrome-Based Neural Decoding A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning Dueling DDQN-Based Adaptive Multi-Objective Handover Optimization for LEO Satellite Networks The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy Optimization of CV-QKD Under Practical Constraints Benchmarking Wireless Representations: High-Dimensional vs. Compressed Embeddings for Efficiency and Robustness Real-Time Text Transmission via LLM-Based Entropy Coding over Fixed-Rate Channels SwiftChannel: Algorithm-Hardware Co-Design for Deep Learning-Based 5G Channel Estimation Evolving Token Communication with Parametric Memory Network Remote Action Generation: Remote Control with Minimal Communication The (Marginal) Value of a Search Ad: An Online Causal Framework for Repeated Second-price Auctions Stabilizing Private LASSO under Heterogeneous Covariates via Anisotropic Objective Perturbation Linear-Readout Floors and Threshold Recovery in Computation in Superposition Soft Graph Diffusion Transformer for MIMO Detection Hierarchical Federated Learning for Networked AI: From Communication Saving to Architecture-Aware Design Exponential families from a single KL identity MIFair: A Mutual-Information Framework for Intersectionality and Multiclass Fairness Diffusion-OAMP for Joint Image Compression and Wireless Transmission Decoupled Descent: Exact Test Error Tracking Via Approximate Message Passing
Structure Entropy and Resistor Graphs
Angsheng Li, Yicheng Pan · 2018-01-09 · via cs.IT updates on arXiv.org

We propose the notion of {\it resistance of a graph} as an accompanying notion of the structure entropy to measure the force of the graph to resist cascading failure of strategic virus attacks. We show that for any connected network $G$, the resistance of $G$ is $\mathcal{R}(G)=\mathcal{H}^1(G)-\mathcal{H}^2(G)$, where $\mathcal{H}^1(G)$ and $\mathcal{H}^2(G)$ are the one- and two-dimensional structure entropy of $G$, respectively. According to this, we define the notion of {\it security index of a graph} to be the normalized resistance, that is, $θ(G)=\frac{\mathcal{R}(G)}{\mathcal{H}^1(H)}$. We say that a connected graph is an $(n,θ)$-{\it resistor graph}, if $G$ has $n$ vertices and has security index $θ(G)\geqθ$. We show that trees and grid graphs are $(n,θ)$-resistor graphs for large constant $θ$, that the graphs with bounded degree $d$ and $n$ vertices, are $(n,\frac{2}{d}-o(1))$-resistor graphs, and that for a graph $G$ generated by the security model \cite{LLPZ2015, LP2016}, with high probability, $G$ is an $(n,θ)$-resistor graph, for a constant $θ$ arbitrarily close to $1$, provided that $n$ is sufficiently large. To the opposite side, we show that expander graphs are not good resistor graphs, in the sense that, there is a global constant $θ_0<1$ such that expander graphs cannot be $(n,θ)$-resistor graph for any $θ\geqθ_0$. In particular, for the complete graph $G$, the resistance of $G$ is a constant $O(1)$, and hence the security index of $G$ is $θ(G)=o(1)$. Finally, we show that for any simple and connected graph $G$, if $G$ is an $(n, 1-o(1))$-resistor graph, then there is a large $k$ such that the $k$-th largest eigenvalue of the Laplacian of $G$ is $o(1)$, giving rise to an algebraic characterization for the graphs that are secure against intentional virus attack.