核心速递

复杂网络中缺失链路的可预测性;
社交媒体和选举操纵分析的危险和挑战：2018年美国中期选举;
基于网络修改的社会网络物质滥用预防（初步研究）;
有向图上的非马尔可夫蒙特卡洛;
一般反馈模型下的自适应影响最大化;
复杂网络涌现的表面深度理论;
StaTIX——关联数据的统计类型推断;

复杂网络中缺失链路的可预测性

原文标题：

Predictability of missing links in complex networks

地址：

http://arxiv.org/abs/1902.00035

作者：

Guillermo García-Pérez, Roya Aliakbarisani, Abdorasoul Ghasemi, M. Ángeles Serrano

摘要： 预测真实网络中的缺失链路是网络科学中的一个重要问题，已经投入了相当多的努力，因此在文献中提供了大量的链路预测方法。在这项工作中，我们对问题采取了不同的观点，并研究了缺失环节可预测性的理论局限性。特别是，我们假设由于其形成过程的随机性，在实际网络上的链路预测存在不可简化的不确定性。

通过考虑由众所周知的网络模型定义的集合，我们在分析上证明即使是由集合连接概率的排名给出的集合的最佳可能链路预测方法也产生有限的精度。该结果表明在实际复杂网络中链路的可预测性存在理论上的限制。最后，我们证明通过将网络模型拟合到实际网络推断出的连接概率允许估计缺失链路的可预测性的上限，并且我们进一步提出了一种方法来逼近来自现实世界网络的不完整实例的这种约束。

社交媒体和选举操纵分析的危险

和挑战：2018年美国中期选举

原文标题：

Perils and Challenges of Social Media and Election Manipulation Analysis: The 2018 US Midterms

地址：

http://arxiv.org/abs/1902.00043

作者：

Ashok Deb, Luca Luceri, Adam Badawy, Emilio Ferrara

摘要： 自由和公平社会的标志之一是能够从一个领导者到另一个领导者进行和平和无缝的权力转移。民主地说，这是以公民人口对选择代议制政府的选举制度的信任来衡量的。鉴于2016年美国总统选举记录良好的问题，我们对2018年美国中期选举进行了深入分析，专门针对选民欺诈或压制。中期选举发生在4年总统任期中。对于2018年的中期，众议院有35名参议员和435个席位进行连任，因此，每个国会选区和几乎每个州都举行联邦选举。

为了收集选举相关的推文，我们在2018年11月6日选举日之前和之后的两个月分析了Twitter。在用于检测统计异常或选举干扰的目标分析中，我们发现了一些可能导致错误结论的偏差。具体来说，我们在选举日寻找实际投票结果与#ivoted主题标签实例之间的差异。该分析突出了三个值得关注的状态：纽约，加利福尼亚和德克萨斯。我们重复分析，丢弃恶意帐户，例如社交机器人。在进一步检查后，在收集的与大选相关的推文的背景下，我们发现了一些混淆因素，例如人口偏见，机器人和政治意识形态推断，这可能导致错误的结论。最后，我们深入讨论了利用社交媒体数据探讨选举操纵问题的风险和挑战。

基于网络修改的社会网络

物质滥用预防（初步研究）

原文标题：

Social Network Based Substance Abuse Prevention via Network Modification (A Preliminary Study)

地址：

http://arxiv.org/abs/1902.00171

作者：

Aida Rahmattalabi, Anamika Barman Adhikari, Phebe Vayanos, Milind Tambe, Eric Rice, Robin Baker

摘要： 在美国，物质的使用和滥用是一个重要的公共卫生问题。基于团体的干预计划提供了预防和减少药物滥用的有希望的手段。虽然有效，但不幸的是，不恰当的干预组可能导致参与者中的离经叛道行为增加，这一过程被称为畸形训练。本文通过对干预群体的精心构建，探讨了优化与异常行为相关的社会影响的问题。我们提出了一种混合整数优化公式，它决定干预组，捕获组对社会网络结构的影响，并模拟这些变化对行为传播的影响。此外，我们提出了一种可扩展的混合元启发式算法，该算法结合了混合整数规划和大邻域搜索，以找到接近最优的网络分区。我们的算法以GUIDE的形式打包，GUIDE是一种基于AI的决策辅助工具，可以推荐干预组。

作为第一个此类量化决策援助，GUIDE能够在三个关键领域为从业人员，特别是社会工作者提供帮助：（a）GUIDE提出通过大量模拟显示的近乎最优解决方案，以显著改善传统形成干预组的定性做法; （b）指南能够确定干预将导致异常训练的情况，从而节省时间，金钱和精力; （c）GUIDE可以评估当前的小组形成策略和丢弃策略，这些策略将导致异常训练。在制定指南时，我们主要关注无家可归青年的物质使用干预措施，因为他们是高风险和脆弱人群。 GUIDE是与位于科罗拉多州丹佛市的无家可归青年服务组织Urban Peak合作开发的，目前正在筹备部署。

有向图上的非马尔可夫蒙特卡洛

原文标题：

Non-Markovian Monte Carlo on Directed Graphs

地址：

http://arxiv.org/abs/1902.00180

作者：

Chul-Ho Lee, Min Kang, Do Young Eun

摘要： 马尔可夫链蒙特卡洛（MCMC）一直是大型图（如在线社会网络）的采样和推理的事实上的技术。 MCMC的核心是构建遍历马尔可夫链的能力，该链获得任何给定的固定分布pi，通常以图上的随机游走或爬行代理的形式。然而，围绕MCMC的大部分工作都假设图是无向的或具有倒数边，并且当图是有向的和非互易时变得不适用。在这里，我们开发了一个类似的有向图框架，我们称之为非马尔可夫蒙特卡洛（NMMC），通过建立映射将pi转换为精确构造的瞬态马尔可夫链的准静态分布。扩展的国家空间。

作为应用程序，我们演示如何在有向图上实现任何给定的分布pi，并使用一组非马尔可夫，历史相关的随机遍历以分布式方式在同一图上估计特征向量中心性。我们还提供了各种真实有向图的数值结果，以确认我们的理论发现，并提出了一些实际的改进，使我们的NMMC方法可以在大多数有向图中实际应用。据我们所知，有向图的NMMC框架是同类中的第一个，解除了无向图的标准MCMC方法设置的所有限制。

一般反馈模型下

的自适应影响最大化

原文标题：

Adaptive Influence Maximization under General Feedback Models

地址：

http://arxiv.org/abs/1902.00192

作者：

Guangmo Tong

摘要： 本文为一般反馈模型下有或没有时间约束的自适应影响最大化问题提供了一些分析。

复杂网络涌现的表面深度理论

原文标题：

A surface-depth theory of the emergence of complex networks

地址：

http://arxiv.org/abs/1902.00336

作者：

Keith M. Smith

摘要： 跨学科发现的复杂网络的广泛一般特征 – 例如高聚类系数和重尾度分布 – 长期以来一直在提出它们背后是否存在一般生成机制的问题。在这里，我们提出了这种机制的理论，并进行了几个验证它的实验。该理论提出在网络的出现中有两个关键原则在起作用，构成了网络边存在概率的“表面”因子和“深度”因子。表面因子将节点描述为具有遵循对数正态分布的附着趋势。深层因素表明，在这些附着潜力之下，存在许多描述节点的重要潜在变量。这些变量被表示为高维流形，并且该流形上的节点对之间的“距离”构成了相似性加权，其通知了任何两个节点连接的概率。

使用标准网络测量，跨越各种学科的110个网络的拓扑结构表明与基于该理论的简单双参数模型一致。重要的是，我们证明了对数正态表面因子可以解释稀疏网络的幂律类度分布，更强烈地说，可以解释在不同密度的网络中发现的各种程度分布。我们还演示了如何基于几何和文化考虑因素反转完整加权世界城市网络的估计表面因子提供比原始网络更可信的节点集群。该理论提出了复杂网络的新基本公式，在复杂系统的多学科领域具有广泛的影响。

StaTIX——关联

数据的统计类型推断

原文标题：

StaTIX – Statistical Type Inference on Linked Data

地址：

http://arxiv.org/abs/1902.00490

作者：

Artem Lutov, Soheil Roshankish, Mourad Khayati, Philippe Cudré-Mauroux

摘要： 大型知识库通常包含遵守具有不完整和/或噪声类型信息的各种模式的数据。这使得进一步的集成和后处理工作变得非常复杂，因为类型信息对于正确处理数据至关重要。在本文中，我们引入了一种新的统计类型推断方法，称为StaTIX，以完全无监督的方式有效地推断关联数据集中的实例类型。我们的推理技术利用了一种强大，高效且可扩展的新的分层聚类算法。

我们引入了一种新方法来降低相似性矩阵的处理复杂性，指定知识库中各种实例之间的关系。由于输入数据中的噪声衰减，该方法加速了推理过程，同时还提高了推断类型的正确性。我们通过引入专用散列函数来进一步优化聚类过程，该函数可以将推理过程加速几个数量级而不会对其准确性产生负面影响。

最后，我们描述了一种新技术，用于从聚类算法的多尺度输出中识别代表性聚类，以进一步提高推断类型的准确性。我们凭经验评估我们在几个真实世界数据集上的方法，并将其与现有技术进行比较。我们的结果表明StaTIX比现有方法（速度和内存消耗方面）更有效，并且更有效。与现有技术相比，StaTIX将预测类型的F1得分误差平均降低约40％，并将执行时间提高了几个数量级。