Influence Maximization on Undirected Graphs: Toward Closing the (1 - 1/e) Gap

GRANT SCHOENEBECK; BIAOSHUAI TAO

首页> 外文期刊>ACM transactions on economics and computation >Influence Maximization on Undirected Graphs: Toward Closing the (1 - 1/e) Gap

【24h】

Influence Maximization on Undirected Graphs: Toward Closing the (1 - 1/e) Gap

机译：在无向图的影响最大化:对关闭(1 - 1 / e)的差距

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We study the influence maximization problem in undirected networks, specifically focusing on the independent cascade and linear threshold models. We prove APX-hardness (NP-hardness of approximation within factor (1 - τ ) for some constant τ > 0) for both models, which improves the previous NP-hardness lower bound for the linear threshold model. No previous hardness result was known for the independent cascade model.

机译：我们研究了影响最大化问题无向网络,特别关注独立级联模型和线性阈值。我们证明APX-hardness (np困难的近似(1 -τ)对一些内部因素两种模型常数τ> 0),改善了前面的np困难的下界线性阈值模型。结果是著名的独立级联模型。

著录项

来源
《ACM transactions on economics and computation》 |2020年第4期|22-1-22-36|共36页
作者
GRANT SCHOENEBECK; BIAOSHUAI TAO;
展开▼
作者单位

School of Information, University of Michigan, 3341 North Quad, 501 State St., Ann Arbor, MI 48109-2121, USA;

John Hopcroft Center for Computer Science, Shanghai Jiao Tong University, No. 800 Dong Chuan Road, Minhang District, Shanghai 200240, P.R. China;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类
关键词
undirected graph; cascades; approximationthreshold models;

机译：无向图、瀑布、approximationthreshold模型;

相似文献

外文文献
中文文献
专利

1. THE AUGMENTATION OF UNDIRECTED WEIGHTED GRAPH TO A K-EDGE-CONNECTED GRAPH [J] . 孙立山, 孙雨耕, 杨山电子科学学刊：英文版 . 1992,第003期
2. The Wiener Index of an Undirected Power Graph [J] . Volkan Aşkin, Şerife Büyükköse 线性代数与矩阵理论研究进展（英文） . 2021,第1期
3. SUPER EDGE-CONNECTIVITY OF DE BRUIJN AND KAUTZ UNDIRECTED GRAPHS [J] . XuJunming, FanYingmei 高校应用数学学报：英文版 . 2004,第004期
4. Comparative study on breakdown characteristics of trigger gap and overvoltage gap in a gas pressurized closing switch [J] . 等离子体科学和技术（英文版） . 2019,第001期
5. D2-brane Chern-Simons theories: F -maximization = a-maximization [J] . Martin Fluder, James Sparks The journal of high energy physics . 2016,第1期

机译：D2- Brane Chern-Simons理论：<重点类型=“斜体”> F -Maximization = -Maximization
6. Self-dual continuous series of representations for $U_{q} (s l (2))$ $$ {mathcal{U}}_qleft(sl(2)ight) $$ and $U_{q} (o s p (1 | 2))$ $$ {mathcal{U}}_qleft(ospleft(1Big|2ight)ight) $$ [J] . Leszek Hadasz, Michal Pawelkiewicz, Volker Schomerus The journal of high energy physics . 2014,第10期

机译： $uq(sl2$$ { mathcal {u }}}}}左（sl（2）右）$$ uq(osp(1| 2$$ { mathcal {u}} _ q左（osp left（1 big | 2 右）右）$$“）”打开=“（”“）”打开=“（”“）”打开=“（”$
7. Ab initio and B3LYP-DFT calculations of GaP~(-) and GaP_2~(-): the electron affinities and vibrational frequencies of GaP and GaP_2 [J] . Archibong Edet F. Chemical Physics Letters . 2000,第1a2期

机译：GaP〜（-）和GaP_2〜（-）的从头算和B3LYP-DFT计算：GaP和GaP_2的电子亲和力和振动频率
8. Growth and Optical Properties of GaP, GaP@GaN and GaN@GaP Core-shell Nanowires [C] . Hung-Min Lin, Jian Yang, Yong-Lin Chen, Symposium on Unconventional Approaches to Nanostructures with Applications in Electronics, Photonics, Information Storage and Sensing; 20030421-20030425; San Francisco,CA; US . 2003

机译：GaP，GaP @ GaN和GaN @ GaP核壳纳米线的生长和光学性质
9. Translating Success and Happiness: A Study on Dale Carnegie’s How to Win Friends and Influence People in Chinese Translations =翻譯成功，譯介幸福：卡內基之How to Win Friends and Influence People譯本研究 [D] . 蘇, 薇方. 2018

机译：Translating Success and Happiness: A Study on Dale Carnegie’s How to Win Friends and Influence People in Chinese Translations =翻译成功，译介幸福：卡内基之How to Win Friends and Influence People译本研究
10. Yes! Maximizers Maximize Almost Everything: The Decision-Making Style Is Consistent in Different Decision Domains [O] . Emilio Moyano-Díaz, Rodolfo Mendoza-Llanos 2021

机译：是的！ Maximizers几乎最大化：决策风格在不同的决策域中是一致的
11. Combining intensification and diversification to maximize the propagation of social influence [O] . Fan X, Li VOK 2013

机译：Combining intensification and diversification to maximize the propagation of social influence
12. Influence of Air Gaps on Long Rod Penetrators Attacking Multi-Plate Target Arrays [R] . Copland, A. , Scheffler, D. 2003

机译：Influence of air Gaps on Long Rod penetrators attacking multi-plate Target arrays

Influence Maximization on Undirected Graphs: Toward Closing the (1 - 1/e) Gap

摘要

著录项

相似文献

相关主题

期刊订阅