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

推荐订阅源

WordPress大学
WordPress大学
博客园 - 司徒正美
小众软件
小众软件
H
Help Net Security
博客园 - 聂微东
宝玉的分享
宝玉的分享
Jina AI
Jina AI
酷 壳 – CoolShell
酷 壳 – CoolShell
阮一峰的网络日志
阮一峰的网络日志
M
MIT News - Artificial intelligence
博客园 - 【当耐特】
U
Unit 42
大猫的无限游戏
大猫的无限游戏
Apple Machine Learning Research
Apple Machine Learning Research
S
SegmentFault 最新的问题
腾讯CDC
MongoDB | Blog
MongoDB | Blog
云风的 BLOG
云风的 BLOG
J
Java Code Geeks
I
InfoQ
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
Martin Fowler
Martin Fowler
博客园 - 三生石上(FineUI控件)
Vercel News
Vercel News

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
On the Complexity of Community-aware Network Sparsification
Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, Frank · 2024-02-24 · via cs.SI updates on arXiv.org

Network sparsification is the task of reducing the number of edges of a given graph while preserving some crucial graph property. In community-aware network sparsification, the preserved property concerns the subgraphs that are induced by the communities of the graph which are given as vertex subsets. This is formalized in the $Π$-Network Sparsification problem: given an edge-weighted graph $G$, a collection $Z$ of $c$ subsets of $V(G)$ (communities), and two numbers $\ell, b$, the question is whether there exists a spanning subgraph $G'$ of $G$ with at most $\ell$ edges of total weight at most $b$ such that $G'[C]$ fulfills $Π$ for each community $C$. Here, we consider two graph properties $Π$: the connectivity property (Connectivity NWS) and the property of having a spanning star (Stars NWS). Since both problems are NP-hard, we study their parameterized and fine-grained complexity. We provide a tight $2^{Ω(n^2+c)} poly(n+|Z|)$-time running time lower bound based on the ETH for both problems, where $n$ is the number of vertices in $G$. The lower bound holds even in the restricted case when all communities have size at most 4, $G$ is a clique, and every edge has unit weight. For the connectivity property, the unit weight case with $G$ being a clique is the well-studied problem of computing a hypergraph support with a minimum number of edges. We then study the complexity of both problems parameterized by the feedback edge number $t$ of the solution graph $G'$. For Stars NWS, we present an XP-algorithm for $t$. This answers an open question by Korach and Stern [Disc. Appl. Math. '08] who asked for the existence of polynomial-time algorithms for $t=0$. In contrast, we show for Connectivity NWS that known polynomial-time algorithms for $t=0$ [Korach and Stern, Math. Program. '03; Klemz et al., SWAT '14] cannot be extended by showing that Connectivity NWS is NP-hard for $t=1$.