检索结果-内蒙古大学图书馆

Learning graphs from Noisy Epidemic Cascades

PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS 2019年第2期3卷 1–34页

作者： Hoffmann, Jessica Caramanis, Constantine Univ Texas Austin Austin TX 78712 USA

We consider the problem of learning the weighted edges of a graph by observing the noisy times of infection for multiple epidemic cascades on this graph. Past work has considered this problem when the cascade information, i.e., infection times, are known exactly. Though the noisy setting is well motivated by many epidemic processes (e.g., most human epidemics), to the best of our knowledge, very little is known about when it is solvable. Previous work on the no-noise setting critically uses the ordering information. If noise can reverse this - a node's reported (noisy) infection time comes after the reported infection time of some node it infected - then we are unable to see how previous results can be extended. We therefore tackle two versions of the noisy setting: the limited-noise setting, where we know noisy times of infections, and the extreme-noise setting, in which we only know whether or not a node was infected. We provide a polynomial time algorithm for recovering the structure of bidirectional trees in the extreme-noise setting, and show our algorithm matches lower bounds established in the no-noise setting, and hence is optimal. We extend our results for general degree-bounded graphs, where again we show that our (poly-time) algorithm can recover the structure of the graph with optimal sample complexity. We also provide the first efficient algorithm to learn the weights of the bidirectional tree in the limited-noise setting. Finally, we give a polynomial time algorithm for learning the weights of general bounded-degree graphs in the limited-noise setting. This algorithm extends to general graphs (at the price of exponential running time), proving the problem is solvable in the general case. All our algorithms work for any noise distribution, without any restriction on the variance.

关键词： Epidemics SIR model Contact process on graph Noisy inverse problem graph reconstruction robust graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Learning graphs from Noisy Epidemic Cascades 19

Learning Graphs from Noisy Epidemic Cascades

引用

Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems

作者： Jessica H. Hoffmann Constantine Caramanis University of Texas at Austin Austin TX USA

ISBN: (纸本)9781450366786

Epidemic models accurately represent (among other processes) the spread of diseases, information (rumors, viral videos, news stories, etc.), the spread of malevolent agents in a network (computer viruses, malicious apps, etc.), or even biological processes (pathways in cell signaling networks, chains of activation in the gene regulatory network, etc.). We focus on epidemics that spread on an underlying graph [5].

关键词： epidemics noisy inverse problem sir model robust graph algorithms contact process on graph graph reconstruction

来源：评论

学校读者我要写书评

暂无评论

Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes

引用

INFORMATION PROCESSING LETTERS 2004年第4期89卷 165-173页

作者： Brandstädt, A Le, VB De Ridder, HN Univ Rostock Fachbereich Informat D-18051 Rostock Germany

Modular decomposition of graphs is a powerful tool for designing efficient algorithms for problems on graphs such as Maximum Weight Stable Set (MWS) and Maximum Weight Clique. Using this tool we obtain O(n (.) m) time algorithms for MWS on chair- and xbull-free graphs which considerably extend an earlier result on bull- and chair-free graphs by De Simone and Sassano (the chair is the graph with vertices a, b, c, d, e and edges ab, be, cd, be, and the xbull is the graph with vertices a, b, c, d, e, f and edges ab, be, cd, de, bf, cf). Moreover, our algorithm is robust in the sense that we do not have to check in advance whether the input graphs are indeed chair- and xbull-free. (C) 2003 Elsevier B.V. All rights reserved.

关键词： efficient graph algorithms robust graph algorithms modular decomposition maximum weight stable set problem on graphs graph algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：